Algorytmy
i
struktury danych
WYKA
AD 8
Dr inż. Krzysztof Pancerz
Krzysztof Pancerz
Algorytmy i struktury danych
Algorytmy genetyczne  podstawowe pojęcia
Populacja  zbiór osobników o określonej liczebności.
Osobniki  zakodowane w postaci chromosomów zbiory parametrów zadania,
czyli rozwiązania (punkty przestrzeni poszukiwań).
Chromosom (inaczej: łańcuch, ciąg kodowy)  uporządkowany ciąg genów.
Genotyp (inaczej: struktura)  zespół chromosomów danego osobnika.
Gen (inaczej: cecha)  pojedynczy element genotypu (lub chromosomu).
Fenotyp  zestaw wartości odpowiadających danemu genotypowi, czyli
zdekodowana struktura.
Allel  wartość danego genu.
Funkcja przystosowania (inaczej: funkcja dopasowania, funkcja oceny)  miara
przystosowania danego osobnika w populacji.
Krzysztof Pancerz
Algorytmy i struktury danych
Algorytmy genetyczne
W klasycznych algorytmach genetycznych chromosomy są ciągami
binarnymi (tj. wartościami genów mogą być tylko 0 albo 1).
chromosom reprezentujący osobnika
0001111010
0101111011
populacja
0111111010
1101001010
gen
Krzysztof Pancerz
Algorytmy i struktury danych
Działanie
algorytmu
genetycznego
y
ródło: L. Rutkowski
 Metody i techniki
sztucznej inteligencji .
PWN, Warszawa,
2005.
Krzysztof Pancerz
Algorytmy i struktury danych
Operatory genetyczne
Krzyżowanie
Rodzic 1: Potomek 1:
01110001 01101110
Rodzic 2: Potomek 2:
11001110 11010001
Punkt krzyżowania
Krzysztof Pancerz
Algorytmy i struktury danych
Operatory genetyczne
Mutacja
01110001 01100001
Mutacja punktowa
Krzysztof Pancerz
Algorytmy i struktury danych
Właściwości algorytmów genetycznych

Algorytmy genetyczne nie przetwarzają bezpośrednio parametrów
zadania, lecz ich zakodowaną postać.

Algorytmy genetyczne prowadzą poszukiwania, wychodząc nie z
pojedynczego punktu, lecz z pewnej ich populacji.

Algorytmy genetyczne korzystają tylko z funkcji celu, nie zaś z jej
pochodnych lub innych pomocniczych informacji.

Algorytmy genetyczne stosują probabilistyczne, a nie
deterministyczne reguły wyboru.
Krzysztof Pancerz
Algorytmy i struktury danych