Genetic Algorithm - Thuật toán di truyền

Thuật toán di truyền (Genetic Algorithm) là một kỹ thuật tối ưu hóa và tìm kiếm lấy cảm hứng từ tiến hóa tự nhiên trên nguyên lý chọn lọc tự nhiên và di truyền học của Darwin. Thuật giải này là một công cụ đơn giản và mạnh mẽ để tìm kiếm trong những bài toán có không gian lớn và phức tạp.

Chọn lọc tự nhiên là quá trình mà các cá thể có đặc điểm di truyền phù hợp nhất với môi trường sống sẽ có nhiều khả năng sống sót và sinh sản hơn. Qua thời gian, các đặc điểm có lợi này sẽ được truyền lại cho thế hệ sau, làm tăng khả năng thích nghi của quần thể với môi trường. Ví dụ, hươu cao cổ có cổ dài hơn có thể tiếp cận nguồn lá cây cao, giúp chúng sống sót tốt hơn trong môi trường khan hiếm thức ăn dưới thấp. Các yếu tố như sự thay đổi môi trường, cạnh tranh sinh tồn và biến dị di truyền đều đóng vai trò quan trọng trong quá trình này. Nhờ chọn lọc tự nhiên, các loài có thể tiến hóa và phát triển để phù hợp với điều kiện sống không ngừng biến đổi.

Lấy cảm hứng từ quá trình chọn lọc tự nhiên, nhà khoa học máy tính John Holland đã phát minh ra thuật toán di truyền vào những năm 1960. Thuật toán này cũng đã đặt nền tảng cho các phương pháp tối ưu tiến hóa, mở đường cho các nghiên cứu và ứng dụng hiện đại trong AI, Machine Learning.

Bài toán ví dụ

Có một căn phòng chứa $n$ bóng đèn, mỗi bóng đèn có thể đang sáng hoặc đang tắt. Để điều khiển việc tắt hoặc mở bóng đèn, có một bản $n$ các công tắc đặt bên ngoài phòng. Làm cách nào bạn có thể bật sáng toàn bộ các bóng đèn trong phòng với bảng công tắc này với các điều kiện:

• Bạn không được vào phòng để xem trạng thái bóng đèn mà chỉ có duy nhất một thông tin là có bao nhiêu bóng đang bật

• Bạn không biết là công tắc nào ứng với cái đèn nào trong phòng

• Công tắc chỉ có hai trạng thái hoặc gạt lên hoặc gạt xuống và không biết ứng với trạng thái mở hay tắt đèn

Dĩ nhiên, bạn có thể giải bài toán này bằng cách lần lượt gạt từng công tắc và kiểm tra xem có bao nhiêu bóng đang được bật để rồi tìm ra trạng thái của bảng công tắc để bật toàn bộ bóng đèn. Trong bài toán này, mình xin giới thiệu một phương pháp để giải bài toán trên bằng thuật toán di truyền.

Khởi tạo

Ý tưởng chủ đạo của thuật toán là ta sẽ khởi tạo ngẫu nhiên một quần thể (population) các lời giải. Mỗi lời giải thể hiện một trạng thái của bảng công tắc và được xem như một cá thể (individual) trong quần thể. Với mỗi lời giải sẽ có một số lượng đèn được bật tương ứng, đây cũng chính là thông số đánh giá chất lượng của một lời giải (fitness). Để thực hiện thuật toán, ta lựa chọn (selection) những lời giải có fitness tốt nhất, lấy thông tin nhiễm sắc thể (chromosome) của chúng đem lai ghép (crossover) với nhau để tạo ra lời giải mới để đưa vào quần thể. Để giúp cho quần thể có tính đa dạng, đôi khi chúng ta sẽ tạo ra biến dị (mutation) trong khi lai tạo ra cá thể mới.

Đối với bàn toán này, ta sẽ xem một trạng thái của bảng công tắc như là một nhiễm sắc thể (chromosome), có giá trị là mảng các bit 0 và 1 tương ứng với trạng thái gạt lên và và gạt xuống của mỗi công tắc. Như vậy một chromosome là một mảng chứa phần tử. Một hàm số đánh giá fitness của mỗi cá thể bằng cách đưa ra số lượng đèn đang bật tương ứng với cá thể ấy. Như vậy mỗi cá thể sẽ có 2 thành phần: chromosome và fitness score.

Thuật toán

Thuật toán bao gồm 3 thành phần chính như sau:

• Chọn lọc cá thể tốt nhất (Selection): ta chọn ra $m$ cá thể trong quần thể sao cho những cá thể có fitness score càng cao thì tỷ lệ được chọn càng cao. Thuật toán có thể được hình dung như sau:

  • Giả sử có 4 các thể A, B, C, D với fitness score lần lượt là 2,7,4,6. Tổng score là 2+7+4+6=19

  • Thiết lập một mảng tạm, sắp thứ tự với 2 phần tử đại diện cho A, 7 phần tử đại diện cho B, 4 phần tử đại diện cho C và 6 phần tử đại diện cho D.

  • Ta chọn ngẫu nhiên một con số random $1\le r \le 19$

  • Giá trị $r$ rơi vào khoảng của cá thể nào thì cá thể đó được chọn

  • Rõ ràng, với cách này thì phần tử nào có fitness score càng cao thì càng có cơ hội được chọn

    

• Lai ghép (Crossover): Lấy 2 cá thể $A,B$ trong $m$ cá thể được chọn và thực hiện lai ghép bằng cách lấy $k$ bit đầu của chromosome $A$ tráo với $k$ bit đầu của chomosome $B$ để tạo ra 2 chromosome mới. Ví dụ: Chromosome $A=11001$, chromosome $B=10101$, ta lấy 2 bit đầu của $A$ và $B$ và tráo nhau để tạo ra chromosome $C=\underbrace{11}_{A} \underbrace{101}_{B}$ và $D=\underbrace{10}_{B} \underbrace{001}_{A}$

• Biến dị (Mutation): Với các cá thể mới vừa tạo ra, có một tỷ lệ nhỏ biến dị bằng cách thay ngẫu nhiên một bit nào đó của chromosome này từ 0 thành 1 hoặc ngược lại từ 1 thành 0. Ví dụ: khi biến dị xảy ra trên $C = 11101 \implies C_{mutated}=11100$ biến dị tại vị trí cuối biến 1 thành 0. Nhờ sự biến dị mà quần thể có được sự đa dạng, không bị hạn chế bởi các đặc trưng cục bộ.

Các bước của thuật toán:

• Bước 1:

  • Khởi tạo một số các cá thể ngẫu nhiên

  • Với mỗi cá thể, dùng fitness function để tính fitness score cho mỗi cá thể thông qua chromosome của nó

  • Thiết lập một hằng số $T$ là threshold tượng trưng cho tỷ lệ xảy ra đột biến

• Lặp:

  • Bước 2: Chọn lọc

  • Bước 3: Lai ghép để tạo ra cá thể mới từ các cá thể được chọn lọc ở Bước 3

  • Bước 4: Thực hiện biến dị cho cá thể mới. Tại mỗi bit của chromosome, một số ngẫu nhiên $x$ được tạo ra, nếu $x \le T$ thì thực hiện biến dị bằng cách swap bit.

  • Bước 5: Đưa cá thể ấy vào quần thể để thay thế những cá thể có fitness yếu nhất

  • Ngừng lặp nếu cá thể mới đã thỏa mãn yêu cầu tìm kiếm hoặc đã lặp một số lần đủ lớn

Demo