GIỚI THIỆU GENETIC ALGORITHMS

Mục lục

6. Một vài ứng dụng thú vị của Genetic Algorithms

Trong bài viết hôm nay chúng ta sẽ tìm hiểu về Genetic Algorithms, đây là một thuật toán tìm kiếm lấy cảm hứng từ quá trình chọn lọc tự nhiên trong hoang dã. Ta sẽ xây dựng một thuật toán dựa trên tư tưởng này để giải quyết bài toán mở đầu.

Sau khi hoàn thiện thuật toán trênPythonvà xem qua kết quả đạt được, bài viết sẽ giới thiệu những ứng dụng mà từ đó bạn có thể xậy dựng một dự án của riêng mình sử dụng Genetic Algorithms.

1. Bài toán mở đầu

Trên hệ thống có một chuỗi S có độ dài L ký tự có thể là các ký tự latin in hoa (A-Z), in thường (a-z), các chữ số và các ký tự đặc biệt.

Nhiệm vụ của người chơi là đoán ra chuỗi S được lưu trên hệ thống. Biết rằng với mỗi chuỗi T người chơi dự đoán, hệ thống sẽ trả về một giá trị P thể hiện số lượng kí tự đã ở đúng vị trí.

Một vài hàm kiểm tra trên hệ thống được cài đặt bằng Python như sau:

secret_string_S = "Big-O Coding {le@rn a1g0ri7ths vv1th 3xp3rt5}"

secret_string_length = len(secret_string_S)

def count_correct_characters(user_string):

assert len(user_string) == secret_string_length

count = 0

for i in range(len(user_string)):

if user_string[i] == secret_string_S[i]:

count += 1

return count

def check_answer(user_string):

assert len(user_string) == secret_string_length

correct_count = count_correct_characters(user_string)

if correct_count == secret_string_length:

return True

return False

Để tìm được chuỗi S ta có thể thử qua tất cả các chuỗi khả thi đến khi nào tìm được chuỗi S thì dừng lại. Với thuật toán này thì thời gian chạy thuật toán sẽ tăng theo hàm mũ khi độ dài chuỗi S tăng lên và vì đây chỉ là một cách tìm kiếm ngẫu nhiên nên ta sẽ không biết được những dự đoán cho chuỗi S có được cải thiện theo thời gian hay không?

Ở phần sau chúng ta sẽ tìm hiểu về một thuật toán tìm kiếm, thuật toán này sử dụng kết quả của những lần tìm kiếm trước để cải thiện kết quả tìm kiếm hiện tại, qua đó ta biết kết quả của việc tìm kiếm thay đổi như thế nào và phán đoán được thuật toán có đi đúng hướng hay không.

2. Tổng quan

Genetic Algorithm là một thuật toán tìm kiếm tự suy lấy cảm hứng từ quá trình chọn lọc tự nhiên trong học thuyết tiến hóa của Darwin. Quá trình chọn lọc tự nhiên là quá trình lựa chọn những cá thể khỏe mạnh nhất trong một quần thể, các cá thể sản sinh ra cá thể con thừa hưởng những đặc điểm từ bố mẹ và được thêm vào các thế hệ sau. Nếu những cá thể bố mẹ có các đặc điểm tốt thì cá thể con sẽ có cơ hội sống sót cao hơn trong môi trường. Quá trình này lặp lại liên tục, đến cuối cùng những cá thể khỏe mạnh nhất sẽ được tìm thấy.

Mỗi thế hệ có một quần thể bao gồm nhiều các thể con, các cá thể này thể hiện cho một lựa chọn khả thi trong không gian đáp án. Trong bài toán mở đầu thì chuỗi T người chơi dự đoán sẽ tương ứng với một cá thể.

3. Xây dựng thuật toán

Ở phần này ta sẽ từng bước hoàn thiện thuật toán để giải quyết bài toán mở đầu dựa trên tư tưởng của Genetic Algorithm.

Không gian đáp án

