Algorytmy genetyczne - Crossover
W tym rozdziale omówimy, czym jest Crossover Operator wraz z innymi jego modułami, ich zastosowaniami i zaletami.
Wprowadzenie do Crossover
Operator krzyżowania jest analogiczny do reprodukcji i biologicznego krzyżowania. W tym przypadku wybiera się więcej niż jednego rodzica i jedno lub więcej potomków jest produkowanych przy użyciu materiału genetycznego rodziców. Crossover jest zwykle stosowany w GA z dużym prawdopodobieństwem -pc .
Operatory zwrotnicy
W tej sekcji omówimy niektóre z najpopularniejszych operatorów crossoverów. Należy zauważyć, że te operatory krzyżowania są bardzo ogólne i Projektant GA może również zdecydować się na zaimplementowanie operatora skrzyżowania specyficznego dla problemu.
One Point Crossover
W tym jednopunktowym skrzyżowaniu wybierany jest losowy punkt krzyżowania, a ogony jego dwóch rodziców są zamieniane, aby uzyskać nowe potomstwo.
Crossover wielopunktowy
Wielopunktowa zwrotnica jest uogólnieniem jednopunktowej zwrotnicy, w której naprzemienne segmenty są zamieniane w celu uzyskania nowych sprężyn.
Jednolity crossover
W jednolitej krzyżówce nie dzielimy chromosomu na segmenty, a raczej traktujemy każdy gen oddzielnie. W tym przypadku zasadniczo rzucamy monetą dla każdego chromosomu, aby zdecydować, czy zostanie on włączony wiosną, czy nie. Możemy również skierować monetę do jednego z rodziców, aby mieć więcej materiału genetycznego w dziecku od tego rodzica.
Pełna rekombinacja arytmetyczna
Jest to często używane do reprezentacji liczb całkowitych i działa na podstawie średniej ważonej dwóch rodziców przy użyciu następujących wzorów:
- Dziecko1 = α.x + (1-α). Y
- Dziecko2 = α.x + (1-α). Y
Oczywiście, jeśli α = 0,5, to oba dzieci będą identyczne, jak pokazano na poniższym obrazku.
Zamówienie Crossover Davisa (OX1)
OX1 jest używany do crossoverów opartych na permutacji z zamiarem przekazywania informacji o względnym zamówieniu do odrostów. Działa w następujący sposób -
Utwórz dwa losowe punkty krzyżowania w rodzicu i skopiuj segment między nimi od pierwszego rodzica do pierwszego potomstwa.
Teraz, zaczynając od drugiego punktu przecięcia w drugim rodzicu, skopiuj pozostałe nieużywane liczby z drugiego rodzica do pierwszego dziecka, zawijając listę.
Powtórz dla drugiego dziecka z odwróconą rolą rodzica.
Istnieje wiele innych zwrotnic, takich jak częściowo mapowany crossover (PMX), zwrotnica oparta na zamówieniu (OX2), Shuffle Crossover, Ring Crossover itp.