Thuật toán di truyền - Lựa chọn cha mẹ

Lựa chọn bố mẹ là quá trình lựa chọn các cặp bố mẹ giao phối và tái tổ hợp để tạo ra các con lai cho thế hệ tiếp theo. Lựa chọn của cha mẹ là rất quan trọng đối với tỷ lệ hội tụ của GA vì cha mẹ tốt hướng các cá nhân đến một giải pháp tốt hơn và phù hợp hơn.

Tuy nhiên, cần cẩn thận để ngăn chặn một giải pháp cực kỳ phù hợp tiếp quản toàn bộ dân số trong một vài thế hệ, vì điều này dẫn đến việc các giải pháp gần nhau trong không gian giải pháp, do đó làm mất tính đa dạng. Maintaining good diversitytrong quần thể là cực kỳ quan trọng cho sự thành công của GA. Điều này chiếm toàn bộ dân số bằng một giải pháp cực kỳ phù hợp được gọi làpremature convergence và là một điều kiện không mong muốn trong GA.

Lựa chọn cân đối về thể chất

Lựa chọn cân đối về thể chất là một trong những cách lựa chọn phổ biến nhất của phụ huynh. Trong điều này, mọi cá nhân đều có thể trở thành cha mẹ với một xác suất tỷ lệ thuận với sức khỏe của nó. Do đó, các cá thể fitter có cơ hội giao phối và truyền bá các tính năng của chúng cho thế hệ tiếp theo cao hơn. Do đó, một chiến lược chọn lọc như vậy áp dụng một áp lực chọn lọc đối với những cá thể phù hợp hơn trong quần thể, tiến hóa những cá thể tốt hơn theo thời gian.

Hãy xem xét một bánh xe tròn. Bánh xe được chia thànhn pies, với n là số lượng cá thể trong quần thể. Mỗi cá nhân nhận được một phần của vòng tròn tỷ lệ với giá trị thể chất của nó.

Có thể triển khai hai lựa chọn tương ứng về thể lực -

Lựa chọn bánh xe Roulette

Trong lựa chọn bánh xe roulette, bánh xe tròn được chia như mô tả trước đây. Người ta chọn một điểm cố định trên chu vi bánh xe như hình vẽ và cho bánh xe quay. Vùng của bánh xe phía trước điểm cố định được chọn làm vùng chính. Đối với cha mẹ thứ hai, quá trình tương tự được lặp lại.

Rõ ràng là một cá nhân lắp bánh xe có bánh lái lớn hơn và do đó cơ hội hạ cánh trước điểm cố định cao hơn khi bánh xe quay. Do đó, xác suất chọn một cá thể phụ thuộc trực tiếp vào thể lực của nó.

Triển khai khôn ngoan, chúng tôi sử dụng các bước sau:

Tính S = tổng của một tinh.
Tạo một số ngẫu nhiên giữa 0 và S.
Bắt đầu từ phần trên cùng của dân số, tiếp tục cộng các số tinh vào tổng một phần P, cho đến khi P <S.
Cá nhân mà P vượt quá S là cá nhân được chọn.

Lấy mẫu chung ngẫu nhiên (SUS)

Stochastic Universal Sampling khá giống với lựa chọn bánh xe Roulette, tuy nhiên thay vì chỉ có một điểm cố định, chúng ta có nhiều điểm cố định như trong hình sau. Vì vậy, tất cả các phụ huynh được chọn chỉ trong một vòng quay của bánh xe. Ngoài ra, cách thiết lập như vậy khuyến khích những cá nhân phù hợp cao được chọn ít nhất một lần.

Cần lưu ý rằng các phương pháp lựa chọn tương ứng với thể lực không hoạt động đối với những trường hợp thể dục có thể có giá trị âm.

Lựa chọn giải đấu

Trong lựa chọn giải đấu K-Way, chúng tôi chọn ngẫu nhiên K cá thể từ quần thể và chọn người tốt nhất trong số này để trở thành bố mẹ. Quy trình tương tự được lặp lại để chọn cha mẹ tiếp theo. Lựa chọn giải đấu cũng rất phổ biến trong văn học vì nó thậm chí có thể hoạt động với các giá trị thể dục tiêu cực.

Lựa chọn xếp hạng

Lựa chọn Xếp hạng cũng hoạt động với các giá trị thể lực âm và chủ yếu được sử dụng khi các cá thể trong quần thể có giá trị thể lực rất gần nhau (điều này thường xảy ra vào cuối cuộc chạy). Điều này dẫn đến việc mỗi cá nhân có một phần gần như bằng nhau của chiếc bánh (như trong trường hợp lựa chọn tương xứng về thể lực) như được hiển thị trong hình ảnh sau đây và do đó mỗi cá nhân bất kể phù hợp với nhau như thế nào đều có xác suất được chọn là cha mẹ. Điều này dẫn đến việc giảm áp lực lựa chọn đối với các cá thể phù hợp, khiến GA đưa ra lựa chọn bố mẹ kém trong những tình huống như vậy.

Trong điều này, chúng tôi loại bỏ khái niệm về giá trị thể chất khi chọn cấp độ gốc. Tuy nhiên, mọi cá nhân trong dân số đều được xếp hạng theo thể lực của họ. Việc lựa chọn của cha mẹ phụ thuộc vào cấp bậc của từng cá nhân chứ không phải thể lực. Những cá nhân được xếp hạng cao hơn được ưu tiên hơn những người được xếp hạng thấp hơn.

Nhiễm sắc thể	Giá trị thể chất	Cấp
A	8.1	1
B	8.0	4
C	8.05	2
D	7.95	6
E	8.02	3
F	7.99	5

Lựa chọn ngẫu nhiên

Trong chiến lược này, chúng tôi chọn ngẫu nhiên các cặp bố mẹ từ dân số hiện có. Không có áp lực lựa chọn đối với các cá nhân phù hợp và do đó chiến lược này thường được tránh.