1
Algorytmy Ewolucyjne
                              
Autorzy:
Wojciech Durczyński
Wojciech Górski
2
Czym sÄ… algorytmy ewolucyjne:
Istotą sformułowanej przez Karola Darwina w 1859 roku teorii jest założenie,
że ewolucja jest procesem przebiegającym bez wyznaczonego celu, a polegającym
na zmianach organizmów wskutek oddziaływania z otoczeniem. Rolą tych
zmian jest poprawa sprawności czy też skuteczności danego organizmu. Trzeba
jednak podkreślić, że sedno darwinowskiej adaptacji polega na znajdowaniu
ulepszeń, a nie rozwiązań optymalnych. Ewolucja większości organizmów
uwarunkowana jest dwoma mechanizmami: doborem naturalnym i rozmnażaniem
płciowym. Pierwszy z tych mechanizmów wyznacza te jednostki, które przeżyją
i wydadzą potomstwo, drugi zaś zapewnia wymieszanie i rekombinację genów
potomstwa. Na dobór naturalny można patrzyć jako przejaw prawa  przetrwania
najsilniejszych .
Johna Hollanda z Uniwersytetu Michigan można nazwać ojcem algorytmów
ewolucyjnych. Jego celem było stworzenie programu komputerowego w sposób
naśladujący naturalny przebieg ewolucji. Pierwsze próby użycia teorii ewolucji
w informatyce przeprowadzono już na przełomie lat pięćdziesiątych i sześć-
dziesiątych. Brak sukcesów wynikał z naśladownictwa ówczesnych podręczników
biologii, które kładły większy nacisk na rolę mutacji jako z
ródła zmienności
genetycznej w porównaniu z reprodukcją płciową. Widocznym przełomem
była zaproponowana przez Hollanda w połowie lat sześćdziesiątych technika
programowania uwzględniająca ewolucję zarówno przez mutację, jak i krzy-
żowanie się. W następnym dziesięcioleciu zakres stosowania tego algorytmu
został poszerzony o kod genetyczny pozwalający reprezentować strukturę
każdego problemu. W ten sposób, naśladujący biologiczne narodziny i śmierć,
reprodukowane osobniki nie są dokładnymi kopiami swoich rodziców.
Algorytmy ewolucyjne i genetyczne to ściśle zdefiniowane matematyczne
procedury stosowane do rozwiązywania niektórych problemów optymaliza-
cyjnych (lub decyzyjnych), dla których standardowe algorytmy są nieznane
lub mają nieakceptowalnie długi czas działania. Algorytm genetyczny rozpo-
czyna pracę przez porównanie licznych początkowych projektów z ustalonym
wcześniej zespołem kryteriów oceny. Projekty najbardziej pasujące do tych
kryteriów są selekcjonowane i poddawane niewielkim losowym zmianom -
 mutacjom i  reprodukcji . W wyniku  krzyżowania się pochodzącej od
 rodziców informacji, jak i przypadkowym  mutacjom powstają nowe warianty
