ag.pdf

Fragment 3 rozdziaþu z ksiĢŇki: S.T. Wierzchoı, Sztuczne systemy immunologiczne. Teoria i

zastosowania. Akademicka Oficyna Wydawnicza EXIT, Warszawa 2001

Rozdziaþ 3

Algorytmy genetyczne

Celem tego rozdziaþu jest prezentacja podstawowych pojħę dotyczĢcych algorytmw genetycznych, ktre

bħdĢ wykorzystywane w dalszych partiach ksiĢŇki. Czytelnika zainteresowanego szczegþami technicznymi

odsyþamy do literatury Ņrdþowej, np. [71], [135]. Tu natomiast skoncentrujemy siħ na omwieniu istoty

algorytmw genetycznych ze wskazaniem wþasnoĻci genetycznych operatorw selekcji, krzyŇowania i

mutacji. Omwimy podstawowe dla teorii algorytmw genetycznych twierdzenie o schematach i wynikajĢce

zeı konsekwencje. W szczeglnoĻci zajmiemy siħ problemem podtrzymywania rŇnorodnoĻci populacji

przedstawiajĢc tzw. techniki niszowe. ZdolnoĻę podtrzymywania takiej rŇnorodnoĻci zarwno w ukþadzie

odpornoĻciowym jak i eko-systemach jest faktem oczywistym. Natomiast algorytmy genetyczne wymagajĢ

sporej dozy inwencji do uzyskania zbliŇonego efektu. Wreszcie przedstawimy dwa przykþadowe

zastosowania algorytmw genetycznych do zadaı uczenia maszynowego. Pierwszy przykþad dotyczy

ekstrakcji wiedzy z baz danych i jej reprezentacji w postaci pewnego skierowanego grafu reprezentujĢcego

zaleŇnoĻci przyczynowo-skutkowe miħdzy atrybutami definiujĢcymi schemat bazy danych. Omwimy tu

wþasne rozwiĢzanie tego problemu. Drugi przykþad to tzw. systemy klasyfikujĢce uznawane przez wielu

autorw za najbardziej nowatorskĢ propozycjħ Johna Hollanda. WykazujĢ one intrygujĢcĢ zbieŇnoĻę z

wþasnoĻciami ukþadu odpornoĻciowego Î do problemu tego powracamy pod koniec rozdziaþu 4.

3.1. Uwagi wstħpne

IstotĢ sformuþowanej przez Karola Darwina w 1859 roku teorii ewolucji jest adaptacja rozumiana jako

proces przebiegajĢcy bez wyznaczonego celu, a polegajĢcy na zmianach organizmw wskutek

oddziaþywania z otoczeniem. RolĢ tych zmian jest poprawa sprawnoĻci czy teŇ skutecznoĻci danego

organizmu. PodkreĻlmy jednak wyraŅnie: sedno darwinowskiej adaptacji polega na znajdowaniu ulepszeı, a

nie rozwiĢzaı optymalnych. Ewolucja wiħkszoĻci organizmw uwarunkowana jest dwoma mechanizmami:

doborem naturalnym i rozmnaŇaniem pþciowym. Pierwszy z tych mechanizmw wyznacza te jednostki,

ktre przeŇyjĢ i wydadzĢ potomstwo, drugi zaĻ zapewnia wymieszanie i rekombinacjħ genw potomstwa. Na

dobr naturalny moŇna spoglĢdaę jak na áarenħ krwawych walk na kþy i pazuryÑ, ale moŇna go teŇ traktowaę

jako przejaw oglniejszego prawa áprzetrwania najstabilniejszychÑ, jak pisze o tym Dawkins, [40].

Pierwsze prby poþĢczenia teorii ewolucji z informatykĢ prowadzono na przeþomie lat piħędziesiĢtych i

szeĻędziesiĢtych. Jak stwierdza Holland, [101], brak sukcesw wynikaþ z naĻladownictwa wczesnych

podrħcznikw biologii, ktre kþadþy wiħkszy nacisk na rolħ mutacji jako Ņrdþa zmiennoĻci genetycznej w

