1. Overview
Trong hướng dẫn này, chúng ta sẽ nghiên cứu phương pháp lựa chọn bánh xe roulette cho các thuật toán di truyền.
2. Thuật toán di truyền
Việc chọn lọc các nhiễm sắc thể để tái tổ hợp là một bước bắt buộc trong thuật toán di truyền.
Các thuật toán di truyền tìm thấy các ứng dụng quan trọng trong học máy. Ví dụ, chúng ta sử dụng chúng trong việc lựa chọn các (policies) chính sách trong học tập củng cố. Nhưng cũng có thể, trong việc tối ưu hóa các tham số cho học sâu, trong bài toán tổng của tập hợp con, trong việc tìm đường, hay nói chung, trong giải pháp cho nhiều vấn đề tìm kiếm trong lý luận và học tập.
Các vấn đề trong thế giới thực mà chúng giúp giải quyết trải dài từ việc phát hiện ra các vật liệu mới cho đến việc xác định các dấu ấn sinh học trong sinh học máy tính. Mà còn, việc tầm soát bệnh và phát hiện thuốc trong y học. Do đó, chúng là những công cụ quan trọng trong hộp công cụ của bất kỳ nhà khoa học dữ liệu nào.
3. Recombination
Định nghĩa điển hình về nhiễm sắc thể coi nó như một mảng có độ dài cố định chứa biến nhị phân
Mỗi bit của biến sau đó ánh xạ tới một tham số hoặc đặc tính của một số kiểu. Theo cách này, chúng ta có thể mô tả một cá nhân sở hữu một tập hợp hữu hạn các đặc điểm nhị phân chỉ riêng về nhiễm sắc thể. Khi đó, nhiễm sắc thể cho phép biểu diễn một quần thể chứa bao nhiêu loại cá thể khác nhau
Trong giai đoạn này, chúng ta chọn một số cá nhân để đóng vai trò là cha mẹ. Đến lượt các cặp bố mẹ này lại trộn lẫn các nhiễm sắc thể của chúng theo một quy trình được gọi là trao đổi chéo hoặc tái tổ hợp.
4. Lựa chọn theo Fitness
Do đó, chúng ta cần một phương pháp để xác định các cặp bố mẹ có nhiễm sắc thể mà chúng ta chịu sự tái tổ hợp:
Phương pháp này cần sử dụng Fitness của các cá thể trong quần thể. Hay nói cách khác, không có sự học hỏi giữa thế hệ này và thế hệ tiếp theo.
Có hai loại phương pháp chính để sử dụng Fitness hỗ trợ việc lựa chọn:
- phương pháp xác định
- phương pháp ngẫu nhiên
Ví dụ, phương pháp xác định liên quan đến việc lựa chọn các cá thể phù hợp nhất trong một quần thể để tái tổ hợp. Nhìn chung, chúng bị mất uy tín vì chúng có xu hướng phát triển dân số đạt mức tối đa cục bộ và sau đó ngừng phát triển.
Ngoài ra, chúng ta cũng có thể sử dụng phương pháp ngẫu nhiên để chọn bố mẹ. Phương pháp khắc nghiệt nhất trong số các phương pháp này chọn các cá thể một cách ngẫu nhiên với xác suất đồng đều, và do đó hoàn toàn không quan tâm đến thể trạng cá nhân của họ.
Thay vào đó, một cách tốt ở giữa là lựa chọn bánh xe roulette, tạo ra một phân phối xác suất rời rạc mà từ đó chúng ta xác định các nhiễm sắc thể để trao đổi chéo.
5. Nguyên tắc lựa chọn Roulette
Lựa chọn Roulette là một phương pháp lựa chọn ngẫu nhiên, trong đó xác suất để lựa chọn một cá nhân tỷ lệ thuận với Fitness của nó. Phương pháp này được lấy cảm hứng từ những con tàu lượn trong thế giới thực nhưng có những điểm khác biệt quan trọng với chúng. Như chúng ta đã biết từ các bộ phim về sòng bạc và cờ bạc, các trò chơi roulettes luôn có các slot cùng kích thước:
Tuy nhiên, điều đó có nghĩa là tất cả các vị trí đều có xác suất được chọn như nhau. Thay vào đó, chúng ta có thể triển khai một phiên bản roulette có trọng số. Với nó, thể lực của một cá nhân càng lớn, thì khả năng lựa chọn của nó càng cao:
Do đó, thành phần đầu tiên của phương pháp lựa chọn roulette là Fitness của từng cá nhân tỷ lệ thuận với khả năng lựa chọn của nó.
Với xác xuất chọn lựa
[math]
p_{i} = \frac{f_{i}}{\sum_{n=1}^{n} f_{i}'}
[/math]
Với fi là kết quả của hàm mục tiêu fitness
Với n là số lượng cá thể trong quần thể
6. Lựa chọn bánh xe Roulette
Cuối cùng, chúng ta có thể tổng hợp các cân nhắc đã thực hiện ở trên và phát triển một phương pháp thỏa mãn các yêu cầu mà chúng ta đặt ra.
tham khảo thêm ở đây