Bài toán cần tìm một chuỗi có độ dài L do đó không gian đáp án sẽ là tập hợp những chuối có độ dài L, không gian này có 94^L phần tử. Với mỗi chuỗi có độ dài L người chơi dự đoán sẽ là một phần tử trong không gian đáp án này.

Ví dụ: Với L = 3, một vài chuỗi trong không gian đáp án: aBc, D∗E, F1+,…

Chỉ số khỏe mạnh

Chỉ số khỏe mạnh của một cá thể thể hiện khả năng cạnh tranh của cá thể đó, hay mức độ phù hợp của dự đoán so với kết quả bài toán.

Với mỗi thế hệ, thuật toán sẽ duy trì n cá thể kèm với chỉ số khỏe mạnh của chúng. Những cá thể có chỉ số khỏe mạnh cao sẽ được cho cơ hội sản sinh cao hơn, các cá thể này sẽ kết hợp với nhau để cho ra các cá thể con mới. Với số lượng cá thể của mỗi thế hệ không đổi là n, chúng ta mong đợi rằng những cá thể có chỉ số khỏe mạnh thấp, ít phù hợp với đáp án, sẽ được loại bỏ và các các cá thể có chỉ số khỏe mạnh cao, phù hợp với đáp án, sẽ được duy trì và cải thiện theo thời gian.

Bằng cách này, trên trung bình sau mỗi thế hệ chỉ số khỏe mạnh của các cá thể sẽ được tăng lên, hay thuật toán đang dần tìm được đáp án phù hợp với yêu cầu của bài toán. Thuật toán sẽ kết thúc nếu như ta tìm được chuỗi S của hệ thống.

Ở bài toán mở đầu, sau mỗi lần người chơi dự đoán một chuỗi T, hệ thống sẽ cho biết giá trị P tương ứng với số lượng ký tự đã ở đúng vị trí. Ta sử dụng giá trị P này như chỉ số khỏe mạnh của dự đoán hiện tại.

Ví dụ: chuỗi S=hello, thì các chuỗi T:

hella có chỉ số khỏe mạnh là 4 vì 4 ký tự đầu đã ở đúng vị trí.
hxxyo có chỉ số khỏe mạnh là 2 vì ký tự đầu và cuối đã ở đúng vị trí.
xxyyz có chỉ số khỏe mạnh là 0 vì không có ký tự nào ở đúng vị trí.

Giai đoạn chọn lọc

Ta bắt đầu với một thế hệ gồm các cá thể và chỉ số khỏe mạnh tương ứng của chúng. Ý tưởng của giai đoạn này là chúng ta muốn tiếp tục duy trì những cá thể có chỉ khỏe mạnh cao để mang sang thế hệ tiếp theo.

Một cách lựa chọn có thể là chọn 10% những cá thể có chỉ số khỏe mạnh cao để mang sang thế hệ tiếp theo. Giá trị 10% này hoàn toàn phụ thuộc vào người thiết kế thuật toán.

Giai đoạn kết hợp

Ý tưởng của giai đoạn này là ta muốn sản sinh ra những cá thể con con mang các đặc điểm tốt của bố mẹ, từ đó đạt được chỉ số khỏe mạnh cao.

Ta sẽ chọn ngẫu nhiên hai cá thể trong nhóm 50% những cá thể có chỉ số khỏe mạnh cao, để cho chúng kết hợp với nhau để tạo ra cá thể con. Giá trị 50% này cũng hoàn toàn phụ thuộc vào người thiết kế thuật toán muốn điều chỉnh như thế nào.

Có nhiều cách kết hợp hai cá thể lại với nhau, ở đây ta sẽ kết hợp chúng lại như sau: “Duyệt qua từng ký tự trong hai chuỗi, lựa chọn ngẫu nhiên một trong hai ký tự này để cho vào chuỗi con”

Ví dụ: Ta có hai chuỗiT_1vàT_2có cùng độ dài làL, thao tác trên được thể hiện bằng đoạn mã giả sau:

string result

for i=0 to L-1:

choice <- choose a random integer between 0 and 1

