1. Podział algorytmów ewolucyjnych.

 Algorytmy Genetyczne GA są algorytmami wzorowanymi na ewolucji biologicznej, która jest bardzo skutecznym naturalnym systemem adaptacyjnym. Organizmy żywe nabywają swoje zdolności poprzez pozornie ślepy mechanizm - dobór naturalny. Stosowanie zasady doboru naturalnego - przeżywają i wydają potomstwo tylko jednostki najlepiej przystosowane - ułatwia projektowanie oprogramowania, ponieważ nie wymaga uprzedniej specyfikacji wszystkich szczegółów problemu i wszystkich działań, które powinien podjąć program. Od czasu opublikowania pracy J.Hollanda, obserwuje się stały wzrost zainteresowania Algorytmami Genetycznymi. Algorytmy Genetyczne AG = Poszukiwanie maksymalnej wartości funkcji przystosowania oparte na mechanizmach doboru naturalnego oraz dziedziczności. Łączy ewolucyjną zasadę przeżycia najlepiej przystosowanych   z systematyczną i po części losową wymianą informacji.

Strategie ewolucyjne (ES) powstały w wyniku badan optymalizacyjnych urządzeń mechanicznych metoda permutowania pewnego początkowego rozwiązania. Autorzy zauważyli, że zaproponowane podejście ma cechy podobieństwa do procesu ewolucji. W wyniku przeprowadzonych prac powstało wiele modeli strategii ewolucyjnych. Wśród nich można wymienić modele: (1+1) , (ì + l) i (ì, l) . W strategii (1+1) przetwarzane jest jedno rozwiązanie (osobnik), które w każdym kroku iteracji algorytmu jest modyfikowane losowo - tzn. nowe rozwiązanie generowane jest poprzez dodanie losowej liczby z rozkładem normalnym. W dalszym kroku algorytmu stare rozwiązanie jest zastępowane nowo powstałym, jeżeli wartość funkcji celu jest odpowiednio bardziej optymalna. Proces tworzenia poprzez losowa perturbacje zwany mutacja wykorzystuje mechanizm adaptacji zasięgu mutacji zwany reguła 1/5 sukcesów. W ogólności reguła ta zwiększa zasięg mutacji (perturbacji), jeżeli pewna założona liczba sukcesów perturbacji(kolejne nowo powstałe rozwiązania są bardziej optymalnie) jest większa niż 1/5 ogólnejliczby wykonywanych mutacji. Natomiast w przeciwnym przypadku zasięg perturbacji jestodpowiednio zmniejszony. Wartość 1/5 oraz pozostałe parametry zwiększania lub nie mutacjizostały zaproponowane na podstawie przeprowadzonych eksperymentów.

Programowanie ewolucyjne (EP) skonstruowano w rezultacie modelowania sztucznej inteligencji na drodze samoczynnej samoorganizacji. Problem rozwiązywany ta metoda dotyczył stworzenia gramatyki nieznanego języka na podstawie zestawu symboli i wyrażeń syntaktycznie poprawnych. Gramatykę modelowano za pomocą poszukiwanych w sposób ewolucyjny grafów złożonych ze stanów i funkcji przejść. Proces tworzenia nowego grafu polegał na perturbacji (mutacji) jego struktury np. poprzez dodanie/usuniecie stanu, zmianę początkowego stanu, zmianę funkcji wyjść lub przejść. W późniejszych badaniach programowanie ewolucyjne przeszło w stronę strategii ewolucyjnych jako kolejnych metod optymalizacji numerycznej.

