Algorytmy genetyczne: jak radzić sobie z krzyżowaniem w problemach "podzbiorów"?

Question

Mam problem, który próbuję rozwiązać za pomocą algorytmów genetycznych. Problem polega na wybraniu pewnego podzbioru (powiedzmy 4) 100 liczb całkowitych (te liczby całkowite są po prostu identyfikatorami reprezentującymi coś innego). Zamówienie nie ma znaczenia, rozwiązaniem problemu jest zbiór liczb całkowitych, a nie uporządkowana lista. Mam dobrą funkcję fitness, ale mam problem z funkcją crossover.

że chcą mieć możliwość mate następujących dwóch chromosomów:

[1 2 3 4] [3 4 5 6] do czegoś użytecznego. Najwyraźniej nie mogę użyć typowej funkcji crossover, ponieważ mogłem skończyć z duplikatami u moich dzieci, które reprezentowałyby nieprawidłowe rozwiązania. Jaka jest najlepsza metoda crossover w tym przypadku.

Answer 1

Wystarczy ignorować żadnego elementu, który występuje w zarówno zestawów (czyli w ich przecięciu.), To znaczy zostawić takie elementy niezmienione w obu zestawach.

Reszta elementów tworzy dwa zestawy rozłączne, do których można zastosować dowolną dowolną transformację losową (np. Zamieniając losowo wybrane pary) bez uzyskiwania duplikatów.

Można to traktować jako zamawianie i dopasowywanie obu zestawów tak, aby pasujące do siebie elementy stykały się ze sobą i stosowały jeden ze standardowych algorytmów crossover.

Answer 2

Czasami korzystne jest, aby Twoje rozwiązanie "wykroczyło poza granice", aby wyszukiwanie było szybsze. Zamiast tworzyć zestaw 4 unikatowych liczb całkowitych, wymagany dla twojego chromosomu, zrób liczbę liczb całkowitych (i ich unikalność) częścią funkcji fitness.

Answer 3

ja naprawdę nie wiem, co masz na myśli o „typowej zwrotnicy”, ale myślę, że można użyć rozjazd podobny do tego, co jest często używany do permutacji:

• biorą m ints od pierwszego Wyjściowy (m < n, gdzie n jest liczbą wskazówki w tabelach)
• skanowania drugiej i napełnić podzbiór to z (nm) int wolnych (nie w podgrupie już) .

ten sposób będziesz mieć n ints z pierwszego i n-M ints z drugim rodzicem, bez duplikacji.

Brzmi jak ważny crossover dla mnie :-).

Sądzę, że może być korzystne, aby nie wykonywać żadnych kroków na zamówionych zestawach (lub przy użyciu iteratora, w którym kolejność zwracanych elementów jest w jakiś sposób skorelowana z naturalną kolejnością elementów), w przeciwnym razie mniejsza lub większa liczba będzie miała większą szansę być w dziecku, co sprawia, że ​​twoje poszukiwania są stronnicze.

Jeśli jest to najlepsza metoda zależy od problemu, który chcesz rozwiązać ...

Answer 4

Aby połączyć zestawy A i B, można wybrać wynikowy zestaw S probabilistycznie, tak aby prawdopodobieństwo, że x jest w S (liczba zestawów z A, B, które zawierają x)/2. Będzie to mieć gwarancję, że będzie zawierał skrzyżowanie i będzie zawarty w związku, i będzie oczekiwał liczności 4.

Answer 5

Ponieważ kolejność nie ma znaczenia, po prostu zbierz wszystkie liczby do tablicy, posortuj tablicę, wyrzuć duplikaty (odłączając je od połączonej listy lub ustawiając je na liczbę ujemną lub cokolwiek innego). Potasuj tablicę i weź pierwsze 4 cyfry.