Nisze I koewolucja



Pobieranie 125.58 Kb.
Strona1/2
Data19.06.2016
Rozmiar125.58 Kb.
  1   2
NISZE I KOEWOLUCJA

  • Nisza ekologiczna. Zakres wszystkich warunków środowiskowych (czynników biotycznych i abiotycznych) w jakich potencjalnie może rozwijać się i żyć populacja danego gatunku, ze względu na swoje przystosowania (np. sposób odżywiania się, unikania drapieżnika, wymagania termiczne, tolerancja na zasolenie wód); nisze ekologiczne poszczególnych gatunków określają ich wzajemne zależności w biocenozie, im są podobniejsze, tym silniejsza konkurencja między gatunkami.

  • Specjacja. Proces gatunkotwórczy, (biol.) Zasadniczy, powszechny proces w ewolucji organizmów, prowadzący do powstania nowych gatunków z gatunków wcześniej ukształtowanych.

  • Dryf genetyczny. (biol.) Nieregularne, losowe wahania częstości występowania genu w małych, izolowanych populacjach; czynnik ewolucji – eliminując dany gen lub zwiększając jego częstość hamuje lub przyspiesza procesy selekcji.

  • Heterozja. (biol.) Zjawisko zwiększonej żywotności i bujności występujące u mieszkańców między liniami wsobnymi – kojarzenia wsobne (chów wsobny), w porównaniu z formami rodzicielskimi.

  • Panmiksja. Całkowita swoboda kojarzenia prowadząca do wymieszania podpopulacji.

Niszowanie
Metody niszowania i specjacji były punktem zwrotnym i w znaczny sposób rozwinęły genetyczne algorytmy w kierunku współbieżnego znajdowania wielu rozwiązań. Jednak jest to bardzo trudne, gdyż te metody w przyrodzie są bardzo złożone i trudno przenieś je do algorytmów genetycznych. Intuicyjnie możemy niszę przyrównać do określonego zawodu (pracy) lub funkcji pełnionej przez dany organizm w środowisku, natomiast przez specjację - gatunek klasy organizmów o wspólnej charakterystyce. Ten podział obszaru i organizmów wykorzystujących środowisko na odrębne podzbiory jest bardzo powszechny w przyrodzie, lecz algorytm genetyczny nie odzwierciedla tego bez specjalnych technik, aby uzyskać pożądany efekt stabilnych podpopulacji (gatunków) związanych z różnymi poddziedzinami funkcji („górkami”). Jeżeli przeszukujemy przestrzeń od populacji początkowej wybranej losowo to otrzymamy zbiór punktów rozmieszczonych mniej więcej równomiernie na odcinku stanowiącym dziedzinę funkcji. Z czasem po następnych przebiegach populacja będzie wspinała się po zboczach gromadząc się ostatecznie (większość osobników) w pobliżu wierzchołka jednego z pięciu wzgórz (tak jak na rys. 2.5).

f1(x)

1







0,5




x

0


0,5

1



Rys. 2.5. Prosty algorytm genetyczny dla f1(x)

Końcowe skupienie się wokół jednego wierzchołka jest spowodowane dryfem genetycznym .

Podobnie niepożądanie zachowuje się algorytm genetyczny w przypadku funkcji wielomodalnych, których maksima lokalne nie są na tej samej wysokości (rys. 2.6).
f2(x)


1







0,5






0


0,5

x

Rys. 2.6. Prosty algorytm genetyczny dla f2(x)
Czasami jednak chcemy zlokalizować inne wierzchołki znajdujące się w innych obszarach przestrzeni lub ustalić proporcjonalność wielkości podpopulacji w sąsiedztwie każdego wierzchołka do jego wysokości. W obu powyższych przykładach widzimy całkowite odrzucenie podziału środowiska na odrębne podzbiory. W przyrodzie jest zupełnie przeciwnie. Aby lepiej zrozumieć, dlaczego tworzenie się odrębnych gatunków na innych obszarach jest opłacalne (nisze i specjacje), przedstawiona zostanie jedna z pierwszych koncepcji teoretycznych dla algorytmów genetycznych Hollanda z 1975 r. – dwuramienny bandyta z podziałem wypłaty.

