Dodatek D
Transformacja współczynników partycyjnych i jej zastosowanie w problemie doboru kodu

Algorytm genetyczny działa efektywnie, kiedy schematy-cegiełki, czyli stosunkowo wąskie schematy niskiego rzędu o ponadprzeciętnej wartości przystosowawczej, łączą się, tworząc optymalne lub niemal optymalne rozwiązania. Przekonanie, że proces taki zachodzi w rzeczywistości - hipoteza cegietek - było często przyjmowane na wiarę. Niedawno opracowano jednak metody analizy, dzięki którym można przewidywać, czy dane zestawienie funkcji, kodu i operacji genetycznych powinno (lub nie) prowadzić do znajdowania lepszych rozwiązań. Metody te dzielą się na dwie kategorie - dynamiczne i statyczne.
Podejście dynamiczne, z którym mieliśmy okazję zapoznać się krótko w rozdziale drugim przy omawianiu mimimalnego problemu zwodniczego, polega na pełnej analizie propagacji współzawodniczących klas schematów, opisanej za pomocą nieliniowych równań rekurencyjnych odpowiadających danemu zestawowi operacji genetycznych, metodzie kodowania oraz funkcji przystosowania. Tego typu analiza prowadzi do rozstrzygających wniosków w przypadku zadań o niedużych rozmiarach. Otrzymane ostatnio (Bridges i Goldberg, 1987) równania propagacji przy reprodukcji i krzyżowaniu dla przypadku ogólnych kodów /-bitowych umożliwiają analizę dynamiczną problemów wyższego rzędu.
W podejściu statycznym (Bethke, 1981; Holland, 1987b) oblicza się średnie przystosowania schematów, korzystając z efektywnych metod transformacji. Dysponując tymi średnimi, możemy następnie stwierdzić, czy hipoteza o cegiełkach jest w danym przypadku spełniona (tzn. czy^wąskie schematy niskiego rzędu o wysokiej wartości przystosowawczej łączą się tworząc szersze, wyższego rzędu schematy o jeszcze wyższej wartości przystosowawczej), czy nie (tzn. czy problem jest AG-zwodniczy). Holland (doniesienie prywatne, 1987) rozszerzył ostatnio swoją metodę analizy na populacje o niejednostajnym rozkładzie ciągów kodowych. Można pokazać, że w przypadku jednostajnym techniki Bethkego i Hollanda są równoważne. W tym dodatku wybraliśmy
376
D. Transformacja współczynników partycyjnych
notację Hollanda i omawiamy jego metodę współczynników partycyjnych; następnie użyjemy jej do analizy prostej kombinacji funkcji i kodu. Naszkicujemy także zastosowanie tej metody do konstruowania problemów AG-zwodniczych.
D.1. Transformacjawspółczynników partycyjnych______________
Rozważmy odwzorowanie / przestrzeni ciągów kodowych długości / w zbiór liczb rzeczywistych:
/: {0, l}'^R
Określamy schematy ciągów kodowych tak jak zwykle i dla każdej klasy (partycji) schematów o tym samym zbiorze pozycji ustalonych definiujemy indeks partycyjny j:
gdzie i jest numerem pozycji w ciągu kodowym, a funkcja a przyjmuje wartość 0, gdy h,= * oraz wartość 1 w przeciwnym przypadku. W ten sposób funkcjay przyporządkowuje w sposób jednoznaczny indeks każdej z 2' partycji w przestrzeni ciągów kodowych, zawierających ciągi o jednakowym zbiorze pozycji ustalonych. I tak na przykład schematowi *** odpowiada indeks partycyjnyy'(***) = 0. Schematy **0 i **1 należą do tej samej partycji o indeksiej=l, a schematowi 0*1 odpowiada indeks partycyjny y(0*l) = 5.
W celu wyznaczenia współczynników partycyjnych definiujemy także funkcję o^, określoną na zbiorze wszystkich schematów, która przyjmuje wartość 1, jeżeli schemat zawiera parzystą liczbę zer oraz wartość -1 w przeciwnym przypadku:
gdzie p(A,.) przyjmuje wartość 1 dla fy = 0 i 0 w pozostałych przypadkach.
MajÄ…c już okreÅ›lone funkcje j i o, możemy teraz zdefiniować współczynniki par-tycyjne e; za poÅ›rednictwem ukÅ‚adu równaÅ„ postaci: •
f(H) =
Sumowaniejest tu rozciągnięte na wszystkie "nadschematy" H' schematu H.
Powyższy układ liczy oczywiście 3' takich równań, jednak tylko 2' z nich to równania niezależne, ponieważ mamy tylko 2' "niewiadomych" e; (można na to spojrzeć w ten sposób, że dokonujemy transformacji 2' wskaźników przystosowania ciągów kodo-
D.2. Przykład: f(x)=f na trzech bitach
377
wych na 2' innych współczynników rzeczywistych). Nie będziemy tutaj dowodzić poprawności tej transformacji; dodajmyjednak, że wjednym z prostych dowodów zamiast bitów rozważa się dwuwartościowe zmienne M,., przebiegające zbiór {-l, 1}. Można łatwo wtedy pokazać, że każdą funkcję / można wyrazić w postaci wielomianu /-tego stopnia zmiennych ut i że istnieje wzajemnie jednoznaczna odpowiedniość między współczynnikami tego wielomianu a liczbami e.. Poprawność transformacji wynika wówczas bezpośrednio z postaci wielomianu. W następnym punkcie zapoznamy się bliżej z tą metodą, obliczając współczynniki partycyjne dla prostej funkcji i kodu.
D.2. Przykład: f(x)=x2 na trzech bitach
Chcąc lepiej zrozumieć transformację współczynników partycyjnych, wyznaczmy współczynniki Ej dla konkretnej funkcji/(*)=*2 i trójpozycyjnego zapisu dwójkowego. Na początek wypiszemy osiem równań, po jednym dla każdego schematu zawierającego jedynie gwiazdki i jedynki:
/(***) = e" "" '
/(**1) = e"+e,
/(*1*) = e"+e2
/(*11) = e0+e,+e2+e3
/(1**) = e()+e4
/(1*1) = e()+e,+e4+e5 ' ' " ' *
/(11*) = efl+e2 + e4+e6
/(111) = en + e,+e2+e3 + e4 + e5
Powyższe wyliczenie wskazuje na możliwość dość efektywnego obliczania współczynników partycyjnych (szybka transformacja Walsha okazałaby się jeszcze bardziej efektywna, ale posłużyliśmy się tą triangularyzacją dla zachowania pewnych intuicji fizycznych): należy wyznaczyć średnie przystosowania schematów we wskazanej kolejności, a następnie obliczyć wartości e; metodą eliminacji. Po wykonaniu tych rachunków otrzymamy następujące wartości/i e;.:
Indeks partycyjny j Schemat H f(H} e
0 1
2 3 4 5 6 7
*** **1 *1*
*11
1**
1*1 11* 111
17,5 17,5
21,0 3,5
24,5 7,0
29,0 1,0
31,5 14,0
37,0 2,0
42,5 4,0
49,0 0,0
378
D. Transformacja współczynników partycyjnych
Po obliczeniu współczynników partycyjnych możemy obliczyć bez trudu średnie przystosowanie każdego wybranego schematu. Na przykład/(**0) = e0-e, = 17,5-3,5=14. Można to zweryfikować obliczając bezposrednio:/(**0) = (0 + 4+16 + 36)/4=14,0. Obliczenia dla innych schematów są równie proste, ale musimy teraz zająć się wyjaśnieniem sensu współczynników e, oraz ich roli w analizie algorytmów genetycznych i przetwarzaniu schematów.
D.3. Interpretacjawspółczynników
partycyjnych______________________________________
Fakt, że umiemy obliczać współczynniki partycyjne w dość efektywny sposób, jest pokrzepiający, ale naprawdę chodzi nam o zrozumienie rodzaju nieliniowości, która ujawnia się we wskaźnikach przystosowania dwójkowych ciągów kodowych, gdy stosujemy algorytm genetyczny. Aby rozpoznać związek między nieliniowością a współczynnikami partycyjnymi, zwróćmy uwagę na pewne głębsze zależności występujące w naszym przykładzie. Rozważmy mianowicie wzory na przystosowanie dla dwóch konkurujących schematów, np. **1 i **0:
/(**l) = e<,+e, /(**O) = e,,-e,
Ponieważ współczynnik e0 jest równy po prostu średniej ze wszystkich ciągów kodowych (czyli przystosowaniu schematu ***), więc współczynnik e, jest bezpośrednim miernikiem wkładu cyfry 1 umieszczonej na ostatniej pozycji ciągu. W konsekwencji jest to średni przyrost (w stosunku do średniej z populacji ogólnej) wynikający z obecności cyfry 1 na tej pozycji. Podobne wnioski można wyciągnąć w odniesieniu do pozostałych współczynników partycyjnych rzędu 1 (e2 i e4) oraz ich wpływu na wskaźniki przystosowaniakonkurującychschematów:
/(*O*) = e0-e2 , , ,.
/(l**) = e0+e4 ' • • - •
/(0**) = e0-L4 ^ -
Teraz niemal samo nasuwa się rozpatrzenie schematów wyższego rzędu. Możemy myśleć o konstruowaniu przybliżeń niskiego rzędu dla schematów wyższego rzędu, sumując przyrosty (lub ubytki) w stosunku do średniego przystosowania po wszystkich schematach pierwszego rzędu. Na przykład, ponieważ schemat * 11 jest przecięciem schematów *1* i **1, przybliżenie pierwszego rzędu dla przystosowania tego schematu znajdziemy, biorąc sumę e, i e2 i dodając ją do średniego ogólnego przystosowania (e()). Używając daszka (^) dla zaznaczenia, że mamy do czynienia z wartością przybliżoną, otrzymujemy następujący związek:
D.4. Zastosowanie współczynników partycyjnych do analizy problemów zwodniczych
379
Porównując to z dokładnym wzorem na przystosowanie schematu *11, otrzymamy różnicę między przybliżeniem pierwszego rzędu a wartością dokładną: , ; .
W tym przypadku współczynnik partycyjny drugiego rzędu, 83, opisuje wkład do przystosowania wynikający z epistatycznej interakcji bitów na dwóch ostatnich pozycjach. Ogólnie, możemy wyjaśnić rolę odgrywaną przez wyższe współczynniki partycyjne. Określają one wkład do przystosowania wnoszony przez interakcje epistatyczne pewnych konfiguracji dwóch lub więcej bitów. Rozwinięcie idei przybliżeń wyższych rzędów dla wskaźników przystosowania schematów nie przedstawia większych trudności. Zamiast się tym zajmować, przejdziemy do zbadania roli współczynników partycyjnych w analizie i konstrukcji problemów AG-zwodniczych.
D.4. Zastosowanie współczynników partycyjnych ___________do analizy problemów zwodniczych
Współczynniki partycyjne opisują efekty nieliniowe związane z funkcją odwzorowującą wektory binarne w zbiór liczb rzeczywistych. Chociaż jest to samo w sobie rzeczą interesującą, w studiach poświęconych algorytmom genetycznym współczynniki partycyjne są wykorzystywane głównie w dwóch celach: do zbadania, czy dany problem jest AG-zwodniczy, oraz do konstrukcji takich problemów. W tym punkcie zapoznamy się z prostymi przykładami analizy zwodniczości.
Analiza zwodniczości jest zadaniem bardzo prostym. Rozważmy nasz trzybitowy przykładowy problem. Czy potrafimy powiedzieć na podstawie znajomości współczynników e; czy funkcja/jest zwodnicza? Ponieważ punktem optymalnym jest 111, więc aby wystąpiła zwodniczość, musiałby istnieć pewien schemat zawierający 0, o wyższym przystosowaniu niż konkurujące z nim schematy zawierające tylko gwiazdki i jedynki. W przypadku schematów pierwszego rzędu musiałaby więc zachodzić przynajmniej jedna z następujących nierówności:
/(**D /(*1*) /0**)W
stać:
terminach współczynników partycyjnych nierówności te przyjmują równoważną po-ń:
e, <0 e2<0 e,<0
380
D. Transformacja współczynników partycyjnych
Sprawdzając tabele wartości współczynników e,, stwierdzamy, że żaden z nich nie jest ujemny, a zatem zwodniczość problemu nie może być pierwszego rzędu ^ednobitowa). Możemy następnie wypisać dodatkowe nierówności dla schematów drugiego rzędu; i znów w tym przypadku żadna z nich nie okaże się myląca. Wyciągamy stąd wniosek, że nasz problem nie jest zwodniczy i wobec tego powinien być podatny na rozwiązanie za pomocą elementarnego algorytmu genetycznego. Gdybyśmy stwierdzili, że co najmniej jeden z warunków zwodniczości jest spełniony, moglibyśmy podejrzewać, że mamy do czynienia z problemem AG-trudnym. Aby to potwierdzić, należałoby jednak przeprowadzić dalszą analizę, gdyż funkcja AG-zwodnicza nie musi być AG-trudna Qak w przypadku minimalnego problemu zwodniczego), natomiast funkcja AG-trudna jest zawsze AG-zwodnicza ".
D.5. Konstruowanie problemów AG-zwodniczych za pomocą współczynników partycyjnych _
Badanie, czy dany problem jest zwodniczy, jest rzeczą użyteczną, ale chcielibyśmy także wiedzieć, jak konstruować problemy częściowo lub całkowicie zwodnicze. Jest to nietrudne do osiągnięcia przy użyciu współczynników partycyjnych. W tym punkcie naszkicujemy wyprowadzenie niezbędnych warunków optymalności i zwodniczości.
Załóżmy, jak poprzednio, że punkt 111 jest optymalny. Wynika stąd siedem nierówności postaci/,|]>/o/(x,, itd. Korzystając z transformacji współczynników partycyjnych, możemy je wyrazić w postaci:
e2+e3-
e,+L2-
0 0
0
0
e2+e3 + e4+e5
ei p r p i p t T^ 09 T^ C^ T^ 07
0 0
Te siedem warunków optymalności należy uzupełnić co najmniej jednym warunkiem zwodniczości, aby wprowadzić zwodnicze efekty nieliniowe. Dla zwodniczości pierwszego rzędu potrzeba spełnienia co najmniej jednego z następujących warunków:
0 Niedawno pojawiły się doniesienia na temat istnienia funkcji nie spełniających warunku zwodniczości, dla których algorytmy genetyczne zachowują się źle. (S. Forrest, M. Mitchell: What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation, Machinę Learning, 13 (1992)) . tlum.).
D.7. Zadania
381
e, <0
E2<0 ., • ,. ,. • '
84<0 ,-.-, .r. ,. •
W przypadku zwodniczości drugiego rzędu musi być spełniony jeden lub więcej z następujących układów warunków:
, + e2<0;
, + e4 < 0; 2 + e4 < 0;
0; 0;
0; 0;
_ ( + e6<0; e2 + e6<0; -^
Konstrukcję konkretnego problemu zwodniczego pozostawiamy jako ćwiczenie.
D.6. Podsumowanie
W tym dodatku przedstawiliśmy metodę analizy statycznej schematów za pomocą współczynników partycyjnych Hollanda. Procedura ta umożliwia bezpośrednią analizę wskaźników przystosowania schematów dla zadanej funkcji przystosowania i danego kodu. Umożliwia również konstrukcję funkcji o określonej epistazie. Badania tego typu pozwalają rzucić więcej światła na problem doboru funkcji, kodu i operacji genetycznych w celu osiągnięcia większej efektywności algorytmu genetycznego.
D.7. Zadania
D.1. Wyznacz współczynniki partycyjne dla funkcji/(*) = (*-3,5)2 (określonej na zbiorze {0, 1, ..., 7}), jeśli parametr x jest kodowany przy użyciu trójpozycyjnego zapisu dwójkowego. Co można powiedzieć o wszystkich współczynnikach rzędu 1? Dlaczego?
D.2. Oblicz współczynniki partycyjne dla funkcji/(*, y, z) = 10+* + 2y + 4z, gdzie x, y i z są zmiennymi dwuwartościowymi o dziedzinie {-l, 1}, jeżeli układ parametrów (x, y, z) jest kodowany w postaci ciągu z'y'x', gdzie operacja primowania oznacza odwzorowanie 1 > 1, -1 ^ 0. Co można powiedzieć o wszystkich współczynnikach partycyjnych rzędu 2 i 3 i dlaczego?
D.3. Uogólnij wyniki zadania D.2 na przypadek dowolnej /-argumentowej funkcji liniowej postaci/(*!, ..., xj) = ^,atx, + b, gdzie xte {-l, 1} i kodu postaci x',x',_\ ...x'2x'h przy czym x'<= {0, 1}.
D.4. Oblicz współczynniki partycyjne dla funkcji/(*, y, z)=\Q+x + 2y + 4z-xy + 2yz--xyz, gdzie x, y i z są zmiennymi dwuwartościowymi o dziedzinie {-l, 1}, jeżeli układ parametrów (*, y, z) jest kodowany w postaci ciągu z 'y 'x', przy czym *', y', z'e {0, 1}. Jaki związek zachodzi między współczynnikami wielomianu a wartościami współczynników partycyjnych? Czy jest to zależność ogólna?
382
D. Transformacja współczynników partycyjnych
D.5. Stwierdziliśmy wcześniej, że współczynnik partycyjny rzędu 3 (e7) dla funkcji f(x)=x1 przy dwójkowym zapisie pozycyjnym jest równy zeru. Pokaż, że jest tak dla dowolnej funkcji kwadratowej f(x).
D.6. Oblicz współczynniki partycyjne dla funkcji/(*)=* przy czterobitowym kodzie Graya dla nieujemnych liczb całkowitych. Jaki jest w tym przypadku najwyższy rząd nieliniowości?
D.7. Skonstruuj trzybitową funkcję zwodniczą, która jest zwodnicza pierwszego rzędu na każdej z trzech pozycji oraz zwodnicza drugiego rzędu na dwóch najmniej znaczących pozycjach. Zdefiniuj funkcję, podając jej wartości we wszystkich ośmiu punktach. Przyjmij, że/ln jest maksimum globalnym.
D.8. Ćwiczenia komputerowe
A. Napisz program komputerowy do obliczania wskaźników przystosowania dowolnego ciągu kodowego lub schematu przy zadanych współczynnikach partycyjnych.
B. Napisz program komputerowy do obliczania współczynników partycyjnych e, przy zadanych wskaźnikach przystosowania ciągów kodowych f,.
C. Oblicz współczynniki Walsha dla pewnej funkcji metodą szybkiej transformaty Walsha. Porównaj współczynniki Walsha ze współczynnikami partycyjnymi obliczonymi za pomocą programu z ćwiczenia B.