Dlaczego więcej niż jeden chromosom na roztwór (lub genotyp)?

Question

Próbuję zacząć używać biblioteki Jenetics JAVA dla algorytmów genetycznych i jest coś, czego nie rozumiem z mojego ograniczonego tła GA;

Jak rozumiem, GA generuje populację tablic o elementach m, gdzie każda z tablic jest potencjalnym rozwiązaniem do oceny, po ocenie, potencjalne rozwiązania są sortowane, a najlepsze są wybierane w celu utworzenia nowej populacji itd. Ale uważam, że rozwiązaniem (Genotype) w Jenetics jest lista tablic, gdzie każda tablica jest tym, co rozumiem jako potencjalne rozwiązanie, również każda tablica może mieć różne długości i nie rozumiem, dlaczego użyć tej struktury zamiast wektora genów.

Patrz strona 6 z the manual, rozdział 3.1.3.

Jeśli to możliwe, chciałbym wiedzieć, dlaczego tak jest. Mam nadzieję, że postawiłem pytanie wystarczająco jasno.

Answer 1

To, co opisałeś, to populacja w podstawowym algorytmie genetycznym. Istnieje wiele technik, które mogą go ulepszyć, a jednym z nich jest kodowanie adaptacyjne.

Termin, którego szukasz, to (zmodyfikowana) rekombinacja puli genów w technikach kodowania adaptacyjnego.

Rekombinacja puli genów operuje na całej populacji, a nie pojedynczych jednostkach i ewoluuje populację. Może lub nie może zachować tej samej struktury.

patrzeć na ten pomysł z punktu widzenia biologii:

• W naturze, najpierw było prostsze organizmy, a potem przekształciła się w bardziej złożonych organizmów.

Tę samą motywację można zastosować z algorytmami genetycznymi. Na początku są prostsze jednostki, które mogą ewoluować z czasem - innymi słowy długość i struktura rozwiązań nie muszą być stałe.

Nie istnieje prosty sposób na powszechne kodowanie informacji o AH, więc należy wziąć pod uwagę każdy problem. Możesz lub nie potrzebujesz rekombinacji puli genów, podstawowego kodowania binarnego lub podstawowej selekcji proporcjonalnej. Opcje te są w dużej mierze zależne od problemu, który próbujesz rozwiązać, oraz od precyzji rozwiązania/czasu przyjętego przez algorytm, który jest akceptowalny.

Podstawowe kodowanie binarne, reprezentujące wektor genów, jest proste, ale GA ma wadę, gdy nie ma możliwości znalezienia najbliższych sąsiadów.

Rozważmy następujący przykład:

• istnieją rozwiązania, 15 i 16 (01111, 10000)

• odstęp Hamminga pomiędzy tymi dwoma numerami wynosi 5

dla ubrań zmienić od 15 do 16, wszystkie 5 bitów powinno zostać zmienione. Tak więc, GA ma problemy z dyskretnymi liczbami sąsiada. Jednym ze sposobów na poprawienie tego jest użycie Gray'a, który pozwala uzyskać 1 punkt pomiędzy wszystkimi rozwiązaniami.

Answer 2

"Szereg" potencjalnych rozwiązań (fenotypy/genotypy) jest gromadzony w populacji. Genotyp reprezentuje jedno możliwe rozwiązanie.Nie dajcie się zwieść dwuwymiarowej strukturze Genotypu, powinno to dać wam dodatkową elastyczność w modelowaniu bardziej skomplikowanych problemów. Geneotyp wciąż reprezentuje jedno możliwe rozwiązanie i jedną osobę z populacji.

genotypem dla klasycznego binarnym GA mogą być łatwo tworzone:

Genotype<BitGene> gt = Genotpe.of(BitChromosome.of(15)); 

mają również do obejrzenia modelu domeny, Rysunek 3.1 w manual. Sekcja 6.1 próbuje podać dodatkowe przykłady kodowania.

jenetics, genetic-algorithm