Mamy dwa ramiona i wypłata wynosi równo 75 $ dla prawego ramienia i 25 $ dla lewego ramienia i początkowo nie wiadomo, które z ramion przynosi większy dochód. Zakładając że mamy populację ze 100 graczy., to z czasem po reprodukowaniu się osobników proporcjonalnie do przystosowania, coraz liczniejsza liczba osobników powinna oczywiście ustawiać się w kolejce do prawego ramienia, aż wreszcie cała populacja skupi się na prawym ramieniu. Teraz zamiast wypłacać pełną wygraną każdemu osobnikowi tj. 75 $, będziemy się ją dzielić (ang. sharing) pomiędzy graczami ustawionymi w tej samej kolejce. Osobnik ustawiony w kolejce do prawego ramienia otrzymuje 0,75 $, w przypadku gdy wszyscy pozostali gracze stoją w tej samej kolejce. Gdyby wszyscy gracze ustawili się przy lewym ramieniu, każdy grający otrzymałby kwotę 25 $ / 100 = 0,25 $. W obu przypadkach pewna liczba graczy ma motywację do zmiany kolejki. W przypadku gracza przy prawym ramieniu, zmiana polegająca na przejściu do lewego ramienia daje dochód 25 $ - 0,75 $ = 24,25 $. W przypadku gracza zmieniającego lewe ramie na prawe motywacja do zmiany kolejki jest jeszcze większa 75 $ - 0,25 $ = 74,75 $. Możemy więc spodziewać się, że gdzieś pośrodku leży punkt, w którym nikomu nie opłaca się już zmieniać kolejki. Dzieje się tak, gdy wypłaty dla poszczególnych graczy w obu kolejkach są jednakowe. W naszym przykładzie całkowite wyrównanie wypłat indywidualnych nastąpi gdy 75 graczy wybierze prawe ramię a 25 graczy lewe ramię, ponieważ 75 $ / 75 = 25 $ / 25 = 1 $. Wprowadzenie przymusowego podziału pociąga za sobą formowanie się stabilnych podpopulacji (gatunków) związanych z różnymi ramionami. W dodatku liczba osobników zajmujących określone ramię jest proporcjonalna do oczekiwanej wypłaty. Ta jedna modyfikacja „sharing” pociąga za sobą dramatyczne i zaskakujące skutki nawet w przypadku k-ramiennego bandyty – a jeszcze bardziej przy analizie funkcji wielomodalnej. Oprócz tego należy zwrócić uwagę, że pozwoliliśmy na losowe kojarzene się osobników, a w przyrodzie takie zjawisko jest niedopuszczalne, gdyż dopuszczenie kojarzenia się osobników różnych od siebie gatunkowo (pies ze świnią) doprowadziłoby do upośledzonego pokolenia degeneratów. Obrazuje to rys. 2.7 z funkcją o wartościach maksymalnych na przeciwległych końcach odcinka, na którym jest określona.



00000

11111
f (x)



00111

11000

0


0

x


Rys. 2.7. Zależność kojarzenia się osobników

Jeśli użyjemy zwykłego dwójkowego kodu pozycyjnego to osobniki położone w pobliżu lewego maksimum będą miały w sobie dużo zer, podczas gdy osobniki położone w pobliżu prawego maksimum będą miały dużo jedynek. Lewe maksimum funkcja osiąga dla ciągu 00000 a prawe dla ciągu 11111. W miarę jak postępuje proces reprodukcji, krzyżowania i mutacji, osobniki potomne będą na ogół przypominać ciągi np. 00111 lub 11000, stosunkowo bezużyteczne – w tym przypadku zestawienie zer i jedynek. Kojarzenie międzygatunkowe prowadzi więc do „chorego” pokolenia osobników potomnych.

Oczywiście przeniesienie koncepcji Hollanda -„sharing” na grunt algorytmów genetycznych jest sprawą trudniejszą, niż sugeruje to powyższy wyidealizowany przykład dwuramiennego bandyty. W rzeczywistym algorytmie genetycznym mamy do czynienia z wieloma „ramionami” – funkcjami wielomodalnymi i decyzja, kto i w jakim stopniu powinien korzystać z podziału nie jest trywialna.