porwnaniu 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ħ zarwno 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 sposb powstaþ uniwersalny

algorytm znany pod nazwĢ algorytmu genetycznego.

Odnotujmy na marginesie, Ňe niemal rwnolegle z pracami Hollanda, w Niemczech prowadzono prace nad

tak zwanymi strategiami ewolucyjnymi wykorzystujĢcymi mechanizmy selekcji i mutacji naturalnej. O ile

algorytmy genetyczne moŇna traktowaę jako algorytmy oglnego przeznaczenia, o tyle strategie ewolucyjne

zorientowane sĢ na rozwiĢzywanie zadaı optymalizacji parametrycznej. Postħp w obu dziedzinach zatarþ

wiele z dzielĢcych je rŇnic. Obecnie czħsto mwi siħ o algorytmach ewolucyjnych rozumiejĢc pod tym

pojħciem dowolny algorytm przetwarzajĢcy populacjħ rozwiĢzaı, ktra to populacja modyfikowana jest w

sposb naĻladujĢcy biologiczne narodziny i Ļmierę, a reprodukowane osobniki nie sĢ dokþadnymi kopiami

swoich rodzicw.

Prostym przykþadem algorytmu ewolucyjnego jest algorytm dopasowywania do wzorca. Algorytm ten

przetwarza populacjħ þaıcuchw znakw inicjowanych losowo, a celem ewolucji jest uzyskanie þaıcucha o

zadanej postaci, powiedzmy áDobr naturalny to krwawa walka na kþy i pazuryÑ. Dopasowanie dowolnego

þaıcucha z populacji do wzorca okreĻla liczba pozycji, na ktrych w obu þaıcuchach wystħpujĢ identyczne

litery. W kaŇdej iteracji, po wymieszaniu osobnikw, populacjħ dzieli siħ na maþe grupy. Najlepszy (w

opisanym wyŇej sensie) osobnik w kaŇdej grupie jest kopiowany i zastħpuje najgorszego osobnika w tej

grupie, przy czym losowo wybrana pozycja kopii poddawana jest mutacji, tzn. wystħpujĢcy tam znak

zmieniany jest na inny, wybrany losowo. Opisana tu operacja odzwierciedla ániedokþadnĢ reprodukcjħÑ

charakterystycznĢ dla naturalnej ewolucji. Nietrudno zauwaŇyę, Ňe populacja þaıcuchw bħdzie z upþywem

czasu (mierzonego liczbĢ ápokoleıÑ, czyli iteracji) dĢŇyę do populacji zawierajĢcej wiele þaıcuchw

zgodnych ze wzorcem. Przeszukiwanie realizowane jest tu wyþĢcznie drogĢ wprowadzania ániewielkich

zmianÑ, czyli mutacji. WprowadzajĢc dodatkowy operator stanowiĢcy odpowiednik reprodukcji pþciowej,

czyli operator krzyŇowania (por. punkt 3.2.5) uzyskujemy algorytm genetyczny. W rozwaŇanym tu

przykþadzie operator ten moŇna zrealizowaę w sposb 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 liter pierwszego þaıcucha kopiowanych od poczĢtku do ustalonej

wczeĻniej pozycji, a resztħ liter pobiera siħ od drugiego rodzica poczynajĢc od kolejnej pozycji. Drugi

potomek tworzony jest analogicznie, z tym, Ňe jego poczĢtkowe litery pobierane sĢ od drugiego rodzica, a

koıcowe od pierwszego.

3. Algorytmy genetyczne

3.2. Operatory genetyczne

Algorytm genetyczny ma dobrze znanĢ postaę Î por. [71], [135]. Po wybraniu odpowiedniej dla

rozwiĢzywanego problemu reprezentacji osobnikw (por. punkt 3.2.1) inicjuje siħ poczĢtkowĢ ich populacjħ

(punkt 3.2.2), a nastħpnie powtarza okreĻlonĢ (poprzez wybranie warunku zatrzymania iteracji) iloĻę razy

nastħpujĢce operacje:

po pierwsze ocenia siħ jakoĻę osobnikw z aktualnej populacji (stosujĢc tzw. funkcjħ dostosowania Î

por. punkt 3.2.3),

po drugie tworzy siħ nowĢ populacjħ stosujĢc operatory selekcji, krzyŇowania i mutacji omwione

odpowiednio w punktach 3.2.4, 3.2.5 i 3.2.6.

3.2.1. Definicja osobnikw

Pierwszym krokiem implementacji algorytmu genetycznego jest okreĻlenie struktury danych dla osobnikw

tworzĢcych populacjħ podlegajĢcĢ ewolucji. Struktura ta okreĻlana jest czħsto terminem chromosom. Jak

stwierdza Goldberg, wybr takiej struktury ánie stanowi Ňadnego problemu, gdyŇ programista jest

ograniczony gþwnie swojĢ wþasnĢ wyobraŅniĢÑ ([71] str. 95). Tym niemniej przy wyborze struktury naleŇy

kierowaę siħ z jednej strony jej uniwersalnoĻciĢ, a z drugiej jej prostotĢ. Przez uniwersalnoĻę struktury

rozumiemy to, Ňe powinna ona umoŇliwiaę reprezentacjħ potencjalnych rozwiĢzaı nie tylko pojedynczego

zadania, ale przynajmniej dowolnego zadania naleŇĢcego do okreĻlonej klasy problemw. Na przykþad

struktura powinna umoŇliwiaę reprezentacjħ rozwiĢzaı dowolnego zadania optymalizacji funkcji

rzeczywistej n zmiennych. Przez jej prostotħ rozumiemy þatwoĻę posþugiwania siħ takĢ strukturĢ, przede

wszystkim þatwoĻę wyznaczania dostosowania konkretnego osobnika.

JednĢ z zasad wyboru struktury jest zasada minimalnego alfabetu, tzn. naleŇy wybraę najmniejszy alfabet, w

ktrym dane zadanie wyraŇa siħ w sposb naturalny, [71]. Najbardziej popularnĢ strukturĢ jest þaıcuch

binarny o dþugoĻci l. DþugoĻę ta Î dla kaŇdego osobnika populacji Î moŇe byę albo staþa, albo zmienna.

Chromosomy o staþej dþugoĻci sĢ znacznie prostsze, ale chromosomy o zmiennej dþugoĻci sĢ bardziej

elastyczne, gdyŇ umoŇliwiajĢ bardziej naturalnĢ reprezentacjħ konkretnych rozwiĢzaı. ReprezentacjĢ

wygodnĢ do rozwiĢzywania zadaı optymalizacji funkcji n zmiennych jest przyjħcie za chromosom n

wymiarowego wektora o skþadowych rzeczywistych. Z kolei w zadaniach uczenia maszynowego

chromosomy reprezentujĢ albo pojedyncze reguþy (jest to tzw. podejĻcie Michigan, ktre moŇna traktowaę

jako komputerowy model ĻwiadomoĻci), albo teŇ caþy zestaw reguþ, czyli oddzielnĢ ĻwiadomĢ jednostkħ

3.3. Twierdzenie o schematach 3

(tzw. podejĻcie Pitt) 1 . JeŇeli natomiast kaŇdy chromosom reprezentuje pojedynczy program Î mamy do

czynienia z tzw. programowaniem genetycznym, [126].

Bez wzglħdu na to, jak zþoŇony jest chromosom przyjmuje siħ, Ňe skþada siħ on z liniowo uszeregowanych

genw (tzn. znakw, cech lub dekoderw), ktre mogĢ wystħpowaę w pewnej liczbie odmian nazywanych

allelami 2 . Pozycjħ genu w chromosomie okreĻla siħ terminem locus.

Zestaw genw charakteryzujĢcy pojedynczego osobnika okreĻlany jest w biologii genotypem. W

algorytmach genetycznych przyjmuje siħ zazwyczaj, Ňe mamy do czynienia z osobnikami haploidalnymi 3 ,

tzn. osobnikami wyposaŇonymi w pojedynczy chromosom. Jak pisze Dawkins á(...) dobr darwinowski nie

