Giải thuật di truyền
Cảm hứng từ tiến hoá
Phần lớn các thuật toán trước đây dựa vào đạo hàm để dò đường đi xuống đáy hàm mất mát, như hồi quy tuyến tính với hạ gradient. Nhưng nhiều bài toán không có đạo hàm để dựa vào: không gian lời giải rời rạc, hàm mục tiêu gồ ghề đầy hố, hoặc đơn giản là quá lớn để duyệt hết. Khi đó ta cần một cách tìm kiếm khác, không cần biết hàm mục tiêu trơn hay lồi, chỉ cần đánh giá được một lời giải tốt tới đâu.
Tự nhiên đã giải bài toán tối ưu hoá khổng lồ này suốt hàng tỉ năm bằng tiến hoá. Một quần thể sinh vật thích nghi dần với môi trường qua nhiều thế hệ: cá thể khoẻ mạnh sống sót và sinh sản nhiều hơn, con cái thừa hưởng đặc điểm tốt từ cha mẹ, thỉnh thoảng đột biến tạo ra biến dị mới. Qua thời gian, quần thể ngày càng thích nghi tốt hơn dù không ai chỉ huy quá trình đó.
Giải thuật di truyền, tiếng Anh là genetic algorithm, viết tắt GA, mượn đúng cơ chế này để tối ưu hoá. Ta coi mỗi lời giải ứng viên là một cá thể trong quần thể, để chúng cạnh tranh, lai ghép, đột biến qua nhiều thế hệ, rồi giữ lại những lời giải tốt dần lên. GA không cần đạo hàm, nên dùng được cả khi hàm mục tiêu rời rạc hay gồ ghề, miễn là ta tính được độ tốt của một lời giải.
Thử ngay: bấm qua từng thế hệ GA trên OneMax
OneMax là bài toán đồ chơi kinh điển của GA: mỗi cá thể là một chuỗi bit, mục tiêu là chuỗi toàn số 1, và độ tốt của một cá thể (gọi là fitness) chính là số bit 1 nó đang có. Hãy bấm qua từng thế hệ dưới đây để thấy trọn vòng đời GA trên OneMax. Quần thể sáu cá thể sinh ngẫu nhiên rồi qua chọn lọc, lai ghép, đột biến và giữ tinh hoa, fitness tốt nhất leo dần lên tới khi cả chuỗi phủ kín bit 1. Toàn bộ chạy tất định từ một hạt giống, nên cùng một hạt thì lần nào cũng cho đúng một kết quả; bấm Gieo lại để xem một lần chạy khác.
Bốn ô còn lại là các tham số thật của thuật toán, đổi cái nào thì GA chạy lại từ thế hệ 0 với đúng tham số đó. Đáng thử nhất là kéo đột biến mỗi bit về 0 (quần thể cạn kiệt biến dị rồi đứng im, không bao giờ tới đích), đẩy nó lên 0,5 (đột biến phá nhanh hơn chọn lọc xây, may mà còn cá thể tinh hoa giữ lại), hay hạ cỡ giải đấu xuống 1, tức bốc cha mẹ bừa và bỏ hẳn áp lực chọn lọc: hãy đổi vài hạt giống ở mức này, bạn sẽ thấy có lần GA vẫn về đích nhờ cá thể tinh hoa, nhưng nhiều lần khác nó bò hết 24 thế hệ mà chuỗi vẫn chưa phủ kín bit 1.
Mã hoá cá thể thành nhiễm sắc thể
Bước đầu tiên khi áp dụng GA là quyết định cách biểu diễn một lời giải. Trong sinh học, đặc điểm của một cá thể được lưu trong nhiễm sắc thể, tiếng Anh là chromosome, là một chuỗi gen. GA cũng vậy: mỗi lời giải ứng viên được mã hoá thành một chuỗi, thường là chuỗi bit hoặc chuỗi số.
Ví dụ kinh điển và đơn giản nhất là dùng chuỗi nhị phân. Một cá thể độ dài 8 có thể là 1 0 1 1 0 0 1 0, trong đó mỗi vị trí là một gen mang giá trị 0 hoặc 1. Cách mã hoá phải phù hợp với bài toán: nếu cần chọn 8 món đồ bỏ vào balô thì mỗi bit nói món thứ i có được lấy hay không; nếu cần một số nguyên thì cả chuỗi bit biểu diễn số đó ở hệ nhị phân.
Cả quần thể là một tập hợp gồm nhiều cá thể như vậy. Ta thường ký hiệu kích thước quần thể là pop_size, ví dụ 40 cá thể, và độ dài nhiễm sắc thể là length, ví dụ 20 bit. Toàn bộ quần thể khi đó là một bảng pop_size dòng, mỗi dòng length bit.
Hàm thích nghi fitness
Để biết cá thể nào tốt hơn cá thể nào, ta cần một thước đo, gọi là hàm thích nghi, tiếng Anh là fitness function. Hàm này nhận vào một cá thể và trả về một con số: số càng lớn thì cá thể càng tốt, tức càng gần lời giải ta mong muốn.
Hàm fitness chính là nơi ta cài đặt mục tiêu bài toán vào GA. Đây cũng là điểm linh hoạt nhất: muốn dùng GA cho bài toán khác, phần lớn chỉ cần thay hàm fitness, còn cả bộ máy chọn lọc, lai ghép, đột biến giữ nguyên. Vì vậy khi gặp một bài toán mới, câu hỏi quan trọng nhất luôn là làm sao chấm điểm một lời giải.
Một hàm fitness tốt nên phân biệt được cả những lời giải gần đúng, chứ không chỉ phân biệt đúng với sai. Nếu fitness chỉ trả về 1 khi lời giải hoàn hảo và 0 cho mọi trường hợp còn lại, GA gần như không có manh mối để leo dần lên, vì mọi cá thể chưa hoàn hảo đều giống nhau dưới con mắt của nó.
Bốn toán tử của vòng đời tiến hoá
Sau khi đã có cách mã hoá và hàm fitness, GA lặp đi lặp lại bốn bước mô phỏng sinh học để biến một thế hệ thành thế hệ tiếp theo.
Chọn lọc, tiếng Anh là selection. Cá thể có fitness cao hơn được ưu tiên chọn làm cha mẹ. Một cách phổ biến là bánh xe roulette, nơi xác suất được chọn tỉ lệ với fitness. Một cách khác đơn giản và rất ổn định là đấu loại, tiếng Anh là tournament: bốc ngẫu nhiên vài cá thể rồi giữ lại cá thể tốt nhất trong nhóm đó. Đây là sức ép tiến hoá đẩy quần thể về phía tốt hơn.
Lai ghép, tiếng Anh là crossover. Hai cá thể cha mẹ trao đổi một phần nhiễm sắc thể để sinh con. Với mã hoá chuỗi, lai ghép một điểm chọn một vị trí cắt ngẫu nhiên rồi ghép chéo: con thứ nhất lấy nửa đầu của cha và nửa sau của mẹ, con thứ hai lấy phần ngược lại. Lai ghép giúp gộp những mảnh tốt từ hai cha mẹ thành một con có thể tốt hơn cả hai.
Đột biến, tiếng Anh là mutation. Với một xác suất nhỏ, vài gen của con bị thay đổi ngẫu nhiên, ví dụ lật một bit từ 0 thành 1 hoặc ngược lại. Đột biến giữ đa dạng di truyền cho quần thể, giúp nó không kẹt mãi trong một vùng nghiệm hẹp. Nếu xác suất đột biến quá nhỏ, quần thể dễ đồng nhất sớm; nếu quá lớn, GA biến thành tìm kiếm ngẫu nhiên mất hết tính tích luỹ.
Thay thế thế hệ. Sau khi đã sinh đủ con, thế hệ con thay cho thế hệ cũ và vòng lặp tiếp tục. Cứ mỗi vòng như vậy ta gọi là một thế hệ, tiếng Anh là generation.
Vòng lặp tiến hoá và điều kiện dừng
Ghép bốn toán tử trên lại, ta được vòng đời hoàn chỉnh của GA:
- Khởi tạo một quần thể ngẫu nhiên gồm
pop_sizecá thể. - Tính fitness cho từng cá thể trong quần thể.
- Lặp lại cho tới khi đạt điều kiện dừng:
- chọn lọc cha mẹ từ quần thể hiện tại,
- lai ghép cha mẹ để sinh con,
- đột biến con với xác suất nhỏ,
- thay quần thể cũ bằng thế hệ con và tính lại fitness.
- Trả về cá thể có fitness cao nhất từng gặp.
Điều kiện dừng thường là một trong hai: đạt số thế hệ tối đa đã định trước, hoặc fitness của cá thể tốt nhất đã đủ tốt theo ngưỡng ta đặt. Có thể kết hợp cả hai để vừa giới hạn thời gian chạy, vừa dừng sớm khi đã tìm được lời giải hài lòng.
Khác với hạ gradient luôn đi xuống một cách xác định, GA mang yếu tố ngẫu nhiên ở mọi bước. Bù lại, nhờ giữ cả một quần thể đa dạng và liên tục pha trộn, GA ít bị kẹt ở một cực trị địa phương duy nhất như các phương pháp leo dốc đơn lẻ.
Tinh hoa và hội tụ sớm
Bốn toán tử cơ bản có một lỗ hổng: khi thay toàn bộ thế hệ cũ bằng thế hệ con, cá thể tốt nhất từng tìm được có thể biến mất, vì lai ghép và đột biến đều mang tính phá vỡ. Một cha mẹ xuất sắc chưa chắc sinh ra con xuất sắc, nên fitness tốt nhất của quần thể đôi khi tụt lùi giữa hai thế hệ liên tiếp. Cách chữa đơn giản và rất hiệu quả là giữ tinh hoa, tiếng Anh là elitism: sao chép nguyên vẹn một hoặc vài cá thể tốt nhất sang thẳng thế hệ sau, không cho lai ghép hay đột biến đụng vào chúng. Nhờ đó fitness tốt nhất không bao giờ giảm qua các thế hệ, và GA luôn giữ được thành quả đã đạt trong khi vẫn tự do thử nghiệm ở phần còn lại của quần thể.
Mặt trái của sức ép chọn lọc là hiện tượng hội tụ sớm, tiếng Anh là premature convergence. Nếu chọn lọc quá gắt, ví dụ luôn ưu ái vài cá thể trội ngay từ những thế hệ đầu, thì chỉ sau ít vòng cả quần thể sẽ giống hệt nhau, đều là con cháu của số ít cá thể đó. Khi mọi cá thể gần như đồng nhất, lai ghép hai cá thể giống nhau chỉ cho ra con y hệt, và nguồn biến dị duy nhất còn lại là đột biến vốn rất yếu. Quần thể kẹt ở một cực trị địa phương và mất khả năng thoát ra, dù lời giải đó chưa phải tốt nhất. Đây là lý do ta luôn phải cân bằng giữa khai thác, tức dồn về vùng nghiệm tốt đã biết, và thăm dò, tức giữ đa dạng để còn tìm được vùng nghiệm mới. Tăng đột biến, giảm sức ép chọn lọc, hay tăng kích thước quần thể đều là những cách nghiêng cán cân về phía thăm dò.
Nhìn từ góc độ này, GA thực chất là một dạng tìm kiếm cục bộ ngẫu nhiên chạy song song trên nhiều điểm cùng lúc. Mỗi cá thể là một điểm trong không gian nghiệm; đột biến là bước đi nhỏ ngẫu nhiên quanh điểm đó, còn lai ghép là bước nhảy kết hợp thông tin từ hai điểm khác nhau. Khác với leo dốc chỉ giữ một điểm và luôn bước lên, GA giữ cả một đám điểm và để chọn lọc quyết định đám đó trôi về đâu. Chính vì dựa vào ngẫu nhiên và không dùng thông tin đạo hàm, GA không bảo đảm tìm được tối ưu toàn cục và cũng không cho biết còn cách tối ưu bao xa; đổi lại nó rất linh hoạt và dễ áp cho những bài toán mà các phương pháp có đạo hàm phải bó tay.
Nhiều người tưởng GA cứ chạy đủ lâu là chắc chắn ra lời giải tối ưu. Không phải vậy. GA là tìm kiếm heuristic ngẫu nhiên, nó có thể hội tụ sớm vào một cực trị địa phương rồi mắc kẹt ở đó gần như vô hạn. Chạy thêm thế hệ khi quần thể đã đồng nhất hầu như không cải thiện gì, vì nguồn biến dị đã cạn. Muốn tăng cơ hội chạm tối ưu, ta phải can thiệp vào đa dạng, chẳng hạn khởi động lại quần thể, tăng đột biến hay chạy nhiều lần với hạt giống ngẫu nhiên khác nhau rồi giữ kết quả tốt nhất, chứ không đơn thuần kéo dài thời gian chạy.
Ví dụ kinh điển: bài toán OneMax
Để thấy trọn vòng đời mà không bị rối vì bài toán phức tạp, ta dùng bài toán OneMax, một bài kiểm thử kinh điển của GA. Đề bài rất gọn: cho chuỗi nhị phân độ dài cố định, hãy tìm chuỗi có nhiều bit 1 nhất. Lời giải tối ưu hiển nhiên là chuỗi toàn bit 1, nên ta dễ dàng biết GA đã chạy đúng hay chưa.
Cách mã hoá ở đây tự nhiên: mỗi cá thể là một chuỗi length bit. Hàm fitness cũng đơn giản nhất có thể: đếm số bit 1 trong chuỗi. Một cá thể độ dài 20 sẽ có fitness chạy từ 0, ứng với chuỗi toàn 0, tới 20, ứng với lời giải tối ưu. Vì fitness phân biệt được cả những lời giải gần đúng, GA có đủ manh mối để leo dần lên qua từng thế hệ.
OneMax tuy đồ chơi nhưng đủ minh hoạ mọi cơ chế. Muốn áp GA cho bài toán thật, ta giữ nguyên khung và chỉ thay hàm fitness cho phù hợp mục tiêu mới.
Mã nguồn Python
Đoạn mã dưới đây cài đặt trọn một vòng đời GA cho bài toán OneMax bằng numpy, chạy được ngay. Ta giả định đã có import numpy as np.
# Genetic algorithm for the OneMax problem: maximise the number of ones.
import numpy as np
def fitness(ind):
# OneMax: count the number of ones in the bit string
return int(ind.sum())
def genetic_algorithm(length=20, pop_size=40, generations=60,
p_cross=0.8, p_mut=0.02, seed=0):
rng = np.random.default_rng(seed)
pop = rng.integers(0, 2, size=(pop_size, length)) # encode: random bits
best_per_gen = [] # track convergence
for gen in range(generations):
scores = np.array([fitness(ind) for ind in pop])
best_per_gen.append(int(scores.max()))
# selection: tournament of size 3
def pick():
cand = rng.integers(0, pop_size, size=3)
return pop[cand[scores[cand].argmax()]]
# build the next generation
children = []
for _ in range(pop_size // 2):
p1, p2 = pick(), pick()
if rng.random() < p_cross: # crossover at one point
point = rng.integers(1, length)
c1 = np.concatenate([p1[:point], p2[point:]])
c2 = np.concatenate([p2[:point], p1[point:]])
else:
c1, c2 = p1.copy(), p2.copy()
for child in (c1, c2): # mutation: flip bits
flip = rng.random(length) < p_mut
child[flip] = 1 - child[flip]
children.extend([c1, c2])
pop = np.array(children) # replace the generation
scores = np.array([fitness(ind) for ind in pop])
best_idx = scores.argmax()
return pop[best_idx], int(scores.max()), best_per_gen
if __name__ == "__main__":
best, score, history = genetic_algorithm()
print("Best fitness per generation:", history)
print("Best solution:", best)
print("Best fitness:", score, "out of", len(best))
Khi chạy, bạn sẽ thấy fitness tốt nhất tăng dần qua các thế hệ và tiến về giá trị tối đa bằng độ dài chuỗi. Quần thể khởi đầu trung bình có khoảng một nửa số bit 1, rồi nhờ chọn lọc giữ lại cá thể nhiều bit 1, lai ghép gộp các đoạn tốt, đột biến thêm thắt biến dị, cả quần thể dần phủ kín bit 1.
Đây là mô hình duy nhất trong chương thuộc nhóm tối ưu tiến hoá, không phải học có giám sát hay không giám sát. Điểm chung với K-means là cùng lặp tới khi hội tụ, nhưng GA hội tụ bằng ngẫu nhiên và quần thể chứ không bằng một bước xác định. Điểm chung sâu hơn với hạ gradient là cùng đi tìm cực trị của một hàm mục tiêu, chỉ khác GA không cần đạo hàm mà dùng chọn lọc tự nhiên làm động lực.
Bài tập thực hành
Bài 1. Đổi hàm fitness để GA tìm một chuỗi bit khớp đúng một mẫu cho trước, ví dụ mẫu target là một chuỗi length bit cố định. Fitness của một cá thể là số vị trí mà nó trùng với target. Chạy lại và kiểm tra GA có hội tụ về đúng target hay không.
Gợi ý
Tạo target = rng.integers(0, 2, size=length) một lần ở ngoài, rồi viết fitness(ind) trả về int((ind == target).sum()). Lời giải tối ưu giờ là chính target với fitness bằng length. Cấu trúc còn lại của GA giữ nguyên, đây chính là sức mạnh của việc tách riêng hàm fitness.
Bài 2. In thêm fitness trung bình của cả quần thể ở mỗi thế hệ, bên cạnh fitness tốt nhất đã có. Vẽ hai đường này theo thế hệ và quan sát khoảng cách giữa chúng thu hẹp dần ra sao.
Gợi ý
Trong vòng lặp, sau khi tính scores, ghi lại cả scores.mean() vào một danh sách thứ hai. Khi quần thể đồng nhất dần về cuối, fitness trung bình tiến sát fitness tốt nhất, đó là dấu hiệu đa dạng di truyền đang cạn. Dùng matplotlib vẽ hai đường để thấy rõ.
Bài 3. Khảo sát ảnh hưởng của xác suất đột biến. Chạy GA với p_mut lần lượt bằng 0.0, 0.02, 0.2 và so sánh fitness cuối cùng cùng tốc độ hội tụ trong mỗi trường hợp.
Gợi ý
Với p_mut bằng 0.0, quần thể dễ kẹt sớm vì không còn nguồn biến dị mới, fitness cuối có thể không đạt tối đa. Với p_mut quá lớn như 0.2, đột biến phá vỡ những lời giải tốt nhanh hơn chọn lọc giữ lại, GA gần như tìm kiếm ngẫu nhiên. Giá trị nhỏ vừa phải như 0.02 thường cho kết quả tốt nhất.
Tự kiểm tra
Câu 1. Vì sao giải thuật di truyền dùng được cho cả những bài toán mà hạ gradient bó tay.
Đáp án
Hạ gradient cần hàm mục tiêu có đạo hàm và thường giả định nó trơn để đi ngược gradient mà xuống đáy. GA không dùng đạo hàm, nó chỉ cần đánh giá được fitness của một lời giải, nên áp được cả khi không gian rời rạc, hàm mục tiêu gồ ghề đầy hố hay không tính được đạo hàm. Bù lại GA dò bằng ngẫu nhiên và quần thể nên thường chậm và không bảo đảm tối ưu tuyệt đối.
Câu 2. Đột biến đóng vai trò gì, và điều gì xảy ra nếu xác suất đột biến quá nhỏ hoặc quá lớn.
Đáp án
Đột biến tạo biến dị mới, giữ đa dạng di truyền cho quần thể để nó không kẹt mãi trong một vùng nghiệm hẹp. Nếu xác suất đột biến quá nhỏ, quần thể nhanh chóng đồng nhất và có thể dừng ở một cực trị địa phương tồi. Nếu quá lớn, đột biến phá vỡ các lời giải tốt nhanh hơn chọn lọc kịp giữ lại, khiến GA mất tính tích luỹ và gần như thành tìm kiếm ngẫu nhiên.
Câu hỏi tự kiểm
- 1Ưu điểm chính khiến GA áp dụng được khi hạ gradient bó tay là gì?
- 2Giữ tinh hoa (elitism) trong GA có tác dụng gì?
- 3Đặt xác suất đột biến quá lớn gây hậu quả gì?
- 4Khi quần thể đã đồng nhất (hội tụ sớm), chỉ kéo dài thêm số thế hệ thường cho kết quả ra sao?
Giải thuật di truyền mô phỏng chọn lọc tự nhiên để tối ưu hoá mà không cần đạo hàm. Mỗi lời giải được mã hoá thành một nhiễm sắc thể, thường là chuỗi bit, và chấm điểm bằng hàm fitness. Vòng đời lặp bốn toán tử: chọn lọc ưu tiên cá thể fitness cao, lai ghép gộp mảnh tốt từ hai cha mẹ, đột biến giữ đa dạng, rồi thay thế thế hệ, cho tới khi đạt số thế hệ tối đa hoặc fitness đủ tốt. Bài toán OneMax tối đa hoá số bit 1 là ví dụ gọn cho thấy trọn vòng đời, và muốn đổi sang bài toán khác thường chỉ cần đổi hàm fitness.