Realizowano już różne metody powodujące formowanie się nisz w algorytmach genetycznych. W niektórych z tych technik podział ujawnia się w sposób pośredni. Przyroda nie dzieli się swoimi dobrami w tak bezpośredni sposób, jak w przykładzie dwuramiennego bandyty. W naturalnych warunkach podział dochodzi do skutku poprzez konkurencję i konflikt. Kiedy siedlisko pewnego organizmu zostaje przepełnione, zamieszkujące je osobniki są zmuszone dzielić się między sobą dostępnymi zasobami.

Cavicchio (w 1970 roku) był jednym z pierwszych, którzy podjęli próbę wywołania „niszopodobnego” zachowania algorytmu genetycznego. Wprowadził on mechanizm nazywany preselekcją (ang. Preselection). Metoda ta miała na celu zastępowanie gorszego z rodziców przez jego potomka, o ile potomek wykazywał lepsze od niego przystosowanie. Populacja była dzięki temu zdolna do zachowania różnorodności, ponieważ ciągi kodowe miały tendencję do zastępowania podobnych do siebie – jednego ze swych rodziców.

De Jong w 1975 roku uogólnił technikę preselekcji w postaci modelu ze ściskiem (ang. Crowding). W modelu tym używa się populacji mieszanych – wielopokoleniowych, przy czym nowe osobniki zastępują inne zgodnie z kryterium podobieństwa. Nowy osobnik zostaje porównany z losową podpopulacją o rozmiarze równym czynnikowi ścisku CF. Osobnik o najwyższym stopniu podobieństwa zostaje następnie zastąpiony przez nowo utworzony ciąg. Początkowo działanie tego mechanizmu nie odbiega od losowego wyboru elementów do usunięcia, gdyż wszystkie osobniki są na ogół w tym samym stopniu niepodobne do siebie. W miarę jak symulacja postępuje i coraz więcej osobników w populacji upodabnia się do siebie, zaczyna się wyłaniać jeden lub więcej gatunków. Zastępowanie jednych osobników innymi, podobnymi do nich osobnikami, sprzyja utrzymaniu różnorodności i tworzy przestrzeń życiową dla dwóch lub więcej gatunków.

Metoda ta jest zainspirowana zjawiskiem ekologicznym, w którym osobniki w naturalnej populacji, często na tym samym terenie, rywalizują ze sobą o ograniczone zasoby. Zróżnicowanie osobników prowadzi z czasem do zajęcia różnych nisz tak, że w zasadzie nie zachodzi rywalizacja. Ostatecznym rezultatem jest to, że w zrównoważonej populacji o stałej wielkości, nowe osobniki z poszczególnych gatunków zastępują starych. W idealnej sytuacji, całkowita ilość członków danego gatunku nie zmienia się. Oczywiście metoda ze ściskiem nie zakłada, że wejściowa populacja jest stabilną mieszanką gatunków, lecz dąży do utrzymania zróżnicowania w początkowej populacji. Można by zadać pytanie, dlaczego nie zostawić populacji początkowej, przecież jest zróżnicowana. Niestety ten sposób nie promuje dobrego zróżnicowania. Dobre zróżnicowanie definiujemy jako istnienie reprezentantów wszystkich gatunków, włączając optymalne osobniki z każdego gatunku.



Samir W. Mahfoud w 1992 dowiódł jednak, że najbardziej efektywny jest algorytm znany pod nazwą Ścisk deterministyczny (ang. Deterministic crowding). Gatunki różnią się tak samo, jak lokalne optima w przestrzeni poszukiwań. Każde optimum rozważane jest jako nisza. Algorytm ten działa w następujący sposób. Najpierw każdy element populacji grupowany jest w pary (jest ich n/2). Następnie osobniki z każdej pary są krzyżowane a potomstwo ulega mutacji. Każdy potomek rywalizuje z rodzicem bardziej podobnym do siebie.

Pseudokod ścisku deterministycznego:
procedure ścisk deterministyczny

begin

for nr_generacji := 1 to n/2 do

begin

wyselekcjonowanie losowo rodziców (p1, p2) z populacji

krzyżowanie((p1, p2)  (c1, c2))

mutowanie (c1’, c2’)

if (d(p1: c1’) + d(p2: c2’)) ≤ (d(p1: c2’) + d(p2: c1’)) then

begin

if f(c1’) > f(p1) then zamień p1 z c1’

if f(c2’) > f(p2) then zamień p2 z c2’

end

else

begin

if f(c2’) > f(p1) then zamień p1 z c2’

if f(c1’) > f(p2) then zamień p2 z c1’

end

end

end
Oba te mechanizmy preselekcja i ścisk nie odzwierciedlają podziału, ale przedstawiają coś w rodzaju podziału pośredniego. Chociaż preselekcja i ścisk koncentrują się na aspekcie zastępowania, to wymuszając wcześniejsze odejście przedstawicieli licznych gatunków, redukując liczbę ich potomstwa i w ten sposób nie realizując pełnego potencjału reprodukcyjnego – zwalniają w ten sposób miejsce dla innych. Dopiero w 1984 w pracy Perry’ego można znaleźć bezpośrednie odniesienie do biologicznej teorii nisz w algorytmach genetycznych. W jego pracy określa się odwzorowanie genotyp-fenotyp, definiuje się środowisko wieloczynnikowe oraz specjalny obiekt zwany schematem zewnętrznym. Schematy zewnętrzne to specyficzne wzorce podobieństwa określone przez projektanta systemu, służące do scharakteryzowania przynależności gatunkowej. Niestety konieczność odwołania się do interwencji czynnika zewnętrznego ogranicza możliwość praktycznego zastosowania tej techniki w modelach poszukiwania genetycznego.

Grosso w 1985 roku również odnosi się do aspektu biologicznej niszy, w swojej pracy poświęconej formowaniu się podpopulacji oraz migracji między nimi. Ponieważ użył on do badań multyplikatywnych funkcji celu faworyzujących osobniki heterozygotyczne – efekt heterozji, otrzymane wyniki nie mają bezpośredniego zastosowania w większości modeli poszukiwań genetycznych. Jednak Grosso był w stanie wykazać wyższość umiarkowanej intensywności migracji nad izolacją podpopulacji - brakiem migracji oraz panmiksją. Badania jego sugerują, że uwzględnianie czynnika geograficznego w poszukiwaniach genetycznych może sprzyjać formowaniu się odrębnych podpopulacji.

Praktyczna metoda kreowania się nisz i gatunków, oparta bezpośrednio na idei podziału zasobów, została opisana przez Goldberga i Richardsona dopiero w 1987 roku. Wprowadza się tam funkcję współudziału (ang. sharing function), która określa sąsiedztwo i stopień współudziału dla każdego ciągu kodowego w populacji. Metoda umożliwia utworzenie stabilnych podpopulacji – gatunków o różnych łańcuchach. W ten sposób algorytm bada wiele optimów równolegle. Funkcja podziału określa zmniejszenie dopasowania osobnika w stosunku do sąsiada oddalonego o pewną odległość. Funkcja współudziału redukuje funkcję przystosowania w indywidualnych osobnikach, które mają wysoki stopień oceny i są podobne do siebie w populacji. Indywidualne najlepsze osobniki, które są unikatowe eksploatują obszary w swoim siedlisku, dopóki nie zniechęcimy nadmiernie do przeszukiwania innych obszarów w celu rozwoju innego gatunku w innym środowisku. Osobnicy znajdujący się w bliskim sąsiedztwie mają duże współudziały i muszą się dzielić swymi dobrami w bardzo dużym stopniu, natomiast osobnicy, którzy są w dalekim sąsiedztwie, mają bardzo małe współudziały i nie dzielą się tak radykalnie. Liniowa funkcja współudziału zaproponowana przez Goldberga i Richardsona jest przedstawiona na rys. 2.8, gdzie s(d) jest proporcjonalnym współudziałem dla osobników o odległości dij = ||xi - x j||.



1


 > 1


s(d)

 < 1



δsh


dij = ||xi - x j||


Rys. 2.8. Liniowa funkcja współudziału

Funkcja przystosowania ze współudziałem na indywidualnym osobniku i jest określona ww wzorem:

g
dzie f( i ) jest początkową wartością przystosowania w osobniku a m( i ) jest obliczeniem niszy na indywidualnym osobniku i z resztą populacji. Aby obliczyć nisze należy zsumować funkcję współudziału we wszystkich członkach populacji,

