Thuật toán di truyền - Crossover
Trong chương này, chúng ta sẽ thảo luận về Crossover Operator cùng với các mô-đun khác của nó, cách sử dụng và lợi ích của chúng.
Giới thiệu về Crossover
Toán tử giao nhau tương tự như tái tạo và giao nhau sinh học. Trong trường hợp này, nhiều hơn một cá thể bố mẹ được chọn và một hoặc nhiều con non được tạo ra bằng cách sử dụng vật liệu di truyền của bố mẹ. Kết hợp chéo thường được áp dụng trong GA với xác suất cao -pc .
Các nhà khai thác chéo
Trong phần này, chúng ta sẽ thảo luận về một số toán tử chéo được sử dụng phổ biến nhất. Cần lưu ý rằng các toán tử giao nhau này rất chung chung và Nhà thiết kế GA cũng có thể chọn triển khai toán tử giao nhau cụ thể cho từng vấn đề.
Giao nhau một điểm
Trong sự giao nhau một điểm này, một điểm giao nhau ngẫu nhiên được chọn và các đuôi của hai cha mẹ của nó được hoán đổi để có được các lò xo mới.
Chéo đa điểm
Sự giao nhau đa điểm là sự tổng quát của sự giao nhau một điểm trong đó các đoạn xen kẽ được hoán đổi để tạo ra các lò xo mới.
Đồng phục chéo
Trong một sự trao đổi chéo đồng đều, chúng ta không chia nhiễm sắc thể thành các đoạn, thay vào đó chúng ta xử lý từng gen riêng biệt. Trong điều này, về cơ bản, chúng tôi lật một đồng xu cho mỗi nhiễm sắc thể để quyết định xem nó có được đưa vào giai đoạn ngoài xuân hay không. Chúng ta cũng có thể thiên vị đồng xu cho một người cha hoặc mẹ để có nhiều vật chất di truyền hơn ở đứa trẻ từ người cha mẹ đó.
Tổng hợp lại toàn bộ số học
Điều này thường được sử dụng cho các biểu diễn số nguyên và hoạt động bằng cách lấy trung bình có trọng số của hai bậc cha mẹ bằng cách sử dụng các công thức sau:
- Con1 = α.x + (1-α) .y
- Con2 = α.x + (1-α) .y
Rõ ràng, nếu α = 0,5, thì cả hai con sẽ giống hệt nhau như trong hình sau.
Davis 'Order Crossover (OX1)
OX1 được sử dụng để hoán vị chéo dựa trên mục đích truyền thông tin về thứ tự tương đối đến các lò xo. Nó hoạt động như sau:
Tạo hai điểm giao nhau ngẫu nhiên ở bố mẹ và sao chép đoạn giữa chúng từ bố mẹ đầu tiên sang thế hệ con đầu tiên.
Bây giờ, bắt đầu từ điểm giao nhau thứ hai trong mã mẹ thứ hai, hãy sao chép các số chưa sử dụng còn lại từ mã mẹ thứ hai sang con đầu tiên, bao quanh danh sách.
Lặp lại cho trẻ thứ hai với vai trò của phụ huynh được đảo ngược.
Có rất nhiều crossover khác như Crossover được ánh xạ một phần (PMX), Order based crossover (OX2), Shuffle Crossover, Ring Crossover, v.v.