Thuật toán di truyền: Làm cách nào để thực hiện sự giao nhau trong các vấn đề "tập hợp con"?

Question

Tôi có một vấn đề mà tôi đang cố gắng giải quyết bằng thuật toán di truyền. Vấn đề là chọn một số tập hợp con (nói 4) của 100 số nguyên (các số nguyên này chỉ là các id đại diện cho cái gì khác). Thứ tự không quan trọng, giải pháp cho vấn đề là SET các số nguyên không phải là một danh sách có thứ tự. Tôi có một chức năng thể dục tốt nhưng đang gặp rắc rối với chức năng chéo.

Tôi muốn để có thể giao phối hai nhiễm sắc thể sau đây:

[1 2 3 4] và [3 4 5 6] vào một cái gì đó hữu ích. Rõ ràng tôi không thể sử dụng chức năng chéo điển hình bởi vì tôi có thể kết thúc với các bản sao trong các con của tôi mà sẽ đại diện cho các giải pháp không hợp lệ. Phương pháp crossover tốt nhất trong trường hợp này là gì.

Answer 1

Chỉ cần bỏ qua bất kỳ yếu tố xảy ra trong cả của bộ (tức là ở ngã tư của họ.), Có nghĩa là rời khỏi đó các phần tử không thay đổi trong cả hai bộ.

Phần còn lại của các thành phần tạo thành hai tập hợp rời nhau, mà bạn có thể áp dụng khá nhiều phép chuyển đổi ngẫu nhiên (ví dụ: hoán đổi một số ngẫu nhiên) mà không bị trùng lặp.

Điều này có thể được coi là sắp xếp và căn chỉnh cả hai tập hợp sao cho các phần tử khớp nhau đối mặt với nhau và áp dụng một trong các thuật toán chéo chuẩn.

Answer 2

Đôi khi có lợi cho giải pháp của bạn "vượt quá giới hạn" để tìm kiếm của bạn sẽ hội tụ nhanh hơn. Thay vì thực hiện một bộ 4 số nguyên duy nhất một yêu cầu cho nhiễm sắc thể của bạn, làm cho số lượng các số nguyên (và tính độc đáo của chúng) một phần của chức năng thể dục.

Answer 3

tôi không thực sự biết những gì bạn có ý nghĩa về "chéo điển hình", nhưng tôi nghĩ rằng bạn có thể sử dụng một chéo tương tự như những gì thường được sử dụng cho các hoán vị:

• mất m ints từ đầu tiên mẹ (m < n, trong đó n là số ints trong bộ của bạn)
• quét thứ hai và điền tập hợp con của bạn từ nó với (nm) ints được miễn phí (không nằm trong nhóm đã được) .

Bằng cách này bạn sẽ có n ints từ đầu tiên và n-m ints từ cha mẹ thứ hai, không trùng lặp.

Có vẻ như một sự giao nhau hợp lệ cho tôi :-). Tôi có thể có lợi khi không thực hiện một trong hai bước trên bộ đặt hàng (hoặc sử dụng một trình lặp mà thứ tự của các phần tử trả về tương ứng với thứ tự ints), nếu không thì số lượng nhỏ hơn hoặc cao hơn sẽ có cơ hội cao hơn để được trong con làm cho tìm kiếm của bạn thiên vị.

Nếu đó là phương pháp tốt nhất phụ thuộc vào vấn đề bạn muốn giải quyết ...

Answer 4

Để kết hợp bộ A và B, bạn có thể chọn tập hợp kết quả S xác suất để xác suất x trong S là (số bộ trong số A, B, chứa x)/2. Điều này sẽ được đảm bảo để chứa giao lộ và được chứa trong công đoàn, và sẽ có cardinality dự kiến ​​4.

Answer 5

Vì thứ tự không quan trọng, chỉ cần thu thập tất cả các số vào mảng, sắp xếp mảng, loại bỏ các bản sao (bằng cách ngắt kết nối chúng khỏi danh sách được liên kết hoặc đặt chúng thành số âm hoặc bất kỳ thứ gì). Trộn mảng và lấy 4 số đầu tiên.