Thuật toán di truyền và ứng dụng

in , , , /

Thuật toán di truyền và ứng dụng



 Đầu thế kỷ 19, một lý thuyết được nêu ra bởi nhà khoa học Darwin: “Loài người có họ hàng với loài vượn” đã làm chấn động nền tảng khoa học. Trong đó, ý tưởng chủ đạo là sự tiến hóa của các muôn loài dựa trên sự chọn lọc tự nhiên. Lấy cảm hứng từ lý thuyết này, các nhà khoa học máy tính đã phát triển một thuật toán phỏng theo ý tưởng này nhằm giải quyết các bài toán tìm kiếm tối ưu có không gian cực lớn mà phương pháp vét cạn đơn thuần không giải quyết nổi.

 GIẢ THUYẾT NHỮNG CON KHỈ VÀ SHAKESPEARE

 Giả thuyết này được tạo ra bởi Nick Hoggard nói rằng khở đầu từ 100 con khỉ, số lượng khỉ sẽ gấp đôi sau vài ngày. Nếu một con khỉ, giả sử rằng mỗi giây gõ được 1 ký tự, và mỗi trang giấy là 2000 ký tự. Xác xuất chọn lựa để gõ 1 phím trên bàn phím của một con khỉ là như nhau. Với một giả thiết như vậy, thì sẽ mất khoảng 2,737,850 tỷ tỷ tỷ tỷ năm để có thể tạo ra một văn bản giống hệt với toàn bộ công trình văn học của Shakespeare.

 Chúng ta không đi sâu vào giả thuyết này. Chỉ xét đơn cử một ví dụ: Giả sử rằng ta sinh ngẫu nhiên các chuỗi ký tự cùng độ dài với chuỗi “to be or not to be”, 18 ký tự kể cả khoảng trắng. Và giả sử các lựa chọn sinh ngẫu nhiên chỉ gồm 27 lựa chọn bao gồm các ký tự từ a đến z và một khoảng trắng. Như vậy số lượng các chuỗi ngẫu nhiên có thể sinh ra là 27^18 (lũy thừa) = 58,149,737,003,040,059,690,390,169. Rõ ràng đối với một số lượng các trường hợp như vậy, vét cạn là phương pháp hoàn toàn không khả thi.

 Thuật toán di truyền đã được giới thiệu để giải quyết các bài toán tối ưu tìm kiếm trong không gian cực lớn như đã nếu ở trên.

 THUẬT TOÁN DI TRUYỀN (GENETIC ALGORITHM)

 Tư tưởng thuật toán này dựa trên ý tưởng về lai tạo và biến dị để tạo ra cá thể tốt hơn như sau:
Giả sử rằng khởi điểm ta có một quần thể các các thể. Các cá thể có thể “lai tạo”(crossover) với nhau và “biến dị”(mutate) để tạo ra cá thể mới. Các cá thể mới tốt hơn và dần thay thế những cá thể cũ. Như vậy sau một số thế hệ tiến hóa, chúng ta sẽ dần tạo ra cá thể tối ưu.

 Ở đây sẽ có một số câu hỏi đặt ra, đó là:

 Thế nào là tối ưu?

 Đó là trạng thái mục tiêu mà ta cần đạt được. Nghĩa là, ta cần sinh ra một cá thể có trạng thái ứng với trạng thái mục tiêu. Ví dụ như sinh ra một chuỗi có nội dung là “to be or not to be”.

 Thế nào là cá thể tốt hơn cá thể khác?

 Đó là sự đánh giá độ mạnh yếu (fitness) được định nghĩa dựa trên khoảng cách từ một cá thể đến cá thể mục tiêu. Khoảng cách càng gần thì cá thể càng tốt.

 Thế nào là sự lai tạo?

 Mỗi cá thể được mã hóa thành một chuỗi các gene gọi là chromosome. Trong máy tính, chromosome thường được mô tả là một chuỗi bit (mỗi gene là một bit) hoặc một chuỗi các ký tự (mỗi gene là một ký tự). Sự lai tạo được thực hiện bằng cách lựa chọn hai cá thể trong quần thể để lai tạo. Để mô tả chọn lọc tự nhiên, cũng như để hướng tới việc cá thể sau tốt hơn cá thể trước, việc chọn lựa sẽ ưu tiên chọn các cá thể mạnh hơn hay nói cách khác, các cá thể mạnh hơn có nhiều cơ hội được lựa chọn để lai tạo hơn. Sự lai tạo giữa hai cá thể thực chất là việc ghép phần đầu chromosome của cá thể này với phần đuôi chromosome của cá thể kia.

 Làm sao để mã hóa thành các chromosome?

 Tùy vào từng bài toán sẽ có những cách mã hóa khác nhau. Đây cũng chính là mấu chốt của vấn đề, nếu ta có thể mã hóa bài toán thành dạng chromosome, bài toán có thể giải quyết bằng thuật giải di truyền.

 Biến dị là gì?

 Việc lai tạo đơn giản là các sự kết hợp giữa 2 chromosome cũ với nhau đến một lúc nào đó sẽ bị bão hòa và không thể tạo ra phần tử mới nữa. Lúc này đòi hỏi phải có một phẩn tử hoàn toàn mới để cung cấp sự đa dạng cho quần thể. Sự biến dị sẽ tạo nên cá thể mới so với quần thể, đảm bảo tính đa dạng cho quần thể. Sự biến dị không phải lúc nào cũng xảy ra mà chỉ xảy ra ở một tỷ lệ nhất định.

 BÀI TOÁN SINH CHUỖI “TO BE OR NOT TO BE”.
  • Trạng thái mục tiêu chính là chuỗi “to be or not to be”.
  • Các trạng thái là các chuỗi được sinh ngẫu nhiên có cùng độ dài. Mỗi chuỗi này biểu diễn cho một chromosome bao gồm các gene nối tiếp nhau, mỗi gene là một ký tự. Sự lai tạo có thể được hình dung như sau:

  • Nếu việc lai tạo được thực hiện ở chính giữa chuỗi, ta có cá thể mới sinh ra bằng cách lấy nửa đầu chuỗi 1 ghép với nửa sau chuỗi 2 để có: “ABCEDD”.
  • Sự biến dị thực chất chỉ là việc thay đổi một số gene trong chuỗi được sinh ra. Ví dụ ký tự đầu của chromosome “ABCEDD” bị biến dị thành “ABCEFD”.

  • Fitness của một trạng thái có thể được định nghĩa là số lượng các ký tự giống với trạng thái mục tiêu

THUẬT TOÁN
  1. Khởi tạo quần thể ngẫu nhiên
  2. Lặp:
        - Tính fitness cho mỗi cá thể so với mục tiêu
        - Lựa chọn ngẫu nhiên 2 cá thể theo quy luật chọn lọc tự nhiên. Ở đây, sau khi update fitness cho từng cá thể, ta tạo ra một mating pool để lấy 2 phần tử sao ngẫu nhiên từ pool này cho cá thể mạnh hơn có cơ hội được chọn lựa cao hơn.