Programowanie genetyczne, (GP) będące kolejnym przedstawicielem metod przetwarzania ewolucyjnego, stanowi nowy kierunek rozwoju algorytmów ewolucyjnych. W pierwszych badaniach próbowano znaleźć metodę, za pomocą której możliwe będzie automatyczne generowanie tekstów programów na podstawie znanych kryteriów oceny prawidłowości ich działania. W owych algorytmach parametry zadania optymalizacji są reprezentowane (kodowane) w postaci drzewiastych struktur. W węzłach takiego drzewa mogą występować symbole, wartości liczbowe, funkcje lub zmienne. Z kolei krawędzie drzew opisują wzajemne relacje pomiędzy węzłami. W drzewach takich mogą występować węzły terminalne (nie mające węzłów podrzędnych) oraz pośrednie (nieterminalne). Ponadto istnieje dokładnie jeden węzeł nadrzędny tzw. korzeń drzewa. W programowaniu genetycznym zestaw wartości stałych, zmiennych oraz funkcji jest określany a priori. Zadaniem takiego algorytmu jest poskładanie z owych elementów składowych takiego drzewa (rozwiązania), które pozwala osiągnąć najlepszy program. Nowe rozwiązania (drzewa) generowane są w ogólności poprzez proces wymiany części poddrzew oraz zmiany zawartości wybranego losowo węzła.

2. Optymalizacja a algorytmy ewolucyjne.

Optymalizacja: działanie mające na celu zwiększenie efektywności aż do osiągnięcia pewnego optimum. Cel główny: ulepszenie. Cel drugorzędny: osiągnięcie optimum.

Metody analityczne :

. pośrednie - szukamy lokalnych ekstremów, rozwiązując równania otrzymane w wyniku przyrównania do zera gradientu funkcji celu.

.bezpośrednie - poruszamy się w kierunku maksymalnego wzrostu/spadku funkcji celu.

Wady metod analitycznych:

. konieczna jest jawna znajomość funkcji celu

. lokalny zakres poszukiwań ekstremum

. założona różniczkowalność funkcji celu

Metody przeglądowe (wyliczeniowe, enumeracyjne).

Zalety

. brak ostrych założeń co do funkcji celu

Wady

. przestrzeń przeszukiwań musi być skończona

. niska efektywność co uwydatnia się w przypadku dużych przestrzeni przeszukiwań

Metody probabilistyczne ( losowe)

Polegają na losowym przeglądaniu przestrzeni

rozwiązań i zapamiętywaniu najlepszego rozwiązania.

Zalety

. brak ostrych założeń co do funkcji celu

Wady

niska efektywność

Metoda poszukiwania z tabu.metoda ta unika wielokrotnego powracania do już przejrzanych rozwiązań. Algorytm jest wyposażony wpamięć już odwiedzanych punktów. Punkty znajdujące się w pamięci są tabu - zakazane jest ponowne ich odwiedzenie. Aby tabu nie absorbowało zbyt dużo pamięci jest zapisywane w pamięci cyklicznej i wymazywane zgodnie z metodą FIFO.

3. Operacje gentyczne

Podstawowe operacje genetyczne:

Reprodukcja ogólnie zwiększa liczebność rozwiązań lepszych kosztem gorszych. Najczęściej stosowane metody reprodukcji to reprodukcja ruletkowa, rangowa i turniejowa.

Krzyżowanie pozwala na znalezienie rozwiązania zawierającego najlepsze cechy innych rozwiązań. W przypadku poszukiwania minimum funkcji można np. wymieniać wartości odpowiedających sobie współrzędnych lub wyznaczaćpunkty leżące na odcinku łączącym rozwiązania rodzicielskie.

Mutacja powinna umożliwiać znajdowanie nowych cech, w przypadku szukania minimum funkcji, nowych wartości współrzędnych, które mogą być nieosiągalne w inny sposób.

Inne modele genetyczne pomagające w zachowaniu najlepszych rozwiązań lub w zachowaniu różnorodności populacji:

Model elitarny - część populacji (najlepsze osobniki) przechodzi bez zmian do populacji potomnej.

Model niszowy - funkcja oceny każdego z rozwiązań jest uzupełniana o człon faworyzujący rozwiązania w dużym stopniu różniące się od pozostałych. To pozwala na utrzymanie większej różnorodności populacji (wypełnienia nisz) w celu zwiększenia szansy znalezienia właściwego obszaru poszukiwań (w niektórych przypadkach) lub pozwala zapobiec utracie istotnych rozwiązań jeśli inne rozwiązania są w jakiś sposób od nich zależne (np. stanowią podrozwiązania).

