Czym są algorytmy ewolucyjne

Tematem niniejszej książki są algorytmy ewolucyjne. Są to algorytmy wykorzystywane do przeszukiwania przestrzeni alternatywnych rozwiązań.
Terminologia, którą się posługujemy, nazywając elementy algorytmów ewolucyjnych, jest dość specyficzna, powstała bowiem wskutek inspiracji genetyką i ewolucją.
Algorytm ewolucyjny przetwarza populację osobników, z których każdy jest propozycją rozwiązania postawionego problemu. Działa on w środowisku, które można zdefiniować na podstawie problemu rozwiązywanego przez algorytm. W środowisku każdemu osobnikowi jest przyporządkowana wartość liczbowa, określająca jakość reprezentowanego przez niego rozwiązania; wartość ta jest nazwana przystosowaniem osobnika.
Każdy osobnikjest wyposażony w informację stanowiącąjego genotyp, będącą "przepisem" na utworzenie fenotypu zestawu cech określanych przez genotyp, podlegających ocenie środowiska; wartość liczbowa tej oceny nazywa się przystosowaniem osobnika. Będziemy mówić o kodowaniu fenotypu przez genotyp*. Tak więc fenotyp jest punktem w przestrzeni rozwiązań problemu, genotyp zaś punktem w przestrzeni kodów.
Środowisko można opisać funkcją przystosowania, za pomocą której osobnikowi przypisuje się przystosowanie na podstawie jego fenotypu**. Funkcja ta może być stacjonarna lub zmienna w czasie; może też zawierać element losowości. Ze względu na fakt, że fenotyp jest wynikiem dekodowania genotypu, w dalszych rozważaniach będziemy przyjmować, że funkcja przystosowania jest określona dla genotypów.
Genotyp osobnika składa się z chromosomów***. Co najmniej jeden z chromosomów zawiera kod określający fenotyp, po-
*W niektórych schematach algorytmów ewolucyjnych fenotyp jest tożsamy z genotypem.
**Funkcję przystosowania określa się niekiedy mianem krajobrazu adaptacyjnego.
***Najczęściej jeden osobnik zawiera jeden chromosom.
16
zostałe mogą natomiast zawierać informacje istotne dla algorytmu ewolucyjnego, lecz nie mające bezpośredniego wplywu na przystosowanie osobnika. Każdy z chromosomów z kolei sklada się z elementarnych jednostek, zwanych genami*.
Działanie algorytmu ewolucyjnego sprowadza się do wykonywania pętli przedstawionej na rys. 1, w której następują po sobie reprodukcja, operacje genetyczne, ocena i sukcesja. W literaturze przedmiotu, reprodukcję i sukcesję określa się łącznym mianem selekcji**.
Reprodukcja w połączeniu z operatorami genetycznymi modeluje rozmnażanie, podczas którego materiał genetyczny rodziców jest przekazywany potomkom.
Podczas reprodukcji zostają powielone losowo wybrane osobniki z populacji bazowej. Możliwejest zarówno wielokrotne powielenie tego samego osobnika, jak również to, że niektóre osobniki nie zostaną wybrane ani razu do powielenia. Losowość wyboru do reprodukcji uwzględnia jednak wartości przystosowania osobników charakteryzujące się większym przystosowaniem mają większe szanse powielenia (a zatem i większą wartość oczekiwaną liczby kopii).
Środowisko
Algorytm ewolucyjny Inicjacja
Reprodukcja
Operacje genetyczne
RYSUNEK 1. Schemat algorytmu ewolucyjnego
*Wartościągenujestaiiei. Powstałe w wyniku reprodukcji kopie, zwane osobnikami ro-
**Terminy reprodukcja dzicieiskimi poddawane są operacjom genetycznym, które pole-
i sukcesja wprowadzono na ' L c ^ J � u J ' r
potrzebytej książki. Nie- gająnadokonamulosowychmodyhkacjiichgenotypów.Mutacja kiedy mówisieo preseiekcji pOiecra na perturbacji genotypu iedncgo osobnika rodzicielskiego.
(reprodukcja) i postselekcji ^ � ^ J o J f J o o
(sukcesja) [32]. Przyjmuje się najczęściej, że niewielkie perturbacje są bardziej
#17
prawdopodobne niż duże. Z kolei krzyżowanie1 jest operatorem genetycznym działającym na wielu osobnikach rodzicielskich (co najmniej dwóch) i prowadzącym do wygenerowania jednego lub wielu osobników potomnych, których chromosomy powstają w wyniku "wymieszania" odpowiednich chromosomów pochodzących z różnych osobników rodzicielskich*. Osobniki utworzone w wyniku działania operatorów genetycznych stanowią populację potomną.
Populacja potomna jest poddawana ocenie środowiska, po czym następuje sukcesja tworzy się nową populację bazową, mogącą zawierać osobniki zarówno z populacji potomnej, jak i ze starej populacji bazowej.
Inicjacja pętli ewolucji polega na utworzeniu początkowej populacji bazowej poprzez wygenerowanie genotypów osobników i obliczenie ich przystosowania. Proces inicjacji jest najczęściej losowy; może być przy tym uwzględniany wpływ środowiska**. Cykl ewolucji może kończyć się wówczas, gdy przystosowanie osobni-kówjest odpowiednio duże, lub gdy stwierdzi się, że stan populacji bazowej świadczy o stagnacji algorytmu.
W przestrzeni genotypów funkcję przystosowania możemy sobie wyobrażać jako łańcuch wzgórz. Działanie algorytmu ewolucyjnego sprowadza się do premiowania takich osobników, które są lepiej przystosowane do środowiska, a zatem są położone bliżej wierzchołka jednego ze wzgórz. Premiowanie to ma jednak wbudowany element losowości, umożliwiający (z odpowiednio małym prawdopodobieństwem) reprodukcję nawet bardzo słabo przystosowanych osobników. Ten właśnie mechanizm, dopuszczający pogorszenie populacji bazowej w kolejnej generacji, umożliwia wyjście z pułapek ewolucyjnych***, czyli z takiej sytuacji, w której niewielkie zmiany fenotypu prowadzą do pogorszenia uzyskiwanego rozwiązania.

