Algorytmy genetyczne i procesy ewolucyjne
Wykład 4  kryteria zatrzymania algorytmu, operatory
krzyżowania i mutacji
Jacek Bieganowski
Instytut Informatyki i Elektroniki
Uniwersytet Zielonogórski
email: [e-mail]
http://www.uz.zgora.pl/~jbiegano/agipe09
23 marca 2009
Algorytmy genetyczne i procesy ewolucyjne  W4
Zatrzymanie algorytmu
Kryteria zatrzymania algorytmu można podzielić na dwie grupy:
kryteria polegające na monitorowaniu wartości funkcji
przystosowania, bazujące na spostrzeżeniu, że wraz z
kolejnymi generacjami maleje szansa na znalezienie lepszych
osobników od dotychczasowych,
kryteria polegające na monitorowaniu zdolności
eksploracyjnych algorytmu
różnorodności osobników pozwalającej na modyfikację w
wyniku krzyżowania,
zasięgu operatora mutacji gdy jest samoczynnie adoptowany.
Algorytmy genetyczne i procesy ewolucyjne  W4
Monitorowanie rozwiązań (1)
Kryterium maksymalnego kosztu jest najprostszym w
implementacji, polega ono no zatrzymaniu algorytmu gdy
zostanie przekroczony maksymalny koszt algorytmu.
Maksymalny koszt może wynikać ze specyfiki zadania 
wymagany jest określony czas na znalezienie odpowiedzi.
Maksymalny koszt zależy od parametrów zadania (np
liczebność populacji).
Kryterium zadowalającego poziomu funkcji
przystosowania jest spełnione, gdy algorytm znajdzie
rozwiązanie o wartości funkcji przystosowania przekraczającej
zadany przez użytkownika próg. Wadą tego kryterium jest
potrzeba znajomości funkcji przystosowania oraz możliwość
praktycznie nieskończenie długiego poszukiwania wartości
powyżej progu.
Algorytmy genetyczne i procesy ewolucyjne  W4
Monitorowanie rozwiązań (2)
Kryterium minimalnej szybkości poprawy bazuje na
obserwacji szybkości zmian wyniku osiąganego przez algorytm.
Algorytm jest zatrzymywany, jeśli w kolejnych � generacjach
nie uda się poprawić wyniku o więcej niż �, czyli spełniony jest
warunek
Ć Ć
|Ś(X(t - �)) - |Ś(X(t))| �.
Często przyjmuje się, że � = 0  czyli, że algorytm jest
zatrzymywany, jeśli nie uda się znalez
ć lepszego rozwiązania w
kolejnych � generacjach.
Algorytmy genetyczne i procesy ewolucyjne  W4
Monitorowanie populacji
Kryterium zaniku różnorodności populacji bazuje na
obserwacji różnorodności populacji, która maleje wraz z
kolejnymi generacjami. Obniżenie różnorodności poniżej
pewnego progu, świadczy o przejściu algorytmu do etapu
eksploatacji ekstremum. Na przykład różnorodność populacji
można określić badając odchylenia standardowe genotypów


1/(� - 1) (Xi - Xi(t))2.
X"Pt
Zanik samoczynnie adaptowanego operatora mutacji
opiera się na spostrzeżeniu, że jeśli w algorytmie stosuje się
adaptację zasięgu mutacji, to od pewnego momentu zasięg
ten ma trwałą tendencję do zmniejszania się. Wiąże się to z
faktem, że algorytm zaczyna eksploatację znalezionego
ekstremum. W tym kryterium przyjmuje się, że zmniejszenie
średniej wartości odchyleń standardowych poniżej zadanego
progu powoduje zakończenie poszukiwań.
Algorytmy genetyczne i procesy ewolucyjne  W4
Cechy operatorów genetycznych (1)
Operatory genetyczne określają sposób przekształcania genotypów.
W przypadku mutacji z jednego osobnika rodzicielskiego powstaje
jeden osobnik potomny. W krzyżowaniu udział bierze k osobników,
tworząc l potomków.
Spójność przestrzeni genotypów uzyskana dzięki
operatorom genetycznym. Należy zapewnić możliwość
wygenerowania (w kolejnych pokoleniach) dowolnego
chromosomu z dowolnego innego.
Brak obciążeń operatorów. Należy zadbać aby w przypadku
braku nacisku selektywnego wszystkie genotypy były osiągalne
z jednakowym prawdopodobieństwem.
Algorytmy genetyczne i procesy ewolucyjne  W4
Cechy operatorów genetycznych (2)
Spełnienie postulatu spójności zapewnia, że nawet w wyniku
niewłaściwej inicjacji populacji bazowej algorytm będzie w
stanie znalez
ć globalne ekstremum poprzez modyfikację
chromosomów za pomocą operatorów genetycznych.
Brak obciążeń operatora mutacji powoduje, że przy
równomiernie zainicjowanej populacji początkowej oraz
wyłączonym krzyżowaniu i selekcji algorytm powinien
odwiedzać z jednakowym prawdopodobieństwem każdy
chromosom.
Brak obciążeń krzyżowania zapewnia, że podczas operacji
wielokrotnego krzyżowania algorytm nie zostanie
 zablokowany na skutek słabego przystosowania pośrednich
