Zastosowanie algorytmów ewolucyjnych

w minimalizacji funkcji logicznej.

Autor:

Karina Murawko

Spis treści

1 Teoria ewolucji w informatyce.

2 Algorytmy genetyczne.

1. Wprowadzenie.

2. Podstawowe zasady.

1. Kodowanie.

2. Funkcja fitness.

3. Reprodukcja.

4. Zbieżność.

3. Schematy.

4. Porównanie z innymi metodami.

3 Minimalizacja funkcji logicznych.

1. Ujęcie ogólne.

2. Minimalizacja funkcji logicznych w klasie wielomianów Reeda-Mullera.

1. Opis wielomianów Reeda-Mullera.

2. Minimalizacja określonych funkcji logicznych w klasie wielomianów R-M.

3. Algorytm genetyczny minimalizacji częściowo określonych funkcji logicznych w klasie wielomianów Reeda-Mullera.

4. Minimalizacja funkcji boolowskiej częściowo określonej - symulacja odręczna.

4 Podsumowanie.

• Teoria ewolucji w informatyce.

W systemach, które do rozwiązywania zadań stosują zasady ewolucji i dziedziczności występuje populacja potencjalnych rozwiązań. Ponadto zawierają one proces selekcji, oparty na dopasowaniu osobników oraz pewne operatory „genetyczne”. Jednym z typów takich systemów jest klasa strategii ewolucyjnych, to znaczy algorytmów naśladujących zasady ewolucji w przyrodzie przy rozwiązywaniu zadań optymalizacji parametrycznej (Rechenberg, Schwefel). Programowanie ewolucyjne Fogla jest metodą przeszukiwania przestrzeni stanów małych automatów o skończonej pamięci. Metody przeszukiwania rozproszonego Glovera utrzymują populację punktów odniesienia i generują potomstwo za pomocą ich liniowych kombinacji. W 1990 roku Koza zaproponował system oparty na zasadach ewolucji, zwany programowaniem genetycznym, w którym poszukuje się programu komputerowego najlepiej dopasowanego do rozwiązania danego zadania. Innym typem systemów używających zasad ewolucji są algorytmy genetyczne Hollanda.

• Algorytmy genetyczne.

2.1 Wprowadzenie.

Algorytmy Genetyczne (Genetic Algorithms) są metodami adaptacyjnymi, które mogą być używane w rozwiązywaniu problemów poszukiwań i optymalizacji. Opierają się na genetycznych procesach biologicznych organizmów. Przez wiele pokoleń naturalne populacje ewoluowały zgodnie z zasadami doboru naturalnego i przeżycia jednostek najlepiej przystosowanych, sformułowanymi pierwszy raz przez Karola Darwina w dziele „O powstawaniu gatunków” („The Origin of Species”). Naśladując ten proces algorytmy genetyczne są w stanie wyewoluować rozwiązanie problemów zaczerpniętych z rzeczywistego świata, jeśli zostały one wcześniej właściwie zakodowane.

Za początek algorytmów genetycznych przyjmuje się prace biologów (Barricelli 1957, Fraser 1960), którzy symulowali procesy genetyczne przy pomocy komputerów. Chociaż nie myślano wtedy o zastosowaniu tych symulacji do rozwiązywania problemów matematycznych, nie były one zbyt odległe od współczesnego rozumienia GA. Podwaliny pod zastosowania algorytmów genetycznych w zagadnieniach sztucznej adaptacji położył Holland podczas prac nad systemami adaptacyjnymi. Od tej pory zaczęto używać algorytmów genetycznych w coraz szerszej klasie zastosowań.

W 1970 zastosowano je do systemu rozpoznającego postacie ludzkie (przykład problemu nierozwiązywalnego tradycyjnymi metodami). W 1971 pojawiła się pierwsza praca badająca skuteczność AG do optymalizacji funkcji (Hollstein). Do dziś GA znalazły setki nowych zastosowań.