Rozwój algorytmów ewolucyjnych

Algorytmy ewolucyjne są technikami, które przez długi czas były rozwijane niezależnie od siebie w wielu ośrodkach naukowych na świecie. Wymienienie wszystkich jest zadaniem trudnym i nie mieści się w szczupłych ramach tej książki; dlatego skupimy uwagę na zaledwie kilku z nich, najbardziej znanych i najsilniej rozwijanych.
1Termin krzyżowanie przyjął się w języku polskim jako odpowiednik angielskiego terminu crossover. Zdaniem autora polski termin jest niefortunny, gdyż w biologii terminu krzyżowanie używa się w odniesieniu do gatu
^^^^BSjjian czy ras, natomiast proces molekularny zachodzący podczas rozmna^!p>rapTctqfl^^o, modelowany w algorytmach ewolucyjnych, określany jest nazwą
i06458 '5'*0*"*
*Ze względu na "wymieszanie" chromosomów wskutek krzyżowania operator ten jest często nazywany rekombinacją.
**Wpływem środowiska na rozkład zmiennych losowych wykorzystywanych do inicjacji.
***Więcej na ten temat w wykładzie 3.
18
Na zachodnim wybrzeżu Stanów Zjednoczonych Lawrence Fogel próbował odpowiedzieć na pytanie, czy zachowanie, oceniane jako inteligentne, może powstać w wyniku ciągu przypadkowych zmian. Badał populację automatów skończonych, z których każdy mial za zadanie rozpoznawać pewien nieznany rnu język. Metoda polegała na tym, że automaty były poddawane losowym perturbacjom i procesowi selekcji. Po wiełu cyklach perturbacji i selekcji powstawały automaty, które prawie bezbłędnie rozpoznawały nieznane wcześniej prawidłowe wyrażenia języka. Prace te dały początek programowaniu ewolucyjnemu.
W Niemczech Ingo Rechenberg i Hans-Paul Schwefel eksperymentowali nad optymalizacją urządzeń mechanicznych metodą permutowania pewnego początkowego rozwiązania. Otrzymali bardzo dobre wyniki, które były odmienne niż uzyskiwane z zastosowaniem dotychczasowej praktyki projektowania. Dostrzegli w tej metodzie podobieństwo do procesu ewolucji i, zachęceni wynikami, uogólnili ją na przypadek, gdy naraz przetwarzanych jest wiele rozwiązań. Stworzone przez nich metody noszą nazwę strategii ewolucyjnych.
Na wschodnim wybrzeżu Stanów Zjednoczonych John Hol-land zajmował się modelowaniem ewolucji populacji osobników, z których każdy był wyposażony w binarny kod genetyczny. Wprowadził on mechanizmy przekształcania słów kodowych w sposób podobny do operacji crossing-over oraz mutacji, a także mechanizm selekcji. Osobnikom przypisał wartości liczbowe zależne od kodu genetycznego i zauważył, że w wyniku działania mechanizmów selekcji i operatorów genetycznych średnia wartość przystosowania populacji ma tendencje wzrostowe. Tak powstał algorytm genetyczny, spopularyzowany później przez Davida Gold-berga.
Wymienione wyżej pomysły były rozwijane począwszy od lat 60. niezależnie od siebie. W owym czasie grono osób zajmujących się tymi technikami było dość niewielkie, wyniki prac zaś rozproszone w różnych, słabo związanych tematycznie źródłach. W latach 80. izolacja została przełamana, natomiast w latach 1985-1995 zorganizowano wiele konferencji poświęconych algorytmom ewolucyjnym; rozpoczęto wydawanie czasopism poświęconych tym metodom, ukazało się także sporo książek popularyzujących tę dziedzinę.
Początkowo, algorytmy ewolucyjne były dość chętnie traktowane jako metody ogólnego przeznaczenia, służące do rozwiązywania dowolnych problemów w identyczny sposób. Wraz z pierwszymi zastosowaniami, na początku lat 90. zaczęto dostrzegać słabość takiego postępowania. Za dużą uniwersalność trzeba mianowicie zapłacić niewielką efektywnością rozwiązywania konkretnego zadania. Pojawiły się propozycje uwzględniania specyfiki zadania poprzez stosowanie specjalizowanego kodowania i operato-
#19
rów genetycznych, sam zaś algorytm ewolucyjny zaczęto trakto-waćjako pewien ramowy sposób postępowania (metaheurystyka), polegający na tym, że kolejnych rozwiązań poszukuje się przede wszystkim w otoczeniu rozwiązań lepiej przystosowanych.
Rozwinięciem tej myśli były próby stosowania algorytmów genetycznych do automatycznego pisania programów w języku LISP (genetyczne programowanie, wiązane z nazwiskiem Johna Kozy), co stanowiło inspirację do wykorzystania drzewiastych struktur danych do reprezentacji zadania w chromosomie (wraz z odpowiednimi operatorami). Obecnie termin "genetyczne programowanie" jest często używany jako synonim algorytmu ewolucyjnego z reprezentacją drzewiastą.
Lata 90. to okres zwiększonego zainteresowania algorytmami ewolucyjnymi i wzajemnego upodobniania się różnorodnych technik. Programowanie ewolucyjne zostało przystosowane do optymalizacji numerycznej w sposób zbliżony do strategii ewolucyjnych. Algorytmy genetyczne przejęły schematy selekcji ze strategii ewolucyjnych i programowania ewolucyjnego, natomiast strategie ewolucyjne w wyniku inspiracji algorytmami genetycznymi zostały wzbogacone o operator krzyżowania.
W wyniku procesów wzajemnego upodobniania, strategia ewolucyjna, algorytm genetyczny czy programowanie ewolucyjne w swoich pierwotnych postaciach są już rzadko spotykane, pełniąc obecnie głównie rolę algorytmów odniesienia dla testów porównawczych. Dlatego też, aby uniknąć problemów z rozstrzyganiem, do którego z nurtów rozwojowych zaklasyfikować nowy pomysł czy modyfikację, ustalono wspólną nazwę: algorytmy ewolucyjne (lub obliczenia ewolucyjne evolutionary computation).
Śledząc uważnie literaturę można sądzić, że wysiłek badaczy jest obecnie kierowany na zastosowania, głównie w zakresie projektowania wspomaganego komputerowo. Sporo jest także prób wypracowania teorii w pełni wyjaśniającej działanie algorytmów ewolucyjnych, jak również określenia zadań, do których szczególnie wskazane jest ich zastosowanie (także takich zadań, które się tym metodom nie poddają). Czynione są wysiłki (zasygnalizowane w ostatniej części książki) zaadaptowania tych metod do zadań wielokryterialnych oraz w warunkach środowiska zmiennego w czasie. Poszukuje się także skutecznych metod wykorzystania równoległości, nie tylko na poziomie implementacji algorytmu, lecz również jego koncepcji.

