Algorytmy ewolucyjne

Wprowadzenie

Algorytmy ewolucyjne - są to algorytmy, które opierają swoje działanie na genetyce (przekazywanie korzystnych cech potomstwu poprzez krzyżowanie i mutacje).

Są one wykorzystywane do rozwiązywania zagadnień optymalizacyjnych (czyli poszukiwania tych rozwiązań, które dziedziczą cechy po swoich rodzicach i „przeżywają”, ponieważ są najlepiej przystosowane).

Klasyczne metody optymalizacji

Klasyczne metody poszukiwania optymalnych rozwiązań dzielimy na : metody analityczne, przeglądowe, oraz losowe.

Metody analityczne - poszukiwane są lokalne ekstrema funkcji rozwiązując układy równań (zwykle

nieliniowych). Metody te mają swoje wady - są złożone i nie zawsze dadzą się zastosować.

Metody przeglądowe - polegają na obliczaniu wartości funkcji jakiegoś celu w całej przestrzeni po kolei.

Dla dużych przestrzeni jest to nieefektywne i niemożliwe.

Metody losowe - losowo przeszukują przestrzeń rozwiązań i zapamiętują wyniki, z których potem wybierane jest najlepsze. Metody te są również mało efektywne.

Idea algorytmów ewolucyjnych

Algorytmy te są oparte na zasadzie doboru naturalnego i dziedziczenia, gdzie wykorzystuje się ewolucyjną zasadę przeżycia osobników najlepiej przystosowanych.

Główne cechy algorytmów ewolucyjnych :

• wyjściem do przeszukiwania nie jest punkt przestrzeni poszukiwań, ale pewna populacja

• przetwarzane są nie parametry zadania, ale zakodowana postać tych parametrów

• losowy wybór jest tu jedynie jednym narzędzi poszukiwań

Podstawowe pojęcia (słowniczek) :

• Populacja - określony zbiór osobników

• Osobnik - zakodowany w postaci chromosomu zbiór parametrów zadania

• Chromosom - to uporządkowany ciągiem genów

• Gen - jest cechą, pojedynczym elementem genotypu

• Genotyp - zespół chromosomów danego osobnika (czasem pojedynczy chromosom)

• Fenotyp - to zakodowana struktura, czyli zbiór parametrów zadania

Funkcja przystosowania (także funkcja dostosowania, oceny) - pozwala ocenić stopień dopasowania osobnika populacji i wybrać wszystkie te najlepiej przystosowane (o największej wartości funkcji dopasowania) zgodnie z zasadą „przetrwa najsilniejszy”. (Odpowiednio w teorii sterowania - funkcja błędu a w teorii gier - funkcja kosztu).

W każdej iteracji algorytmu ewolucyjnego ocenia się przystosowanie osobnika za pomocą funkcji przystosowania i na tej podstawie tworzy się nową populację, jako zbiór potencjalnych rozwiązań.

Klasyczny algorytm genetyczny

Inicjacja - polega na losowym wyborze żądanej liczby chromosomów (osobników) reprezentowanych przez ciągi binarne o określonej długości.

Ocena przystosowania - polega na obliczeniu wartości funkcji przystosowania dla każdego chromosomu z populacji.

Sprawdzenie warunków zatrzymania - zależą one od zadania. Najczęściej jest to:

• osiągnięcie wartości optymalnej

• osiągnięcie wartości optymalnej z określoną dokładnością

• przekroczenie czasu działania (timeout)

• wykonanie obliczeń dla określonej liczby generacji.

Selekcja chromosomów - odbywa się na podstawie wartości funkcji przystosowania, tych chromosomów, które będą tworzyć następne pokolenia. Najbardziej popularna metoda to metoda ruletki.

W wyniku tego procesu zostaje utworzona populacja rodzicielska o liczebności podobnej do bieżącej populacji.

Operatory genetyczne

Zastosowanie operatorów genetycznych do chromosomów (w procesie selekcji) prowadzi do utworzenia

nowej populacji potomków. Stosuje się dwa podstawowe operatory genetyczne: operator krzyżowania i

operator mutacji.

W klasycznym algorytmie genetycznym krzyżowanie występuje prawie zawsze (prawdopodobieństwo <0,5-1> a mutacje bardzo rzadko (prawdopodobieństwo na poziomie 0,1).

Operację mutacji stosujemy na populacji rodziców przed operacją krzyżowania, oraz na populacji potomków, już po krzyżowaniu.

Przykładowe operacje krzyżowania i mutacji

Przykład krzyżówki:

Chromosomy ch₁ i ch₂ mają po 10 genów. Stanowią one parę rodzicielską. W celu przeprowadzenia krzyżowania losujemy liczbę z przedziału [1,9]. Wylosowano nr.5.

Przykład mutacji:

Losujemy liczbę rzeczywistą z przedziału [0,1] dla każdego z dziesięciu genów. Wylosowano :

0.23 0.76 0.54 0.10 0.28 0.68 0.01 0.30 0.95 0.12

Przyjmijmy, że prawdopodobieństwo p_m = 0,2. Do mutacji zostaną dopuszczone tylko te geny, gdzie

liczba jest p_m<= 0,1 - tylko gen nr. 7 (czerwony).

Przykład wykorzystania algorytmu genetycznego

Zadanie :

Znaleźć maksimum funkcji y = 2*x +1 w przedziale liczb całkowitych [0,31]. Zbiorem potencjalnych rozwiązań (czyli przestrzenią poszukiwań) jest zbiór {0,1,2,…,32}. Każdy z elementów zbioru jest fenotypem. Fenotypy zakodujemy jako chromosom 5-bitowy (bo wartości 32 odpowiada [11111]).

1. Losowanie populacji początkowej :

Ustalono początkową populacja na N=8

2. Ocena funkcji dostosowania :

wartości funkcji dostosowania obliczono

wg. wagi wzoru F(chi)=2* chi+1

3. Selekcja chromosomów :

Selekcji dokonano metodą koła ruletki.

(diagram poniżej).

Pola wycinków koła ruletki obliczono wg wzoru

Selekcja chromosomów - za pomocą koła ruletki odbywa się przez losowym zakręceniem koła ruletki

(tutaj ośmiu) liczb z przedziału [0,100]. Suma wszystkich wartości ( chi) jest równa 100%.

Wylosowano liczby : 79 44 9 74 45 86 48 23, które odpowiadają chromosomom :

ch6 ch4 ch2 ch6 ch5 ch6 ch5 ch3

Piąty wylosowany chromosom to ch5 ponieważ jako piątą wylosowano liczbę 45 , która jest większa od sumy granicznej 44,34.

---