Algorytmy genetyczne symulują procesy istotne dla ewolucji. W przyrodzie, jednostki w populacji rywalizują ze sobą o zasoby takie jak jedzenie, woda i schronienie. Także osobniki tego samego gatunku często konkurują o partnerów. Jednostki, które osiągają najlepsze rezultaty w przystosowaniu się i przyciąganiu partnerów, będą miały stosunkowo dużą liczbę potomków. Natomiast słabsze osobniki będą produkowały niewiele potomstwa lub wcale nie będą go posiadały. Oznacza to, że geny jednostek dobrze zaadaptowanych rozprzestrzenią się w rosnącą liczbę osobników kolejnych generacji. Kombinacja korzystnych cech różnych przodków może doprowadzić do wyprodukowania „najlepiej przystosowanego potomka”, tzn. lepiej przystosowanego niż jego rodzice. W ten właśnie sposób gatunki ewoluują, aby jak najlepiej przystosować się do swojego środowiska. GA działają na zasadzie dokładnej analogii do naturalnego zachowania. Pracują na populacji osobników, z których każdy stanowi możliwe rozwiązanie postawionego problemu.

Ważną zaletą algorytmów genetycznych, jest fakt że potrafią one poradzić sobie z szerokim zakresem problemów. Nie gwarantują one otrzymania globalnego optymalnego rozwiązania, ale w rzeczywistym czasie („akceptowalnym”) znajdują rozwiązanie „wystarczająco dobre” (tzn. możliwe do zaakceptowania rozwiązanie przybliżone). Jeśli istnieją wyspecjalizowane techniki do rozwiązywania określonych problemów to będą one prawdopodobnie osiągać lepsze wyniki niż GA (zarówno dotyczące czasu jak i jakości rozwiązania). Dlatego też główną dziedziną zastosowania GA są te obszary, dla których takie techniki nie istnieją. Ponadto można ulepszyć techniki specjalizowane tworząc ich hybrydy z algorytmami genetycznymi.

1. Podstawowe zasady.

Zanim algorytm genetyczny zostanie uruchomiony konieczne jest określenie odpowiedniej reprezentacji parametrów rozwiązywanego problemu, funkcji fitness (ang. fitness function, zwanej funkcją celu lub oceny) oraz metod selekcji i operatorów genetycznych. Klasyczny algorytm genetyczny może być przedstawiony w sposób pokazany na rys. 1.

BEGIN /* algorytm genetyczny */

wygeneruj początkową populację

określ przystosowanie każdego osobnika

WHILE NOT warunek_zakończenia DO

BEGIN /* wytwórz nowe pokolenie */

FOR rozmiar_ populacji / 2 DO

BEGIN /* cykl reprodukcyjny */

wybierz dwa osobniki z poprzedniego pokolenia w celu rozmnożenia

/* wybieraj osobniki lepiej przystosowane */

skrzyżuj te dwa osobniki, żeby otrzymać dwóch potomków

oblicz przystosowanie otrzymanych potomków

umieść potomków w nowej populacji

END

IF populacja jest zbieżna THEN

warunek_zakończenia := TRUE

END

END

Rys. 1. Klasyczny algorytm genetyczny.

1. Kodowanie.

Zakłada się, że potencjalne rozwiązanie problemu może być przedstawione jako zbiór parametrów. Te parametry - zwane genami - łączone są razem w ciąg (łańcuch) wartości - chromosom. Według Hollanda idealnym alfabetem do zapisu chromosomu jest alfabet binarny, ale istnieją również inne możliwości m.in. reprezentacja w postaci wektora całkowitoliczbowego. Przykładowo jeżeli zadanie polega na maksymalizacji funkcji trzech zmiennych: F(x,y,z) to możemy każdą zmienną przedstawić jako 10-bitową liczbę (odpowiednio wyskalowaną). Wówczas nasz chromosom będzie zawierał 3 geny czyli 30 cyfr binarnych.

W genetycznej terminologii zbiór parametrów reprezentowany przez konkretny chromosom nosi nazwę genotypu. Genotyp zawiera informację wymaganą do skonstruowania organizmu, który określa się mianem fenotypu. Tych samych określeń używa się w dziedzinie algorytmów genetycznych.

Na przykład w zadaniu projektowania mostu zbiór parametrów opisujących dany projekt to genotyp, natomiast skończona konstrukcja będzie fenotypem. Przystosowanie osobnika zależy od wyników osiąganych przez fenotyp i może być wywnioskowane z genotypu - tj. może być obliczone z chromosomu przy użyciu funkcji przystosowania.

2. Funkcja fitness.

Funkcja fitness musi być zaprojektowana dla każdego rozwiązywanego problemu. Po wykonaniu działań na danym chromosomie funkcja fitness zwraca pojedynczą numeryczną wartość przystosowania („fitness”) lub liczbę wartości („figure of merit”). Otrzymany wynik powinien być proporcjonalny do „użyteczności” lub „zdolności” osobnika reprezentowanego przez ten chromosom.