moŇe dziaþaę bezpoĻrednio na geny. Wszystkie geny wyglĢdajĢ podobnie, tak samo jak podobne do siebie sĢ

taĻmy magnetofonowe. Istotne rŇnice miħdzy genami ujawniajĢ siħ w skutkach ich dziaþania. (...) Termin

ÒfenotypÓ uŇywany jest dla okreĻlenia cielesnej manifestacji genu Î jego wpþywu na rozwj osobnika, w

porwnaniu do wpþyww wywieranych przez jego allele.Ñ 4 W rozpatrywanym w tym rozdziale ácyfrowymÑ

Ļwiecie, jeŇeli genotypem jest na przykþad þaıcuch binarny, to fenotypem jest jego reprezentacja dziesiħtna.

3.2.2. Populacja poczĢtkowa

Populacja poczĢtkowa stanowi zbir chromosomw, ktre bħdĢ poddawane ewolucyjnym modyfikacjom.

Przy jej tworzeniu poŇĢdane jest zachowanie jak najwiħkszej rŇnorodnoĻci osobnikw, co sprzyja szybkiej

ocenie moŇliwie duŇej liczby potencjalnych rozwiĢzaı, bez nadmiernego zwiħkszania rozmiaru populacji.

NajpopularniejszĢ i najprostszĢ metodĢ tworzenia populacji poczĢtkowej jest losowa generacja

chromosomw. W pewnych sytuacjach metoda taka nie jest efektywna, gdyŇ wiele osobnikw moŇe nie

speþniaę ograniczeı wystħpujĢcych w rozwiĢzywanym zadaniu (przykþadem moŇe byę zadanie

programowania liniowego lub nieliniowego polegajĢce na wyznaczeniu optimum funkcji przy dodatkowych

ograniczeniach rwnoĻciowych i nierwnoĻciowych Î por. rozdziaþ 7 w [135]). W takich przypadkach

dobrze jest odwoþaę siħ do wiedzy o rozwiĢzywanym problemie i ázaprojektowaęÑ zestaw chromosomw 5 .

Nawet jeŇeli populacja tworzona jest losowo, wiedzħ o problemie moŇna wykorzystaę do wyboru rozkþadu

prawdopodobieıstwa, z ktrym bħdĢ wybierane poszczeglne allele 6 . Inna metoda polega na wykorzystaniu

wynikw poprzedniego przebiegu algorytmu genetycznego do zainicjowania populacji. Wreszcie, czasem

wystarczy wprowadzenie do populacji kilku specjalnie zaprojektowanych osobnikw i zapeþnienie reszty

populacji osobnikami losowymi.

WaŇnym parametrem algorytmu jest liczebnoĻę populacji. JeŇeli bħdzie ona zbyt maþa, algorytm moŇe

zbiegaę zbyt szybko; jeŇeli bħdzie zbyt duŇa Î niepotrzebnie bħdzie zuŇywaę siħ czas i zasoby komputerowe.

LiczebnoĻę populacji moŇe byę staþa we wszystkich iteracjach, albo teŇ moŇe ulegaę zmianom Î problemy te

omwiono w punkcie 4.4 ksiĢŇki [135].

3.2.3. Ocena dostosowania

Zasadniczym etapem kaŇdej iteracji algorytmu jest obliczenie tzw. dostosowania osobnikw wchodzĢcych

w skþad modyfikowanej populacji. Dostosowanie jest pewnĢ miarĢ obrazujĢcĢ, jak dobrze okreĻlony osobnik

áradzi sobieÑ z rozwiĢzywanym problemem. WþaĻciwy dobr dostosowania jest kluczowym elementem

algorytmu genetycznego. Jest to þĢcznik miħdzy abstrakcyjnym (uniwersalnym) algorytmem powielajĢcym

1 Krtki przeglĢd tych zagadnieı moŇna znaleŅę w rozdziale 12 ksiĢŇki [135].

SĢ to w gruncie rzeczy wartoĻci cech. W przypadku þaıcuchw binarnych allele to symbole 0, 1.

