Crossover (algorytm genetyczny) - Crossover (genetic algorithm)

Część serii na
Algorytm ewolucyjny
Algorytm genetyczny
Programowanie genetyczne

W algorytmów genetycznych i ewolucyjnego obliczeń , rozjazd , zwany także rekombinacji , to operator genetycznej stosowane do łączenia informacji genetycznej dwóch rodziców do generowania nowego potomstwa. Jest to jeden ze sposobów stochastycznego generowania nowych rozwiązań z istniejącej populacji i jest analogiczny do krzyżowania, które zachodzi podczas rozmnażania płciowego w biologii . Rozwiązania można również generować przez klonowanie istniejącego rozwiązania, co jest analogiczne do rozmnażania bezpłciowego . Nowo wygenerowane roztwory są zazwyczaj mutowane przed dodaniem do populacji.

Różne algorytmy w obliczeniach ewolucyjnych mogą wykorzystywać różne struktury danych do przechowywania informacji genetycznej, a każda reprezentacja genetyczna może być rekombinowana z różnymi operatorami krzyżowania. Typowymi strukturami danych, które można rekombinować za pomocą krzyżowania, są tablice bitów , wektory liczb rzeczywistych lub drzewa .

Przykłady

Tradycyjne algorytmy genetyczne przechowują informacje genetyczne w chromosomie reprezentowanym przez tablicę bitów . Metody krzyżowania dla tablic bitowych są popularnym przykładem rekombinacji genetycznej .

Zwrotnica jednopunktowa

Punkt na chromosomach obojga rodziców jest wybierany losowo i oznaczony jako „punkt skrzyżowania”. Bity na prawo od tego punktu są zamieniane między dwoma rodzicielskimi chromosomami. Powoduje to powstanie dwojga potomstwa, z których każde niesie informacje genetyczne od obojga rodziców.

OnePointCrossover.svg

Zwrotnica dwupunktowa i k-punktowa

W dwupunktowym krzyżowaniu dwa punkty krzyżowania są wybierane losowo z chromosomów rodzicielskich. Bity pomiędzy dwoma punktami są zamieniane między organizmami rodzicielskimi.

TwoPointCrossover.svg

Zwrotnica dwupunktowa jest równoważna wykonaniu dwóch zwrotnic jednopunktowych z różnymi punktami zwrotnicy. Tę strategię można uogólnić na krzyżowanie k-punktowe dla dowolnej dodatniej liczby całkowitej k, wybierając k punktów krzyżowych.

Jednolita zwrotnica

W równomiernym przejściu zwykle każdy bit jest wybierany z jednego z rodziców z równym prawdopodobieństwem. Czasami stosuje się inne proporcje mieszania, w wyniku czego potomstwo dziedziczy więcej informacji genetycznej od jednego rodzica niż drugiego.

Crossover dla uporządkowanych list

W niektórych algorytmach genetycznych nie wszystkie możliwe chromosomy stanowią prawidłowe rozwiązania. W niektórych przypadkach możliwe jest użycie wyspecjalizowanych operatorów krzyżowania i mutacji, które mają na celu uniknięcie naruszenia ograniczeń problemu.

Na przykład algorytm genetyczny rozwiązujący problem komiwojażera może wykorzystać uporządkowaną listę miast do przedstawienia ścieżki rozwiązania. Taki chromosom stanowi poprawne rozwiązanie tylko wtedy, gdy lista zawiera wszystkie miasta, które sprzedawca musi odwiedzić. Korzystanie z powyższych krzyżowań często skutkuje chromosomami, które naruszają to ograniczenie. Algorytmy genetyczne optymalizujące kolejność danej listy wymagają więc różnych operatorów krzyżowania, co pozwoli uniknąć generowania nieprawidłowych rozwiązań. Opublikowano wiele takich crossoverów:

  1. częściowo zmapowany zwrotnica (PMX)
  2. zwrotnica rowerowa (CX)
  3. operator krzyżowania zamówień (OX1)
  4. operator krzyżowania na zlecenie (OX2)
  5. operator zwrotnicy oparty na pozycji (POS)
  6. operator zwrotnicy rekombinacji głosowania (VR)
  7. Operator zwrotnicy naprzemiennej (AP)
  8. sekwencyjny konstruktywny operator krzyżowania (SCX)
  9. symulowany binarny operator crossover (SBX)

Inne możliwe metody obejmują operator rekombinacji krawędzi . Alternatywnie, aby przezwyciężyć wspomniany problem, można zastosować podwójne chromosomy.

Zobacz też

Bibliografia

  • John Holland, Adaptacja w systemach naturalnych i sztucznych , University of Michigan Press , Ann Arbor, Michigan. 1975. ISBN  0-262-58111-6 .
  • Larry J. Eshelman, Algorytm wyszukiwania adaptacyjnego CHC: Jak zapewnić bezpieczne wyszukiwanie podczas angażowania się w nietradycyjną rekombinację genetyczną , w: redaktor Gregory JE Rawlins, Proceedings of the First Workshop on Foundations of Genetic Algorithms. strony 265-283. Morgan Kaufmann, 1991. ISBN  1-55860-170-8 .
  • Tomasz D. Gwiazda, Genetic Algorithms Reference Vol.1 Crossover for jednoobiektywnych problemów optymalizacji numerycznej , Tomasz Gwiazda, Łomianki, 2006. ISBN  83-923958-3-2 .

Linki zewnętrzne