niszowanie_koewolucja.pdf

(476 KB) Pobierz
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
AG – sprawozdanie do
seminarium
Prowadzący: dr hab. H. Kwaśnicka
„Niszowanie i koewolucja”
Autorzy:
Konrad Falkowski (cz. 1)
Marcin Żybura (cz. 2)
Paweł Wnuk-Lipiński (cz. 3)
1
1.1.1
Terminologia. .................................................................................................................................. 3
1.1.2
Czym jest niszowanie (ang. niching)? ............................................................................................. 3
1.1.3
Do czego służy niszowanie? ............................................................................................................ 4
1.1.4
Dlaczego nie można lokalizować wielokrotnych rozwiązań za pomocą iterowanego AG? ............ 4
1.1.5
Trochę historii.................................................................................................................................. 4
1.2
1.2.1
Terminologia. .................................................................................................................................. 4
1.2.2
Kilka cytatów, czyli: Gdzie spotkamy się z koewolucją?............................................................... 5
1.3
2
2.2
2.3
2.4
2.5
2.6
2.7
3
Podstawowe algorytmy..............................................................................................................................
19
3.1.1
Algorytm wyspowy ....................................................................................................................... 19
3.1.2
Algorytm komórkowy ................................................................................................................... 21
3.2
3.2.1
Zastosowanie koewolucji w sortowaniu łańcuchów...................................................................... 23
3.2.2
Zastosowanie koewolucji w robotyce............................................................................................ 23
4
2
834144830.001.png
1 Wstęp
1.1 Niszowanie
1.1.1 Terminologia .
Słowo „niszowanie” jak nie trudno się domyśleć pochodzi od słowa „nisza”.
Czym jest nisza? Słowo pochodzi z języka francuskiego, oznacza wnękę.
Możemy spotkać się z następującymi określeniami:
Nisza architektoniczna – pionowe wgłębienie w murze, filarze itp.
-
Nisza ekologiczna – zespół czynników ekologicznych i przestrzeń fizyczna
zajmowana przez dany organizm niezbędna dla jego egzystencji
-
Nisza abrazyjna – wklęsła forma u podstaw klifu, tworząca się w wyniku
działalności fal morskich.
-
Nisza rynkowa – segment rynku lub jego wydzielona część, w której
niewielka gruba nabywców, posiadająca konkretne potrzeby, gotowa jest
zapłacić wyższą cenę za dobro lub usługę
-
Nisza źródłowa – wgłębienie w terenie powstałe wokół wypływu wody.
-
Nisza matematyczna - obszar podejrzany o optimum.
-
Ogólnie: wnęka, wydzielony obszar.
Niszowanie jest właśnie mechanizmem wyszukującym nisze.
1.1.2 Czym jest niszowanie (ang. niching)?
Niszowanie jest techniką, która promuje formowanie i utrzymywanie stabilnych
podpopulacji (subpopulations) w AG.
podpopulacje
( subpopulations)
optimum
(maksimum lokalne)
3
834144830.002.png 834144830.003.png 834144830.004.png
1.1.3 Do czego służy niszowanie?
Niszowanie służy do znajdowania większej liczby rozwiązań danego problemu.
Inaczej mówiąc, korzystając z niszowania, znajdziemy wszystkie optima, nie tylko
globalne.
W niektórych przypadkach znalezienie wszystkich optimów funkcji jest
podstawą prawidłowego rozwiązania problemu. Przede wszystkim w tym celu
powstał mechanizm niszowania, który pozwala zostać osobnikom na optimach
lokalnych.
Niszowanie jest także pomocne dla znalezienia lepszego, pojedynczego
rozwiązania trudnych problemów.
1.1.4 Dlaczego nie można lokalizować wielokrotnych rozwiązań za pomocą
iterowanego AG?
Można, ale dają one bardzo słabe rezultaty i niepożądane efekty uboczne, takie jak:
-
przedwczesne, wielokrotne zbieganie się osobników populacji w tym
samym optimum;
dyskryminowanie słabszych rozwiązań
-
1.1.5 Trochę historii.
Niszowane AG (AG z wykorzystaniem technik niszowania) zostały zauważone w
świecie dzięki swojej zdolności do znajdowania wielu dobrych zróżnicowanych
rozwiązań.
Techniki niszowania stosuje się od ponad 10 lat.
W zwykłym AG, ciśnienie selekcyjne powodowały zbyt szybkie zbieganie do
jednolitej populacji, zawierającej kopie najlepszego rozwiązania. Dzięki różnorakim
mechanizmom niszowania (o których powie Marcin) pojedyncze osobniki populacji,
stały się „samowystarczalnymi” dobrymi rozwiązaniami, co najważniejsze: różnymi.
Dzięki temu, jakby załatano dziury rozwiązań optymalnych przestrzeni poszukiwań.
1.2 Koewolucja.
1.2.1 Terminologia.
Koewolucja – inaczej ewolucja kooperacyjna. Proces, najczęściej długoterminowy
polegający na zmianie w kompozycji genetycznej jednego gatunku (bądź grupy) w
odpowiedzi na zmianę genetyczną innego gatunku (grupy).
Bardziej ogólnie: obustronna zmiana ewolucyjna w środowisku odziaływującym na
siebie.
4
1.2.2 Kilka cytatów, czyli: Gdzie spotkamy się z koewolucją?
w biologii:
(...) Zasadą doboru naturalnego jest utrwalanie się tych właściwości organizmu,
które zwiększają szansę jego przeżycia i rozrodu. Dotyczy to również takich
właściwości, które objawiają się skłonnością do współdziałania z innymi osobnikami,
pod warunkiem jednak, że są one nosicielami tych samych genów. Wówczas ten sam
"gen kooperacji" rozprzestrzeni się poprzez potomstwo każdego z partnerów (piszę
"gen kooperacji" w cudzysłowie, bo na pewno nie chodzi tu o jeden gen, lecz o
zestaw wielu genów). Na tym polega działanie doboru krewniaczego, bo u bliskich
krewnych z dużym prawdopodobieństwem występują takie same geny. Również
współpraca osobników o zupełnie odmiennych genotypach może doprowadzić do
utrwalenia się ich "genów współpracy" (różnych u obu partnerów), osobno u
potomstwa każdego z nich, o ile efekty tej współpracy są opłacalne dla obu stron.
Taka obustronna korzyść może zachodzić w sytuacji, gdy partnerzy korzystają z
rozmaitych zasobów, wzajemnie ułatwiając sobie ich zdobycie, ale nie konkurują o te
same dobra. Na tej zasadzie opiera się koewolucja różnych gatunków, prowadząca
do częstej w przyrodzie symbiozy mutualistycznej, na przykład kwiatów z
zapylającymi je owadami (...)
w biologii (a konkretniej w lesie):
(...) w naturalnym lesie następuje ciągła koewolucja patogenów i drzew.
Patogeny ewoluują bardzo szybko – często maja wiele pokoleń rocznie.
Nowe siewki już na początku swego życia przechodzą przez sito selekcyjne
- te które są podatne na patogenny które przystosowały się do żerowania
na ich rodzicach - po prostu nie przeżywają. A wiec drzewa są różne,
jedne maja więcej metabolitów wtórnych, inny skład itd. Jest to
mechanizm który zapobiega tym sławnym gradacjom szkodników. (...)
w literaturze (esej S. Lema):
(...)Wirusy tak długo z małpami współistniały, ze obecnie już nie powodują im
żadnych przypadłości. Takim to sposobem koewolucja , trwająca wiele milionów lat,
powoduje "pokojowe współżycie" prapasożyta i pragospodarza. (...)
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin