Tối ưu hóa

Định nghĩa thuật toán di truyền

Khi thảo luận về cách cBot có thể được tối ưu hóa, chúng tôi đã đề cập rằng cBot có thể được tinh chỉnh bằng phương pháp thuật toán di truyền. Trong hướng dẫn này, chúng tôi giải thích chính xác nó là gì và cách nó hoạt động.

Phương pháp thuật toán di truyền dựa trên lý thuyết chọn lọc tự nhiên. Lý thuyết này nêu rằng chỉ những cá thể phù hợp nhất mới sống sót để sinh sản tiếp theo.

Trong việc tối ưu hóa cBot, mỗi lần tối ưu hóa được coi là một cá thể. Để đánh giá các lần chạy riêng lẻ, thuật toán di truyền tính toán một điểm số phù hợp nhất định cho mỗi lần chạy và so sánh điểm số này với tất cả các lần chạy khác.

Để hoạt động, thuật toán di truyền cần một quần thể ban đầu. Để tạo ra nó, trình tối ưu hóa sẽ chạy một số lần chạy khác nhau với các tham số ngẫu nhiên. Sau khi tạo quần thể ban đầu, thuật toán sẽ bắt đầu quá trình tìm kiếm lần chạy tối ưu hóa phù hợp nhất. Quá trình này tiếp tục cho đến khi điểm số phù hợp của các lần chạy con bắt đầu trì trệ và hội tụ. Tại thời điểm này, thuật toán sẽ dừng lại.

Các giai đoạn của thuật toán di truyền

Bất kỳ thuật toán di truyền nào cũng có các giai đoạn sau.

graph TB
  B([Chọn lọc]) ==> C([Lai ghép]);
  C ==> D([Đột biến]);
  D ==> B;

Các giai đoạn được giải thích như sau.

Chọn lọc

Trong giai đoạn này, thuật toán tìm ra hai lần chạy tối ưu hóa phù hợp nhất bằng cách sử dụng điểm số phù hợp tương ứng của chúng.

Lai ghép

Sau khi tìm ra hai lần chạy tối ưu hóa phù hợp nhất, thuật toán sử dụng chúng để tạo ra các lần chạy con (hoặc con cháu) mới bằng cách sử dụng các kết hợp giá trị tham số của cả hai lần chạy cha mẹ.

Đột biến

Ở giai đoạn này, thuật toán đột biến các lần chạy con bằng cách sửa đổi ngẫu nhiên một hoặc nhiều giá trị tham số.

Sau giai đoạn đột biến, trình tối ưu hóa sẽ chạy một lần chạy tối ưu hóa con mới. Sau đó, nó sẽ lặp lại tất cả các giai đoạn nhưng chỉ khi điểm số phù hợp của một lần chạy con cao hơn lần chạy tối ưu hóa phù hợp nhất trước đó. Kết quả như vậy sẽ có nghĩa là vẫn còn chỗ để cải thiện, cho thấy rằng việc tối ưu hóa nên tiếp tục.

Nếu không, thuật toán sẽ tăng bộ đếm trì trệ của nó. Nếu bộ đếm trì trệ đạt đến giá trị của tham số thời gian trì trệ của thuật toán, quá trình tối ưu hóa sẽ tự động dừng lại.

Các tham số của thuật toán di truyền

Thuật toán di truyền có một số tham số mà nó sử dụng trong suốt thời gian tồn tại của nó. Các tham số này không thể thay đổi.