projektów, które ponownie oceniane są przez ustalone kryteria, a te najlepsze
selekcjonowane sÄ… do dalszej  ewolucji . Genetyczny algorytm powtarza ten
schemat tak długo, aż pojawi się optymalny projekt, to jest najlepiej spełniający
3
założone wcześniej kryteria oceny. Mamy tu więc do czynienia ze swoistym
procesem optymalizacji.
Algorytmy ewolucyjne zawierają w sobie element losowości konieczny
do otrzymania najlepszych wyników optymalizacji. To powoduje, że są one
często przedstawiane jako doskonała ilustracja, a nawet potwierdzenie, teorii
biologicznej ewolucji. Jest to jednak twierdzenie fałszywe. Dokładniejsza analiza
algorytmów ewolucyjnych precyzyjnie demonstruje dlaczego nie mogą one
służyć jako analogia naturalistycznej biologicznej ewolucji: istnienie i funkcjonowanie
mechanizmu bazującego na próbach i błędach wymaga wcześniejszego zapro-
jektowania wielu fundamentalnych parametrów (jak zdefiniowanie długoterminowego
celu ewolucji i określenie kryteriów selekcji wyników), które same są poza
zasięgiem tego mechanizmu. Parametry te muszą zostać określone zanim
mechanizm prób i błędów zacznie operować, determinują one całkowicie teren,
na którym ten mechanizm może operować, określają jakie cechy będą selekcjonowane
i nawigują cyfrową ewolucję w kierunku żądanej optymalizacji. Mimo to
algorytmy ewolucyjne znalazły zastosowanie w wielu dziedzinach nauki i
techniki.
Algorytmy genetyczne:
Prostym przykładem algorytmu ewolucyjnego jest algorytm dopasowania
do wzorca. Algorytm ten przetwarza populację łańcuchów znaków inicjowanych
losowo, a celem ewolucji jest uzyskanie łańcucha o zadanej postaci. Dopasowanie
dowolnego łańcucha z populacji do wzorca określa liczba pozycji, na których
w obu łańcuchach występują identyczne grupy. Najlepszy osobnik w każdej
grupie jest kopiowany i zastępuje najgorszego osobnika w tej grupie, przy
czym losowo wybrana pozycja kopii poddawana jest mutacji. Nietrudno zauważyć,
że populacja łańcuchów będzie z upływem czasu dążyć do populacji zawierającej
wiele łańcuchów zgodnych ze wzorcem. Przeszukiwanie jest tu realizowane
wyłącznie drogą wprowadzania  niewielkich zmian , czyli za pomocą mutacji.
WprowadzajÄ…c dodatkowy operator stanowiÄ…cy odpowiednik reprodukcji
płciowej, czyli operator krzyżowania, uzyskujemy algorytm genetyczny. Operator
ten można realizować na przykład w sposób następujący: Z każdej grupy
wybiera się dwa najlepsze osobniki, nazywane rodzicami, a następnie wybiera
się losowo numer pozycji w łańcuchu. Pierwszy potomek tworzony jest z
danych od poczÄ…tku Å‚ancucha do wyznaczonego miejsca pierszego rodzica
i z danych od wyznaczonego miejsca do konca Å‚ancucha rodzica drugiego.
Drugi potomek tworzony jest analogicznie, z tym że jego początkowe dane
4
pobierane są z rodzica drugiego, a końcowe z rodzica pierwszego.
Pierwszym krokiem w implementacji algorytmu genetycznego jest zdefiniowanie
struktury danych dla osobników tworzących populacje podlegającą ewolucji.
Struktura ta określana jest często jako chromosom. Wybierając taka strukture,
programista powinien kierować się z jednej strony jej uniwersalnością, z
drugiej strony jednak też jej prostotą. Wybrana struktura ma w końcu posłużyć
do rozwiązywania problemów danej klasy, z drugiej strony jednak powinna
też być łatwa w obłudze, przede wszystkim w wyznaczaniu dostosowania
konkretnego osobnika i mutowaniu/krzyżowaniu.
JednÄ… z zasad wyboru struktury jest zasada minimalnego alfabetu, tzn.
Należy wybrać najmniejszy alfabet, w którym dane zadanie wyraża się w
sposób naturalny. Najbardziej popularną struktura jest łancuch binarny. Jego
długość może być stała lub zmienna. Prostsze w użyciu są te łancuchy ze stałą
długością łancucha, jednak dynamicznie zmieniająca sie długość łancucha
powoduje, że reprezentacja ta staje się bardziej elastyczna, tj. pozwala modelować
większą gamę rozwiązań w sposób bardziej naturalny. W zadaniach optymalizacyjnych
funkcji n-zmiennych jako chromosom warto przyjąć wektor n-wymiarowy o
składowych rzeczywistych.
Chromosom w każdym przypadku złożony jest z ciągu genów, które mogą
występować w pewnej liczbie odmian zwanych allelami (praktycznie mowiąc,
są to po prostu wartości cech. Dla łancucha binarnego allele to symbole 0 i
1). Pozycje genu w łańcuchu określa się jako locus.
W szczególnych przypadkach, jak na przykład zadaniu z wieloma zmiennymi,
stosując nieodpowiednią strukture limfocytów, możemy otrzymać chromosomy,
które stwarzają problemy przy operowaniu na nich. Przykładem może być
funkcja 20 zmiennych, gdzie każda zmienna reprezentowana jest przez 20
genów. Już dla takich wartości, które nie są aż tak wygórowane, otrzymamy
aż 400 genów w chromosomie. Rozwiązaniem tego problemu jest wprowadzenie
innego sposobu kodowania danych. AlternatywÄ… sÄ… np. kodowanie logarytmiczne
i kodowanie rzeczywiste.
Kodowanie logarytmiczne polega na reprezentacji liczby za pomocÄ… wzoru:
a
(-1)be(-1) [bin]10
W tym kodowaniu pierwszy gen chromosomu reprezentuje znak liczby
wyrażonej za pomocą funkcji wykładniczej, drugi - znak wykładnika, a pozostała
część stanowi łańcuch kodowy wykładnika. Dzięki zastosowaniu funkcji wykładniczej
5
uzyskujemy skrócenie długości chromosomu.
Stosując kodowanie rzeczywiste, geny w chromosomach przyjmują wartości
rzeczywiste. Allele, czyli wartości genów, są wtedy liczbami równymi składowym
wektorów odpowiadających punktom tej wielowymiarowej przestrzeni. Operator
krzyżowania, wymieniając geny pomiędzy osobnikami tworzy w ten sposób
nowe punkty w przestrzeni rozwiązań, czyli generuje nowe osobniki. Zaletą
tego kodowania jest znaczne skrócenie chromosomów. Stosowane jest często
w przypadku wielowymiarowych przestrzeni potencjalnych rozwiązań
Populacja początkowa to zbiór chromosomów, które w dalszym przebiegu
algorytmu będą poddawane ewolucyjnym modyfikacjom. Przy jej tworzeniu
pożądane jest, aby mieściła ona w sobie jak najszerszą gamę różnych osobników,
co sprzyja szybkiej weryfikacji możliwie dużej liczbie rozwiązań przez nich
reprezentowanych.
Najbardziej popularna metoda wyboru populacji poczÄ…tkowej jest losowa
generacja chromosomów. W pewnych warunkach ta metoda jest nieefektywna,
gdyż może stworzyć nieużytecznych osobników, które nie spełniają pewnych
warunków narzuconych przez opis problemu (np. dodatkowe warunki narzucone
na wektor rozwiÄ…zanie przy optymalizacji funkcji). W takich przypadkach,
najlepiej zaprojektowac populacje początkową używając wiedzy na temat
ograniczeń chromosomów. Czasami warto także zastosować prosty algorytm
nie-ewolucyjny, aby uzyskać rozwiązanie sub-optymalne, co znacznie przyspieszy
proces znajdowania zadowalającego rozwiązania. Przy takim podejściu istnieje
jednak niebezpieczeństwo zawężenia się przestrzeni rozwiązań, które można
obejść dodając do populacji część losowo wybranych osobników.
Ważnym parametrem populacji początkowej jest jej liczebność. Gdy jest
ona za mała, algorytm zbyt szybko może  zbiegać ; gdy jest ona za duża,
niepotrzebnie wykonuje się zbędne obliczenia.
Bardzo ważnym etapem każdej iteracji algorytmu jest ocena dostosowania
osobników wchodzących w skład modyfikowanej populacji. Dostosowanie jest
pewnÄ… miarÄ… obrazujÄ…cÄ…, jak  dobre jest uzyskane rozwiÄ…zanie. W przypadku
optymalizacji funkcji za miare dostosowania można np. przyjąć wartość opty-
malizowanej funkcji. Ze względu na to, że będzie ona stanowiła ważną część
algorytmu i będzie obliczana za każdą iteracją, istotne jest to, aby funkcja
określająca miarę dostosowania była jak najprostsza. Możliwe jest też skon-
struowanie dwuetapowej funkcji określającącej dostosowanie. W początkowych
iteracjach funkcja będzie sprawdzała dopasowanie osobników w sposób przybliżony;
w dalszych iteracjach, gdy zbliżamy sie do optimum, pomiary te muszą być
6
dokładniejsze. Wtedy stosujemy bardziej precyzyjne obliczanie dostosowań
proponownych rozwiązań.
Osobniki początkowej populacji mogą podlegać dwom typom modyfikacji.
Pierwszy z nich, nazywany po prostu ewolucja, polega na niezależnym pomiarze
każdego osobnika. Jako miare jakości przyjmuje się tutaj dostosowanie osobnika
do wymogów stawianych poszukiwanemu rozwiązaniu. W drugim typie, ko-
ewolucjii, dostosowanie danego osobnika jest zależne od własności innych
członków populacji. Obecność dużej liczby osobników o dużym dostosowaniu
skoncentrowanych wokół pewnego punktu wpływa na obniżenie ich dostosowania
 postrzeganego przez algorytm. W ten sposób populacja koewoluuje ze sobą.
Bardzo ważnym etapem w algorytmie genetycznym jest selekcja. Pod tym
terminem kryje się sposób wyboru osobników następnej generacji z generacji
rodzicielskiej. Selekcji dokonuje siÄ™, gdy warunek warunek zatrzymania siÄ™
nie jest spełniony, czyli populacja otrzymana w poprzedniej iteracji nie jest
populacją końcową. W wyniku selekcji z bieżącej populacji P(k) tworzona jest
populacja rodzicelska M(k), na której następnie wykonywane są operacje jak
mutacja, krzyżowanie w celu uzyskania następnego pokolenia.
Istnieje wiele sposobów selekcji, jednym z nich jest metoda w której
selekcja odbywa się za pomocą  koła ruletki . Rodzice wybierani są z praw-
dopodobieństwem proporcjonalnym do ich dostosowania. Jeżeli dostosowanie
i-tego osobnika oznaczymy przez fi, to prawdopodobienstwo jego selekcji jest
równe pi = fi/F, gdzie F oznacza sumę dostosowań wszystkich osobników
populacji. Oczywiście taki sposób określania prawdopodobienstwa jest poprawny
tylko wówczas, jeżeli dostosowanie każdego osobnika jest liczbą nieujemną,
a przynajmniej jednego osobnika - liczbÄ… dodatniÄ…. Gdy dostosowanie jest
liczbÄ… rzeczywistÄ…, konieczne jest jego skalowanie. WadÄ… selekcji proporcjonalnej
jest jednak towarzyszący jej stosunkowo wielki błąd stochastyczny, oraz praw-
dopodobienstwo zdominowania osobnika o wysokim dostosowaniu poczÄ…tkowych
etapów ewolucji, co skutecznie ogranicza obazar poszukiwanych rozwiązań i
skutkuje w rozwiÄ…zaniach suboptymalnych.
Wielkość procentowa sektorów:
v(chi) = ps(chi) " 100%
Prawdopodobieństwo selekcji chromosomu:
7
F
n (chi)
ps(chi) =
F (chi)
i=1
Åšrednie przystosowanie populacji:
n
F (chi)
i=1
F {P } =
n
Pojedyncza selekcja turniejowa polega na podzieleniu populacji na małe
grupy, najczęściej złożone z około czterech osobników. Z takich grup wybiera
się po dwóch najlepiej dostosowanych osobnikow, które stanowią rodziców
przyszłego potomstwa. Metoda ta posiada cały szereg zalet.
- W przypadku grup o rozmiarze k zapewnia on przetrwanie k-2 najlepiej
dostosowanym potomkom, co powoduje, że ogólne dostosowanie się populacji
nie pogarsza siÄ™ z czasem.
- Bez względu na to, jak dobrze dopasowany jest osobnik w porównaniu
z resztą populacji, jest on w stanie wygenerować najwyżej jednego potomka
w każdej iteracji, co zapobiega przedwczesnej zbieżności algorytmu.
Selekcja ta znajduje zastosowanie w szerokiej gamie problemów optymalizacyjnych
(wielokryterialnych), jak i zagadnieniach maksymalizacji i minimalizacji
Jeżeli przy generacji następnych populacji dba się o to, aby najlepiej
dopasowane osobniki zawsze znalazły się w puli rodzicelskiej, nazywamy
taką strategię mianem  elitarnej . Taka strategia może znacznie przyspieszyć
proces poszukiwania optymalnego rozwiązania. Istnieje jednak zagrożenie
ograniczenia zdolności eksploracyjnych algorytmu, gdyz początkowa elita niekoniecznie
będzie zawierać geny charakteryzujących najlepsze osobniki.
W podwójnej selekcji turniejowej najpierw wybiera się grupe k osobników,
z której wyłania się jednego rodzica. Drugiego otrzymuje się powtarzając tą
procedure. Selekcja ta może dopuszczać podwójne wylosowanie tego samego
osobnika ( wtedy ten sam osobnik jest pierwszym i drugim rodzicem ), lub
nie. W drugim przypadku mówimy o selekcji bez powtórzeń.
Selekcja rangowa (porządkowa) jest podobna do selekcji  koła ruletki ,
z tym że osobniki są sortowane według ich dostosowania. W ten sposób
ustalana jest ich ranga, która w dalszej części pełni rolę dostosowania osobnika.
Podobnie jak selekcja turniejowa, jest ona odpowiednia do problemów maksymalizacji
i minimalizacji. Nie posiada ona także wady metody ruletki dotyczącej konieczności
8
skalowania funkcji przystosowania.
Kolejną czynnością w algorytmie genetycznym jest krzyżowanie. Polega
ono na losowym kojarzeniu chromosomów w pary i mieszanie ich genomów w
celu utworzenia nowych osobników - potomków. Zazwyczaj podczas krzyżowania
konkretnej pary wybierany jest losowo locus, czyli punkt krzyżowania, a
następnie następuje wymiana odpowiednich części łańcucha między rodzicami,
tak jak jest to przedstawione na poniższych rysunkach:
Istnieją jeszcze inne metody krzyżowania chromosomów. W krzyżowaniu
wielopunktowym na przykład wybierane są dwa lub więcej punktów krzyżowania
chromosomów. Jest ono przydatne, gdy chromosomy są bardzo długie. Poniższy
rysunek pokazuje przykład krzyżowania dwupunktowego:
9
Natomiast w krzyżowaniu równomiernym mamy do czynienia z wylosowaniem
wzorca określającego, które geny potomków są dziedziczone od każdego z
rodziców. Wzorzec jest to łańcuch binarny, w którym wartości 1 wskazują
pozycje (locus) w chromosomie rodzica 1, a wartości 0 odpowiadają pozycjom
w chromosomie rodzica 2. Taka kombinacja tworzy potomka pierwszego,
analogicznie z pozostałych genów powstaje potomek drugi. Przedstawia to
następująca ilustracja:
Różnorodność populacji może być także uzyskana na drodze mutacji.
Mutacja jest procesem losowej zmiany wartości losowego genu w chromosomie
na przeciwny. Zachodzi ona jednakże bardzo rzadko, o wiele rzadziej niż
krzyżowania. Tutaj na przykład został poddany mutacji 4 gen:
Jednakże proces mutacji może być inaczej zdefiniowany w zależności od
rozpatrywanego problemu. Jeżeli chromosom nie posiada reprezentacji binarnej
tylko np. jest kodowany za pomocÄ… liczb rzeczywistych, wtedy mutacjÄ… jest
zmiana tej wartości na inną w sposób losowy korzystając na przykład z
rozkładu normalnego. Jeszcze inaczej realizuje się operacje mutacji w przypadku
problemów kombinatorycznych, gdzie chromosomy stanowią kombinację genów
o wartościach rzeczywistych.
Operator krzyżowania jest operatorem odróżniającym algorytmy genetyczne
od innych algorytmów ewolucyjnych. Jego rola jest jednak krytykowana przez
10
wielu badaczy. Konsekwencja krzyżowania jest  przedwczesna zbieżność
algorytmu, jak określa się zbyt szybką utratę różnorodności populacji. Środkiem
służącym podtrzymaniu właściwej dywersyfikacji populacji, a w konsekwencji
zapewniającym dostateczną eksplorację przestrzeni rozwiązań jest mutacja.
Jednakże mutowanie łańcuchów bitowych z dużym prawdopodobienstwem
jest często destrukcyjne. Dobre rozwiązania tracone są w kolejnych pokoleniach.
Należy dążyć do podtrzymywania właściwej różnorodności populacji, aby
móc eksplorować nowe obszary przestrzeni rozwiązań bez gubienia dotychczas
zdobytej informacji.
Inne rodzaje algorytmów ewolucyjnych:
Oprócz podstawowego algorytmu genetycznego wraz z modyfikacjami rozwinęły
się także inne typy algorytmów ewolucyjnych. Należą do nich: strategie ewolucyjne,
programowanie ewolucyjne i programowanie genetyczne.
We wszystkich strategiach ewolucyjnych mutacja jest najważniejszym
operatorem genetycznym. Razem z selekcją decyduje o działaniu algorytmu
i ma największy wpływ na jego zbieżność. Można wyróżnić trzy główne typy
strategii ewolucyjnych. SÄ… to strategie (1+1), (µ+ ), (µ,).
Przez wybór współczynników µ i  można regulować zasiÄ™g mutacji istotny
z punktu widzenia zbieżności algorytmu. Dodatkowo w porównaniu z PAG
mamy tutaj inny sposób reprezentacji osobników w postaci chromosomów, a
operatory mutacji i krzyżowania są zdefiniowane inaczej.
W strategii (1+1) przetwarzany jest tylko jeden chromosom. W wyniku
losowej modyfikacji wartości każdego genu wchodzącego w skład tego chromosomu
(przez dodanie odpowiedniej liczby zgodnie z rozkładem normalnym) tworzony
jest nowy chromosom. Proces ten nazwany jest w tym przypadku perturbacjÄ….
W każdej iteracji algorytmu porównywane są wartości przystosowania obu
chromosomów i do następnej generacji wybierany jest ten o większej wartości
przystosowania. strategie (1+1), (µ+), (µ,) sÄ… uogólnieniem tej strategii
dla populacji zÅ‚ożonej z µ osobników.
W strategii (µ+) z populacji zÅ‚ożonej z µ osobników tworzy siÄ™ populacje
potomków składającą się z  osobników. Dokonuje się tego przez wielokrotne
losowanie (ze zwracaniem) z populacji o liczebnoÅ›ci µ. Kopie wylosowanych
osobników umieszczamy w grupie pomocniczej tworząc tzw. populację rodzicielską.
Następnie populacja ta jest poddawana mutacjom i krzyżowaniu. W wyniku
11
tych operacji powstaje populacja potomków o liczebności . Po połączeniu
tej populacji z poprzedniÄ… powstaje populacja o wielkoÅ›ci µ + , z której ?
najlepszych osobników bierze udział w kolejnej generacji algorytmu.
Natomiast strategia (µ,) różni siÄ™ od strategii (µ+) tym, że nowÄ…
populacjÄ™, w kolejnej generacji algorytmu, tworzy siÄ™ na podstawie populacji
 potomków zapominając o osobnikach rodzicielskich. W strategii tej każdy
osobnik istnieje tylko podczas jednej generacji, natomiast w (µ+) osobniki
mogą pozostawać w populacji przez wiele kolejnych generacji.
Programowanie ewolucyjne zostało wprowadzone w latach 60 w USA
przez Lawrence Fogela. Fogel stosował tą ewolucyjną metodę w odniesieniu
do automatów skończonych, których działanie było oceniane przez funkcję
przystosowania, a poprzez mutację następowała ewolucja osobników. W latach
90 David Fogel dokonał wielu modyfikacji tej metody upodabniając ją do
strategii ewolucyjnych. Programowanie ewolucyjne znalazło zastosowanie w
modelowaniu i identyfikacji systemów, sterowanie, uczenie sieci neuronowych,
prognozowanie, rozpoznawanie obrazów i problemy kombinatoryczne.
Natomiast programowanie genetyczne jest stosunkowo nowÄ… metodÄ… ewolucyjnÄ….
Rozwinęło się dopiero na początku lat 90. Dotyczy ewolucji programów komputerowych
pisanych wcześniej w takich językach jak LISP, a obecnie również w językach
zbliżonych do C. W metodzie programowania genetycznego chromosomy re-
prezentowane są w postaci drzewa, składającego się z węzłów i krawędzi. Za
pomocą takiej struktury przedstawia się kod programu. Występują operatory
krzyżowania i mutacji, a chromosomy są oceniane na podstawie funkcji przystosowania.
W efekcie otrzymywany jest najlepszy chromosom reprezentujÄ…cy najlepszy
kod programu. Programowanie genetyczne znalazło również zastosowanie w
innych problemach, gdzie można skorzystać z drzewiastej struktury chromosomów,
takich jak synteza drzew decyzyjnych, projektowanie systemów elektronicznych
i teleinformatycznych lub poszukiwanie optymalnej struktury sieci neuronowych.
Zastosowanie algorytmów ewolucyjnych:
Algorytmy ewolucyjne znajdujÄ… zastosowanie w wielu dziedzinach techniki
i nauki m.in. medycynie, ekonomii, matematyce i inżynierii. Głównym lecz
nie wyłącznym obszarem ich zastosowań jest optymalizacja. Można stosować
je do wytyczania trasy połączeń kablowych, sterowania, rozwiązywania zadań
transportowych, optymalizacji wag sieci neuronowych, planowaniu optymalnej
ścieżki robota z omijaniem przeszkód, a także konstrukcja ewolucyjnego robota.
Możliwym zastosowaniem są oczywiście też zagadnienia kombinatoryczne.
Można wykorzystywać algorytmy genetyczne do rozwiązania problemu komi-
12
wojażera, tworzenia harmonogramów, planowania zakupów.
Bardzo ciekawym przykładem potęgi algorytmów genetycznych było za-
projektowanie crooked wire genetic antennas, czyli optymalnego kształtu
anteny nadającej równomiernie we wszystkich kierunkach ponad krzywizną
ziemi. Dokonali tego inżynierowie Edward Altshuler i Derek Linden. W przeci-
wieństwie do przewidywań, symetryczne anteny o geometrycznych kształtach
nie rozwiązywały tego problemu optymalnie. Dopiero algorytm genetyczny
znalazł optymalne rozwiązanie którym okazała się śmieszna plątanina drutów.
Co więcej, znaczące jest, że genetyczny algorytm wyszukał ją wśród innych,
podobnie fantazyjnie poskręcanych anten, z których większość jednak nie
pracowała właściwie. Zanim jednak Altshuler i Linden napisali genetyczny
algorytm do znajdowania takich anten, byli oni po prostu zainteresowani
w ich znalezieniu. Dokładnie zdefiniowali co szukają i jakie kryteria musi
spełniać przyszła antena. Stworzona przez nich funkcja dostosowania mierzyła
stopień w jakim kolejne testowane anteny nadawały równomiernie. Funkcja
ta nie spadła z nieba, ale była precyzyjnie zaprojektowana na bazie ich
naukowej wiedzy. Od momentu gdy inżynierowie ci zdefiniowali właściwą
funkcję dostosowania, rozwiązali tym samym oryginalny problem. Pozostało
tylko, by algorytm genetyczny testował pod kątem zdefiniowanych wcześniej
kryteriów różne losowo  powykrzywiane anteny. I odnalazł tę, która najlepiej
spełnia zadane kryteria.
Z ciekawszych zrealizowanych zastosowań tych algorytmów można wymienić
także: adaptacyjny program do gry w pionki stworzony przez Begleya już w
1967 roku, system analizy obrazów medycznych za pomocą cyfrowej angiografii
różnicowej (Fitzpatrick, Grefenstette, Van Gucht), zaprojektowanie zestawu
detektorów cech dla urządzenia rozpoznającego (Cavicchio w pracy doktorskiej
w 1970 roku).
13
Bibliografia:
http://www.creationism.org.pl/weasel
http://www.ii.uni.wroc.pl/ lipinski/ea notes.html
http://www.alife.pl/portal
http://panda.bg.univ.gda.pl/ sielim/genetic/
http://www.republika.pl/k0pper/geny.htm
David E. Goldberg -  Algorytmy genetyczne i ich zastosowania
Zbigniew Michalewicz -  Algorytmy genetyczne + struktury danych = programy
ewolucyjne