Zastosowania algorytmów ewolucyjnych

O zainteresowaniu algorytmami ewolucyjnymi zadecydowały przede wszystkim prostota schematu oraz liczne zastosowania
#20
praktyczne w różnych dziedzinach*. Metody te znajdują zastosowanie w oprogramowaniu wspomagającym projektowanie (CAD). Znane jest na przykład wykorzystanie tych technik w procesie projektowania kształtu komory silnika odrzutowego, w mikroelektronice do projektowania rozłożenia elementów na płytce krzemu, w radiotechnice do projektowania anten. Znane są również zastosowania w dziedzinach, będących domeną badań operacyjnych, na przykład w optymalizacji kolejności dostarczania przesyłek, w harmonogramowaniu zadań itp. Podejmowane są próby wykorzystania algorytmów ewolucyjnych w zadaniach sterowania, na przykład w sterowaniu predykcyjnym z modelem (gdzie problem polega na wyznaczeniu optymalnych sterowań na pewnym horyzoncie czasowym), we wspomaganiu nawigacji, w planowaniu tras robotów. Również ekonomiści sięgają po algorytmy ewolucyjne jako narzędzie wspomagania decyzji. Znane są też próby wykorzystania w sztucznej inteligencji i maszynowym uczeniu, gdzie na przykład poszukuje się optymalnych reguł klasyfikacji opisujących dostępne dane.
Ogólnie rzecz biorąc, algorytm ewolucyjny realizuje proces ciągłej adaptacji populacji do środowiska. Nie można niestety zagwarantować, że wynikiem tego procesu będzie znalezienie najlepszego osobnika z możliwych (czyli znajdującego się na wierzchołku najwyższego wzgórza funkcji przystosowania). Jednakże przy pewnych, niezbyt rygorystycznych założeniach można wykazać, że wraz z upływem czasu prawdopodobieństwo takiego zdarzenia wzrasta i dąży asymptotycznie do jedności.
Algorytmy ewolucyjne określa się niekiedy mianem "metod ostatniej szansy". Można to rozumieć w następujący sposób: jeżeli wiedza o problemie wystarcza do sformułowania efektywnego sposobu rozwiązania, to z pewnością będzie on skuteczniejszy niż zastosowanie algorytmu ewolucyjnego. Przykładem takiej sytuacji może być rozwiązywanie problemu opisanego za pomocą zależności liniowych, lub poszukiwanie minimum wypukłej funkcji różniczkowalnej, danej w postaci analitycznej. Jeśli jednak wiedza, którą dysponujemy, nie pozwala na sformułowanie metody specjalizowanej, można sięgnąć po algorytm ewolucyjny. Nawet wówczas jednak można wykorzystać tę ubogą wiedzę do "przykrojenia" algorytmu ewolucyjnego do potrzeb problemu (wprowadzając metodę kodowania i operatory genetyczne zależne od zadania). Brak jakiejkolwiek wiedzy nie wyklucza możliwości zastosowania algorytmu ewolucyjnego: można wtedy użyć standardowych metod kodowania i operatorów genetycznych, opracowanych dla dziedzin dyskretnych i ciągłych.
*Nie bez znaczenia jest Na zakończenie warto wspomnieć o twierdzeniu "No Free
atrakcyjność wynikająca Lunch Theorem"**. Twierdzenie to mówi, że dla dowolnej funkcji przystosowania każdy algorytm będzie równie dobrze działać.
z iezyka opisu tych metod.
**W żartobliwym tłumaczeniu - nie ma lekko"
W praktyce oznacza to, że jeśli nie założy się występowania żad-
#
nych regularności w rozwiązywanym zadaniu, to nie sposób racjonalnie dobrać dla niego algorytm optymalizacji. W przypadku algorytmów ewolucyjnych nie jest niestety znana klasa funkcji, dla których metody te byłyby bardziej efektywne niż inne określenie tych funkcji jest obecnie dość ważnym, lecz zarazem trudnym problemem. Nie zmienia to faktu, że dla wielu funkcji testowych i zadań praktycznych zastosowanie algorytmów ewolucyjnych prowadzi do uzyskiwania zadowalających rozwiązań w rozsądnym czasie, co (przy prostocie implementacji) stanowi powód znacznej popularności tych metod.

