Bắt nguồn từ clip này Link, với một đứa chỉ vài lần nghe thoảng qua về thuật toán này thì thấy hết sức là hấp dẫn. Vì thế quyết định tìm hiểu thử. :D

Giải thuật di truyền khác gì với các thuật toán tối ưu bằng gradient?

Sử dụng gradient chỉ hiệu quả tốt trên các hàm tối ưu có 1 điểm tối ưu (single-peaked), trong thực tế có nhiều hàm tối ưu không thoả mãn yêu cầu trên làm cho các thuật toán gradient bị mắc ở điểm tối ưu địa phương.

Thuật ngữ

  1. population: Bộ tất cả các giải pháp cho 1 vấn đề.

  2. Chromosome: Nhiễm sắc thể, tương ứng với 1 giải pháp cho vấn đề

  3. Gene: gien, 1 vị trí trên nhiễm sắc thể

  4. Allele: Giá trị của 1 gene

  5. Genotype: Population trong không gian tính toán

  6. Phenotype: Population trong vấn đề thực tế

  7. Decoding: Chuyển từ genotype sang phenotype

    1. Cần được thực hiện nhanh vì được lặp lại trong khi thuật hiện GTDT

  8. Fitness function: Lấy 1 solution làm đầu vào và output độ phù hợp của solution đó.

  9. Genetic Operatorr: Mutatoion, Selection …

Cấu trúc thuật toán

  1. Bắt đầu vs 1 bộ population ( có thể tạo random hoặc heuristic )

  2. Tính điểm fitness của các cá thể trong population

  3. Crossover??

  4. Mutation: biến dị

  5. Chọn lựa cá thể sống sót

  6. Lắp lại bước 2

  7. Kết thúc và đưa ra the best

Biểu diễn genotype 

Việc lựa chọn cách biểu diễn genotype là điều thiết yếu quyết định độ chính xác của thuật toán.

  1. Biểu diễn binary

  2. Biểu diễn real value

  3. Biểu diễn integer

  4. Biểu diễn hoán vị

Fitness function 

Fitness function: Lấy 1 solution làm đầu vào và output độ phù hợp của solution đó.

Parent selection

Chọn parent và kết hợp để tạo ra con ở thế hệ kế tiếp.

Fitness proportionate selection

Xác suất để được chọn làm parent của mỗi phần tử tỉ lệ với độ fitness của phần tử đó. Do dó phần tử có độ fitness cao hơn có cơ hội được chọn và truyền feature của nó đêns thế hệ tiếp theo cao hơn.

Roulettle Wheel Selection

Chiếc nón kỳ diệu, mỗi phần tượng trưng cho 1 phần tử, có độ to tỉ lệ vs fitnesss. Quay rồi fix point chỉ vào đâu thì phần tử đó là parent.

Stochastic Universal Sampling

Có 2 điểm fix point trên vòng quay.

Tournament selection

  1. Chọn k phần tử, lấy 2 phần tử best fitness để chọn làm parent

  2. Hoạt động được với fitness âm

Rank selection

  1. Phù hợp khi các phần tử có độ fitness tương tự nhau

  2. Sắp xếp theo rank, chọn phần tử có rank cao để làm parent

Random selection

Cái tên nói lên tất cả

Crossover Giao thoa??

One Point Crossover

Chọn 1 điểm, tráo đổi phần đuôi từ điểm đó (gene) của 2 parent cho nhau để tạo ra 2 con 

1,2,3,4,|5,6
a,b,c,d,|e,f
=> 
1,2,3,4,e,f
a,b,c,d,5,6

Multi Point crossover

Chọn 2 điểm, tráo đổi phần giữa 2 vị trí gene.

Uniform crossover

Flip coin để quyết định xem có tráo đổi 1 vị trí gene của 2 parent hay không, lặp lại cho đến hết cả phần tử.

Whole Arithmetic Recombination 

Child1 = α.x + (1-α).y
Child2 = α.x + (1-α).y

Davis’ Order Crossover (OX1)

  1. Chọn 2 điểm gene random của parent 1, copy vào child 1

  2. Chọn những điểm không chứa gene đã chọn ở bước 1 của parent 2 rồi đền nốt vào child 1

  3. Lặp lại để tạo ra child 2

Mutation

Bit flip gene

Chọn 1 gene rồi đảo ngược

Random resetting

Chọn 1 gene rồi random giá trị (trong vùng giá trị có thể )

Swap mutation

Chọn 2 gene rồi tráo đổi

Scramble mutation

Hoán vị 1 đoạn subset genee của nhiễm sắc thể

Inversion mutation

Lật ngược 1 đoạn gene của nhiễm sắc thể

Survivor selection

Chọn phần tử nào để loại bỏ hoặc giữ lại cho thế hệ kế tiếp

Age kickout

  1. Kickout dựa trên tuổi.

  2. Tạo ra child rồi kickout parent

  3. Tăng tuổi của phần còn lại thêm 1

Fitness base kickout

Child sẽ replace phần tử có độ fitness thấp

Termination condition

Điều kiện để dừng thuật toán

  1. Không có cải thiện trong bộ population

  2. Đạt đến số lượng thế hệ tối đa