gdzie funkcja współudziału wynosi :




dla



w przeciwnym przypadku

a odległość d(i,j) reprezentuje dystans pomiędzy dwoma osobnikami w populacji, deterministycznie przez podobieństwo metryczne - różnica bezwzględna. Jeśli dystans jest większy lub równy бsh to osobniki te nie podlegają funkcji współudziału, czyli nie muszą dzielić się swymi zasobami i ich funkcja przystosowania się nie zmienia. Parametr α jest stałą która reguluje kształt funkcji współudziału. W naturze rozróżnienie funkcji współudziału bazuje na fenotypie, ale w algorytmach genetycznych używa się obu zespołu cech – fenotypu i genotypu w zależności od problemu. Przy podziale na poziomie genotypu argumentem funkcji współudziału jest względna różnica ciągów kodowych, czyli odległość Hamminga między ciągami (liczba różnych bitów) podzielona przez długość ciągów. Częściej stosuje się podział na poziomie fenotypowym, gdyż podział na poziomie genotypowym dopiero się rozwija i wymaga wielu badań.

Ogólnie mówiąc, wartość funkcji dopasowania zmniejsza się proporcjonalnie do liczby bliskości sąsiednich punktów. Oznacza to, że kiedy sąsiaduje ze sobą wielu osobników to obniżają sobie wzajemnie wskaźniki przystosowania, co wpływa na liczebność niszy. W rezultacie metoda ta ogranicza niekontrolowany wzrost poszczególnych gatunków w populacji. Poniżej przedstawiony jest podstawowy algorytm.
ALGORYTM NISZOWANIA


  1. Wykonaj przebieg algorytmu genetycznego z początkową funkcją przystosowania, uporządkowując chronologicznie osobników zaczynając od najlepszego.

  2. Oblicz funkcję współudziału dla każdego osobnika w populacji pomiędzy najlepszym osobnikiem w populacji.

  3. Oblicz funkcję przystosowania ze współudziałem, dzieląc początkowy potencjalny wskaźnik przystosowania przez sumę wszystkich wartości funkcji współudziału wnoszonych przez inne ciągi populacji, aby spowodować obniżenie (dla maksymalizacji zadania) w obszarze wokół najlepszego osobnika, tworząc w ten sposób nową funkcję przystosowania.

  4. Podstaw za funkcję przystosowania nową zmodyfikowaną funkcję przystosowania.

  5. Jeżeli nie znaleziono wszystkich rozwiązań, to wróć do punktu 2.

Na rys. 2.9 i 2.10 przedstawiono przykłady działania algorytmu genetycznego z funkcją przystosowania ze współudziałem dla funkcji wielomodalnych jednowymiarowych.



f1(x)

1







0,5




x


0

Bez współudziału
f1(x)

1



0,5






x


0

Ze współudziałem
Rys. 2.9. Działanie funkcji dzielącej na f1(x)


f2(x)




1


0,5










0

x


Bez współudziału
f2(x)


1






0,5










0

x

Ze współudziałem
Rys. 2.10. Działanie funkcji dzielącej na f2(x)

Stosując liniową funkcję współudziału, otrzymujemy po stu pokoleniach równomierny rozkład punktów wokół wszystkich maksimów (rys. 2.9), gdyż wszystkie maksima funkcji testowej są równe. Bez zastosowania funkcji współudziału widzimy, że dryf genetyczny gubi wszystkie maksima poza jednym. Na rys. (2.10) widać wokół wierzchołków o malejącej wysokości, że tworzą się stabilne podpopulacje odpowiedniej wielkości, proporcjonalne do wysokości wierzchołków. Bez funkcji współudziału osobnicy szybko skupiają się na obszarze w okolicy najwyższego wierzchołka, nie przejawiając inicjatywy tworzenia się nisz w innych wierzchołkach.