3 Informacjħ na temat diploidalnoĻci, czyli podwjnego zestawu chromosomw i dominowania, czyli waŇonych zaleŇnoĻci miħdzy

genotypem a fenotypem, moŇna znaleŅę w rozdziale 5 ksiĢŇki [71].

4 Por. [40], str. 321.

W literaturze anglosaskiej uŇywa siħ terminu seeding the run na okreĻlenie tak inicjowanej populacji.

6 Por. punkt 7.3.3.1

opisane wczeĻniej kroki a rzeczywistym problemem. W przypadku optymalizacji funkcji za miarħ

dostosowania moŇna przyjĢę wartoĻę optymalizowanej funkcji. W wielu jednak problemach, np. uczenia

maszynowego, dobr miary dostosowania nie jest sprawĢ trywialnĢ. Z uwagi na fakt, Ňe dostosowanie

obliczane jest dla kaŇdego osobnika i w kaŇdej iteracji algorytmu, funkcja czy teŇ procedura realizujĢca

pomiar dostosowania powinna byę moŇliwie prosta. Powinna jednoczeĻnie odzwierciedlaę charakterystyki

istotne dla poszukiwanego rozwiĢzania. W pewnych, szczeglnie zþoŇonych, sytuacjach moŇna wyobrazię

sobie dwuetapowy pomiar dostosowania osobnikw. W poczĢtkowych iteracjach dostosowanie to moŇna

liczyę w sposb przybliŇony, stosujĢc uproszczonĢ procedurħ, aby moŇliwie szybko zlokalizowaę obszary

wystħpowania potencjalnych rozwiĢzaı. Dopiero w dalszych iteracjach, gdy prbne rozwiĢzania poddawane

sĢ kolejnym modyfikacjom genetycznym, moŇna obliczaę precyzyjnie dostosowanie proponowanych

rozwiĢzaı.

3. Algorytmy genetyczne

IstniejĢ dwa typy modyfikacji, ktrym mogĢ podlegaę osobniki poczĢtkowych populacji. Pierwszy z tych

typw, nazywany po prostu ewolucjĢ, polega na niezaleŇnym pomiarze dostosowania kaŇdego osobnika.

Jako miarħ jakoĻci przyjmuje siħ tu jego bezwzglħdne dostosowanie do wymogw stawianych

poszukiwanemu rozwiĢzaniu. W drugim typie, nazywanym koewolucjĢ, dostosowanie pojedynczego

osobnika uwzglħdnia wþasnoĻci pozostaþych czþonkw populacji. Omawiane w punkcie 3.5 metody niszowe,

stosowane w optymalizacji wielomodalnej, sĢ najprostszym przykþadem koewolucji. ObecnoĻę duŇej liczby

osobnikw o duŇym dostosowaniu skoncentrowanych wokþ pewnego punktu wpþywa na obniŇenie ich

dostosowania ápostrzeganegoÑ przez algorytm. W ten sposb populacja koewoluuje ze sobĢ, co prowadzi

(przynajmniej w zamyĻle) do oczekiwanego rezultatu. Podany przykþad jest tylko niewielkĢ modyfikacjĢ

ástandardowegoÑ algorytmu ewolucyjnego. Niejako klasycznym juŇ przykþadem bardziej wyrafinowanego

traktowania koewolucji jest praca [93] poĻwiecona symulowaniu zachowaı pasoŇytw, omwiona w

punkcie 3.5.3.

PrzypisujĢc kaŇdemu osobnikowi populacji jego dostosowanie moŇemy mwię o pejzaŇu dostosowaı Î

przestrzeni, w ktrej istnieje i ewoluuje dana populacja. Aby prawidþowo przedstawiaę takĢ przestrzeı,

naleŇy okreĻlię najpierw relacjħ podobieıstwa na zbiorze wszystkich struktur. Pojħcie pejzaŇu dostosowaı

uŇywane jest przez biologw od lat 30-tych dwudziestego wieku do opisu ewolucji genotypw jako procesu

poszukiwania, w ktrym zmiany genetyczne gatunkw powodujĢ ich przemieszczanie siħ miħdzy ápikamiÑ