Giải thuật sẽ được thực hiện qua các bước sau:
  • Khởi tạo quần thể: Sinh ra ngẫu nhiên một quần thể gồm n cá thể (trong đó n là lời giải cho bài toán).
  • Tính giá trị thích nghi: Ước lượng độ thích nghi của mỗi cá thể.
  • Điều kiện dừng: Kiểm tra điều kiện để kết thúc giải thuật.
  • Chọn lọc: Chọn hai cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn).
  • Trao đổi chéo: Với một xác suất được chọn, trao đổi chéo hai cá thể bố mẹ để tạo ra một cá thể mới.
  • Đột biến: Với một xác suất đột biến được chọn, biến đổi cá thể mới.
  • Chọn kết quá: Nếu thỏa mãn điều kiện dừng thì giải thuật kết thúc và chọn được lời giải tốt nhất trong quần thể hiện tại.

 Ta có thể thấy rằng, khi Điều kiện dừng chưa được thỏa mán, quần thể mới sẽ liên tục được tạo ra bằng cách lặp lại 3 bước Chọn lọc, Trao đổi chéo và Đột biến.

 GAs có 2 điều kiện dừng cơ bản:
  • Dựa trên cấu trúc nhiễm sắc thể, kiểm soát số gene được hội tụ, nếu số gene được hội tụ tại một điểm hoặc vượt quá điểm đó thì giải thuật kết thúc.
  • Dựa trên ý nghĩa đặc biệt của nhiễm sắc thể, đo sự thay đổi của giải thuật sau mỗi thế hệ, nếu thay đổi này nhỏ hơn một hằng số xác định thì giải thuật kết thúc.
Ví dụ:
  • Có 5 cá thể A,B,C,D,E lần lượt có fitness như sau: 1, 3, 2, 0, 4. 
  • Như vậy mating pool như sau: A, B, B, B, C, C, E, E, E, E. 
  • Rõ ràng nếu ta lấy ngẫu nhiên 1 phần tử trong pool này, tỷ lệ chọn ra E sẽ là cao nhất.
  • Thực hiện lai ghép để tạo ra cá thể mới
  • Thay thế cá thể cũ bằng cá thể mới tạo ra
  • Nếu cá thể mới giống với mục tiêu hoặc giống ở mức chấp nhận được thì dừng. Ở đây, rất có thể chúng ta không tìm được kết quả tối ưu hoặc sẽ rất lâu mới tìm thấy trạng thái này, như vậy ta có quyền dừng ở trạng thái chấp nhận được để tiết kiệm thời gian.

 THIẾT KẾ THUẬT TOÁN:
// khởi tạo quần thể với số lượng n cá thể, mỗi cá thể có chiều dài k
InitializePopulation(int len, int nPopulation);
while (foundTarget){
// tạo mating pool
var matingPool = UpdateFitnessAndCreateMatingPool();
// lấy 2 phần tử dựa vào mating pool
var p1 = population[matingPool[_rnd.Next(pool.Count)]];
var p2 = population[matingPool[_rnd.Next(pool.Count)]];
// ngẫu nhiên tìm điểm cắt
var splitPoint = _rnd.Next(_target.Length - 2) + 1;
// lai tạo để tạo ra phần tử mới
var newDNA = p1.CrossOver(p2, splitPoint);
// biến dị dựa trên tỷ lệ biến dị
newDNA.Mutate(mutationRate, materials);
// thay thế phần tử cũ
population[i] = newDNA;
// kiểm tra điều kiện dừng
if (newDNA.CompareTo(target) == target.Length)
foundTarget = true;
}

 Như vậy, ta cần định nghĩa thêm một class DNA để đại diện cho một cá thể trong quần thể:
class DNA
{
public char[] Content { get; private set; } // chuỗi gene
// lai tạo ra dna mới
public DNA CrossOver(DNA dna, int splitPoint);
// biến dị theo tỷ lệ
public void Mutate(double mutationRate);
// hàm tính khoảng cách tới DNA khác
// hỗ trợ việc tính fitness
public int CompareTo(char[] content);
}

 ***********