W 1993 roku Beasley, Bull i Marti opisali nową metodę sekwencyjnych nisz (ang. Sequential niching), do optymalizacji funkcji wielomodalnych. Jest ona pozbawiona kilku niedogodności metody podziału – wydłużenie czasu liczenia z powodu obliczania podzielonych dopasowań oraz wielkość populacji, która powinna być proporcjonalna do liczby optimów. W algorytmie tym także używa się funkcji odległości od osobnika i funkcji oceny. Po każdej iteracji algorytm ma za zadanie zlokalizować jeden szczyt. Metoda ta polega na wielokrotnym uruchamianiu prostego AG i utrzymywanie najlepszego rozwiązania z każdej iteracji. Aby uniknąć wielokrotnego zbiegania się populacji do tych samych obszarów przestrzeni rozwiązań za każdym razem, gdy sekwencyjne niszowanie znajdzie rozwiązanie,

zmniejsza się wartość funkcji w pewnym otoczeniu rozwiązania (podobnie jak parametr δsh w metodzie współudziału).

Następną metodą jest procedura czyszcząca (ang. Clearing procedure), która została zainspirowana pracami J.H. Hollanda w 1975 nad funkcjami współudziału. Jednakże zamiast równomiernie dzielić zasoby między członków subpopulacji, procedura clearing oddaje całość zasobów tylko najlepszym osobnikom z każdej subpopulacji. Działanie takiego mechanizmu nie pozwala nam dowiedzieć się, do jakich nisz należą poszczególne osobniki populacji. W zasadzie dany osobnik może być zdominowany przez wiele innych, ale z drugiej strony, dla danej populacji, zbiór osobników dominujących jest unikatowy. To twierdzenie jest dowiedzione przez indukcję: osobnik, który jest lepiej przystosowany w populacji staje się z konieczności osobnikiem dominującym. Możliwe jest także uogólnienie algorytmu clearing poprzez akceptowanie kilku osobników dominujących wybranych spośród najlepiej przystosowanych osobników w danej niszy. Pojemność niszy jest definiowana jako maksymalna ilość osobników dominujących, których może zaakceptować nisza. Zauważmy, że jeżeli pojemność niszy jest większa, niż jeden wtedy zbiór osobników dominujących nie

jest w ogólności unikatowy.


procedure czyściciel(σsh-radius,Vniszy)

begin

sortuj_przystosowanie(P)

for i := 0 to n-1 do

if przystosowanie(P[i]) > 0 then

begin

D := 1

for j := i + 1 to n-1 do

if (przystosowanie(P[j]) > 0)

and (odległość(P[i], P[j]) < σsh-radius) then

if D < Vniszy then D := D + 1

else przystosowanie (P[j]) := 0

end

end
gdzie:

σsh-radius – parametr określający, czy osobnik należy do subpopulacji;

Vniszy – pojemność niszy;

D – liczba osobników dominujących w subpopulacji;
W 1994 roku Spears zaproponował jeszcze inną metodę. W algorytmie użyto podziału dopasowania i ograniczonego doboru (zapobiega krzyżowaniu między osobnikami z dwóch maksimów). Jednak zrezygnowano z odległości metrycznej i przyjęto koncepcję etykiet. Każdy osobnik w populacji ma etykietę – łańcuch o n bitach generowany początkowo losowo, która pozwala na podział dopasowania w sposób dynamiczny.

Jeszcze inną metodę niszowania zaproponował niedawno Samir W. Mahfoud w 1995 roku rozumianą jaką ogólną ideę wykorzystania nadmiarowości w genotypie – diploidalny aparat genetyczny do poszukiwania nisz (ang. overspecification). Dotychczas rozważaliśmy jedynie najprostszy rodzaj genotypów spotykanych w przyrodzie - o haploidalnej liczbie chromosomów. W modelu tym pojedynczy ciąg kodowy zawiera całą informację istotną dla rozpatrywanego zagadnienia. Mimo, że przyroda zna wiele organizmów haploidalnych, większość z nich reprezentuje raczej nieskomplikowane formy życia. Wydaje się, że ilekroć przyroda chciała wytworzyć wyższe formy życia roślinnego lub zwierzęcego, musiała polegać na bardziej skomplikowanej strukturze genetycznej – genotypach o diploidalnej liczbie chromosomów. Genotyp w postaci diploidalnej składa się z jednej lub więcej par chromosomów - zwanymi chromosomami homologicznymi. Diploidalny chromosom powinien być zdolny do przechowywania informacji o rozwiązaniach, które okazały się dobre w przeszłości i mogą być przydatne w przyszłości. Według przeprowadzonych badań z 1987 roku przez D.E.Goldberga i Smitha bardzo skuteczna okazała się diploidalność do śledzenia globalnego optimum, które zmieniało się regularnie pomiędzy dwoma szczytami. Populacja utrzymywała w chromosomie obie lokalizacje optimum. Chociaż tylko jedna lokalizacja była, w danym czasie, odkryta. O tym, który allel będzie dominujący decyduje mapa dominacji. Każda pozycja w diploidalnym chromosomie zawiera dwa allele, ale w danym czasie tylko jeden chromosom jest uznany za dominujący.