w przestrzeni genotypw.

3.2.4. Modele ewolucji

Pod pojħciem ámetoda ewolucjiÑ rozumiemy metodħ wyboru osobnikw do tzw. puli rodzicielskiej.

Osobniki tworzĢce tħ pulħ poddawane sĢ nastħpnie operacjom krzyŇowania i mutacji prowadzĢcym do

utworzenia potomnej populacji osobnikw przetwarzanej w kolejnej iteracji algorytmu. Wybr wþaĻciwego

modelu ewolucji znaczĢco wpþywa na jakoĻę algorytmu.

Najprostszym typem selekcji jest selekcja proporcjonalna wykorzystujĢca reguþħ ruletki. Rodzice

wybierani sĢ z prawdopodobieıstwem proporcjonalnym do ich dostosowania. JeŇeli dostosowanie i-tego

osobnika oznaczymy przez f i , to prawdopodobieıstwo jego selekcji jest rwne p i = f i /F, gdzie F oznacza

sumħ dostosowaı wszystkich osobnikw populacji. OczywiĻcie taki sposb okreĻlania prawdopodobieıstwa

jest poprawny tylko wwczas, jeŇeli dostosowanie kaŇdego osobnika jest liczbĢ nieujemnĢ, a przynajmniej

jednego osobnika Î liczbĢ dodatniĢ. W sytuacjach, gdy dostosowanie pojedynczego osobnika wyraŇa siħ

liczbĢ rzeczywistĢ, konieczne jest jego skalowanie. Problem ten omwiono wyczerpujĢco w [71]. WadĢ

selekcji proporcjonalnej jest towarzyszĢcy jej stosunkowo duŇy bþĢd stochastyczny selekcji. Brindle, [22],

obliczyþa wariancjħ tego bþħdu: s i 2 = nµp i µ(1-p i ), gdzie n oznacza rozmiar populacji. Aby zmniejszyę tħ

wariancjħ, zaproponowaþa ona metodħ nazwanĢ wyborem losowym wg reszt z powtrzeniami 7 ; w tym

wypadku wariancja jest rwna s i 2 = r i µ(1-r i )/(Ã i=1,...,n r i ), gdzie r i = nµp i µ(1- nµp i ), jest prawdopodobieıstwem

7 Por. [71], str. 136-137.

3.3. Twierdzenie o schematach 5

resztowego wyboru osobnikw. InnĢ metodĢ redukcji wariancji jest uniwersalna selekcja stochastyczna, w

ktrej tarcza ruletki dzielona jest na m rwnych czħĻci, gdzie m oznacza liczbħ osobnikw przeznaczonych

do wylosowania, [9]. W przypadku tej startegii wariancja jest rwna zero, a liczba kopii danego osobnika

jest nie mniejsza niŇ É nµp i Ù i nie wiħksza niŇ Ç nµp i ×.

Pojedyncza selekcja turniejowa polega na áwymieszaniuÑ populacji i podzieleniu jej na maþe grupy

najczħĻciej zþoŇone z czterech osobnikw. Z kaŇdej grupy wybiera siħ dwch osobnikw o najwyŇszym

dostosowaniu. Pary wybranych w ten sposb osobnikw stanowiĢ rodzicw przyszþego potomstwa. Taki

mechanizm wyboru rodzicw posiada szereg zalet. Po pierwsze, w przypadku maþych grup o rozmiarze k

zapewnia to szansħ przetrwania k-2 najlepszym osobnikom, co z kolei gwarantuje, Ňe dostosowanie populacji

nie pogarsza siħ w trakcie kolejnych iteracji. Po drugie, bez wzglħdu na to, jak dobrze dostosowany jest

osobnik w porwnaniu z resztĢ populacji, produkuje on co najwyŇej jednego potomka w kaŇdej iteracji.

WþasnoĻę ta zapobiega przedwczesnej zbieŇnoĻci populacji Î problemowi, z ktrym boryka siħ wiħkszoĻę

modeli ewolucji. W selekcji proporcjonalnej osobnik o wysokim dostosowaniu dominuje poczĢtkowe etapy