Bài toán: Guessing Password — Đoán mật khẩu
Nào chúng ta bắt đầu ứng dụng giải thuật di truyền vào giải quyết bài toán đoán mật khẩu.

 Về bài toán, sử dụng những ký tự trong bảng chữ cái để tái tạo lại mật khẩu. Cụ thể, ở bài này chúng ta sẽ bắt đầu với những ký tự: a-z, A-Z, !. để tái tạo nên mật khẩu: “Hello World!”.

 Các bước giải bài toán:
  • Khởi tạo quần thể: Sinh ra ngẫu nhiên một đoạn dài 11 ký tự (dài bằng với mục tiêu “Hello World”.
  • Tính giá trị thích nghi: Đếm số ký tự trùng giữa đoạn tạo ra và “Hello World”.
  • Điều kiện dừng: Kiểm tra xem số ký tự trùng bằng 11 hay không.
  • Chọn lọc: Chọn hai cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn).
  • Trao đổi chéo (Không thực hiện ở bài toán này): Với một xác suất được chọn, trao đổi chéo hai cá thể bố mẹ để tạo ra một cá thể mới.
  • Đột biến: Với một xác suất đột biến được chọn, biến đổi cá thể mới.
  • Chọn kết quá: Khi số ký tự trùng bằng 11 thì dừng giải thuật.
Chromosomes và Gene

 Trong sinh học, nói một cách khái quát, trong một Chromosomes (nhiễm sắc thể) sẽ có thể chứa rất nhiều loại gene khác nhau.

 Ở bài toán của chúng ta, tất cả những trình tự đoạn 11 ký tự ( độ dài bằng với “Hello World”) được gọi là Chromosomes. Và mỗi loại ký tự sẽ đại diện cho 1 loại Gene khác nhau.
geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
target = "Hello World"

Đầu tiên chúng ta khai báo biến geneSet chứa các ký tự trong bảng chữ cái, mỗi ký tự đại diện cho một loại Gene. Cùng với đó, khai báo biến target là đoạn ký tự mục tiêu “Hello World”.
Bước 1: Khởi tạo quần thể
import random
def initialize_chromosomes(length):
    chromosomes = []
    while len(chromosomes) < length:
        sampleSize = min(length - len(chromosomes), len(geneSet))
        chromosomes.extend(random.sample(geneSet, sampleSize))
    return ''.join(chromosomes)
Sử dụng random.sample để tạo ngẫu nhiên từ geneSet theo độ dài cho trước. Chúng ta có thể có test bằng initialize_chromosomes(11). Kết quả sẽ có dạng: ‘yTtumWSgfkM’
Chú ý: Vòng While sinh ra nhằm xử lý vấn đề nếu độ dài của Chromosomes dài hơn số lượng loại Gene ban đầu
Bước 2: Tính giá trị thích nghi
Chúng ta thấy rằng, Chromosomes có khả năng là những trường hợp như:
  • Sekmo xosmd
  • Seklo Wocle
  • Fello Wosld
  • Gello World
  • Hello World
Có thể nhận ra ngay đoạn cuối cùng là đoạn chính xác. Nhưng làm sao chúng ta có thể “đo” được độ tối ưu của Chromosomes này?
Hàm lỗi (error function/ cost function/loss function) là một hàm số giúp đo độ tối ưu của một Chromosome. Ở hàm này, chúng ta đang hướng tới giá trị càng nhỏ càng tốt.
Với bài toán Đoán mật khẩu, để đo độ tối ưu, chúng ta đếm số kí tự sai khác trên cùng vị trí giữa Chromosome và đoạn kí tự mục tiêu “Hello World”. Vì vậy, hàm lỗi ở đây sẽ tối ưu ở số kí tự sai khác bằng 0.
Dùng quy luật trên để tính sai khác cho các trường hợp Chromosomes trên:
  • Sekmo xosmd(6)
  • Seklo Wocle(4)
  • Fello Wosld(2)
  • Gello World(1)
  • Hello World(0)
def error_function(chromosome):
    return len(target) - sum(1 for expected, actual \
                             in zip(target, chromosome)  \
                             if expected == actual)