chromosomów.
Algorytmy genetyczne i procesy ewolucyjne  W4
Warianty krzyżowania
Operatory krzyżowania wymieniającego.Chromosom
potomny powstaje w wyniku złożenia genów chromosomów
rodzicielskich. Do tej grupy można zaliczyć:
krzyżowanie jednopunktowe (op. obciążony),
krzyżowanie dwupunktowe (op. obciążony),
krzyżowanie równomierne (op. nieobciążony).
Krzyżowanie uśredniające. Jest specyficzne dla kodowania
za pomocą liczb rzeczywistych, powoduje modyfikację
wartości genów w chromosomach. Wartości genów w
chromosomach potomnych są zwarte między największą i
najmniejszą wartością chromosomów rodzicielskich.
Algorytmy genetyczne i procesy ewolucyjne  W4
Krzyżowanie uśredniające
W krzyżowaniu uśredniającym wartości genów chromosomów
potomnych oblicza się wg. następujących wzorów:
Y = X1 + �U(0,1)(X2 - X1)
Z = X2 + X1 - Y
Krzyżowanie uśredniające nie jest obciążone.
Chromosomy potomne są generowane na odcinku łączącym
chromosomy rodzicielskie.
Odległość między chromosomami potomnymi jest mniejsza niż
między rodzicielskimi.
Zastosowanie rozkładu równomiernego zapewnia jednakową
osiągalność każdego z osobników potomnych.
Algorytmy genetyczne i procesy ewolucyjne  W4
Krzyżowanie uśredniające  wariant alternatywny
Krzyżowanie przeprowadza się realizując zmienną losową dla
osobno dla każdego genu wg schematu:
Yi = Xi1 + �U(0,1),i(Xi2 - Xi1)
Z = X2 + X1 - Y
Operator jest nieobciążony.
Zbiór chromosomów potomnych jest wnętrzem
hiperpotopadłościanu, którego przeciwległymi wierzchołkami
są chromosomy rodzicielskie, a krawędzie są równoległe do osi
układu współrzędnych odpowiadających genom.
Ponowne krzyżowanie chromosomów potomnych generuje
zbiór osiągalności zawarty wewnątrz hiperprostopadłościanu
rodziców.
Zastosowanie rozkładu równomiernego zapewnia jednakową
osiągalność każdego z osobników potomnych.
Algorytmy genetyczne i procesy ewolucyjne  W4
Mutacja
Mutacja dla kodowania binarnego:
negacja bitu Yi = 1 - Yi,
namiana bitu na losowy Yi = �B(0,1),i ,
oba schematy mutacji są nieobciążone.
Mutacja dla liczb rzeczywistych polega na modyfikacji
poszczególnych genów chromosomu o wektor, będący
realizacja n-wymiarowej zmiennej losowej � o zadanym
rozkładzie Yi = Xi + �i. Najczęściej stosuje się z rozkłady:
normalny �N(0,1),
Cauchy ego �C(0,1).
rozkład prostokątny.
Algorytmy genetyczne i procesy ewolucyjne  W4
Zasięg operatorów
Można przyjąć, że zasięg operatora genetycznego jest związany ze
zbiorem chromosomów przez niego osiąganych.
O zasięgu mutacji decyduje rozkład zmiennej losowej. Z
małym zasięgiem mamy do czynienia, gdy
prawdopodobieństwo tego, że wynik mutacji chromosomu
znajdującego się w obszarze przyciągania maksimum
globalnego opuści ten obszar, jest niewielkie. Duży zasięg
oznacza łatwość opuszczania tego obszaru
W krzyżowaniu zasięg operatora zależy od więcej niż jednego
chromosomu rodzicielskiego. Mały zasięg oznacza, że zbiór
chromosomów potomnych zawiera się w obszarze
przyciągania. Aby zapewnić duży zasięg krzyżowania, należy
dobierać chromosomy ze zbiorów przyciągania różnych
maksimów lokalnych.
Algorytmy genetyczne i procesy ewolucyjne  W4