Model ze ściskiem - w ramach reprodukcji nowe rozwiązania zastępują rozwiązania, które mają jednocześnie małą wartość i są do nich podobne. Cel jest taki sam, co w modelu niszowym

4. Sposoby kodowania

W klasycznym algorytmie stosuje się kodowanie binarne chromosomów. Można stosować także kod Gray'a, który charakteryzuje się tym, że ciągi binarne odpowiadające dwóm kolejnym liczbom całkowitym różnią się jednym bitem. Taki sposób może okazać się uzasadniony ze względu na mutację Innym rodzajem jest kodowanie logarytmiczne używane jest w celu zmniejszenia długości chromosomów w algorytmie genetycznym. Pierwszy bit (a) ciągu kodowanego jest bitem znaku funkcji wykładniczej, drugi bit (b) jest bitem znaku wykładnika funkcji wykładniczej, a pozostałe bity (bin) są reprezentacją wykładnika funkcji wykładniczej gdzie [bin]10 oznacza wartość dziesiętną liczby zakodowanej w postaci ciągu binarnego bin.

[αβbin]=(-1)^βe^{(-1)α[bin]10}

5. Twierdzenie o schematach

Schematy w algorytmach genetycznych

Rzędem schematu o(S) jest liczba symboli różnych od # we wzorcu. Przykładowo dla schematu 0#101100# o(S)=7.