ewolucji, co skutecznie ogranicza obszar poszukiwaı i powoduje zbieŇnoĻę populacji do rozwiĢzaı

suboptymalnych.

JeŇeli przy wyborze rodzicw dba siħ o to, aby najlepiej dostosowane osobniki, nazywane elitĢ, byþy zawsze

czþonkami puli rodzicielskiej, strategiħ takĢ okreĻla siħ mianem elitarnej. Strategia ta powoduje, Ňe w

dalszych iteracjach maksymalne dostosowanie w populacji nie bħdzie zbyt wysokie, ale potomstwo elity

bħdzie dominowaę przyszþe populacje. MoŇe to ograniczaę zdolnoĻci eksploracyjne algorytmu, gdyŇ

poczĢtkowa elita niekoniecznie zawiera geny charakteryzujĢce najlepsze osobniki. RozwiĢzaniem jest

utrzymywanie elity o niewielkim rozmiarze, podobnie jak ma to miejsce w pojedynczej selekcji turniejowej,

gdzie elita skþada siħ z dwch osobnikw.

W podwjnej selekcji turniejowej wybiera siħ najpierw grupħ zþoŇonĢ z k osobnikw, a nastħpnie z grupy

tej wybiera siħ najlepiej dostosowanego osobnika i traktuje go jako pierwszego rodzica. W celu wyboru

drugiego rodzica procedura jest powtarzana. Selekcja rodzicw moŇe albo dopuszczaę powtrzenia (ten sam

osobnik jest pierwszym i drugim rodzicem), albo nie. W drugim przypadku mwimy o selekcji bez

powtrzeı.

Selekcja rangowa (porzĢdkowa) jest podobna do selekcji wedþug reguþy ruletki z tym, Ňe osobniki sĢ

sortowane wedþug ich dostosowania, a ich rangi peþniĢ rolħ funkcji dostosowania.

DysponujĢc pulĢ rodzicielskĢ naleŇy opracowaę strategiħ wprowadzania potomkw do nowej populacji.

MoŇna to czynię zwiħkszajĢc rozmiar populacji (np. w ciĢgu kilku iteracji doþĢczaę potomkw do starej

populacji, a po pewnej ich liczbie usunĢę ánadmiarowychÑ osobnikw wracajĢc do poczĢtkowego rozmiaru

populacji), albo teŇ w kaŇdej iteracji zachowywaę staþy rozmiar populacji. W tym drugim przypadku

najprostszĢ, losowĢ, strategiĢ jest wstawianie potomka w losowo wybrane miejsce. JeŇeli wybieranie

osobnikw do zastĢpienia odbywa siħ z prawdopodobieıstwem odwrotnym do ich dostosowania, mamy do

czynienia z zastħpowaniem wedþug reguþy ruletki. Odpowiednikiem rangowej strategii zastħpowania jest

uszeregowanie osobnikw w kolejnoĻci odwrotnej niŇ w selekcji rangowej i wybieranie ich z

prawdopodobieıstwem proporcjonalnym do przydzielonej rangi. Inna metoda to zastħpowanie wedþug

absolutnego dostosowania: najsþabiej dostosowane osobniki starej populacji zastħpowane sĢ przez nowe

osobniki. Kolejna metoda polega na zastħpowaniu starych osobnikw nowymi tylko wwczas, gdy nowe

osobniki majĢ wyŇsze dostosowanie niŇ stare. Mianowicie, dwch rodzicw porwnuje siħ z ich

potomstwem; potomek zastħpuje rodzica tylko wtedy, gdy jest od niego lepszy. Jest to tzw. lokalne

zastħpowanie elitarne. W losowym zastħpowaniu elitarnym potomek porwnywany jest z losowo

wybranym rodzicem.

W kaŇdej z omwionych strategii na poczĢtku podejmuje siħ decyzjħ, jak wiele par rodzicw naleŇy wybraę

do stosownego porwnania. Kraıcowe rozwiĢzania polegajĢ na zastĢpieniu wszystkich rodzicw, albo tylko

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: