Tự học giải thuật di truyền qua sách Genetic Algorithms with Python

Mình mua quyển sách bản Kindle qua trang amazon.com. Vì tiếc tiền quá nên cố gắng đọc và học hết quyển sách này bằng cách vừa học vừa làm các ví dụ của nó và post lên đây
Các bạn có thể mua nó tại
https://www.amazon.com/Genetic-Algorithms-Python-Clinton-Sheppard-ebook/dp/B01MYOWVJ2/ref=sr_1_1?crid=3ICTBG4223P4P&keywords=genetic+algorithms+with+python&qid=1574139820&sprefix=Genetic+al%2Caps%2C369&sr=8-1


Nếu không có điều kiện học trên máy có cài sẵn Python thì chúng ta có thể thực thi python trên webbrowser với các Python online IDE như

https://www.jdoodle.com/python-programming-online/

https://www.onlinegdb.com/online_python_compiler

https://repl.it/ << Trang này có thể liên kết với github. Bạn có thể lưu project mình vào github hoặc xem các project của người khác (nếu có quyền xem)

Ví dụ: Bạn có thể xem mọi ví dụ của quyển sách này tại địa chỉ của chính tác giả của quyển sách này: https://repl.it/EWUh

Bài 1: Hello World!

Nói một chút về thuật toán di truyền trước khi chúng ta đi sâu hơn về các vấn đề lập trình với thuật toán này.

Ví dụ trong sách hơi trẻ con nên mình đề xuất một ví dụ gần gũi hơn.

Một ngày đẹp trời năm bạn 17 tuổi, học lớp 12 và sắp tốt nghiệp phổ thông. Bạn cùng bàn của bạn nhận được thư tình của một cô bạn trong lớp. Cậu ấy hồ hởi khoe với bạn và muốn bạn đoán tên của người .
Trong danh sách của cậu bạn đào hoa đó có chừng 10-11 cái tên là:
An, Bình, Cúc, Đào, Lan, Hồng, Thu, Hương, Diễm, Vi, Yến

Bạn đoán "Có phải An không?" "Có phải Cúc không?" "Có phải Vi không? "... Câu trả lời có thể là "đúng" hay "sai". Nếu bạn đoán trượt 8 lần thì lần thứ 9 xác xuất đoán đúng của bạn vẫn là 50/50 hay đúng/sai.
Nhưng nếu bạn bạn của bạn thay đổi câu trả lời bằng "xinh hơn", "không xinh bằng", "chuẩn chỉnh" bạn không cần đến 8 lần mà vẫn đoán ra đó là ai
Tại sao bạn không cần tới 8 lần để đoán được người đó là? Lý do là chúng ta có ký ức về những người đó, dựa trên câu trả lời của cậu bạn để từ từ suy luận ra ai là người gửi bức thư tình.

Giải thuật di truyền không biết thế nào là "xinh hơn", Nếu không có trí thông minh, không được học, nó sẽ sai giống nhau cho mọi lần thử làm điều gì đấy. Nó chỉ tốt khi giải quyết một vấn đề như con người viết ra mã đó. Vậy mà, nó có thể tìm ra giải pháp cho vấn đề mà con người gặp trở ngại khi giải quyết hay không thể giải quyết hoàn toàn. Sao có thể như vậy? Các thuật toán di truyền sử dụng  các bước thăm dò ngẫu nhiên không gian vấn đề kết hợp với các tiến trình tiến hóa như đột biến hay trao đổi chéo (trao đổi thông tin di truyền) để cải thiện các dự đoán. Những cũng bởi vì nó không có kinh nghiệm trong không gian vấn đề, nên chúng sẽ thử với những thứ mà một người bình thường sẽ không bao giờ nghĩ đến việc thử. Vì thế một người sử dụng thuật toán di truyền có thể học được nhiều hơn về không gian vấn đề và các giải pháp tiềm nằng, cho họ khả năng cải tiến  thuật toán, như một vòng nhân quả, cái này tiếp nối cái kia.

Chúng ta sẽ bắt đầu với một bài toán đơn giản là đoán một cụm từ mật mã . Ý tưởng là

[mcode]
_letters = [a.. zA.. Z !]
target = "Hello World!"
guess = get 12 random letters from _letters
while guess != target:
            index = get a random value from [0.. length of target]
            guess[ index] = get 1 random letter from _letters
[/mcode]

Đầu tiên là ta cần một không gian đầu vào là một mảng ký tự có chữ hoa chữ thường và ký tự !. Tiếp đó ta cần một đích đến toàn cục của vấn đề là "Helllo World!". Sau khi khởi tạo một giá trị ban đầu rồi tiến các bước thử và kiểm tra để tìm ra kết quả sau cùng của bài toán. Bài toán này không phải là đích đến ngắm tới của thuật giải di truyền bởi vì nó không tận dụng được một thứ gọi là kinh nghiệm của lần đoán trước trong không gian tìm kiếm. Với câu trả lời là đúng hay sai thì lần đoán sau không có sự kế thừa kết quả của lần đoán trước.
Do vậy ta sẽ thêm một khái niệm mới vào bài toán của mình đó là fitness hay còn gọi là độ phù hợp là tiêu chuẩn đánh giá của mỗi lần đoán.
Để tập làm quen với giải thuật di truyền ( viết tắt là GA = Genetic Algorithm) ta sẽ định nghĩa mỗi một kết quả của một quá trình biến đổi giá trị (đột biến (mutation), lai chéo (crossover)) là một  thế hệ (Generation). Mỗi một thế hệ có 1 giá trị gien (gene) khác nhau. Ý tưởng giải thuật là :

[mcode]
_letters = [a.. zA.. Z !]
target = "Hello World!"
guess = get 12 random letters from _letters
fitness = evaluate guess by comparing with target
while fitness != lengh of target:
           child_guest = guess
           index = get a random value from [0.. length of target]
           child_guess [ index] = get 1 random letter from _letters
           child_fitness = evaluate child_guess by comparing with target
           fitness  = child_fitness  AND guess = child_guess if child_fitness > fitness  
[/mcode]

Code:


[mutilTab]
[tab1]
GuessPassword.py
[/tab1]
[contentTab1]
# guessPassword from  the book Genetic Algorithms with Python

import random     # use import to load existing library or self-defined library
import datetime

geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
target = "Hello World!"
def generate_parent( length):
   genes = []
   while len( genes) < length:
       sampleSize = min( length - len( genes), len( geneSet))
       genes.extend( random.sample( geneSet, sampleSize))
   return ''. join( genes)

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)
def get_fitness( guess):
   return sum( 1 for expected, actual in zip( target, guess) if expected == actual)


def display( guess):
   timeDiff = datetime.datetime.now() - startTime
   fitness = get_fitness( guess)
   print("{}\ t{}\ t{}". format( guess, fitness, timeDiff))

if __name__ == '__main__':
   random.seed()
   startTime = datetime.datetime.now()
   bestParent = generate_parent( len( target))
   bestFitness = get_fitness( bestParent)
   display( bestParent)
   while True:
       child = mutate( bestParent)
       childFitness = get_fitness( child)
       if bestFitness >= childFitness:
           continue
       display( child)
       if childFitness >= len( bestParent):
           break
       bestFitness = childFitness
       bestParent = child
[/contentTab1]
[tab2]
Giải thích code
[/tab2]
[contentTab2]
Python dùng dấu # để tạo 1 dòng ghi chú (comment). Mỗi một dòng lệnh, khối lệnh, khối hàm phân biệt nhau bằng các đoạn giật lùi (indent). đoạn code bị thụt lề nhiều hơn thì sẽ là nằm trong đoạn code trước đó. Điều này thay cho dấu { } trong ngôn ngữ lập trình C/C++, java,..
Nhân của quá trình tạo đột biến (mutation) là phép tạo ra những giá trị ngẫu nhiên (random). Trong python ta nạp vào thư viện random sử dụng như sau:

random
Khởi tạo bộ máy ngẫu nhiên với random.seed(). Thực chất của quá trình tạo số ngẫu nhiên không có gì là ngẫu nhiên. Nó được tạo ra dựa trên các xung nhịp của vi xử lý. Nếu bạn không quan tâm đến vấn đề này thì bỏ qua ý nghĩa thực của hàm seed(). Ý nghĩa của hàm seed(n) là tạo ra một bộ những giá trị ngẫu nhiên để thuận tiện cho quá trình test khi ta cần lặp lại chính xác giá trị đã test trước.  Khởi tạo seed1 sẽ random ra giá 123, giá trị thứ 2 là 125 khi bạn chạy lại seed1 vẫn cho giá trị 123 cho lần đầu và 125 cho lần sau....
random.randrange( 0, len( parent)) sẽ cho ra một số ngẫu nhiên trong khoảng (0, lent(parent)). Là khoảng 0<a<lent(parent)
random.sample( geneSet, 2) sẽ chọn ra 2 giá trị ngẫu nhiên nằm trong geneSet. Kết quả trả về là 1 list. Nếu bạn gán kết quả cho 1 biến thì biến đó là 1 list. Nếu bạn gán nó cho 1 tập hợp các biến, thì từng biến sẽ giữ 1 giá trị trả về . Ví dụ như ở đây là  newGene, alternate = random.sample( geneSet, 2)

datetime
Sẽ  sử dụng thời gian để hỗ trợ cho quá trình xuất log, thống kê giá trị..... Import thư viện datetime và để lấy thời gian hiện tại ta dùng datetime.datetime.now(). Lưu ý thì biến dạng datetime có thể  + / - được.

if else
Câu lệnh điều kiện if được đi kèm else để rẽ nhánh logic.
  Dạng 1 là dạng cơ bản , sau cùng là dấu : để đánh dấu. Câu lệnh khởi đầu bởi if, rẽ nhánh bởi else, phía sau là những câu, khối lệnh.
      if bestFitness >= childFitness:
           continue
  Dạng 2 là dạng biến hóa của  python dùng để rút gọn câu lệnh if tương đương với C/C++ là : childGenes[ index] =  newGene == childGenes[ index] ?  alternate  : newGene;
        childGenes[ index] = alternate if newGene == childGenes[ index] else newGene
While
Tạo ra một vòng lặp thực thi các hàm bên trong khối lệnh khi vẫn thỏa điều kiện đặt ra.

sum( 1 for expected, actual in zip( target, guess) if expected == actual)
Đây là 1 dòng rối não nhưng giúp cho code ngăn gọn tựa như suy nghĩ của con người, ý của nó là : Nếu như ta có 2  từ có độ dài giống nhau, ta sẽ đếm số ký tự giống nhau giữa 2 cụm từ đó.
zip (target, guess): hàm zip là hàm ghép cặp các giá trị có trong các dữ liệu dạng chuỗi mảng, ví dụ  A có 3 phần tử 1,2,3 B có 3 phần tử là 'a','b','c', zip sẽ cho ta 3 phần tử là (1, 'a'), (2, 'b'), (3, 'c')
for expected, actual in zip( target, guess): đây là hàm [b]for[/b] lấy ra giá trị của hàm ghép cặp zip. ta biết được zip sẽ tạo ra 1 cặp 2 phần tử nên ta gán chúng vào 2 biến expected, actual
sum ()  là hàm tổng các số có trong list


[/contentTab2]
[tab3]
[/tab3]
[contentTab3]
[/contentTab3]
[/mutilTab]


Kết quả là
[mcode]
PSmh.AruwtlY    0       0:00:00
PSmhoAruwtlY    1       0:00:00.001000
PSmhoAruwllY    2       0:00:00.003000
PSmho ruwllY    3       0:00:00.003000
PSmho ruwll!    4       0:00:00.003000
PSmho Wuwll!    5       0:00:00.004000
PSmho Wuwld!    6       0:00:00.005000
HSmho Wuwld!    7       0:00:00.005000
HSmho Wurld!    8       0:00:00.007000
Hemho Wurld!    9       0:00:00.007000
Helho Wurld!    10      0:00:00.008000
Helho World!    11      0:00:00.010000
Hello World!    12      0:00:00.023000
[/mcode]

Bước tiếp theo là chúng ta module hóa các phần code có thể tái sử dụng được để có thể sử dụng ở phần khác trong dự án hay trong các dự án khác. Việc module này cũng có thể giúp bạn tối ưu hóa các dòng code, tránh rườm rà. Lõi genetic hiện nay gồm có khởi tạo, đột biến và lấy kết quả. Sau này ta có thể thêm nhiều thuật toán vào lõi này để hoàn thiện nó.

Phần này mình sẽ giới thiệu về module Unitest của chính python. Công cụ này giúp các lập trình viên xây dựng các bước kiểm thử cho các thuật toán của mình. Các trường hợp kiểm tra - test case - được con người định sẵn để đánh giá các thuật toán hoặc các bước xây dựng thuật toán.

# guessPassword from  the book Genetic Algorithms with Python
[mcode]
# guessPassword from  the book Genetic Algorithms with Python
import datetime
import genetic
import unittest

def get_fitness( genes, target):
   return sum(1 for expected,actual in zip(target,genes) if expected == actual)


def display( genes, target, startTime):
   timeDiff = datetime.datetime.now() - startTime
   fitness = get_fitness(genes,target)
   print("{}\ t{}\ t{}". format( genes, fitness, timeDiff))


def test_Hello_World():
   target ="Hello World"
   guess_password(target)

def guess_password(target):
   geneset = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
   startTime = datetime.datetime.now()

   def fnGetFitness(genes):
      return get_fitness(genes, target)
   def fnDisplay(genes):
      return display(genes,target, startTime)
   
   optimalFitness = len(target)

   genetic.get_best(fnGetFitness,len(target),optimalFitness,geneset,fnDisplay)

class guessPasswordTest(unittest.TestCase):

   def test_helloworld(self):
      target = "Hello New world"
      guess_password(target)

   def test_friendzone(self):
      target = "You are apple of my eyes, aren't you?"
      guess_password(target)

if __name__ == '__main__':
   unittest.main()
[/mcode]