Długością definiującą schematu ( rozpiętością schematu) d((S)jest odległość pomiędzy skrajnymi pozycjami schematu różnymi od #.Przykładowo dla schematu 0#101100# δ(S)= 8-1=7.

W niektórych publikacjach rozpiętość jest definiowana jako odległość skrajnych określonych pozycji +1, co odpowiada liczeniu lewej skrajnej pozycji od 0 a nie od 1.

Twierdzenie o schematach

Schematy małego rzędu, o małej rozpiętości i o przystosowaniu powyżej średniej otrzymują rosnącą wykładniczo liczbę reprezentantów w kolejnych generacjach algorytmu genetycznego.

6. Nacisk selektywny

Wzajemny stosunek eksploatacji do eksploracji nacisk selektywny można regulować poprzez

- usuwanie najgorzej przystosowanych osobników,

- usuwanie osobników najbardziej podobnych do potomnych, należy przedtem wprowadzić miarę podobieństwa osobników,

- usuwanie losowo wybranych osobników.

7. Eksploatacja a eksploracja

Eksploatacja, czyli poszukiwanie lokalnego ekstremum funkcji przystosowania. Eksploatacja ma na celu poprawę wartości funkcji przystosowania kolejnej populacji.

Eksploracja poszukiwanie ekstremum globalnego. Zapewnia różnorodność genetyczną populacji

8. Metody selekcji

Selekcja następuje

1. Na etapie reprodukcji, czyli wyboru rodziców z populacji bazowej P do operacji genetycznych, w wyniku, których powstaje populacja tymczasowa T, dająca w rezultacie kolejnych operacji genetycznych populację potomną O.

2. Na etapie sukcesji, czyli tworzenia nowej populacji w oparciu o starą populację P i populację potomną O.

Jeżeli do nowej populacji wchodzą tylko osobniki z O to nie zawsze przejdą do następnej populacji najlepsze osobniki ze starej populacji bazowej. Wady tej nie ma selekcja elitarna, w której do następnego populacji bazowej przechodzą najlepsze osobniki ze starej populacji bazowej oraz z populacji O.

Reprodukcja proporcjonalna (metoda koła ruletki)

Prawdopodobieństwo wylosowania osobnika do reprodukcji jest wprost proporcjonalne do wartości jego funkcji przystosowania.

Reprodukcja rangowa

Każdemu osobnikowi w populacji bazowej nadaje się numer-rangę równą jego miejscu w uporządkowanej względem malejącej wartości funkcji przystosowania populacji.(Osobnik najlepszy ma rangę 1).Następnie definiuje się zmienną losową przypisując każdemu osobnikowi prawdopodobieństwo reprodukcji na podstawie jego rangi. Funkcja ta musi być nierosnąca względem rangi.

Reprodukcja Turniejowa

Wybieramy z jednakowym prawdopodobieństwem q osobników z populacji bazowej. Następnie z tak utworzonej populacji Q wybieramy najlepszego osobnika do populacji tymczasowej T. Proces powtarzamy aż do zapełnienia populacji T. Losowanie do populacji Q możemy prowadzić ze zwracaniem oraz bez zwracania. R Zazwyczaj q=2.

Reprodukcja elitarna

Gwarantuje ona przejście do następnego etapu osobników należących do określonego w pewien sposób zbioru E. Pozostałe osobniki są wybierane zgodnie z innymi zasadami, na przykład w oparciu o metodę koła ruletki.

SUKCESJA

Sukcesją nazywamy proces ustalania kolejnej populacji (n+1) w oparciu o poprzednią populację (n) oraz jej potomstwo. Sposób sukcesji powinien zapewnić spełnienie dwóch przeciwstawnych celów:

1. Poprawić wartość funkcji przystosowania kolejnej populacji. Odpowiada to tzw. eksploatacji, czyli poszukiwaniu lokalnego ekstremum funkcji przystosowania.

2. Zapewnić różnorodność genetyczną populacji, co w przyszłości zwiększa prawdopodobieństwo znalezienia estremu globalnego. Odpowiada to tzw eksploracji przestrzeni rozwiązań.

Wzajemny stosunek eksploatacji do eksploracji określa tzw nacisk selektywny.

Sukcesja z całkowitym zastępowaniem

Jest to najczęściej stosowanym sposobem tworzenia kolejnej populacji bazowej. Staje się nią cała populacja potomna. Sukcesja ta nie wprowadza mechanizmu nacisku selektywnego, ponieważ do kolejnej populacji nie muszą przechodzić najlepsze osobniki z poprzedniej populacji. W sukcesji takiej eksploracja przeważa nad eksploatacją.

Sukcesja z częściowym zastępowaniem

W najprostszym wariancie przyjmuje się współczynnik wymiany  owa populacja bazowa składa się z  osobników z populacji potomnej oraz z (1- osobników ze starej populacji bazowej. Część osobników ze starej populacji bazowej usuwamy korzystając z jednej z poniższych metod;

- usuwamy najgorzej przystosowane osobniki,

- usuwamy osobniki najbardziej podobne do potomnych, należy przedtem wprowadzić miarę podobieństwa osobników,

- usuwamy losowo wybrane osobniki.

Zmieniając współczynnik wymiany możemy regulować nacisk selektywny.

Sukcesja elitarna

Polega na tym, że cześć osobników ze starej populacji bazowej przechodzi do nowej populacji, w taki sposób, aby zagwarantować przeżycie, co najmniej najlepszego osobnika. Najpierw sortuje się populację bazową P^t i wybiera  najlepszych osobników tworząc populację P^t_η. W drugim kroku tworzy się następną populację bazową P^t+1 wybierając  najlepszych osobników z sumy populacji potomnej P^t i populacji P^t_η.

9. Język LISP

rodzina języków programowania z długą historią i charakterystyczną składnią. Lisp jest drugim z kolei pod względem wieku językiem programowania wysokiego poziomu pozostającym w użyciu (starszy jest tylko Fortran). Lisp powstał jako wygodna matematyczna notacja dla programów komputerowych, oparta na rachunku lambda. Szybko został najchętniej wybieranym językiem do badania i rozwoju sztucznej inteligencji.

Podstawową strukturą danych w Lispie jest lista. Kod źródłowy programów w Lispie składa się z list. W wyniku tego programy mogą manipulować kodem źródłowym jak zwykłą strukturą danych. Umożliwia to pisanie makr, pozwalających programiście tworzyć nową składnię lub nawet małe zagnieżdżone w Lispie języki.

Kod tworzony jako struktura danych sprawia, że Lisp ma charakterystyczną składnię. Cały kod źródłowy ma postać tzw. S-wyrażeń (S-expressions), czyli list otoczonych nawiasami. Wywołanie funkcji, makra lub formy specjalnej ma postać listy, której pierwszym elementem jest nazwa funkcji, a następnymi elementami - jej argumenty. Na przykład funkcję o nazwie f z argumentami a, b i c wywołuje się za pomocą kodu (f a b c).

Główne cechy:

-dynamiczne typowanie danych, ale z silną kontrolą typów

-wieloparadygmatowość- łączy wiele styli programowania: programowanie funkcyjne oraz programowanie obiektowe i refleksyjne

-Garbage collection, self - hosting compiler, język homologiczny

- wszystkie wyrażenia są zapisywane w notacji polskiej

-przejrzysta składnia oraz dynamiczne typowanie

-wyróżnia się 2 dialekty: Scheme oraz Common Lisp

Podstawy:

Podstawowymi elementami Lispa są listy i atomy. Każdym elementem listy jest albo lista, albo atom. Atomami są np. liczby, podstawowe operatory arytmetyczne (+ - * /), stałe znakowe czy dłuższe łańcuchy. W przypadku zagnieżdżania w sobie list mamy do czynienia z tzw. Ewaluacją.

10. Funkcja przystosowania

Funkcją przystosowania Ф(x) nazywamy odwzorowanie kodu x osobnika w wartość mówiąca o jego przystosowaniu do środowiska. Jeżeli szukamy wartości maksymalnej funkcji wielu zmiennych to funkcja przystosowania jest tożsama z funkcją, której ekstremum poszukujemy. Funkcja przystosowania pozwala ocenić stopień przystosowania (dopasowania) danego osobnika w populacji. Funkcja ta powala ocenić stopień przystosowania poszczególnych osobników w populacji i na tej podstawie wybrać osobniki najlepiej przystosowane, (czyli o najwyższej wartości funkcji przystosowania)

11. Programowanie genetyczne

Programowanie genetyczne (GP) to metoda automatycznego generowania rozwiązania programistycznego, dla problemu zadanego definicją wysokiego poziomu. Programowanie Genetyczne zaczyna od problemu zadanego w formie, „co ma być zrobione” i automatycznie tworzy program komputerowy, który rozwiązuje problem.

Programowanie Genetyczne (GP) to uogólnione określenie znaczące zazwyczaj ewolucyjny system przetwarzający, służący rozwiązywaniu problemów. Konwencjonalne Programowanie Genetyczne Koza'y zakłada reprezentację programów przez drzewa parsujące. Drzewo parsujące jest strukturą drzewiastą, która ujmuje kolejność wykonywania komponentów funkcjonalnych wewnątrz programu, w ten sposób, że wyjście program występuje w postaci korzenia; funkcje występują pod postacią węzłów a argumenty funkcji dane są w węzłach potomnych; symbole terminalne natomiast możemy odnaleźć w liściach. Drzewo parsujące oryginalnie było wyborem naturalnej struktury dla reprezentacji programów w języku LISP, używanym przez Koza'e na początku programowania genetycznego. To tylko jeden z powodów wyboru tej reprezentacji. Problem w programowaniu genetycznym jest charakteryzowany przez funkcję dopasowania, zbiór komponentów funkcjonalnych i wyrażeń terminalnych. Zbiór funkcji i terminali determinuje, z jakich komponentów program może się składać a funkcja dopasowania mierzy jak wyjście danego programu jest bliskie oczekiwanemu wyjściu (wynikowi). Inicjująca populacja składa się z osobników o losowej kombinacji komponentów funkcjonalnych I terminalnych w obrębie dopuszczalnych zbiorów, wspomnianych powyżej. Konwencjonalne programowanie genetyczne dziedziczy nowe programy z istniejących na trzy różne sposoby. Punktowa mutacja losowo zamienia funkcje albo znaki terminalne w wybranej części drzewa z innym w obrębie tego samego drzewa.

12. Rola liczebności populacji

Jeśli populacja będzie zawierała zbyt mało osobników, to algorytm może zatrzymać się bardzo szybko np. w jakimś minimum lokalnym. Rezultat będzie wówczas mało wiarygodny.

Z drugiej strony zbyt duża liczebność populacji zmniejsza szybkość działania algorytmu zużywając czas i zasoby komputerowe.

13. Metody krzyżowania

Zadaniem kroku krzyżowania jest wymiana „materiału genetycznego” pomiędzy dwoma rozwiązaniami w populacji. W wyniku krzyżowania, na podstawie dwóch rozwiązań (rodzice) tworzone są dwa nowe osobniki (dzieci). Po wykonaniu krzyżowania dzieci zastępują w populacji rodziców. Oczywiście w tym kroku nie wszystkie rozwiązania musza się ze sobą krzyżować. Liczbę krzyżowań określa tzw. współczynnik krzyżowania (o wartości od, 0 do 1), który pokazuje, jaka część osobników powinna być w jednej iteracji skrzyżowana, bądź określa prawdopodobieństwo, z jakim każde rozwiązanie może wziąć udział w krzyżowaniu.

W przypadku binarnej reprezentacji chromosomu najprostsze krzyżowanie polega na podziale dwóch chromosomów (rodzice) na dwie części (niekoniecznie równe) i utworzeniu dzieci przez połączenie fragmentu od jednego rodzica z fragmentem od drugiego. Rozszerzeniem takiego krzyżowania jest krzyżowanie wielopunktowe, gdzie chromosomy rodziców dzieli się na kilka części a później dzieci tworzy się na podstawie przeplatanych wycinków rodziców

14. Metody mutacji

Mutacja, podobnie jak krzyżowanie, zapewnia wprowadzanie do populacji nowych osobników. Jednak, w odróżnieniu od krzyżowania, w przypadku mutacji modyfikowany jest jeden, a nie dwa osobniki. Podobnie jak w przypadku

krzyżowania istnieje tzw. współczynnik mutacji, który określa jaka część osobników będzie w jednej iteracji ulegała mutacji.

Mutacja polega na losowej zmianie wartości niektórych (lub wszystkich) genów reprezentujących osobnika. Ma ona za zadanie zwiększyć różnorodność osobników w populacji, czyli zapobiegać przedwczesnej zbieżności algorytmu oraz eksplorować przestrzeń rozwiązań. Mutacja zachodzi z pewnym przyjętym prawdopodobieństwem - zazwyczaj rzędu 1%. Jest ono niskie, ponieważ zbyt silna mutacja przynosi efekt odwrotny do zamierzonego: zamiast subtelnie różnicować dobre rozwiązania - niszczy je. Stąd w procesie ewolucji mutacja ma znaczenie drugorzędne, szczególnie w przypadku długich chromosomów. Może być zarówno operatorem lokalnym (jak w algorytmach genetycznych), jak i operatorem globalnym (jak w strategiach ewolucyjnych).

W algorytmie genetycznym, zależnie od metody kodowania genotypu, może wyglądać następująco:

-W przypadku chromosomów kodowanych binarnie losuje się zazwyczaj dwa geny i zamienia się je miejscami bądź np. neguje pewien wylosowany gen.

-W przypadku genotypów zakodowanych liczbami całkowitymi stosuje się permutacje.

-W przypadku genotypów zakodowanych liczbami rzeczywistymi wprowadza się do przypadkowych genów losowe zmiany o danym rozkładzie - najczęściej normalnym.

15. Ograniczenia w algorytmach ewolucyj.

Model ewolucji przyjęty w algorytmie ewolucyjnym nie odzwierciedla wielu aspektów naturalnych procesów ewolucyjnych, takich jak:

-dynamicznie zmieniające się warunki środowiska.

-jednoczesny wpływ wielu kryteriów

- brak wiedzy globalnej i synchronizacji pokoleniowej

-ewolucja gatunków

-ewoluujące odwzorowanie cech geno- i fenotypowych

Jako najistotniejsze ograniczenia klasycznych obliczeń ewolucyjnych wskazać, zatem należy:

1. cały proces ewolucji jest realizowany przy pomocy jednego algorytmu, przez co jest on scentralizowany

2. obiekty podlegające ewolucji są zredukowane do struktur danych (genów)

---