O czym jest ta książka

Algorytmy ewolucyjne są jeszcze w fazie rozwoju, dlatego też nie sposób rzetelnie ocenić poszczególne pomysły składające się na tę dziedzinę. Napisanie podręcznika, w którym zostanie ona przedstawiona w sposób systematyczny, jest więc bardzo trudnym zadaniem, pełne zaś omówienie stanu badań znacznie przekracza możliwości autora i cierpliwość Czytelnika. Wybór materiału i rozłożenie akcentów są z konieczności podyktowane zainteresowaniami autora i choć najczęściej stanowią odzwierciedlenie dotychczas dostępnej literatury, to niektóre kwestie zostały szczególnie zaakcentowane, niektóre zaś są wprowadzone po raz pierwszy w tej książce*.
Jest wiele utartych sposobów patrzenia na algorytmy ewolucyjne. Jedni widzą w nich metody sztucznej inteligencji, inni modele ewolucji i genetyki (,^ztuczne życie"), jeszcze inni traktują je jako próbę rozwiązania zadania optymalizacji globalnej. W tej książce będzie prezentowany ten ostatni punkt widzenia z dwoma zastrzeżeniami: nie można mówić o optymalizacji w ścisłym tego słowa znaczeniu, lecz raczej o adaptacji, sam zaś proces ewolucyjny niekoniecznie musi przebiegać w przestrzeni Rn.
Niewiele uwagi poświęcono zagadnieniom teoretycznym, koncentrując się na eksperymentalnym aspekcie omawianych metod. Główną tego przyczyną jest fakt, że dotychczasowe wyniki analizy teoretycznej dotyczą albo przypadków bardzo prostych funkcji przystosowania, dla których z łatwością można by wskazać znacznie bardziej efektywne algorytmy rozwiązania, albo też założenia potrzebne do analizy są bardzo niepraktyczne (nieskończona liczność populacji bazowej, czas trwania eksperymentu zdążający
do nieskońCZOnOŚci).
Każdemu z rozdziałów towarzyszy przegląd literatury, zwią-zanei z poruszanymi zagadnieniami, do której powinien sięgnąć p"acazoweoyczyo
J .\ . J to .' J r . Yto ^ zwłaszczazagadnienzwią-
Czytelmk zainteresowany kwestiami szczegółowymi, hksperymen- zanych z zapobieganiem ty, których wyniki przedstawiono w wykładach, w większości prze- przedwczesnej zbieżności). prowadzono z użyciem oprogramowania gabi, napisanego przez **Szczeg�łowa informacja
11 , i i � -i-**AT- i , . -i � , � oprogramowaniu gabi
autora dla potrzeb książki. Niektóre wyniki są cytowane z prac znajduje się w dodatku e.
*są to postuiaty kodo-
wania ' operatorów gene-tycznych oraz rozważania
związane z iicznościa po-
#22
innych autorów wówczas w spisie literatury wskazana jest odpowiednia pozycja. Każdemu z rozdziałów towarzyszy zestaw pytań i problemów, których przemyślenie powinno utrwalić i pogłębić informacje zawarte w rozdziale.

Dla kogo jest ta książka

Książka powstała na podstawie prowadzonych przez autora wykładów na Wydziale Elektroniki i Technik Informacyjnych Politechniki Warszawskiej. Były to:
� Metody optymalizacji globalnej (wspólnie z dr inż. Ewą Nie-wiadomską-Szynkiewicz),
� Metody rozmyte i strategie ewolucyjne (wspólnie z dr. inż. Pawłem Domańskim),
� Metody ewolucyjne i uczenie się maszyn (wspólnie z dr. inż. Pawłem Cichoszem i prof. Janem Mulawką).
Zamiarem autora było napisanie podręcznika akademickiego dla studentów kierunków ścisłych, którego lektura pozwoliłaby zaznajomić się z podstawowymi kierunkami rozwoju algorytmów ewolucyjnych, a także stanowiłaby punkt wyjściowy do rozpoczęcia własnych prac. Zakłada się przy tym przygotowanie Czytelnika w zakresie podstaw rachunku prawdopodobieństwa, statystyki i analizy matematycznej, a także (pobieżną) znajomość problemów i metod optymalizacji ciągłej i dyskretnej; nie jest potrzebne przygotowanie w zakresie nauk biologicznych.
Adresatami książki są nie tylko studenci i doktoranci, lecz również osoby pracujące zawodowo i rozważające zastosowanie omawianych metod w praktyce, na przykład w projektowaniu wspomaganym komputerowo, podejmowaniu decyzji, sterowaniu i innych dziedzinach, w których jednym z istotnych elementów jest poszukiwanie optymalnego rozwiązania. Znajdą oni omówienie wielu zagadnień, na które należy zwrócić szczególną uwagę w czasie wdrożenia.

Jak korzystać z tej książki

Książka ma formę zapisu wykładów ilustrowanych przykładami obliczeniowymi. Pierwsza część książki może służyć jako krótka informacja o algorytmach ewolucyjnych, przekazana w ramach wykładu poświęconego innym zagadnieniom, na przykład badaniom operacyjnym, metodom optymalizacji, sztucznej inteligencji itp. Druga część zawiera nieco bardziej zaawansowany i usystema-
#23
tyzowany materiał, będący wyjaśnieniem podstawowych mechanizmów wykorzystywanych przez algorytmy ewolucyjne. Może być ona częścią wykładu poświęconego metodom optymalizacji globalnej, heurystykom itp. Trzecia część to materiał będący przeglądem literatury, może służyć do samodzielnej pracy naukowej czy wdrożeniowej. Zdaniem autora może być ona pomocna jako zwięzły przegląd kierunków badań dla poszukujących inspiracji studentów wyższych semestrów i doktorantów. Materiał zawarty w książce może także służyć nauczycielom akademickim w przygotowaniu wykładów i ćwiczeń.

Uwagi bibliograficzne

Pierwsze pozycje poświęcone algorytmom ewolucyjnym mają już raczej łiistoryczny charakter. Są to książki Lawrcnce'a Fogela [25], Ingo Rechenberga i Hansa-Paula Schwefela [87, 94], Johna Hol-landa [35].
Najbardziej znanym podręcznikiem jest książka Davida Goldberga [31], w której autor zaprezentował klasyczne algorytmy genetyczne. Wiele uwagi Goldberg poświęcił wykorzystaniu tych metod w maszynowym uczeniu (zwłaszcza w systemach klasyfikatorowych), omówił także dość szczegółowo historię rozwoju algorytmów genetycznych. Podręcznik wydany przez Law-rence'a Davisa [34] stanowi kolekcję przykładów wykorzystania algorytmów genetycznych w praktyce. Szczególną uwagę poświęcił autor sposobom wykorzystania "nieewolucyjnych", lokalnych metod w rozwiązaniach hybrydowych z algorytmami genetycznymi.
Nowocześniejszemu podejściu do algorytmów ewolucyjnych, polegającemu na uwzględnianiu specyfiki rozwiązywanych problemów na etapie kodowania i operatorów genetycznych, poświęcony jest podręcznik Zbigniewa Michalewicza [54]. Autor wykorzystał problemy z dziedziny badań operacyjnych w celu ilustracji korzyści płynących z takiego podejścia. Książka Johna Kozy [40] zawiera kolekcję licznych przykładów ilustrujących potencjalne możliwości programowania genetycznego.
Podręcznik Hansa-Paula Schwefela [93] jest przeglądem metod ewolucyjnych (głównie strategii ewolucyjnych) i innych metod optymalizacji (zarówno wypukłej, jak i globalnej). Autor zilustrował omawiane metody eksperymentami z funkcjami testowymi. Thomas Back [6] skoncentrował się na porównaniu strategii ewolucyjnych, algorytmów genetycznych i programowania ewolucyjnego. Dokonał analizy porównawczej metod nacisku selektywnego, a także omówił zagadnienia związane ze zbieżnością w sensie probabilistycznym. Książka ta zawiera również eksperymentalne
#24
porównanie omawianych podejść. Próbę odpowiedzi na pytanie, jak dobrać metodę przeszukiwania do rozwiązywanego zadania i jaki jest na tym tle zakres zastosowań algorytmów ewolucyjnych, stanowi książka [24]. Autorzy porównali w niej najbardziej znane heurystyczne metody rozwiązywania problemów dyskretnych, w tym również algorytmy ewolucyjne.
W rozprawie habilitacyjnej Romana Galara [26] został przedstawiony model poszukiwań z miękką selekcją. Model ten to populacja osobników, z których każdy jest wektorem liczb rzeczywistych, poddawanych operacjom generycznym: mutacji (polegającej na dodaniu wartości zmiennej losowej o rozkładzie normalnym) oraz krzyżowania (tworzony jest osobnik potomny, będący średnią arytmetyczną osobników rodzicielskich). Osobniki podlegają reprodukcji proporcjonalnej, co Galar nazywa miękką selekcją. W rozprawie autor skupił uwagę na umiejętności procesu ewolucji z miękką selekcją wykraczania z obszarów przyciągania ekstremów lokalnych (tzw. zdolność przekraczania siodeł funkcji przystosowania).
Pewną ciekawostkę stanowi książka Richarda Dawkinsa [16], poświęcona popularyzacji idei ewolucjonizmu. Autor, pragnąc zilustrować działanie ewolucji, stworzył algorytm przetwarzający populację biomorfów rysunków o specjalnej strukturze (niektóre z nich przypominają drzewa, inne owady itp.). Funkcją przystosowania było to, czy obrazek podoba się autorowi. To podejście dało początek tzw. ewolucji interakcyjnej.