if choice == 1:

result += T_1[i]

else:

result += T_2[i]

Chuỗiresultlà kết quả của quá trình kết hợp chuỗi T_1và T_2.

Giai đoạn đột biến

Ý tưởng của giai đoạn này là ta muốn mang một vài yếu tố ngẫu nhiên vào thuật toán. Các yếu tố ngẫu nhiên có thể có lợi hoặc có hại nhưng nhờ và các yếu tố này mà các cá thể con trở nên đa dạng hơn.

Có nhiều cách để tạo ra sự đột biến này, ở đây ta sẽ thực hiện bằng cách: “Duyệt qua từng ký tự của chuỗiresultở giai đoạn kết hợp, với xác suất 5% ta sẽ thay đổi ký tự này thành một ký tự ngẫu nhiên trong các ký tự đề bài cho phép”. Giá trị 5% này thể hiện cho tỷ lệ đột biến và hoàn toàn phụ thuộc vào lựa chọn của người thiết kế thuật toán.

Thao tác trên được thể hiện bằng đoạn mã giả sau:

for i=0 to L-1:
choice <- choose a random real number between 0 and 1
if choice <= 0.05:
result[i] <- choose a random character

Tiểu kết

Toàn bộ thuật toán được tóm tắt trong đoạn mã giả sau:

1) Tạo một quần thể gồm N cá thể ngẫu nhiên
2) Lặp lại cho đến khi tìm được chuỗi S, với mỗi thế hệ:
- Lựa chọn 10% các cá thể có chỉ số khỏe mạnh cao nhất để mang sang thể hệ tiếp theo
- Lặp lại cho đến khi thế hệ tiếp theo có đủ N cá thể:
+ Lựa chọn ngẫu nhiên hai cá thể trong 50% những cá thể có chỉ số khỏe mạnh cao nhất.
+ Kết hợp hai cá thể vừa được chọn
+ Thực hiện quá trình đột biến trên cá thể con

4. Hoàn thiện thuật toán

Ở phần này ta sẽ cài đặt thuật toán để giải quyết bài toán mở đầu bằng Python

import random

characters_set = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP"\

"QRSTUVWXYZ 1234567890, .-;:_!\"#%&/()=?@${[]}" # Các ký tự hợp lệ

population = 100 # Số lượng cá thể trong một thế hệ

carried_over_rate = 0.1 # Tỉ lệ cá thể có chỉ số khỏe mạnh được cao được mang trực tiếp sang thế hệ sau

parent_portion = 0.5 # Tỉ lệ cá thể được lựa chọn để kết hợp với nhau

mutation_rate = 0.05 # Tỉ lệ đột biến

def initialize_generation():

first_generation = []

for i in range(population):

string = ""

for j in range(secret_string_length):

# Thêm một ký tự ngẫu nhiên trong

# characters_set vào chuỗi hiện tại

string += random.sample(characters_set, 1)[0]

# Tìm chỉ số khỏe mạnh của chuỗi

fitness_score = count_correct_characters(string)

# Thêm cá thể vào trong thế hệ hiện tại

first_generation.append((string, fitness_score))

return first_generation

def perform_selection(first_str, second_str):

assert len(first_str) == second_str

L = len(first_str)

result = ""

# Kết hợp hai chuỗi với nhau

for i in range(L):

choice = random.randint(0, 1)

result += first_str[i] if choice else second_str[i]

# Thực hiện đột biến

for i in range(L):

choice = random.random()

if random < mutation_rate:

result = result[:i] + random.sample(characters_set, 1)[0] + result[i+1:]

# Tìm chỉ số khỏe mạnh của chuỗi

fitness_score = count_correct_characters(result)

return (result, fitness_score)

def solve():

generation_id = 0

next_generation = initialize_generation()

current_generation = []

while True:

generation_id += 1

current_generation = next_generation

next_generation = []

# Sắp xếp các cá thể theo chỉ số khỏe mạnh giảm dần

current_generation.sort(key=lambda tup: -tup[1])