Kolejną metodą również zaproponowaną przez Samir W. Mahfoud jest metoda wspinaczki (ang. parallel hillclimbing). Metoda ta rozpoczyna się od wygenerowania losowej populacji i wymusza na każdym z jej elementów dążenie do najbliższego optimum.
Pseudokod metody wspinaczkowej:

procedure metoda wspinaczkowa

begin

inicjacja(T)

while T ≥ ε do

begin

for i := 1 to popsize do

begin

wylosuj zmienną startową

zmiana := true

while zmiana do

begin

zmiana := false

for j := 1 to k do

if dodanie T do bieżącej zmiennej powoduje

polepszenie przystosowania then

begin

wykonaj dodanie

zmiana := true

end

else

if odjęcie T do bieżącej zmiennej powoduje

polepszenie przystosowania then

begin

wykonaj odjęcie


gdzie:

zmiana – zmienna logiczna wskazująca na zmianę kroku T,

ε – minimalna wartość kroku
zmiana := true

end

end

end

T := T/2

end
Każdy osobnik populacji wspina się o określoną długość kroku tak długo, jak długo przynosi to pozytywne rezultaty. Jeżeli wykonanie kroku o pierwotnej długości nie powoduje zwiększenia przystosowania, wtedy długość kroku jest zmniejszana o połowę i ponownie zaczyna się wspinanie wszystkich osobników. Algorytm powtarzany jest tak długo, aż długość kroku osiągnie minimalną wartość n. Problem jest z dobraniem początkowej długości kroku. Jeżeli krok będzie zbyt mały to będzie to prowadziło do bardzo długiego działania. Jeżeli krok będzie zbyt duży osobniki będą przeskakiwały z jednego optimum do innego.

Niedawno Mahfoud w 1995 roku porównał kilka metod z niszami pogrupowanymi w dwie grupy:



- sekwencyjne

- równoległe

Metody sekwencyjne lokują nisze czasowo a metody równoległe tworzą i utrzymują nisze równocześnie z populacją. Wyniki wskazują na to, że metody równoległe są lepsze od sekwencyjnych.


II. ALGORYTMY RÓWNOLEGŁE I WSPÓŁEWOLUUJĄCE



  1   2


©snauka.pl 2019
wyślij wiadomość

    Strona główna
Komunikat prasowy
przedmiotu zamówienia
najkorzystniejszej oferty
Informacja prasowa
wyborze najkorzystniejszej
warunków zamówienia
istotnych warunków
sprawie powołania
Regulamin konkursu
udzielenie zamówienia
przetargu nieograniczonego
zamówienia publicznego
Nazwa przedmiotu
Specyfikacja istotnych
modułu kształcenia
Rozporządzenie komisji
studia stacjonarne
wyborze oferty
Zapytanie ofertowe
Szkolny zestaw
Ochrony rodowiska
ramach projektu
prasowy posiedzenie
trybie przetargu
obwodowych komisji
zagospodarowania przestrzennego
komisji wyborczych
komisji wyborczej
Program konferencji
Wymagania edukacyjne
Lista kandydatów
szkoły podstawowej
która odbyła
Województwa ląskiego
Decyzja komisji
przedmiotu modułu
poszczególne oceny
Sylabus przedmiotu
szkół podstawowych
semestr letni
Postanowienia ogólne
przedsi biorców
produktu leczniczego
Karta przedmiotu
Scenariusz lekcji
Lista uczestników
Program nauczania
Projekt współfinansowany
Informacje ogólne
biblioteka wojewódzka
semestr zimowy