Hàm error_function sẽ tính số ký tự sai khác ở cùng một vị trí giữa Chromosome và “Hello World”. Có thể test hàm trên như sau: error_function(“Hello World”) sẽ cho kết quả bằng 0.
Bước 3: Điều kiện điểm dừng
Kiểm tra điều kiện điểm dừng là error_function có bằng 0 hay không.
Bước 4: Tiến hóa
Trong bước này, chúng ta sẽ gộp chung cả 3 kỹ thuật: chọn lọc, trao đổi chéo và đột biến. Mục tiêu của bước này là tạo ra thế hệ mới tối ưu hơn thế hệ cũ. Độ tối ưu sẽ được đo theo hàm lỗi. Chúng ta có thể mường tượng ra rằng, đây là một vòng lặp, mỗi vòng lặp sẽ thực hiện 3 kỹ thuật trên, sau đó check điều kiện dừng. Nếu không đáp ứng được thì vòng lặp sẽ tiếp tục cho đến khi đáp ứng được thì thôi.
Ở bài toán này, chúng ta sẽ chỉ sử dụng chọn lọc và đột biến. Phần về trao đổi chéo tôi sẽ có một bài riêng vì nó có chút phức tạp hơn.
def mutate(parent):
    index = random.randrange(0, len(parent))
    childGenes = list(parent)
    newGene, alternate = random.sample(geneSet, 2)
    childGenes[index] = alternate \
    if newGene == childGenes[index] \
    else newGene
    return ''.join(childGenes)
index sẽ là một số được chọn ngẫu nhiên tức là đột biến sẽ xảy ra một cách ngẫu nhiên trên Chromosome. newGene và alternate cũng sẽ được ngẫu nhiên tạo ra từ geneSet.
Vì sao lại phải tạo ra tận 2 đột biến? Câu trả lời là đột biến có thể vô nghĩa tại 1 điểm nên cần 1 đột biến khác thay thế.
Hàm hỗ trợ
Xây dựng hàm display giúp hiển thị sự thay đổi qua từng thế hệ và thời gian chạy tương ứng
import datetime
def display(guess):
    timeDiff = datetime.datetime.now() - startTime
    fitness = error_function(guess)
    print("{0}\t{1}\t{2}".format(guess, fitness, str(timeDiff)))
Main
Sau đây sẽ là phần chạy main cho giải thuật GAs:
random.seed(1)
startTime = datetime.datetime.now()
bestParent = initialize_chromosomes(len(target))
bestFitness = error_function(bestParent)
display(bestParent)
while True:
    child = mutate(bestParent)
    childFitness = error_function(child)
     
    if bestFitness <= childFitness:
        continue
    display(child)   
    if childFitness == 0:
        break
    bestFitness = childFitness
    bestParent = child

Kết quả:

hJYVdpgEBDO 11 0:00:00
HJYVdpgEBDO 10 0:00:00
HJYVdpgEBDd 9 0:00:00.001003
HJYVopgEBDd 8 0:00:00.001003
HJYVopgErDd 7 0:00:00.004010
HJYVopgErld 6 0:00:00.005012
HJlVopgErld 5 0:00:00.008021
HJlVo gErld 4 0:00:00.008021
HelVo gErld 3 0:00:00.009036
HelVo gorld 2 0:00:00.010026
Hello gorld 1 0:00:00.017045
Hello World 0 0:00:00.020052
Khởi tạo quần thể với Chromosome đầu tiên bestParent . Tính hàm lỗi cho Chromosome này cho chúng ta kết quả là 11, cho thấy chưa có vị trí nào giữa Chromosome khởi tạo và “Hello World” trùng nhau.
Chúng ta sẽ thấy rằng, việc chọn lọc đã diễn ra ở điều kiện vòng lặp, tức là cứ mỗi khi hàm lỗi giảm là sẽ giữ lại bestParent thay thế cho Chromosome cũ kém tối ưu hơn.
Kết luận
Chúng ta đã cùng nhau xây dựng một giải thuật di truyền và hiểu các bước diễn ra bên trong giải thuật.
Giải thuật trên gần như là dạng đơn giản nhất. Nếu có bài tiếp theo, tôi sẽ giới thiệu thêm về một số vấn đề bên trong và xử lý những bài toán phổ biến và có đôi chút phức tạp hơn.

#