Wykład 6.
Uwzględnianie specyfiki problemu

W wykładzie tym omówiono problemy, zjakimi borykają się praktycy, próbując rozwiązać zadania o strukturze bardziej skomplikowanej niż optymalizacja wektora zmiennych niezależnych. Aby uwzględnić specyfikę takich zadań, należy wy-korzystaćszczególne sposoby kodowania chromosomów i ich przekształcania za pomocą operatorówgenetycznych. Omówiono typowe dla algorytmów ewolucyjnych metody uwzględniania ograniczeń, rozwiązywania zadań wielokryte-rialnych oraz z funkcją przystosowania zmienną w czasie.

6.1. Wykorzystanie skomplikowanych struktur danych

Rozwiązywanie zadania wymaga niekiedy wykorzystania chromosomów mających postać struktur danych bardziej skomplikowanych niż wektor genów odpowiadających poszczególnym zmiennym niezależnym. Potrzeba użycia takich struktur bierze się najczęściej z istnienia dodatkowych więzów, wynikających z natury zadania, których wyrażenie w postaci funkcji jest trudne lub niemożliwe.
6.1.1. Zadania o ustalonej liczbie parametrów
Kodowanie łańcuchowe. W takim kodowaniu oprócz wartości genów ważna jest kolejność ich ustawienia w chromosomie. Przykładem jest napis, w którym liczą się zarówno litery, jak i ich
.244.
t'\
6. Uwzględnianie specyfiki problemu
kolejność. Przykładowo, napisy kto, kot i tok, będące pemiuta-cjami zbioru liter {k, o,t}, mają zupełnie inne znaczenia.
Wykorzystanie kodowania łańcuchowego nie powoduje żadnej komplikacji dla mechanizmów mutacji nadal może ono polegać na niezależnych modyfikacjach genów. W przypadku krzyżowania, zależność zbioru chromosomów osiągalnych od kolejności ustawienia genów w chromosomach rodzicielskich staje się zaletą. Dlatego też operatory krzyżowania wymieniającego, polegającego na rozcinaniu i sklejaniu (krzyżowanie jednopunktowe i wielopunktowe) są stosowane chętniej niż krzyżowania równomiernego lub uśredniającego.
PRZYKŁAD (poszukiwanie optymalnej strategii włączania przedmiotów do plecaka). Rozważmy problem plecakowy. Załóżmy trochę inny niż dotychczas sposób kodowania. Umieśćmy przedmioty na liście, uszeregowanej w kolejności nierosnących wartości proporcji współczynników pi/Wi. Chromosom jest wektorem n 1--elementowym liczb całkowitych Xi, z których każda spelnia ograniczenie , , . , . , ,
1 Fenotyp x � Z% jest tworzony w następujący sposób. Chromosom X jest analizowany element po elemencie, dla każdego i = 1, 2,..., n 1. Przechowywany jest również zbiór K(i) przedmiotów włożonych do plecaka po przeanalizowaniu pierwszych i l genów chromosomu. Wartość Xi oznacza numer elementu z listy przedmiotów pozostałych do rozpatrzenia; oznaczmy go przez k. Jeśli waga w^ tego przedmiotu nie przekracza dopuszczalnej wagi plecaka, pomniejszonej o sumę wag przedmiotów w nim się znajdujących, czyli gdy spełniony jest warunek
< w
to Xk jest włączany do plecaka
(6.2)
W przeciwnym przypadku, x^ jest pomijany . " K(i + l):=K(i}
W obu przypadkach, element x^ jest usuwany z listy przedmiotów do rozpatrzenia.
W celu ilustracji metody kodowania rozważmy sześcioelemen-towy plecak zdefiniowany następująco:
w = [l,4,5,8,4,2]
p=[3,4,3,ll,6,l] ''-"-- " " '-;;- y
W= 12 ' .
6.1. Wykorzystanie skomplikowanych struktur danych
.245.
TABELA 6.1. Sposób dekodowania genotypu X = [1, 1, 1, 1, lj; wynikiem jest fenotyp x = [1,1,0,0,1,1]
i Xi k Wk W ~ S wJi:EJ Zj6A'(i) tf(i + l) Lista przedmiotów do rozważenia
1 1 1 1 12 {*i} {X5,X4,X2,X3,X(i}
2 1 5 4 11 {0:1,0:5} {XA,X-2,X3,Xo}
3 1 4 8 7 {3:1,3:5} {X2,X3,Xe}
4 1 2 4 7 {3:1,3:5,3:2} {xa,xe}
5 1 3 5 3 {3:1,0:5,3:2} {xe}
6 2 3 {xi,xs,X2,xe}
Uszeregowanie początkowe elementów jest następujące:
{xi,X5,X4,X2,X3,X6}
Łatwo sprawdzić (tab. 6.1), że chromosomowi
X=[1,1,1,1,1]
odpowiada fenotyp
Waga tego plecaka wynosi 11, całkowita zaś wartośćfunkcji przystosowania jest równa lĄ-Rozważmy inny genotyp
X = [3,4,l,3,2] odpowiada mu fenotyp x=[l,0,0,l,0,l]
Plecak tenjest lepszy odpoprzedniego jego waga wynosi 11, lecz całkowita wartośćfunkcji przystosowaniajest równa 15*.
Opisany sposób kodowania umożliwia zastosowanie dowolnego operatora krzyżowania wymieniającego. Mutacja może polegać na modyfikacji każdego genu z prawdopodobieństwem pm. Wynikiem modyfikacji genu Xi może być wartość wylosowana z rozkładem równomiernym ze zbioru liczb calkowitych {1, 2, . . . ,n i}, czyli z zakresu wartości dopuszczalnych**.
Kodowanie cykliczne. W kodowaniu łańcuchowym, informacja o rozwiązaniu jest zawarta zarówno w wartościach poszczególnych genów, jak też w sekwencji ich występowania w łańcuchu. W niektórych zadaniach pojawia się problem izomorficzności jeden fenotyp jest reprezentowany przez wiele genotypów. Przykładem może być problem reprezentacji fenotypu o strukturze pierścienia (cyklu). Chcąc przedstawić n-elementowy pierścień w postaci liniowego wektora, mamy do wyboru 2n możliwych,
*Zaprezentowany sposób kodowania opisuje więc strategię wyboru kolejności włączania elementówdo plecaka wybór elementu zawsze pierwszego z uszeregowanej listy jest odpowiednikiem strategii zachłannej, co (jak można się przekonać) nie musi prowadzić do najlepszych rozwiązań.
**Zauważmy jednak, że w przyjętym sposobie kodowania geny nie odpowiadają zmiennym niezależnym modyfikacja wartości ż-tego genu pociąga za sobą zmianę kolejności włączania pozostałych n ~ i elementów.
� spp^-
^flfi 6.Uwzglednianiespecyfikiproblemu -,.i,-,.: i{
równoważnych (izomorficznych) realizacji, powstających w wyniku cyklicznego przesunięcia i inwersji kolejności ustawienia numerów węzłów w chromosomie.
PRZYKŁAD. W zadaniu komiwojażera rozwiązanie postaci
[1,2,3,4] , !
(z węzła 1 do węzła 2, z 2 do 3, z 3 do Ą, z powrotem do 1) ma jeszcze siedem równoważnych reprezentacji
[2,3,4,1] : : ;
[3,4,1,2]
[4,1,2,3]
[4,3,2,1]
[3,2,1,4]
[2,1,4,3] ' '�"�� ""� "--- \ �<� , ;
[1,4,3,2] �- , v, . ..
Wieloznaczność reprezentacji stanowi niemałą trudność w doborze operatora krzyżowania.
PRZYKŁAD. Problem komiwojażera jest zadaniem dość chętnie rozwiązywanym za pomocą algorytmów genetycznych, co zaowocowało mnogością operatorów krzyżowania odpowiednich dla niego; znanych jest również wiele różnych sposobów kodowania, niekoniecznie wykorzystujących reprezentację cykliczną. Poniżej omówiono dwa przykładowe operatory krzyżowania zaproponowane dla tego problemu.
Pierwszym jest operator PMX (partially matched crossover). Operator ten jest uogólnieniem krzyżowania dwupunktowego. Działa w następujący sposób. Wybierane są losowo dwa miejsca rozcięcia, ci,c%. Chromosomy potomne są tworzone zgodnie z zależnościami
'X} jeśli i < ci lub i > c% i X\ w przeciwnym przypadku
jeśli i < ci lub i > c% i X? w przeciwnym przypadku
X? X
{XCI,...,. �,...,-
(6.3) (6.4)
Przykładowo, wynikiem krzyżowania chromosomów
[1,3,6,7,4,2,5,8,9] , , ..
[4,6,5,8,1,2,3,7,9]
z miejscami rozcięcia c\ = 3, c% 6 są chromosomy
[4,3,5,8,1,2,6,7,9] '.
[1,5,6,7,4,2,3,8,9] ,. . ' ,,_.'/, '
(powstały one w wyniku następującego przyporządkowania węzłów: 6 ^ 5,7 ^ 8,4 ^ 1).
6.1. Wykorzystanie skomplikowanych struktur danych
.247.
Operator PMX nie uwzględnia izomorficzności cykli. Przykładowo, wynikiem krzyżowania dwóch różnych reprezentacji tego samego cyklu
[1,2,3,4,5,6,7,8,9]
[4,5,6,7,8,9,1,2,3]
z miejscami rozcięcia c\ = 3, c% = 5 są chromosomy
[1,2,3,7,8,9,4,5,6]
[7,8,9,4,5,6,1,2,3]
reprezentujące wprawdzie identyczne rozwiązania, lecz różniące się od chromosomów rodzicielskich.
Odmienne podejście jest prezentowane w operatorze z rekombinacją krawędzi. Ten operator przypomina nieco krzyżowanie równomierne. Tworzy się jeden chromosom potomny. W początkowej fazie, dla każdego węzla v określa się zbiory węzłów osiągalnych w cyklu reprezentowanym przez pierwszy i przez drugi chromosom potomny; oznaczmyje ^4(t>,X1) i j4(v,X2).
Gen Y\ wybiera się w dowolny sposób; może on mieć choćby wartość genu X\. Dla genu Yi sprawdza się, czy istnieje węzeł w spełniający warunek w G ^4(Yi_i,X1) nj4(YJ_i,X2). Jeśli tak, to gdy nie został on wcześniej odwiedzony, wówczas jego numer staje się wartością genu Yi. W pozostałych przypadkach wartością Yi staje się numer losowo wybranego, nie odwiedzonego jeszcze węzła ze zbioru A(Yi-i,X*}UA(Yi-i,X?).
Prześledźmy krzyżowanie chromosomów
[1,2,3,6,7,4,5,8,9] [4,6,7,8,1,2,3,5,9]
Zbiory węzłów osiągalnych są dane w tab. 6.2. Jednym z możliwych do wygenerowania chromosomów potomnych jest
[1,2,3,5,8,7,6,4,9]
TABELA 6.2. Zbiory węzłów osiągalnych w cyklach reprezentowanych przez chromosomy rodzicielskie
V A(v,X1) A(v,X2)
1 2.9 2.8
2 1.3 1.3
3 2.6 2.5
4 5.7 6.9
5 4.8 3.9
6 3.7 4.7
7 4.6 6.8
8 5.9 1.7
9 1.8 4.5
.248.
6. Uwzględnianie specyfiki problemu
Zauważmy, że operator ten nie jest wrażliwy na sposób zapisu cyklu. Ze względu na to, że wymieniane są tak naprawdę nie węzły, lecz krawędzie, to sposób zapisu cyklu (ani dobór początkowego węzła, z którego rozpoczyna się tworzenie cyklu) nie wpływa na zbiór osiągalnych chromosomów potomnych.
Mutacja, jako operator działający dła każdej wartości niezależnie, nie jest wrażliwa na nadmiarowość reprezentacji. Typowym operatorem jest mutacja przestawiająca*, zilustrowana w następnym przykładzie. Sprowadza się do zamiany m genów chromosomu. Wykonuje się ją w następujący sposób. Losowo wybiera się (bez zwracania) m-elementowy wektor numerów genów cx. Następnie losuje się wektor cn, będący permutacją wektora [1, 2, . . . , m]. Wektor cn określa sposób zamiany elementów wektora cx. Chromosom potomny tworzy się następująco:
X' =
jeśli i i cx gdzie l = cx, k =
cx = i
(6.5)
PRZYKŁAD. Rozważmy mutację chromosomu
X=[l,2,3,6,7,4,5,8,9]
Niech m 4. Załóżmy, że wylosowano następujące wektory:
[1,6,4,2]
cx =
cn = [3,l,4,2]
Łatwo sprawdzić (tab. 6.3), że wynikiem mutacji będzie chromosom . ,.; ;
X' = [4,6,3,l,7,2,5,8,9] ..,. ,, ,
TABELA 6.3. Wartości i,j,k,l przy mutacji przestawiającej chromosomu X = = [1,2,3,6,7,4,5,8,9] przy wektorach modyfikujących cx = [1,6,4,2], cn =
= [3,l,4,2]
i 3 k 1
1 1 3 4
2 4 2 6
4 3 4 2
6 2 1 1
Kodowanie macierzowe. Niektóre zadania mają wygodne kodowanie macierzowe. Za pomocą wierszy i kolumn macierzy można przedstawić parametry związane ze sobą w pewien sposób. Krzyżowanie wymieniające (np. schemat równomierny) może wte-*Schemat tej mutacji jest ^ dotyczyć nie pojedynczych komórek macierzy, lecz całych iei
wzorowany na algorytmie J J J ^ J J J ^' J J J
fc-opt. wierszy lub kolumn.
6.1. Wykorzystanie skomplikowanych struktur danych
PRZYKŁAD. Przykładem zastosowania kodowania macierzowego może być reprezentacja grafu skierowanego w postaci macierzy wag polączeń między węzłami. Graf taki może np. zawierać informacje o połączeniach w sieci telekomunikacyjnej. Wagi Wij krawędzi wchodzących do węzła j są zgrupowane w j-tej kolumnie macierzy, natomiast wagi krawędzi z niego wychodzących znajdują się w wierszu i.
Rozważmy równomierne krzyżowanie wymieniające, polegające na wymianie węzłów między grafami. Jeśli wraz z węzłem wymianie podlegają krawędzie do niego wchodzące, oznacza to wymianę odpowiednich kolumn macierzy; podobnie, jeśli operacja wymiany dotyczy krawędzi wychodzących z węzła, prowadzi to do zmian w odpowiednich wierszach tych macierzy.
.249.
(a) (b)
RYSUNEK 6.1. Grafy kodowane przez chromosomy X1 (a) oraz X2 (b)
W celu ilustracji powyższego opisu rozważmy dwa chromosomy (na rys. 6.1 przedstawiono odpowiadające im grafy)
X1-
X2 =
'0 3 0 0 0 15"
0 0 3 5 0 0
0 0 0 0 0 0
0 0 8 0 0 0
0 0 0 24 0 18
.15 0 0 0 0 0
"0 5 0 10 0 0"
0 0 0 0 13 5
0 0 0 10 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 3 0 0 0
(6.6)
(6.7)
Jeśli podczas krzyżowania równomiernego będą wymieniane kolumny macierzy (czyli węzły wraz z wchodzącymi krawędziami),
. 250
6. Uwzględnianie specyfiki problemu
to wynikiem wymiany kolumn 2, 3, 5 będzie chromosom
Y1 =
0 5 0 0 0 0'
0 0 0 5 13 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 24 0 18
15 0 3 0 0 0
(6.8)
odpowiadający strukturze jak na rys. 6.2a. Z kolei, jeśli wymianie podlegałyby wiersze macierzy (węzły z krawędziami wychodzącymi), to wynikiem krzyżowania z wymianą wierszy 2, 3, 5 byłby chromosom
Y =
0 3 0 0 0 0'
0 0 0 0 13 5
0 0 0 10 0 0
0 0 8 0 0 0
0 0 0 0 0 0
15 0 0 0 0 0
(6.9)
kodujący graf, którego strukturę przedstawiono na rys. 6.2b.
(a) - .......... V (b) ' '' ;
RYSUNEK 6.2. Grafy kodowane przez chromosomy Y1 (a) oraz Y2 (b)
6.1.2. Zadania o nieustalonej liczbie parametrów
Niektórych praktycznych problemów, na przykład zadań projektowania, nie można przedstawić w wygodnej postaci optymalizacji parametrycznej, w której liczba zmiennych niezależnych jest ustalona. Jeśli przedmiotem projektowania jest na przykład system złożony z wielu prostych elementów i nie jest dokładnie określona ich konfiguracja, zadanie może polegać na zestawieniu elementów takiego rodzaju i w takiej liczbie, aby system jako całość funkcjo-
L
6.1. Wykorzystanie skomplikowanych struktur danych
.251,
nował jak najlepiej. Należy zarysować strukturę systemu, której stopień komplikacji oraz wymagania stawiane spełnianym przez system funkcjom, wpływają na funkcję przystosowania.
Przy rozwiązywaniu zadań o nieustalonej liczbie parametrów należy korzystać z operatorów genetycznych modyfikujących strukturę systemu, które mogą ją zarówno upraszczać, jak i komplikować.
Kodowanie kaskadowe. W takim kodowaniu chromosom jest łańcuchem parametrów genów. Wprowadza się, oprócz mutacji modyfikującej wartość genu (zwanej perturbacją), dwa dodatkowe operatory mutacji ekspansję i kontrakcję. Ekspansja polega na wstawieniu między dwa kolejne, losowo wybrane geny Xi i Xi+i, dodatkowego genu (rys. 6.3a). W zależności od specyfiki zadania, jego wartość jest albo przypadkowa, albo też zależy od wartości sąsiadujących genów. Z kolei kontrakcja polega na usunięciu z chromosomu losowo wybranego genu (rys. 6.3b).
Przed ekspansją:
Przed kontrakcją:
114131521086443
Po ekspansji:
Miejsce ekspansji
Gen ulegający kontrakcji
Po kontrakcji:
Jl4ljj 15^ 2 10 9_l 8 16 4_l 4 3
32
443
(a) (b)
RYSUNEK 6.3. Sposób działania operatora ekspansji (a) i kontrakcji (b)
Wykorzystanie kodowania kaskadowego z nieustaloną liczbą parametrów wymaga określenia specjalnego operatora krzyżowania. Z wyjątkiem szczególnych zadań, nie da się zastosować krzyżowania uśredniającego; to samo dotyczy operatora równomiernego krzyżowania wymieniającego*. W kodowaniu kaskadowym, oprócz wartości poszczególnych genów, istotna jest kolejność ich ustawienia w chromosomie. Z tych powodów szczególnie odpowiednie dla takiego kodowania wydają się być operatory krzyżowania wymieniającego fragmenty łańcuchów genów: krzyżowanie jednopunktowe i wielopunktowe. Odmiennie niż w kodowaniu z jednakową liczbą genów w każdym chromosomie, pozycje punktów rozcięcia w poszczególnych chromosomach rodzicielskich nie muszą się ze sobą pokrywać. Dzięki temu, możliwe jest uzyskanie w wyniku krzyżowania chromosomów potomnych o długości różnej od rodzicielskich.
PRZYKŁAD. Przykładem zastosowania kodowania kaskadowego *Wymka
jest zadanie projektowania ukladu mikrofaloweqo realizowaneqo mosomy poddawane krzy-
^ r J J J J zowaniu mogą miec rozną
w technice planarnej. Uklad taki powstaje poprzez naniesienie na iiczb? genów.
6. Uwzględnianie specyfiki problemu
m
RYSUNEK 6.4. Przykładowy kształt metalizacji projektowanego układu
płytkę laminatu metalizacji o określonym kształcie. Kształt tej metalizacji decyduje o funkcji i parametrach układu. Projektowanie układu sprowadza się więc do zadania optymalizacji kształtu metalizacji (rys. 6.4)-
Celem naszym jest uzyskanie jak najmniejszego układu, który przesyła moc ze źródła (np. generatora impulsów) do obciążenia (którym może być antena) w taki sposób, aby straty przesyłanej mocy (wynikające z niedopasowania impedancji źródła i obciążenia) były nie większe niż pewna wartość progowa (będąca warunkiem projektu).
W omawianym przykładzie wykorzystano kodowanie kaskadowe; każdy gen był liczbą rzeczywistą, ograniczoną od góry i od dołu. Stosowano operatory ekspansji, kontrakcji i perturbacji oraz krzyżowaniejednopunktowe. Jako metodę selekcji wybrano (^t,A). Projektowano układ dopasowujący impedancję 50 O źródła do 20 f2 obciążenia, w pasmie częstotliwości 1 GHz-2 GHz. Wartości współczynnika strat energii oraz długość odpowiadających im układów dla dwóch metod projektowania stosowanych w technice mikrofalowej (układ ćwierćfalowy i asynchroniczny) oraz dwóch wariantów algorytmu ewolucyjnego z dostrajaniem (ewolucja z efektem Baldwina) i bez dostrajania metodą optymalizacji parametrycznej zamieszczono w tab. 6.Ą.
TABELA 6.4. Wyniki projektowania układu dopasowującego impedancję. Podano długość układów uzyskanych w wyniku optymalizacji, których współczynnik strat mocyjest nie większy niż zadany
Metody projektowania Zadany współczynnik strat, dB
15 20 30
Długość układów, mm
Układ ćwierćfalowy 100 150
Układ asynchroniczny 80 120
Algorytm z dostrajaniem 50 73 144
Algorytm bez dostrajania 44 58 102
6.1. Wykorzystanie skomplikowanych struktur danych
.253.
Jak można zauważyć, zastosowanie algorytmu ewolucyjnego może prowadzić do lepszych wyników niż uzyskane za pomocą pozostałych porównywanych metod.
Kodowanie drzewiaste. W kodowaniu kaskadowym chromosom ma strukturę liniową, która niekiedy jest zbyt prosta, aby oddać powiązania między elementami systemu. Dlatego dość często wykorzystuje się strukturę drzewiastą (w programowaniu genetycznym jest to wręcz podstawowa postać chromosomu)*.
PRZYKŁAD. Wykorzystanie kodowania drzewiastego zamiast kaskadowego do projektowania układu mikrofalowego pozwoliło na dalszą jego miniaturyzację. W tabeli 6.5 podano pole powierzchni płytki prostokątnej, na której można zrealizować układ, przy zastosowaniu kodowania kaskadowego i drzewiastego (obie wersje algorytmu ewolucyjnego z dostrajaniem rozwiązania ewolucja z efektem Baldwina); zamieszczono również wyniki nieewolucyj-nych metod projektowania.
TABELA 6.5. Wyniki projektowania układu dopasowującego impedancję. Podano pole powierzchni płytki prostokątnej mieszczącej uzyskany w wyniku optymalizacji układ, którego współczynnik strat mocy jest nie większy niż zadany
Metody projektowania Zadany współczynnik strat, dB
15 20 30
Pole powierzchni płytki, mm2
Układ ćwierćfalowy 4000 6000
Układ asynchroniczny 3200 4800
Algorytm kaskadowy 1760 2320 4080
Algorytm drzewiasty 1920 2112 2496
Jak widać, wraz ze stopniem utrudnienia zadania (mniejszy dopuszczalny współczynnik strat mocy), stosując kodowanie drzewiaste 'otrzymuje się coraz lepsze wyniki na tle porównywanych metod. Można było tego oczekiwać, gdyż daje ono więcej stopni swobody niż kodowanie kaskadowe.
Problemy z nadmiernym rozrostem drzewa. Jednym z podstawowych problemów w przypadku kodowania drzewiastego i operatorów umożliwiających zmianę rozmiarów drzewa jest zjawisko nadmiernego rozrostu wielkości chromosomu. Wynika to z faktu, że zwiększanie chromosomu powoduje zwiększanie się liczby stopni swobody (liczby genów), za pomocą których można
parametryZOWaĆ rOZWiąZanie. *Operatory genetyczne
r J " specyficzne dla kodowa-
nia drzewiastego omówiono
PRZYKŁAD. Załóżmy, że rozwiązujemy zadanie aproksymacji nie- ^t^t,anS^ znanej funkcji g(x}, dysponując zbiorem T jej próbek par tycznemu (p. 2.4.2).
.254.
6. Uwzględnianie specyfiki problemu
(x,g(x)). Wyrażenie aproksymujące zapisujemy w postaci drzewiastej. Zadanie aproksymacji sprowadza się do minimalizacji funkcji błędu
z^
(x,g(x))eT
(6.10)
gdzie gp(x) oznacza wartość aproksymacji dla argumentu x, p zaś oznacza zbiór wartości parametrów wyrażenia aproksymują-cego. Zauważmy, że jeśli nie narzucimy dodatkowych wymagań co do liczby parametrów i struktury wyrażenia, to jedno z minimów globalnychfunkcji blędu (6.10) (dla którego błądprzyjmie zerową wartość!) będzie odpowiadać takiemu aproksymatorowi, który polega na zapamiętaniu wszystkich próbek i przekazuje na wyjście wartość funkcji Zjawisku nadmiernego rozrostu drzewiastego chromosomu można zapobiegać następującymi metodami.
� Karanie za rozrost < Najprostszym sposobem jest zmniejszanie wartości funkcji przystosowania w stopniu proporcjonalnym do wielkości chromosomu**. Jako wielkość drzewa można przyjąć zarówno jego wysokość, jak i liczbę węzłów.
V:- �
� Automatyczne upraszczanie chromosomu
Sposób ten wynika z obserwacji, że w chromosomie mogą występować takie poddrzewa, które można zapisać w prostszej postaci. Poddrzewa te należy wyszukać i zastąpić równoważnymi. W ten sposób można doprowadzić do znacznej redukcji wymiarów chromosomu, lecz wymaga to dużego nakładu obliczeń związanego z poszukiwaniem upraszczalnych poddrzew.
� Zakazywanie niektórych operacji genetycznych
Dla każdego węzła określa się dopuszczalne operatory, zależne od wielkości drzewa. Dla przykładu: jeśli węzeł jest terminalny i JeS� głębokość jest równa maksymalnej dopuszczalnej wysokości **jest to metoda anaio- drzewa, to nie może dojść do takiej mutacji węzła, która pro-giczna do metody uwzgięd- wadzi}aDy do zastąpienia eo korzeniem losowo wygenerowanego
mama ograniczeń przez ze- J "^ & J � �
wnętrznąfunkcjękary.
nauka
6.2. Modyfikacje algorytmu ewolucyjnego związane z uwzględnianiem ograniczeń
6.2. Modyfikacje algorytmu ewolucyjnego związane z uwzględnianiem ograniczeń
W wykładzie 1 zapoznaliśmy się z metodami uwzględniania ograniczeń poprzez modyfikację zadania. Były to metody transformacji zmiennych oraz funkcji kary. W tym podrozdziale poświęcimy więcej uwagi metodom uwzględniania ograniczeń, które polegają na modyfikacji niektórych mechanizmów algorytmu ewolucyjnego. Są to:
� wykorzystanie kodowania specjalizowanego i operatorów genetycznych, których cechą charakterystyczną jest niedopuszczanie do wygenerowania chromosomu poza obszarem dopuszczalnym,
� naprawa chromosomów reprezentujących niedopuszczalne rozwiązania.
.255.
6.2.1. Kodowanie specjalizowane i operatory genetyczne
Niedopuszczanie do wygenerowania chromosomu poza obszarem dopuszczalnym wymaga zdefiniowania:
� metody generowania początkowej populacji chromosomów spełniających ograniczenia,
� specjalizowanych operatorów genetycznych, które gwarantują, że z rodziców należących do obszaru dopuszczalnego będzie generowane potomstwo w obszarze dopuszczalnym; może to wymagać również modyfikacji metody kodowania.
Spełnienie powyższych warunków gwarantuje, że wszystkie chromosomy, które wygeneruje algorytm ewolucyjny, są rozwiązaniami dopuszczalnymi.
Generowanie punktów dopuszczalnych może niekiedy stanowić wyzwanie samo w sobie (zwłaszcza w obecności ograniczeń nieliniowych lub wielu funkcyjnych ograniczeń równościowych), jednakże w przypadku niektórych zadań jest stosunkowo łatwo wykonalne. Z kolei zdefiniowanie specjalizowanych operatorów genetycznych wymaga szczególnej dbałości o to, aby nie wprowadzić niepotrzebnych obciążeń oraz nie uniemożliwić dostępu do podzbiorów zbioru dopuszczalnego.
Zarysowana metoda jest w istocie podejściem z niejawną transformacją zmiennych niezależnych (dokonywaną na poziomie operacji genetycznych), dlatego też jest szczególnie odpowiednia do uwzględniania ograniczeń równościowych (zwłaszcza liniowych) .
.256.
6. Uwzględnianie specyfiki problemu
PRZYKŁAD. Rozważmy zadanie, w którym chromosom zawiera n genów będących nieujemnymi liczbami całkowitymi, spełniającymi ograniczenie*
(6.11)
(6.12)
z=l
Wziąwszy pod uwagę ograniczenia kostkowe 0 < Xl < d
można stwierdzić, że obszar dopuszczalny jest zbiorem punktów o współrzędnych będących liczbami całkowitymi, należących do (n l)-wymiarowego sympleksu. Chromosomy w populacji początkowej możemy wygenerować między innymi jednym z następujących sposobów:
� wartość i* G {1, 2,..., n} losuje się z rozkładem jednostajnym; przyjmuje się, że Xi* = d, geny zaś o numerach i ^ i* mają wartość zero; chromosomy w populacji początkowej rozmieszczane są losowo w wierzchołkach sympleksu;
� wszystkie geny mają wartość początkową równą zero; d razy powtarza się następujące czynności: losowanie z rozkładem jednostajnym numeru genu i* oraz zwiększenie o jeden wartości genu Xj*; chromosomy są rozmieszczane we wszystkich punktach dopuszczalnych, jednak jak łatwo się przekonać prawdopodobieństwo wygenerowania chromosomów nie jest jednakowe.
*Alternatywną do omawianej w przykładzie metody uwzględnienia suma-cyjnego ograniczenia równościowego jest zamiana zmiennych niezależnych. Łatwo zauważyć, że do pełnego opisu zadania wystarczy wartości nie n, lecz ii, 1 zmiennych.
Znając sposób generowania chromosomów dopuszczalnych, spróbujmy określić operator mutacji, gwarantujący dopuszczalność chromosomów potomnych. Operator taki może być zdefiniowany w następujący sposób.
W pierwszym etapie losuje się numer genu i* z rozkładem równomiernym spośród genów o niezerowych wartościach. Następnie losuje się wartość &X � {l,2,...,J*Q*}. Później powtarza się &X razy losowanie numeru genu j z rozkładem jednostajnym (spośród wszystkich genów oprócz Xi*), po czym wartość Xj zwiększa się o jeden. Na koniec, wartość X^ zmniejsza się o AJ*f.
Krzyżowanie jest trudne do zdefiniowania, gdyż zastosowanie operatora wymieniającego może doprowadzić do powstania chromosomów nie spełniających ograniczenia (6.11), wynikiem uśredniania zaś może być chromosom złożony z liczb rzeczywistych, nie całkowitych. Pewnym rozwiązaniem może być zastosowanie krzyżowania uśredniającego ze specjalnym zaokrąglaniem, w dół lub w górę, tak aby wymusić zachowanie ograniczenia (6.11).
6.2. Modyfikacje algorytmu ewolucyjnego związane z uwzględnianiem ograniczeń
6.2.2. Algorytmy naprawy
Wykorzystując algorytm naprawy jako metodę uwzględniania ograniczeń, należy zdefiniować odwzorowanie Af, które każdemu chromosomowi niedopuszczalnemu X przyporządkowuje "naprawiony" chromosom Y, zawarty w zbiorze dopuszczalnym. Możliwe są przy tym dwa warianty metody naprawy.
1) Pierwszy z nich polega na wygenerowaniu Y na brzegu zbioru dopuszczalnego. Takie postępowanie sprawia, że algorytm ewolucyjny w intensywniejszy sposób przeszukuje brzeg zbioru dopuszczalnego niż jego wnętrze (zwłaszcza gdy proporcja miar zbioru dopuszczalnego i zbioru wszystkich rozwiązań jest niewielka)*.
2) W drugim wariancie otrzymujemy rozwiązanie położone zarówno na brzegu, jak i we wnętrzu zbioru dopuszczalnego.
W obu wariantach metody naprawy należy tak definiować odwzorowanie Af, aby (w miarę możliwości) nie "dyskryminować" żadnych obszarów zbioru dopuszczalnego. Łatwo sobie bowiem wyobrazić sytuację patologiczną, gdy Af będzie wybierać zawsze ten sam chromosom Y dla dowolnego naprawianego X.
.257.
PRZYKŁAD. Ilustracją metod naprawy może być następujący sposób rozwiązywania problemu plecakowego. Chromosom jest wektorem X e Z% zawiera informacje o decyzjach związanych z załadowaniem przedmiotów do plecaka lub ich pozostawieniem. Jeśli plecak ma wagę mieszczącą się w ograniczeniu, fenotyp jest identyczny jak chromosom. W przeciwnym przypadku przystępuje się do wykonania algorytmu naprawy. Polega on (podobnie jak w przypadku prawdziwego plecaka) na usuwaniu zeń przedmiotów tak długo, aż waga plecaka będzie się mieścić w ograniczeniu.
Najlepszy wybór zbioru przedmiotów do usunięcia to taki, który spełnia warunki
mm
L
i6AT(X)
przy ograniczeniu
(6.13)
(6.14)
i=l
gdzie AT(X) oznacza zbiór numerów przedmiotów do usunięcia. Tak więc najlepszego wyboru przedmiotów możemy dokonać, roz- *rMe zacnoW3nie moze wiązując ponownie problem plecakowy! Oczywiście, jeżeli plecak być pożądane, jeśii rozwią-będzie bardziej,,pojemny" (tzn. ELi^ � W), to takie rozwiąza- ^/*d^szS nie prowadzi do uproszczenia zadania, niemniej jednak w ogólnym nego.
.258.
6. Uwzględnianie specyfiki problemu
przypadku nie przynosi zbyt dużych korzyści. Dlatego też jesteśmy zmuszeni posłużyć się szybką metodą przybliżoną. Może nią być na przykład usuwanie przedmiotów zgodnie ze zwiększającą się wartością współczynnika p-i/w-i (analogia do metody zachłannej) lub też usuwanie losowo wybranych przedmiotów.
Ewolucja lamarkowska i efekt Baldwina. Zastosowanie algorytmu naprawy stawia nas przed podobnym dylematem, jaki należało rozwiązać, łącząc algorytm ewolucyjny z metodą optymalizacji lokalnej. Podobnie jak w tamtym przypadku, dysponujemy dodatkową informacją, którą jest naprawiony genotyp i jego funkcja przystosowania. Do wyboru są ponownie dwa schematy ewolucji lamarkowska i darwinowska (z efektem Baldwina). W pierwszym z wymienionych schematów wyjściowy niedopuszczalny chromosom jest usuwany z populacji bazowej i zastępowany naprawionym. W drugim schemacie chromosom wyjściowy pozostaje w populacji bazowej, lecz jego przystosowanie jest równe przystosowaniu naprawionego.
Podobnie jak w przypadku łączenia metody optymalizacji lokalnej i algorytmu ewolucyjnego, w literaturze można znaleźć sprzeczne opinie o przydatności wymienionych schematów ewolucji. Niektórzy autorzy nie stwierdzają wręcz istotnego wpływu któregokolwiek ze schematów na odporność i szybkość działania algorytmu. Dylemat ten pozostawmy więc nierozstrzygnięty.
6.3. Modyfikacje algorytmu ewolucyjnego uwzględniające zadania wielokryterialne
Powróćmy do zadań wielokryterialnych. W wykładzie 1 poznaliśmy sposób ich rozwiązywania poprzez skalaryzację. Obecnie zajmiemy się innymi metodami, nie posługującymi się skalaryzacją, lecz "widzącymi" wielokryterialność zadania.
Jak wiadomo, rozwiązaniem zadania wielokryterialnego jest nie jeden punkt, lecz zbiór punktów niezdominowanych. Jeśli założymy dodatkowo, że punkty należą do przestrzeni Rn, to rozwiązań zadania wielokryterialnego może być nieskończenie wiele. Dlatego w literaturze dotyczącej algorytmów ewolucyjnych spotyka się uproszczenie polegające na wymaganiu, aby znaleźć nie wszystkie, lecz możliwie najwięcej rozwiązań niezdominowanych. Dodatkowo, powinny one jak najbardziej równomiernie pokrywać zbiór wszystkich rozwiązań, aby dać decydentowi jak największą swobodę wyboru jednego z nich.
6.3. Modyfikacje algorytmu ewolucyjnego uwzględniające zadania wielokryterialne
.259.
6.3.1. Reprodukcja oparta na dominacji
W sytuacji, gdy kryterium optymalności nie jest wyrażane funkcją skalarną, lecz wektorową, nie da się zastosować reprodukcji proporcjonalnej wykorzystującej wartości funkcji przystosowania. Można natomiast zmodyfikować reprodukcję rangową i turniejową, wykorzystując relację dominacji.
Stosowane rozwiązania. W reprodukcji turniejowej należy założyć, że zwycięzcą turnieju zostaje osobnik, dla którego nie istnieje w turnieju inny osobnik o fenotypie go dominującym. Jeśli osobników takich jest wiele, to wybierany jest losowo jeden z nich.
W reprodukcji rangowej konieczne jest nadanie rang. Następnie oblicza się prawdopodobieństwa reprodukcji na podstawie nadanych wartości rang, podobnie jak w przypadku ze skalarną funkcją przystosowania.
W literaturze znane są dwa warianty tej procedury. W pierwszym, rangi są nadawane w sposób uwzględniający kolejność dominacji punktów (rys. 6.5). Osobniki niezdominowane otrzymują rangę 0. Następnie wśród pozostałych osobników poszukuje się niezdorninowanych, które otrzymują rangę 1 i tak dalej, aż do momentu, gdy wszystkie osobniki otrzymają wartość rangi.
Drugi wariant polega na tym, że ranga osobnika jest wyznaczona przez liczbę osobników go dominujących
gdzie F(X), F(Y) oznacza fenotypy kodowane przez chromosomy X,Y, a >- oznacza relację dominacji, opisaną dokładniej w podrozdziale 1.5.1.
procedurę Nadawanie rang begin
A := P*
k := 0
while (A ź 0) do
begin
VX e P r(X) A := A \ Ap
k := k + l
:= k
\Ap F(X)xF(Y), F(Z)^F(X)}
end
end
RYSUNEK 6.5. Procedura nadawania rang na podstawie kolejności dominacji
.260.
6. Uwzględnianie specyfiki problemu
Problem równomiernego pokrycia zbioru rozwiązań nie-zdominowanych. Wykorzystanie technik opartych na dominacji prowadzi najczęściej do wystąpienia problemu nierównomiernego pokrycia zbioru rozwiązań niezdominowanych. Przy niewielkich populacjach bazowych, większość chromosomów jest najczęściej zdominowana. Schemat selekcji preferujący niezdominowane chromosomy prowadzi do intensywniejszego przeszukiwania ich sąsiedztwa. W efekcie, powstają skupiska chromosomów wokół uprzednio niezdominowanych. Liczba tych skupisk ma tendencję do zmniejszania się w kolejnych generacjach. Wskutek tego, rozmieszczenie chromosomów w zbiorze punktów niezdominowanych jest bardzo nierównomierne. Zjawisku temu zapobiega się, stosując techniki optymalizacji wielomodalnej, przede wszystkim podział przystosowania, któremu podlega funkcja rang.
Jeszcze jednym ciekawyrn zjawiskiem charakterystycznym dla metod reprodukcji opartych na dominacji punktów szczególnie dobrze widocznym, jeśli nie są stosowane techniki optymalizacji wielomodalnej jest tendencja do preferowania przez algorytm ewolucyjny tych fragmentów zbioru rozwiązań niezdominowanych, w których wartości pochodnej cząstkowej wektora kryteriów po zmiennych decyzyjnych są równe co do modułu. Zjawisko to można zaobserwować wówczas, gdy stosowanyjest operator mutacji o stałej wielkości kroku, jednakowej w każdym kierunku. Wynika to z faktu, że taki sposób mutacji daje największą wartość oczekiwaną poprawy (w sensie dominacji). Można zapobiegać temu zjawisku, stosując np. operatory mutacji ze zmiennym (adaptowanym) zasięgiem.
6.3.2. Podejście koewolucyjne
Podejście, które można by nazwać koewolucyjnym, wykorzystuje się w algorytmie VEGA (Vector Evaluated Genetic Algorithm}. Przetwarza się rn populacji P-, w każdej z nich funkcja przystosowania (frj(X) jest określana na podstawie innego składnika wektorowego wskaźnikajakości /j(F(X)). Po dokonaniu sukcesji, a przed ponowną reprodukcją, populacje te są łączone, a następnie ponownie dzielone tak, że każdy osobnik może trafić do dowolnej populacji (rys. 6.6).
Algorytm ten ma tendencję do poszukiwania "ekstremalnych" rozwiązań niezdominowanych, tzn. takich, które znajdują się blisko krańców zbioru rozwiązań niezdominowanych. Można zapobiegać temu zjawisku, stosując techniki podziału przystosowania, jednakże istnieje wówczas ryzyko wystąpienia trudności z osiągnięciem rozwiązań niezdominowanych. Innym rozwiązaniem jest ograniczenie wymiany osobników między populacjami zarówno
6.3. Algorytm ewolucyjny w środowisku dynamicznym
.261,
procedurę VEGA begin
t := 0
inicjacja Ps
ocena P*
while (not warunek stopu) do
begin
wykonaj losowy podział P* na m podpopulacji
for (j = 1,..., m) do
begin
T*- := reprodukcja P*-: sJ. O' := operacje genetyczne T'-
ocena O*.
5*+1 := sukcesja (P*, Oj-)
end
t := t+1
p< ._ i \� r>t
r � Ui=i *j
end
end
RYSUNEK 6.6. Schemat algorytmu VEGA
jej częstości (nie w każdej generacji), jak też intensywności (nie wszystkie osobniki, lecz np. najlepsze, przeciętne czy najgorsze).
6.4. Algorytm ewolucyjny w środowisku dynamicznym
Zadaniem algorytmu ewolucyjnego jest adaptacja do zmieniającego się środowiska. W dalszym ciągu rozważań przyjmiemy założenie upraszczające, że wszelkie zmiany (zarówno funkcji przystosowania, jak i zbioru rozwiązań dopuszczalnych) następują w sposób dyskretny, synchronicznie z kolejnymi pokoleniami algorytmu ewolucyjnego.
Zasada działania algorytmu ewolucyjnego stanowi przeszkodę dla zastosowania go do problemów ze środowiskiem zmiennym w czasie. Algorytm ewolucyjny wykorzystuje zasadę stopniowego budowania rozwiązania, prowadząc intensywniejsze przeszukiwanie przestrzeni rozwiązań wokół punktów o większym przystosowaniu. Nie można go więc wykorzystywać do optymalizacji funk-
.262.
6. Uwzględnianie specyfiki problemu
cji, których zmienność jest pozbawiona pewnej regularności*. Ponadto, wymóg globalności przeszukiwań, sprzeczny z szybkością zbieżności, nie pozwala także liczyć na precyzyjne nadążanie algorytmu za bardzo szybko zmieniającym się położeniem maksimum globalnego. W takiej sytuacji można się spodziewać, że osobniki skupią się w obszarze, gdzie średnia wartość funkcji przystosowania, przez pewien okres zależny od nacisku selektywnego, będzie stosunkowo duża.
6.4.1. Informacja o zajściu zmiany ;
Ważne jest, aby algorytm ewolucyjny "miał świadomość" zmiany, jaka dokonała się w środowisku, tzn., aby można było stwierdzić w chwili t, że zmiana nastąpiła.
Dostępność tej informacji może znacznie uprościć działanie algorytmu, pozwala bowiem skupić większą uwagę na eksploracji w każdej populacji po zajściu zmiany, natomiast później, w okresie stabilności środowiska, pozwala stopniowo zwiększać eksploatację, aby szybciej dojść w okolice poszukiwanego maksimum. Brak informacji o zajściu zmiany zmusza do utrzymywania "potencjału eksploracyjnego" algorytmu na stosunkowo wysokim, w przybliżeniu stałym poziomie. Oznacza to, że w każdej generacji zadanie należy traktować tak, jakby środowisko uległo zmianie**.
*Wówczas możemy się spodziewać co najwyżej tego, że większość populacji skupi się w tych fragmentach obszaru dopuszczalnego, w których funkcja przystosowania zmienia się stosunkowo nieznacznie. **Nie oznacza to, że w każdej generacji środowisko rzeczywiście ulegnie zmia-
6.4.2. Metody adaptacji
Utrzymywanie różnorodności. W dynamicznym środowisku szczególnie ważne jest utrzymywanie zdolności eksploracyjnych algorytmu. Utrata różnorodności może bowiem sprawić, że populacja rozwiązań będzie skupiona w jednym tylko fragmencie obszaru dopuszczalnego, co nie byłoby może dużą wadą dla środowiska niezmiennego w czasie, jeśli tylko obszar ten zawierałby maksimum globalne. W przypadku środowiska dynamicznego, takie zachowanie algorytmu groziłoby utratą możliwości nadążania za zmianami w środowisku.
Podstawowym, najbardziej uniwersalnym sposobem utrzymywania różnorodności jest wprowadzanie do populacji osobników wygenerowanych z rozkładu prawdopodobieństwa niezależnego od stanu populacji (mechanizm losowych imigrantów). Jeśli obszar dopuszczalny jest skończonej miary, dobrym wyborem wydaje się być rozkład jednostajny na tym zbiorze; w przeciwnym przypadku można wykorzystać np. rozkład normalny z wartością oczekiwaną w środku ciężkości populacji bazowej.
Jeśli funkcja przystosowania zmienia się nieznacznie w kolejnych generacjach (a zatem zmiany liczby i położeń ekstremów
6.4. Algorytm ewolucyjny w środowisku dynamicznym
.263.
lokalnych są niewielkie), to godne polecenia wydają się techniki osłabiania nacisku selektywnego stosowane w optymalizacji wie-lomodalnej niszowanie, grupowanie osobników czy też metody koewolucyjne.
Wykorzystywanie dodatkowej pamięci. W przypadku funkcji o okresowym charakterze zmian dobre wyniki można uzyskać, wykorzystując dodatkową pamięć. Może być ona wprowadzona na różnych poziomach:
� na poziomie populacji,
� na poziomie osobnika.
6.4.3. Pamięć na poziomie populacji
Wprowadza się drugą populację, niezależnie od populacji bazowej algorytmu ewolucyjnego, przechowującą najlepsze znalezione rozwiązania. Jest ona zazwyczaj zorganizowanajako kolejka FIFO i są w niej przechowywane "najbardziej pożyteczne" osobniki. Mogą to być:
� najlepsze osobniki w populacji,
� osobniki wprowadzające największą różnorodność do pamięci,
przy czym pierwszy wybór jest bardziej rozpowszechniony.
Sposób wykorzystania tej pamięci może być dwojaki. Niektórzy autorzy dopuszczają do tego, aby wybierać z niej jednego z osobników rodzicielskich do krzyżowania (wówczas algorytm taki przypomina koncepcję reprodukcji elitarnej). Z kolei inni łączą ten pomysł z techniką restartu populacji bazowej (z podobną techniką zetknęliśmy się już przy omawianiu niszo-wania sekwencyjnego). Różnica polega na tym, że w przypadku zmiennej w czasie funkcji przystosowania podczas inicjacji populacji bazowej w kolejnym uruchomieniu algorytmu ewolucyjnego fragment populacji bazowej jest wypełniany perturbacjami chromosomów z pamięci pozostała część to chromosomy losowane z rozkładem niezależnym od pamięci i poprzedniej zawartości populacji bazowej.
Podsumowując zaletą przedstawionych technik jest ich duża ogólność; konieczne jest jednak, aby funkcje przystosowania w kolejnych generacjach były ze sobą dość dobrze skorelowane.
6.4.4. Pamięć na poziomie osobnika
Wykorzystanie pamięci na poziomie osobnika polega na wprowadzeniu do osobnika dodatkowych chromosomów, które wpływają na wartość funkcji przystosowania tylko w pewnych szczególnych
.264.
6. Uwzględnianie specyfiki problemu
warunkach. Innymi słowy, genotyp osobnika zawiera chromosomy kodujące więcej niżjeden punkt obszaru dopuszczalnego; rozstrzygnięcie, który z tych chromosomów przyczyni się do ukształtowania fenotypu, może być rozwiązane dwoma sposobami. ;
Dominacja genów. Pierwszy sposób, stosowany przy kodowaniu binarnym, polega na wprowadzeniu pojęcia genu dominującego i recesywnego. Genotyp osobnika zawiera dwa chromosomy. Jako przykład omówimy metodę przedstawioną w pracy [61]. Autorzy wprowadzili cztery litery kodowe: dominujące zero 0^, dominujące jeden 1^, recesywne zero Or i recesywne jeden lr. Osobnik zawiera dwa chromosomy X^1 i Xs, z których każdy może być łańcuchem złożonym z wymienionych liter. Do obliczenia przystosowania osobnika bierze się taki punkt przestrzeni genotypu, jaki wynika z ekspresji genów. Ekspresja polega na tym, że "efektywny" chromosom osobnika, na podstawie którego określa się fenotyp, jest wyznaczany w następujący sposób:
~V { V^ yl V" Q \ - f r> 1 r> \
Xi e(Xi , Xi } (b.l6J
(operator ekspresji e() zdefiniowano w tab. 6.6). Dodatkowo, autorzy wprowadzili procedury modyfikujące materiał genetyczny, w przypadku gdy na tej samej pozycji ta sama litera kodowa wy-
TABELA 6.6. Operator ekspresji tablica dominacji
A x?
Xi Od or Id lr
od 0 0 0
Or 0 0 1
Id 1 1 1
lr 0 1 1
stępuje wjednym chromosomiejako recesywna, w drugim zaśjako dominująca; wówczas recesywna jest zamieniana na dominującą. W sytuacji gdy występują dwie różne recesywne litery kodowe, losowo wybrana z nich jest zamieniana na dominującą. W przypadku niezgodności dominujących liter, ekspresji ulega wybrana losowo.
Pamięć materiału genetycznego przodków. W drugim sposobie osobnik przechowuje chromosomy swoich przodków aż do k generacji wstecz. Zapamiętywany jest chromosom tego z rodziców, który był najlepiej przystosowany. Jeśli środowisko uległo zmianie, to dla każdego osobnika oblicza się przystosowanie wszystkich pamiętanych przezeń chromosomów i wybiera najlepszy z nich. Chromosom ten staje się aktualnym chromosomem osobnika.
6.5. Uwagi bibliograficzne
.265.
Sposób ten wydaje się dość wygodny w przypadku chromosomów rzeczywistoliczbowych, gdyż trudno byłoby wprowadzić ,piaturalne" mechanizmy dominacji naśladujące biologiczny pierwowzór. Jego wadą jest konieczność przeliczania przystosowania k alternatywnych chromosomów dla każdego osobnika. Łatwo też zauważyć analogie do lamarkowskiego modelu ewolucji (zamiana chromosomu na lepszy chromosom przodka), co może pociągać za sobą zmniejszenie różnorodności populacji bazowej i w efekcie osłabienie zdolności przeszukiwawczych algorytmu. Dlatego też w eksperymentach łączono algorytm z zapamiętywaniem materiału genetycznego przodków z mechanizmem wprowadzania losowych osobników (losowych imigrantów).
Jak można się spodziewać, sposób ten wydaje się być szczególnie efektywny w przypadku środowisk, w których zmiany mają charakter cykliczny, jednakże trzeba wówczas zadbać o to, aby pamięć sięgała co najmniej jednego okresu zmian wstecz (k > T). Niespełnienie tego warunku nasila negatywne cechy lamarkowskiego modelu i może prowadzić do pogorszenia działania algorytmu nawet w porównaniu z metodą bez pamięci.
6.5. Uwagi bibliograficzne
Obszerny przegląd metod specjalizowanego kodowania i operatorów genetycznych dla różnych problemów badań operacyjnych (komiwojażera, plecakowego i wielu innych) zawiera praca [54]; tam również omówiono różne metody uwzględniania ograniczeń. Reprezentację macierzową grafów i związane z nią operatory genetyczne opisano na podstawie [90, 91], a zadanie projektowania układów mikrofalowych wraz z wynikami na podstawie [3].
Algorytm VEGA przedstawiono w pracy [92] i obszernie omówiono w [31].
Opis metod uwzględniania ograniczeń w algorytmach ewolucyjnych można znaleźć w pozycjach [55, 56, 57], a w [63] zaproponowano ciekawą, koewolucyjną metodę uwzględniania ograniczeń.
Zadanie adaptacji ze zmienną w czasie funkcją przystosowania zostało dość wcześnie zauważone. Autorzy zajmujący się strategiami ewolucyjnymi ograniczają się zazwyczaj do stwierdzenia, że wystarczy posługiwanie się schematem selekcji ([i, A) (ewentualnie (^t,�;, A)), aby umożliwić nadążanie za maksimum globalnym [6, 93]. Testy potwierdzające tę tezę ograniczają się z reguły do zadań, w których minimum globalne w kolejnej chwili znajduje się w otoczeniu poprzedniego maksimum globalnego; promień tego otoczenia jest ograniczony. Zmiany położenia maksimum następują co pewien ustalony czas i nie mają charakteru okresowego.
.266.
6. Uwzględnianie specyfiki problemu
Z kolei wśród osób zajmujących się algorytmami genetycznymi popularne stały się podejścia z genami dominującymi i re-cesywnymi [31]. Opisany algorytm z dominacją genów pochodzi z pracy [61], natomiast pamięć materiału genetycznego przodków opisano w [10, 104, 105]. Oba rodzaje metod dodawania do osobnika pamięci przodków wydają się dobrze działać przy funkcjach przystosowania o cyklicznym charakterze zmienności.
6.6. Pytania i ćwiczenia : ��-'�
1. Narysuj drzewo odpowiadające wyrażeniu (sin(x) + cos(x)) � -cos(.x) tg(x). Korzystając z właściwości funkcji trygonometrycznych, uprość postać wyrażenia i zmniejsz w ten sposób
.* wielkość drzewa.
2. Załóżmy, że parametry zadania plecakowego są następujące:
p = [3,4,3,ll,6,l] .,-.. ,...,^:v ,,,,,^,,,>4 , ��-. , -
w=[l,4,5,8,4,2]
W = 12
Przyjmijmy, że genotyp i fenotyp są tożsame, tj. chromosom osobnika zawiera wartości zmiennych decyzyjnych. Załóżmy, że został wygenerowany osobnik niedopuszczalny o chromosomie
X=[1,0,0,1,1]
Jaki będzie chromosom Y, będący wynikiem działania "zachłannego" algorytmu naprawy, polegającego na usuwaniu z plecaka kolejnych przedmiotów o najmniejszej wartości Pi/Wil Jaki jest najlepszy chromosom osiągalny w wyniku naprawy X?
W sześciu wykładach stanowiących zasadniczą treść tej książki przedstawiłem podstawy algorytmów ewolucyjnych, a także większość kierunków rozwojowych. Wiadomości te stanowią (nieco poszerzony w trzeciej części) "kanon" algorytmów ewolucyjnych. Sześć wykładów to jednak za mało, aby wyczerpać tę tematykę. Zadanie to było tym trudniejsze, że jest ona w stanie ciągłego rozwoju, powstają nowe pomysły jedne trafne, inne chybione. Siłą rzeczy, materiał potraktowałem w sposób wybiórczy; nie bez wpływu na ten wybór były moje zainteresowania i doświadczenie.
Całkowicie pominąłem kwestie związane z teorią algorytmów ewolucyjnych (wyjątek stanowi wzmianka o teorii schematów, która została poczyniona głównie ze względów historycznych; jej znajomość ułatwia lekturę wielu artykułów, nawet nie poświęconych teorii). Wynikło to z faktu, że jak na razie teoria jest bardzo słabo rozwinięta, wymaga zaawansowanego aparatu matematycznego, uzyskiwane zaś wyniki raczej uzasadniają obserwacje eksperymentalne niż pozwalają na modyfikacje istniejących czy wprowadzanie nowych schematów selekcji, operatorów genetycznych lub strojenie parametrów.
Również celowo nie zamieściłem obszernego omówienia zastosowań algorytmów ewolucyjnych. Wnikliwe omówienie wymagałoby bowiem poznania szczegółów wdrożeń, których mnogość mogłaby przesłonić kwestie związane z samymi algorytmami ewolucyjnymi; sądzę, że jest to materiał na osobną książkę. Do aspektów praktycznych odwołałem się w ostatnim wykładzie, w którym wdrożenie służy tylko jako pretekst do omówienia zagadnień związanych z kodowaniem i operatorami genetycznymi.
u
w
A G I
K O
Ń C O
W
E

. 268 _____ Uwagi końcowe
Pominąłem zagadnienia zwyczajowo wiązane z algorytmami ewolucyjnymi. Nie zająłem się tematyką bardzo szeroko reprezentowaną w wielu źródłach zastosowaniom w sztucznej inteligencji czy maszynowym uczeniu (w tym z ostatnio silnie akcentowanymi sieciami neuronowymi i systemami z logiką rozmytą), sztucznemu życiu, analogiom z ewolucją systemów biologicznych bądź ekonomicznych i wielu innym, niewątpliwie bardzo ciekawym zagadnieniom.
Mam nadzieję, że powyższa "lista braków" nie zniechęciła Czytelników do książki, lecz raczej pobudziła do pogłębiania wiedzy poprzez samodzielne studiowanie literatury przedmiotu i do prowadzenia własnych badań. Wydaje się bowiem, że rozwój algorytmów ewolucyjnych nie osiągnął swego kresu i wiele jeszcze pozostało do odkrycia.