Thuật toán di truyền là một thuật toán tiến hóa phổ biến. Nó sử dụng lý thuyết tiến hóa tự nhiên của Darwin để giải quyết các vấn đề phức tạp trong khoa học máy tính. Tuy nhiên, để làm như vậy, các thông số của thuật toán cần phải điều chỉnh một chút.
Một trong những thông số quan trọng là đột biến. Nó tạo ra những thay đổi ngẫu nhiên trong nhiễm sắc thể (tức là các giải pháp) để tăng chất lượng cá thể (hàm thích nghi). Đột biến được áp dụng cho một số gen cố định. Theo truyền thống, cùng một số lượng gen bị đột biến trên tất cả các nhiễm sắc thể, bất kể mức độ thích nghi của chúng.
Trong hướng dẫn này, chúng ta sẽ xem tại sao đột biến với một số lượng gen cố định là không tốt và cách thay thế nó bằng đột biến thích ứng. Sử dụng thư viện PyGAD Python, chúng ta sẽ thảo luận một số ví dụ sử dụng cả đột biến ngẫu nhiên và đột biến thích ứng.
Tổng quan về thuật toán di truyền
Thuật toán di truyền là một thuật toán tiến hóa dựa trên quần thể, trong đó một nhóm các giải pháp làm việc cùng nhau để tìm ra các tham số tối ưu cho một bài toán. Hình dưới đây tóm tắt các bước trong thuật toán di truyền.
Quần thể các giải pháp được khởi tạo ngẫu nhiên, trong đó mỗi giải pháp bao gồm một số gen. Chất lượng của các giải pháp được đánh giá bằng cách sử dụng một hàm thích nghi, trả về một giá trị số thể hiện mức độ thích nghi của giải pháp.
Các cá thể (giải pháp) chất lượng cao (thích nghi cao) tồn tại lâu hơn các cá thể có độ thích nghi thấp. Cá thể thích nghi càng cao thì xác suất được chọn để trở thành bố mẹ sinh ra thế hệ con mới càng cao. Để tạo ra con cái, các cặp bố mẹ giao phối bằng cách sử dụng phép lai chéo, nơi một cá thể mới được tạo ra mang gen từ bố mẹ của nó.
Sau khi lai, đột biến được áp dụng để thêm một số thay đổi ngẫu nhiên trên cá thể. Sự phát triển tiếp tục qua một số thế hệ để đạt được giải pháp chất lượng cao nhất.
Mặc dù các bước giống nhau được áp dụng cho tất cả các dạng bài toán, bạn vẫn cần chọn các thông số thích hợp để phù hợp với các bài toán khác nhau. Một số thông số này bao gồm:
- Số lượng các cá thể trong quần thể,
- Cách lựa chọn bố mẹ,
- Kiểu toán tử lai,
- Loại toán tử đột biến,
- Xác suất lai,
- Xác suất đột biến,
- Hàm thích nghi.
Ví dụ: có nhiều cách lựa chọn bố mẹ khác nhau, như xếp hạng và bánh xe roulette, và bạn nên biết loại nào nên sử dụng khi thiết kế thuật toán cho một vấn đề cụ thể.
Thông số chúng ta sẽ tập trung vào là xác suất đột biến. Vì vậy, ta hãy xem lại các thao tác đột biến và xem thử xác suất đột biến cao hay thấp sẽ tốt hơn.
Cách thức hoạt động của đột biến
Cho hai cặp bố mẹ, thao tác đầu tiên trong quá trình sinh ra thế hệ mới là phép lai. Cá thể con được tạo ra bằng cách lấy một số gen từ bố mẹ của nó. Không có gì mới ở đứa trẻ, vì tất cả các gen của nó đều đã tồn tại ở cha mẹ nó. Hình tiếp theo cho thấy cách thức hoạt động của phép lai.
Nếu có một số gen xấu bên trong bố mẹ, chúng chắc chắn sẽ được chuyển sang con cái của chúng sau khi lai. Phép đột biến đóng một vai trò quan trọng trong việc khắc phục vấn đề này.
Trong quá trình đột biến, một số gen được chọn ngẫu nhiên từ mỗi cá thể và áp dụng một số thay đổi ngẫu nhiên. Các gen được chọn dựa trên xác suất ngẫu nhiên cho mỗi gen. Nếu xác suất đột biến gen nhỏ hơn hoặc bằng ngưỡng xác định trước thì gen này sẽ được chọn để gây đột biến. Nếu không, nó sẽ bị bỏ qua. Chúng ta sẽ thảo luận về xác suất đột biến ở phần sau.
Giả sử có 4 gen trong giải pháp, như trong hình tiếp theo, trong đó chỉ gen cuối cùng được chọn để đột biến. Một thay đổi ngẫu nhiên được áp dụng để thay đổi giá trị cũ của nó là 2 và giá trị mới là 4.
Sau khi xem xét ngắn gọn cách hoạt động của đột biến ngẫu nhiên, tiếp theo, chúng ta sẽ giải quyết một vấn đề bằng cách sử dụng thuật toán di truyền với đột biến ngẫu nhiên.
Ví dụ về đột biến ngẫu nhiên
Trong hướng dẫn này, ta sẽ sử dụng thư viện Python 3 nguồn mở có tên là PyGAD, cung cấp một giao diện đơn giản để giải quyết các vấn đề bằng cách sử dụng thuật toán di truyền. Để biết thêm thông tin, vui lòng xem tài liệu đi kèm. Mã nguồn có sẵn tại github.com/ahmedfgad.
Cài đặt PyGAD thông qua pip như sau:.
pip install pygadSau khi cài đặt, hãy sử dụng nó để tối ưu hóa một phương trình tuyến tính đơn giản với 4 đầu vào và 1 đầu ra.
Y = w1X1 + w2X2 + w3X3 + w4X4Chúng ta muốn có các giá trị của w1 đến w4 để làm cho phương trình sau đây được thỏa:
Y = w1(4) + w2(-2) + w3(3.5) + w4(5)Đây là mã Python để giải quyết vấn đề này:
import pygad
import numpy
function_inputs = [4,-2,3.5,5]
desired_output = 44
def fitness_func(solution, solution_idx):
output = numpy.sum(solution*function_inputs)
fitness = 1.0 / (numpy.abs(output - desired_output) + 0.000001)
return fitness
ga_instance = pygad.GA(num_generations=100,
sol_per_pop=5,
num_genes=4,
num_parents_mating=2,
fitness_func=fitness_func,
mutation_type="random")
ga_instance.run()
ga_instance.plot_result()
Có 3 bước như sau:
- Xây dựng fitness là một hàm Python thông thường (hàm tối đa hóa).
- Tạo một thực thể của lớp pygad.GA.
- Gọi phương thức run().
Hàm fitness được đặt tên là fitness_func() và nó phải có 2 tham số. Hàm này sẽ trả về một số thể hiện độ thích nghi của giải pháp. Giá trị này càng cao, giải pháp càng tốt.
Trong thực thể lớp pygad.GA, các đối số sau được sử dụng:
- num_generations = 100: Số thế hệ.
- sol_per_pop = 5: Quy mô quần thể.
- num_genes = 4: Số lượng gen.
- num_arent_mating = 2: Số lượng cặp bố mẹ giao phối.
- fitness_func = fitness_func: Hàm thích nghi.
- mutation_type=”random”: Loại đột biến, được đặt mặc định là ngẫu nhiên.
Để chạy thuật toán di truyền, chỉ cần gọi phương thức run(). Sau khi hoàn tất, phương thức plot_result() có thể được gọi để hiển thị một biểu đồ tóm tắt các giá trị thích nghi của các giải pháp tốt nhất qua tất cả các thế hệ.
Sau khi hoàn tất 100 thế hệ, một số thông tin về giải pháp tốt nhất được tìm thấy bởi thuật toán di truyền có thể được trả về bằng cách sử dụng best_solution().
Giải pháp tốt nhất có giá trị thích nghi là 761.4506452116121 và đây là các giá trị của w1 đến w4:
w1 = 2.26799886
w2 = -0.86295921
w3 = 4.85859239
w4 = 3.2391401
Tiếp theo, hãy thảo luận về tầm quan trọng của xác suất đột biến.
Xác suất đột biến không đổi
Phép đột biến là điều cần thiết trong thuật toán di truyền. Nó làm thay đổi các giá trị của một số gen để tăng chất lượng của những cá thể mới. Để quyết định một gen có bị đột biến hay không, người ta sử dụng xác suất đột biến.
Trong thuật toán di truyền truyền thống, chỉ có một giá trị hằng số duy nhất cho xác suất đột biến. Vì vậy, không phụ thuộc vào độ thích nghi của giải pháp, số lượng gen bị đột biến như nhau.
Do xác suất không đổi, một giá trị hợp lý cho xác suất đột biến phải được sử dụng cho mỗi bài toán. Nếu xác suất cao thì nhiều gen sẽ bị đột biến. Nếu có quá nhiều gen bị đột biến trong một cá thể fitness cao, thì những thay đổi ngẫu nhiên có thể làm cho giải pháp này trở nên tệ hơn. Đối với một cá thể fitness thấp, việc đột biến một số lượng cao các gen có lợi để tăng chất lượng của nó, vì có thể thay đổi nhiều gen xấu.
Mặt khác, một xác suất đột biến nhỏ khiến chỉ một vài gen bị đột biến. Đối với một cá thể fitness cao, chỉ thay đổi ngẫu nhiên một số gen của nó sẽ giữ được chất lượng cao. Đối với một cá thể fitness thấp, một số lượng nhỏ các gen của nó bị thay đổi, vì vậy chất lượng có thể vẫn thấp.
Như vậy:
- Một xác suất đột biến nhỏ là tốt cho các cá thể fitness cao, nhưng không tốt cho các cá thể fitness thấp.
- Xác suất đột biến cao là tốt cho các cá thể fitness thấp, nhưng không tốt cho các cá thể fitness cao.
Ví dụ về xác suất đột biến không đổi trong Python
PyGAD đưa ra một đối số có tên là mut_probability trong hàm khởi tạo của lớp pygad.GA để cung cấp một xác suất đột biến không đổi, được sử dụng trên tất cả các giải pháp bất kể độ thích nghi của chúng. Xác suất không đổi là 0,6, có nghĩa là nếu xác suất ngẫu nhiên của gen là <= 0,6, nó sẽ bị đột biến.
import pygad
import numpy
function_inputs = [4,-2,3.5,5]
desired_output = 44
def fitness_func(solution, solution_idx):
output = numpy.sum(solution*function_inputs)
fitness = 1.0 / (numpy.abs(output - desired_output) + 0.000001)
return fitness
ga_instance = pygad.GA(num_generations=100,
sol_per_pop=5,
num_genes=4,
num_parents_mating=2,
fitness_func=fitness_func,
mutation_type="random",
mutation_probability=0.6)
ga_instance.run()
ga_instance.plot_result()
Nếu xác suất đột biến là một giá trị rất nhỏ, chẳng hạn như 0,001, thì các giải pháp sẽ được cải thiện rất ít. Sau 100 thế hệ, giá trị fitness của cá thể tốt nhất là 0,077, so với 328,35 khi xác suất là 0,6 trong ví dụ trước.
Đột biến thích ứng
Đột biến thích ứng ban đầu được đề xuất trong một bài báo có tiêu đề Đột biến thích ứng trong thuật toán di truyền. Bài báo đã tóm tắt những vấn đề của việc sử dụng xác suất đột biến không đổi:
“Điểm yếu của GAs “cổ điển” là tính ngẫu nhiên tổng thể của đột biến, được áp dụng như nhau cho tất cả các nhiễm sắc thể, bất kể mức độ thích nghi của chúng. Do đó, một nhiễm sắc thể rất tốt cũng có khả năng bị phá vỡ do đột biến như một nhiễm sắc thể xấu.
Mặt khác, nhiễm sắc thể xấu ít có khả năng tạo ra nhiễm sắc thể tốt thông qua phép lai cho đến khi chúng đột biến.”.
Bài báo đề xuất cách tốt nhất để làm việc với xác suất đột biến không đổi là chọn một xác suất thấp. Hãy nhớ rằng, xác suất đột biến thấp trên tất cả các cá thể là tốt cho các cá thể fitness cao, nhưng không tốt cho các cá thể fitness thấp.
“Thông thường, một thỏa hiệp hợp lý trong trường hợp đột biến liên tục là giữ cho xác suất thấp để tránh phá vỡ các nhiễm sắc thể tốt, nhưng điều này sẽ ngăn tỷ lệ đột biến cao của các nhiễm sắc thể có thể trạng thấp. Do đó, một xác suất đột biến có thể không đạt được cả hai mục tiêu và dẫn đến sự cải thiện quần thể chậm chạp.”
Bài báo đề xuất việc sử dụng đột biến thích ứng để giải quyết các vấn đề về đột biến. Đây là cách hoạt động của đột biến thích ứng:
- Tính giá trị fitness trung bình của quần thể (f_avg);
- Đối với mỗi nhiễm sắc thể, hãy tính giá trị fitness của nó (f);
- Nếu f <f_avg, thì cá thể này được xem là chất lượng thấp và do đó tỷ lệ đột biến phải được giữ ở mức cao vì điều này sẽ làm tăng chất lượng của cá thể;
- Nếu f> f_avg, thì cá thể này được xem là giải pháp chất lượng cao và do đó tỷ lệ đột biến phải được giữ ở mức thấp để tránh làm gián đoạn giải pháp chất lượng cao này.
Ví dụ về đột biến thích ứng trong Python
Để sử dụng đột biến thích ứng trong PyGAD, đây là những gì bạn cần thay đổi:
- Đặt đối số mut_type thành “adaptive”: mut_type = ”adaptive”;
- Gán list / tuple / numpy.ndarray với chính xác 2 giá trị cho đối số mut_probability. Đây là một ví dụ: mut_probability = [0.57, 0.32]. Giá trị đầu tiên 0,57 là xác suất đột biến đối với các cá thể fitness thấp. Giá trị thứ hai 0,32 là tỷ lệ đột biến đối với các cá thể fitness thấp.
Đoạn mã tiếp theo sử dụng đột biến thích nghi để giải quyết vấn đề tuyến tính.
import pygad
import numpy
function_inputs = [4,-2,3.5,5]
desired_output = 44
def fitness_func(solution, solution_idx):
output = numpy.sum(solution*function_inputs)
fitness = 1.0 / (numpy.abs(output - desired_output) + 0.000001)
return fitness
ga_instance = pygad.GA(num_generations=100,
sol_per_pop=5,
num_genes=4,
num_parents_mating=2,
fitness_func=fitness_func,
mutation_type="adaptive",
mutation_probability=[0.6, 0.2])
ga_instance.run()
ga_instance.plot_result()
Thực thi đoạn code, giá trị fitness được tìm thấy sau 100 thế hệ là 974 và 4 tham số w1 đến w4 như sau:
w1=2.73998896
w2=-2.7606857
23=-1.67836889,
w4=6.67838764
Hình tiếp theo cho thấy độ thích nghi của giải pháp tốt nhất thay đổi như thế nào theo từng thế hệ.
Kết luận
Chúng ta đã thảo luận về thuật toán di truyền và đột biến thích ứng, thuật toán này chọn xác suất đột biến dựa trên độ thích nghi của cá thể.
Chúng tôi bắt đầu với tổng quan về thuật toán di truyền và tập trung vào hoạt động đột biến. Bạn đã thấy những hạn chế của việc sử dụng xác suất đột biến không đổi và cách giải quyết chúng bằng đột biến thích ứng.