TABELA 1. Zestawienie nazw największych konferencji poświęconych algorytmom ewolucyjnym
Nazwa Miejsce Okres Początek
International Conference on Gene- USA 2 lata 1985
tic Algorithms (ICGA)
Foundations of Genetic Algorithms USA 2 lata 1990
(FOGA)
Parallel Problem Solving from Na- Europa 2 lata 1990
turę (PPSN)
IEEE Conference on Evolutionary świat coroczna 1994
Computation (ICEC)
IEE Conference on Genetic Algo- Wielka Brytania coroczna 1995
rithms in Engineering Systems and
Industrial Applications (GALESIA)
Annual Conference on Evolutio- USA coroczna 1992
nary Programming (EP)
International Conference on Gene- USA coroczna 1994
tic Programming (GP)
Congress on Evolutionary Compu- USA coroczna 1999
tation (CEC)
Genetic and Evolutionary Compu- USA coroczna 1999
tation (GECCO)
#25
Próbą zebrania osiągnięć w dziedzinie algorytmów ewolucyjnych jest Handbook of Evolutionary Computation [33] zbiór tekstów napisanych przez badaczy reprezentujących różne ośrodki naukowe i różne trendy w tej dziedzinie.
Od pewnego czasu ukazują się czasopisma poświęcone algorytmom ewolucyjnym są to Evolutionary Computation (od 1993 roku) oraz IEEE Transactions on Evolutionary Computation (od 1997 roku). Artykuły na ten temat można również spotkać w IEEE Transactions on Systems, Man and Cybernetics, International Journal on Artificial Intelligence, Neural Networks, IEEE Transactions on Neural Networks i innych, przede wszystkim poświęconych sztucznej inteligencji i dziedzinie soft computing (sieci neuronowe, zbiory rozmyte).
Z wynikami najnowszych prac można się zapoznać, przeglądając materiały konferencji naukowych poświęconych algorytmom ewolucyjnym; nazwy niektórych z nich (zdaniem autora mających największy wpływ na rozwój dziedziny i cieszących się największym zainteresowaniem) zestawiono w tab. 1.
Począwszy od 1996 roku (z przerwą w 1998 r.) odbywa się w Polsce coroczne spotkanie pod nazwą Krajowa Konferencja "Algorytmy Ewolucyjne i Optymalizacja Globalna".
Przegląd praktycznych zastosowań algorytmów ewolucyjnych można znaleźć w pracach [20, 34, 40] oraz w czasopismach i materiałach konferencji poświęconych algorytmom ewolucyjnym.