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.
#
