w minimalizacji funkcji logicznej.
1 Teoria ewolucji w informatyce.
2 Algorytmy genetyczne.
2.1 Wprowadzenie.
2.2 Podstawowe zasady.
2.2.1 Kodowanie.
2.2.2 Funkcja fitness.
2.2.3 Reprodukcja.
2.2.4 Zbieżność.
2.3 Schematy.
2.4 Porównanie z innymi metodami.
3 Minimalizacja funkcji logicznych.
3.1 Ujęcie ogólne.
3.2 Minimalizacja funkcji logicznych w klasie wielomianów Reeda-Mullera.
3.2.1 Opis wielomianów Reeda-Mullera.
3.2.2 Minimalizacja określonych funkcji logicznych w klasie wielomianów R-M.
3.2.3 Algorytm genetyczny minimalizacji częściowo określonych funkcji logicznych w klasie wielomianów Reeda-Mullera.
3.2.4 Minimalizacja funkcji boolowskiej częściowo określonej - symulacja odręczna.
4 Podsumowanie.
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 (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.
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
Rys. 1. Klasyczny algorytm genetyczny.
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.
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.
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
% 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.
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.
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...
Automation_Engineering