Dla wielu problemów jest oczywiste co powinna mierzyć funkcja fitness, w szczególności w zadaniach optymalizacji funkcji będzie to po prostu jej wartość. Inaczej będzie w przypadku optymalizacji kombinacyjnej. Przykładowo przy rzeczywistym projektowaniu mostu wiele parametrów może być poddanym optymalizacji: stosunek siła / waga, rozpiętość, szerokość, maksymalne obciążenie, koszty, czas budowy - czy, co jest bardziej prawdopodobne, kombinacja wszystkich tych parametrów.

3. Reprodukcja.

Podczas reprodukcyjnej fazy GA z populacji są wybierane osobniki, na których dokonuje się rekombinacji, powstałe potomstwo będzie tworzyć następne pokolenie. Z populacji rodzice są wybierani losowo przy użyciu schematu faworyzującego lepiej przystosowane osobniki. „Dobre” osobniki będą przypuszczalnie wybrane kilka razy, natomiast „złe” mogą w ogóle nie być wybrane .

Operację selekcji można zrealizować na wiele sposobów. Jednym z najprostszych jest symulacja odpowiednio wykalibrowanej tarczy obrotowej, tzw. ruletki. Każdemu ciągowi kodowemu (chromosomowi) odpowiada sektor o rozmiarze proporcjonalnym do przystosowania. Rozpatrzmy działanie tego algorytmu w oparciu o następujący przykład (tab. 1.): weźmy dowolne 4 ciągi 5-bitowe. Niech każdy z nich reprezentuje liczbę całkowitą zapisaną w systemie dwójkowym, natomiast funkcja celu niech będzie kwadratem liczby reprezentowanej przez chromosom.

Nr	Ciąg kodowy	Przystosowanie	% całości
1	01101	169	14,4
2	11000	576	49,2
3	01000	64	5,5
4	10011	361	30,9
Łącznie		1170	100,0

Tablica 1. Ciągi kodowe i ich wskaźniki przystosowania w przykładowym zadaniu.

Suma wskaźników przystosowania wszystkich czterech ciągów kodowych wynosi 1170. W tablicy 1. Są także podane udziały procentowe poszczególnych ciągów. Tarcza używana w procesie reprodukcji została pokazana na rys. 2:

Rys. 2. Tarcza ruletki widoczna na rysunku została

skomponowana wg danych z tab. 1.

Reprodukcji dokonujemy czterokrotnie uruchamiając ruletkę. W naszym przykładzie chromosom nr 1 ma wskaźnik przystosowania 169, co odpowiada 14,4% sumarycznej wartości. Na ciąg ten przypada zatem 14,4% obwodu koła, tak więc w każdej próbie prawdopodobieństwo otrzymania ciągu nr 1 wynosi 0,144. Za każdym razem, gdy jest potrzebny nowy potomek, uruchamiamy ruletkę wybierając jednego z kandydatów do reprodukcji. Dokonujemy tego w następujący sposób: losujemy liczbę z przedziału [0 ; 1], zaś chromosomom przypisujemy określone rozłączne podprzedziały tego przedziału (np. ciąg nr 1 - (0 ; 0,144), ciąg nr 2 - (0,144 ; 0,636), gdzie 0,636 = 0,144 + 49,2 itd.). Dzięki temu lepiej przystosowane ciągi kodowe wprowadzają większą liczbę potomków do następnego pokolenia. Dla każdego ciągu wybranego do reprodukcji tworzymy dokładną replikę, która zostaje następnie włączona do nowego pokolenia pośredniego, stanowiącego pulę rodzicielską (mating pool) w dalszych operacjach genetycznych.

Następnie możemy przejść do krzyżowania i mutacji. Podstawowym typem krzyżowania jest tak zwane krzyżowanie proste (simple crossover), które przebiega w dwóch etapach. W pierwszej fazie kojarzymy w sposób losowy osobniki z puli rodzicielskiej w pary. Potem, każda para przechodzi proces krzyżowania, który zachodzi z określonym z góry prawdopodobieństwem (zazwyczaj od 0.6 do 1.0, przy czym jeśli krzyżowanie nie zajdzie potomstwo jest tworzone poprzez duplikację rodziców). Krzyżowanie odbywa się następująco: wybieramy w sposób losowy (z jednakowym prawdopodobieństwem) jedną z pozycji (punkt krzyżowania k) spośród l -1 początkowych pozycji w ciągu kodowym (gdzie l jest długością ciągu), po czym zamieniamy miejscami wszystkie znaki od pozycji k+1 do l włącznie w obu elementach pary, tworząc w ten sposób dwa nowe ciągi. Rozważmy, dla zobrazowania, dwa ciągi z przykładowej populacji początkowej (oznaczone jako: RODZICE):

punkt krzyżowania k = 3

RODZICE: 0 1 1 | 0 1 1 1 0 | 0 0

POTOMSTWO: 0 1 1 0 0 1 1 0 0 1

Przypuśćmy, że wybierając losowo jedną z liczb od 1 do 4 (l = 5), otrzymaliśmy k = 3 (co zaznaczono wyżej za pomocą kreski pionowej | ). Odpowiednia operacja krzyżowania daje dwa nowe ciągi wchodzące w skład nowego pokolenia (POTOMSTWO).

Mechanizmy reprodukcji i krzyżowania są niezwykle proste, obejmują generowanie liczb losowych, kopiowanie ciągów i wymianę podciągów. Swą siłę algorytmy genetyczne zawdzięczają w głównej mierze efektowi współdziałania reprodukcji i uporządkowanej (chociaż zrandomizowanej) wymiany informacji przez krzyżowanie.

Skoro reprodukcja według przystosowania w połączeniu z krzyżowaniem decydują w przeważającej mierze o mocy obliczeniowej algorytmów genetycznych, to warto byłoby rozpatrzyć jaką rolę odgrywa w nich operacja mutacji. Możemy stwierdzić, że jest to rola drugorzędna. Z drugiej strony jednak operacja mutacji jest niezbędna w działaniu algorytmów genetycznych, ponieważ reprodukcja i krzyżowanie, mogą niekiedy wyeliminować obiecujący materiał genetyczny (zera lub jedynki na określonych pozycjach ciągu kodowego). W sztucznych systemach genetycznych mutacja zapobiega takim bezpowrotnym stratom. W elementarnym algorytmie genetycznym mutacja polega na sporadycznej (tj. zachodzącej z niewielkim prawdopodobieństwem - najczęściej około 0.001), przypadkowej zmianie wartości ciągu kodowego. W przypadku kodu binarnego oznacza to po prostu zamianę jedynki na zero i na odwrót. Sama w sobie, mutacja jest błądzeniem przypadkowym w przestrzeni ciągów kodowych. Stosowana oszczędnie, jako dodatek do reprodukcji i krzyżowania, zabezpiecza przed utratą ważnych składników rozwiązania.

4. Zbieżność.

Jeśli algorytm genetyczny został poprawnie zaimplementowany, populacja będzie ewoluować w taki sposób, że przystosowanie najlepszego i przeciętnego (średnie) osobnika będzie zbliżać się do globalnego optimum. Zbieżność jest postępem w kierunku wzrastającej uniformizacja (wśród osobników). Gen określa się mianem zbieżnego, jeżeli 95% populacji ma tę samą wartość. Natomiast populacja jest określana jako zbieżna gdy wszystkie geny są zbieżne.

Przystosowanie w typowym GA zmienia się w następujący sposób: gdy populacja zbiega się, średnie przystosowanie osiąga wartość przystosowania najlepszego osobnika.

2. Schematy.

Teoria schematów Hollanda była pierwszym dokładnym wyjaśnieniem działania algorytmów genetycznych. Schemat to wzorzec opisujący podzbiór ciągów podobnych ze względu na ustalone pozycje. Jeżeli pracujemy z alfabetem dwójkowym: {0, 1} to schemat będzie reprezentowany przez ciąg znaków w alfabecie trójkowym: {0, 1, #}, w którym symbol # oznacza cokolwiek - w naszym przypadku 0 lub1. Dany ciąg zawiera dany schemat, gdy zgadzają się ich symbole na pozycjach ustalonych (różnych od #), np. chromosom „1010” zawiera , między innymi, następujące schematy: „10##”, „#0#0”, „##1#” oraz „101#”. Rzędem schematu nazywamy liczbę ustalonych pozycji we wzorcu (w powyższym przykładzie odpowiednio 2, 2, 1, 3). Natomiast rozpiętością schematu nazywamy odległość między dwiema skrajnymi pozycjami ustalonymi (w powyższym przykładzie odpowiednio 2, 3, 1, 3).

Skuteczność algorytmów wynika z faktu, że selekcja zwiększa liczbę łańcuchów pasujących do schematu (krótkiego, niskiego rzędu) ocenianego powyżej średniej („dobrze” przystosowanego) i że ta zmiana jest wykładnicza (twierdzenie o schematach). Sama selekcja nie wprowadza nowych schematów. To jest właśnie przyczyna wprowadzenia operacji krzyżowania - aby umożliwić ukierunkowaną, ale jednocześnie losową wymianę informacji genetycznej. Dodatkowo operator mutacji wprowadza większą zmienność w populacji.

Ponadto z hipotezy o blokach budujących wynika, iż GA poszukuje działania zbliżonego do optymalnego przez zestawianie krótkich, niskiego rzędu schematów o dużej wydajności działania, zwanych blokami budującymi.

3. Porównanie z innymi metodami.

Obecnie wyróżnia się trzy główne rodzaje metod optymalizacji i poszukiwania: analityczne, enumeratywne (przeglądowe) oraz losowe.

Metody analityczne dzielą się w ogólności na dwie klasy: metody pośrednie i bezpośrednie. W metodach pośrednich poszukujemy lokalnych ekstremów rozwiązując układ równań (zazwyczaj nieliniowych) otrzymanych przez przyrównanie gradientu funkcji celu do zera. Metody bezpośrednie poszukiwania lokalnego maksimum polegają na „skakaniu” po wykresie funkcji w kierunku wyznaczonym przez lokalny gradient. Zgodnie z zasadą górskiej wspinaczki (hillclimbing): aby dostać się na (lokalny) wierzchołek, wspinaj się po zboczu wzdłuż najbardziej stromej z możliwych dróg.

Obie metody mają zakres lokalny, szukają bowiem optymalnego rozwiązania w sąsiedztwie danego punktu, dlatego osiągając lokalne optimum możemy przeoczyć globalne rozwiązanie. Ponadto zastosowanie metod analitycznych jest uzależnione od istnienia pochodnych. Metody te muszą być dostosowywane dla każdego zadania z osobna i nie można ich użyć w niezmienionej postaci do rozwiązania różnych zadań.

Idea metod enumeracyjnych jest prosta: mając skończoną przestrzeń poszukiwań (lub dyskretny odpowiednik przestrzeni nieskończonej), algorytm oblicza wartości funkcji celu, przeglądając po kolei wszystkie punkty przestrzeni. Algorytm działania jest prosty, ale bardzo nieefektywny, gdyż w wielu spotykanych w praktyce przypadkach mamy do czynienia z przestrzeniami, które są zbyt wielkie na to, by sprawdzanie wszystkich ich elementów po kolei mogło zakończyć się znalezieniem użytecznej odpowiedzi. Nawet programowanie dynamiczne załamuje się na zadaniach o umiarkowanym rozmiarze i złożoności z powodu tzw. „przekleństwa wymiaru”. Z drugiej strony jednak główną zaletą tych metod jest to, że jako jedyne metody zawsze dają gwarancję na to, że znalezione przez nie rozwiązanie jest globalnie najlepsze (nie ma rozwiązania lepszego).

Błądzenie przypadkowe i inne schematy poszukiwania losowego oparte na szukaniu i zapamiętywaniu najlepszego rozwiązania są również wysoce nieefektywne. W odróżnieniu od nich algorytmy genetyczne należą do technik zrandomizowanych. W GA wybór losowy jest narzędziem do ukierunkowania procesu poszukiwań. Podobnie w innej technice poszukiwania, zwanej symulowanym wyżarzaniem (simulated annealing), używa się procesów losowych w celu określenia kierunku poszukiwań stanów o minimalnej energii.

Metody stosowane przez algorytmy genetyczne polegają na samo-dostosowaniu (adaptacji) reguł przeszukiwania przestrzeni rozwiązań do konkretnego zadania. Dzieje się to w sposób automatyczny, bez zaangażowania człowieka. Dzięki temu mogą one być stosowane bez zmian do różnych zadań. Ich dodatkową zaletą jest to, że prowadzą poszukiwania globalnie najlepszego rozwiązania (są odporne na lokalne maksima - mechanizm mutacji). Metody stosowane przez algorytmy genetyczne są metodami odpornymi.

• Minimalizacja funkcji logicznych.

1. Ujęcie ogólne.

Minimalizacja form funkcji logicznych jest procesem polegającym na przekształcaniu form funkcji logicznych w celu otrzymania możliwie najprostszych postaci końcowych. Minimalne formy funkcji logicznej mają szczególne praktyczne zastosowanie przy optymalizacji układowej w procesie projektowania układów logicznych.

Istnieje wiele kryteriów minimalizacji form funkcji logicznych, z których najczęściej stosowane wynika z dążenia do minimalizacji kosztu (poprzez zmniejszenie złożoności układowej) projektowanego układu i formułuje się następująco:

• minimalna forma zawiera minimalną liczbę produktów, oraz

• żaden z produktów nie może być zastąpiony przez inny o mniejszej liczbie literałów.

Istnieje wiele metod minimalizacji funkcji logicznych: m. in. techniki z zastosowaniem diagramów decyzyjnych, przy pomocy map Karnaugha, metoda Quine'a-McClaskeya oraz Tabu-wyszukiwanie. Do minimalizacji funkcji logicznych możemy również stosować algorytmy genetyczne.

1. Minimalizacja funkcji logicznych w klasie wielomianów Reeda-Mullera.

Każda funkcja logiczna może być przedstawiona przy użyciu operacji NOT, AND i EXOR, algebra związana z taką postacią funkcji logicznej to algebra Reed-Mullera. Upraszczanie funkcji logicznych w tej dziedzinie jest znacznie trudniejsze, ponieważ reguły algebraiczne pozwalają na opisanie jednej funkcji za pomocą różnych reprezentacji, z drugiej strony prowadzi to często do bardziej zwartych reprezentacji.

Ponadto układy realizujące funkcje logiczne w postaci wielomianów R-M nie wymagają skomplikowanych testów i posiadają, w porównaniu z innymi formami przedstawienia funkcji, minimalną ilość produktów.

Problem wyszukiwania optymalnej realizacji formy Reed-Mullera dla danej funkcji logicznej można ogólnie podzielić na dwa zagadnienia: minimalizacja zupełnych i minimalizacja niezupełnych funkcji logicznych.

1. Opis wielomianów Reeda-Mullera.

Dla funkcji logicznej n zmiennych: f(X)=f(x₁, x₂, ..., x_n) najbardziej popularną formą kanoniczną jest wielomian R-M postaci:

gdzie:

Rozkład R-M, który też nazywa się formą kanoniczną ustalonej biegunowości, jest funkcją:

gdzie: jest biegunowością wielomianu,

natomiast:

c₁, c₂,..., c_n jest dwójkową reprezentacją c; c_j,∈ (0,1), j=1,...,n.

Jeżeli funkcja logiczna f(X) jest określona wektorem wartości :

to współczynniki wielomianu wyznacza się poprzez przekształcenie ortogonalne:

gdzie: jest wektorem współczynników wielomianu F_c(X),

jest macierzą prostego przekształcenia o rozmiarze

,która jest tworzona według wzoru:

gdzie '⊗' oznacza iloczyn Kronekera.

Przykładowo dla c=0 (polaryzacja zerowa) podstawowa macierz przekształcenia jest następująca:

2. Minimalizacja określonych funkcji logicznych w klasie wielomianów R-M.

Minimalizacja określonych funkcji logicznych w klasie wielomianów R-M polega na wyznaczeniu minimalnego wielomianu R-M, przy czym poszczególne wielomiany w tym wypadku różnią się od siebie biegunowością. Sprowadza się ona zatem do określenia biegunowości, której odpowiada minimalny wielomian R-M.

3. Algorytm genetyczny minimalizacji częściowo określonych funkcji logicznych w klasie wielomianów Reeda-Mullera.

GA minimalizujący częściowo określone funkcje logiczne można określić następująco - jako zbiór parametrów:

• populacja początkowa P⁰ składająca się z m osobników (m - rozmiar populacji można modyfikować),

• długość reprezentacji osobników l, która jest równa ilości nieokreślonych wartości funkcji minimalizowanej,

• operator selekcji,

• operator przekształcający geny na cechy,

• zbiór operatorów genetycznych zawierający krzyżowanie i mutację , przy czym wartość prawdopodobieństwa wystąpienia tych operacji jest również określona (odpowiednio p_k i p_m),

• funkcja przystosowania, która jest ilością zer w wektorze F współczynników wielomianu R-M wyznaczonym dla danego osobnika (wraz z określonymi wartościami badanej funkcji logicznej,

• warunek końca, sprawdzający czy ilość generacji jest równa maksymalnej ilości generacji.

Schemat działania oraz etapy algorytmu są zgodne z klasycznym GA, opisanym w punkcie 2.

1. Minimalizacja funkcji boolowskiej częściowo określonej - symulacja odręczna.

Dana jest funkcja boolowska 3 zmiennych, określona dla 4 wartości, zatem długość ciągu osobnika również wynosi 4 (l=8-4), przy biegunowości równej zero. Niech rozmiar populacji m=8, ilość generacji wynosi 2.

Funkcja jest dana wektorem prawdy, stany nieokreślone oznaczono jako d_i, gdzie i=1,...,4:

Zatem wektor F możemy określić następująco:

Wygenerowano 8 ciągów, o następujących wartościach funkcji fitness:

nr	Ciąg	f. fitness	% całości	przedział na kole ruletki
1	1011	5	14,29	(0,0000 ; 0,1429)
2	0010	4	11,43	(0,1429 ; 0,2572)
3	0101	3	8,57	(0,2572 ; 0,3429)
4	1111	5	14,29	(0,3429 ; 0,4858)
5	0001	5	14,29	(0,4858 ; 0.6287)
6	1110	6	17,14	(0,6287 ; 0.8001)
7	0100	4	11,43	(0,8001 ; 0,9144)
8	1001	3	8,57	(0,9144 ; 1,0000)

Wyniki ruletki: 0.4806, 0.8812, 0.2476, 0.4145, 0.7752, 0.3778, 0.1650, 0.7758. Zatem będziemy krzyżować następujące pary osobników: (4,7), (2,4), (4,6), (2,6).

Przyjmujemy, że p_k=1, zaś p_m=0.01 (krzyżowanie zajdzie dla każdej pary chromosomów, mutacji ulegnie 0.01*4*8=0.24 bit, czyli możemy przyjąć że mutacja nie zajdzie).

Losowo wybrano punkty krzyżowania k odpowiednio dla kolejnych par: (1,3,3,2).

Nr	Rodzice	Potomstwo	f. fitness potomstwa
4	1 | 1 1 1	0 1 1 1	3
7	0 | 1 0 0	1 1 0 0	4
2	0 0 1 | 0	0 0 1 1	3
4	1 1 1 | 1	1 1 1 0	6
4	1 1 1 | 1	1 1 1 0	6
6	1 1 1 | 0	1 1 1 1	5
2	0 0 | 1 0	0 0 1 0	4
6	1 1 | 1 0	1 1 1 0	6

Kończymy wykonywanie algorytmu - ilość generacji wynosi dwa. Warto zauważyć, że wzrosło sumaryczne przystosowanie całej populacji, od wartości 35 dla P⁰ do wartości 37 dla P¹.

W tym wypadku ciągi osobników potomnych nr 4, 5 i 8 (licząc od góry tabeli) określają optymalne uzupełnienie funkcji, to znaczy dają następujący wektor wartości funkcji X=[1 1 1 0 1 1 1 0]^T, któremu odpowiada wektor współczynników wielomianu R-M (przy biegunowości równej zero) F=[1 0 0 1 0 0 0 0]^T. Temu wektorowi odpowiada minimalna postać wielomianu R-M:

• Podsumowanie

Algorytmy genetyczne są często wykorzystywane przy rozwiązywaniu problemów optymalizacyjnych. W szczególności algorytmy te są kombinacją podejść deterministycznych jak i stochastycznych. Obecnie algorytmy genetyczne mają zastosowanie przy minimalizacji funkcji logicznych o małej ilości zmiennych.

Bibliografia:

1. Beasley D., Bull D.R., Martin R. R.: An overview of Genetic Algorithms: Part 1, fundamentals, University Computing, 15(2):58-69,1993

2. Goldberg D. E.: Algorytmy genetyczne i ich zastosowania, Wyd. NT, Warszawa 1996

3. Michalewicz Z.: Algorytmy genetyczne + struktury danych = programy ewolucyjne, Wyd. NT, Warszawa 1996

4. Stankiewicz W.: Opracowanie algorytmów genetycznych syntezy wielomianów dla częściowo określonych funkcji logicznych, Politechnika Szczecińska, Szczecin 1996

5. Wojciechowski D.: Genetyczny algorytm minimalizacji programowalnego układu PLA, Politechnika Szczecińska, Szczecin 1996

1

---