# In cá thể tốt nhất của từng thế hệ

best = current_generation[0]

print(f"Generation {generation_id}")

print(f"Best string: {best[0]}")

print(f"Fitness score: {best[1]}")

if best[1] == secret_string_length:

break

# Chọn 10% cá thể có chỉ số khỏe mạnh cao nhất

# để mang sang thể hệ sau

carried_over_idx = population * carried_over_rate

next_generation += current_generation[:carried_over_idx]

# Chọn 50% cá thể có chỉ số khỏe mạnh cao nhất

# để kết hợp với nhau

parent_idx = population * parent_portion

parent_group = current_generation[:parent_idx]

while len(next_generation) < population:

# Chọn ngẫu nhiên hai cá thể

first, second = random.sample(parent_group, 2)

new_child = perform_selection(first[0], second[0])

next_generation.append(new_child)

5. Kết quả

Các bạn có thể xem qua chương trình được chạy trên ideone tại đây https://ideone.com/hKsi93

Kết quả thu được:

...
--------------------------
Generation 404
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 405
Best string: Big-O Coding {le@rn a1g0ri ths vv1th 3xp3rt5}
Fitness score: 44
--------------------------
Generation 406
Best string: Big-O Coding {le@rn a1g0ri7ths vv1th 3xp3rt5}
Fitness score: 45
--------------------------

Thuật toán đã tìm được chuỗi S Sau khoảng 406×100=40600 lần thử. Đây là kết quả tốt hơn rất nhiều so với việc tìm kiếm một cách ngẫu nhiên có thể tốn đến 95⁴⁵ $ $ lần thử (chuỗi cần tìm có độ dài 45 ký tự)

6. Một vài ứng dụng thú vị của Genetic Algorithms

Bằng cách xây dựng một thuật toán dựa trên tư tưởng của Genetic Algorithms chúng ta đã giải quyết được bài toán mở đầu. Bài này này đơn giản và minh họa được ý tưởng cơ bản của nhóm thuật toán này.

Ở phần này mình muốn giới thiệu đến bạn đọc những ứng dụng thú vị đã được thực hiện bằng ý tưởng của Genetic Algorithms, các bạn thể từ đó phát triển nên một dự án của riêng mình nhé:

7. Kết luận

Genetic Algorithms là một nhóm thuật toán tìm kiếm dựa trên ý tưởng của việc chọn lọc tự nhiên ở ngoài hoang dã. Qua từng thế hệ ta thấy được thuật toán dần cài thiện kết quả thông qua việc chỉ số khỏe mạnh của các cá thể tăng cao lên, ở một mức độ nào đó ta cảm giác thuật toán đang thông minh lên.

Dù vậy đây cũng chỉ là một thuật toán tìm kiếm và vẫn có nhiều hạn chế như trong quá trình thiết kế thuật toán ta phải lựa chọn một cách không có căn cứ các tham số có trong thuật toán như tỉ lệ đột biến, tỉ lệ cá thể bố mẹ,… Do đó người ta sẽ kết hợp song song theo đó là những thuật toán Machine Learning, Deep Learning được kiểm chứng bằng toán học để đạt được kêt quả tối ưu hơn.

Thuật ngữ sử dụng

Tiếng Việt	Tiếng Anh
Cá thể	Individual
Chỉ số khỏe mạnh	Fitness score
Đột biến	Mutation
Không gian đáp án	Search space
Quần thể	Population
Thế hệ	Generation

Thuật Toán

GIỚI THIỆU GENETIC ALGORITHMS

1. Bài toán mở đầu

2. Tổng quan

3. Xây dựng thuật toán

Không gian đáp án

Chỉ số khỏe mạnh

Giai đoạn chọn lọc

Giai đoạn kết hợp

Giai đoạn đột biến

Tiểu kết

4. Hoàn thiện thuật toán

5. Kết quả

6. Một vài ứng dụng thú vị của Genetic Algorithms

7. Kết luận

Thuật ngữ sử dụng

Nguồn tham khảo