Konstruowanie populacji genotypów w postaci ciągów binarnych

Program ewolucyjny oparty na klasycznym algorytmie genetycznym operuje na zbiorze, którego liczba elementów jest stała, a każdy z elementów jest dopuszczalnym rozwiązaniem zadania. Zgodnie z terminologią zapożyczoną z genetyki naturalnej elementy zbioru możliwych rozwiązań nazywane są najczęściej osobnikami, genotypami lub chromosomami, natomiast ich zbiór nazywany jest populacją.

Pierwszym krokiem, przed rozpoczęciem głównego procesu symulacji ewolucji genotypów, jest ustalenie sposobu reprezentacji rozwiązania zadania takiego, aby przy jego pomocy można było przedstawić każdą permutację należących do dziedziny wartości zmiennych decyzyjnych. W klasycznej wersji algorytmu genetycznego używa się chromosomu w postaci wektora binarnego. Taki właśnie sposób kodowania użyty zostanie w omawianym dalej przykładzie optymalizacji funkcji jednej zmiennej.

Długość ciągu binarnego reprezentującego rzeczywistą zmienną decyzyjną zależy od długości dziedziny funkcji i żądanej dokładności obliczeń. Przy założeniu, że wymagana jest dokładność do 6 cyfr po przecinku oraz że dziedzina zmienności x ma długość 3 i zawiera się w przedziale [ – 1, 2] , przedział ten musi zostać podzielony na 3 • 1.000.000 równych podprzedziałów. Oznacza to, że genotyp musi mieć 22 bity, gdyż

2.097.152 = 2²¹ < 3.000.000 ≤ 2²² = 4.194.304

Odwzorowanie łańcucha binarnego < b21 b20 … b0 > w liczbę rzeczywistą x z przyjętego zakresu [ – 1, 2 ] można wykonać w dwóch krokach: przekształcenie łańcucha binarnego < b21 b20 … b0 > z systemu dwójkowego na dziesiętny:

( 1.1. )

obliczenie odpowiedniej liczby rzeczywistej x: x = -1,0 + 3x’ / (2²²-1), gdzie -1 jest lewą granicą dziedziny, a 3 jest długością przedziału.

Przy takim sposobie kodowania genotypy (0000000000000000000000) i (1111111111111111111111) reprezentują odpowiednio granice dziedziny, – 1,0 i 2,0.

W tym rozdziale omówiony zostanie prosty przykład optymalizacji funkcji f(x) = x² przy pomocy odręcznej symulacji klasycznego algorytmu genetycznego. W przykładzie tym, zmienna decyzyjna x może przybierać tylko wartości całkowite z przedziału [ 0 , 31 ] , a zatem do reprezentacji całej dziedziny wystarczy kod pięciobitowy, którego minimalną wartością jest 0 (00000) natomiast maksymalną 31 (11111). Odwzorowanie takiego łańcucha < b4 b3 … b0 > w liczbę całkowitą, wymaga tylko jednego kroku – bezpośredniej zamiany liczby binarnej na dziesiętną.

Po wyborze sposobu reprezentacji genotypu przychodzi czas na losowy wybór populacji początkowej, czyli z reguły od 50 do 100 ciągów binarnych tej samej długości. W omawianym przykładzie populacja składa się z czterech osobników, pierwsze pokolenie można zatem utworzyć przy pomocy 20 rzutów rzetelną monetą.

Tabela 1.1. Populacja początkowa wygenerowana losowo

Konstruowanie funkcji celu i funkcji przystosowania genotypów Podstawowym elementem każdego programu ewolucyjnego jest reprodukcja, czyli proces, w którym indywidualne ciągi kodowe zostają powielone w stosunku zależnym od wartości, jakie przybiera dla nich funkcja celu. Funkcja celu jest zatem kluczowym elementem programu, treścią zadania do rozwiązania, środowiskiem w jakim żyją osobniki. Najczęściej jest to funkcja wielu zmiennych, o nieznanej przeciwdziedzinie, bardzo trudna lub niemożliwa do rozwiązania metodą analizy matematycznej. Funkcja celu stanowi pewien miernik zysku, użyteczności lub innej wartości, którą należy zmaksymalizowć.

W klasycznym wydaniu algorytmu genetycznego prawdopodobieństwo wyboru osobnika do reprodukcji jest wprost proporcjonalne do jego użyteczności. Tymczasem wiele zadań wyraża się w bardziej naturalny sposób w kategoriach minimalizacji pewnej funkcji kosztu niż maksymalizacji pewnej funkcji użyteczności lub zysku. Nawet, jeśli zadanie w naturalny sposób dotyczy maksymalizacji, nie gwarantuje to, że funkcja użyteczności będzie przyjmowała wartości wyłącznie nieujemne. Wskutek tego często zachodzi potrzeba przekształcenia oryginalnej funkcji celu w funkcję przystosowania (nieujemne kryterium jakości), czego można dokonać w jednym lub kilku krokach.

W badaniach operacyjnych, przejście od zadania minimalizacji do zadania maksymalizacji, polega na pomnożeniu funkcji kosztu przez minus jeden. W przypadku algorytmu genetycznego taka operacja jest niewystarczająca, gdyż otrzymany miernik nie musi być zawsze nieujemny. Stosuje się zamiast tego powszechnie następujące przekształcenie kosztu g(x) w przystosowanie f(x):

 ( 1.2. )

Współczynnik Cmax może być równy największej napotkanej do tej pory wartości funkcji g(x), albo największej wartości g(x) w populacji bieżącej lub w kilku ostatnich populacjach. Może też wahać się w zależności od wariancji populacji.

Kiedy w zadaniu występuje w naturalny sposób funkcja zysku lub użyteczności i nie wykonuje się przejścia z zadania minimalizacji do maksymalizacji, ujemne wartości funkcji celu nadal sprawiają trudności. Nadal konieczne jest przekształcenie funkcji celu u(x) w funkcję przystosowania f(x):

Współczynnik Cmin jest najczęściej wartością bezwzględną najmniejszej wartości u(x) w populacji bieżącej lub kilku ostatnich populacjach, może też być funkcją wariancji dostosowania populacji.

Omawiany przykład polega na maksymalizacji funkcji f(x) = x2 , gdzie x ∈ [0, 31]. Tak sformułowana funkcja celu nie wymaga przekształcenia aby zostać funkcją przystosowania. Przyjmuje wyłącznie wartości nieujemne, zatem w niezmienionej formie umożliwia zastosowanie reprodukcji różnicującej szansę wyboru osobników proporcjonalnie do ich przystosowania. Wybrane wcześniej losowo genotypy mogą już zostać ocenione, a co za tym idzie może zostać oszacowana szansa każdego z nich na przetrwanie i reprodukcję:

Tabela 1.2. Ocena pierwszego pokolenia