Algorytm genetyczny

Z BioInf

Spis treści

Algorytm genetyczny

Idea algorytmu

Jest to heurystyczny sposób wyszukiwania rozwiązań problemów optymalizacyjnych, czerpiący pojęciowo z biologicznej teorii ewolucji. W swojej podstawowej formie opiera się o założenia teorii ewolucji C.Darwina oraz korzysta z mechanizmu dziedziczenia zaproponowanego przez G.Mendla. Polega na ewoluowaniu "genomu" - zbioru informacji kodujących "fenotypy" - kandydatów na rozwiązania zagadnienia optymalizacji, poprzez wybieranie z każdego pokolenia osobników najlepiej przystosowanych (na podstawie zdefiniowanej heurystycznie funkcji wypłaty). Z genotypów osobników wybranych tworzona jest kolejna generacja - tym sposobem, po odpowiednio dużej ilości iteracji, algorytm powinien podać rozwiązanie zadanego zagadnienia. Algorytm genetyczny często nazywany jest GA (Genetic Algorithm).

Etapy realizacji algorytmu

Inicjalizacja

Rozpoczęcie algorytmu wymaga stworzenia pierwotnej postaci genotypu oraz pierwotnej populacji - zwykle decyduje się na rozwiązanie losowe. Generowany jest więc zbiór losowych kandydatów na rozwiązania problemu.

Ewaluacja populacji

Na podstawie funkcji wypłaty (lub również: "funkcji dopasowania") ocenia się jakość rozwiązań w danej populacji. Pozwala to na wybranie lepiej dopasowanych kandydatów, którzy w następnych etapach będą bazą dla utworzenia kolejnego pokolenia.

Dziedziczenie

Na podstawie najlepszych kandydatów, w zdefiniowany w procesie tworzenia algorytmu sposób, tworzy się ich "potomstwo". Przykładową metodą jest dziedziczenie z prawdopodobieństwem - polega na przypisaniu każdemu elementowi populacji wartości prawdopodobieństwa (tym większej, im lepiej jest dopasowany względem funkcji wypłaty), z którym będzie uczestniczył w dziedziczeniu. Następnie losowane są, z uwzględnieniem prawdopodobieństw, elementy z których genotypów tworzy się następną populację.

Mutacje - etap opcjonalny

By poszerzyć zbiór sprawdzanych przez algorytm rozwiązań, można w procesie dziedziczenia (lub nawet obok niego) zdefiniować prawdopodobieństwo mutacji, które zaburza częściowo genotyp przekazywany z poprzedniego pokolenia.

Nowa generacja

Na podstawie genotypów i mutacji z poprzedniego pokolenia, powstaje nowy zbiór kandydatów na rozwiązania.

Dokowanie ligandów

Algorytm Genetyczny

Problem dokowania liganda do białkowego receptora jest dobrym przykładem zagadnienia optymalizacyjnego, do którego zastosować warto procedurę genetyczną. Zagadnienie narzuca jednocześnie wybór funkcji dopasowania - jako energii całkowitej liganda w potencjale receptora. Przykładem praktycznego zastosowania tej procedury jest program AutoDock.

Całkowity opis ustawienia liganda można podzielić na dwa zestawy zmiennych:"zmienne stanu" (opisywać będą orientację, translację oraz konformację cząsteczki względem receptora) oraz współrzędne położeń atomów. Pierwszy zbiór będzie traktowany jako genotyp (a każdy z jego elementów jako osobny gen), drugi - jako fenotyp.

Zastosowanie opisanego powyżej algorytmu polegać będzie na badaniu energii osobników w danej populacji (będącej funkcją fenotypu), oraz wybieranie do dziedziczenia rozwiązań dających najniższe energie w populacji.

Algorytm Genetyczny - Lamarck

Analiza opisanego powyżej algorytmu dokowania prowadzi jednak do wniosku, że ma on charakter globalnego wyszukiwania minimów energetycznych układu - co może być rozumiane fizycznie jako granica dużych temperatur. Jakościowo można rozumieć to jako sytuację, w której cząsteczki mogą pokonywać (i, w drodze dziedziczenia, będą to robić) względnie duże bariery potencjału w poszukiwanie minimów energii.

Warto wobec takiej sytuacji zastanowić się nad umożliwieniem zmiany fenotypu cząsteczki w czasie trwania jednego pokolenia. Można to zrealizować poprzez dopuszczenie zmiany konformacji cząsteczki pod wpływem lokalnego pola receptora. Powtarzając tę operację w kilku krokach, można szukać lokalnych minimów potencjału. Dodatkowo, należałoby też upewnić się, że ustawienia poprawione (w sensie funkcji dopasowania) względem swoich genotypów są utrwalane w populacji. Podejście to fizycznie ma sens cząsteczki o niskiej energii (w niskiej temperaturze) relaksującej swoje ustawienie w stałym polu.

Algorytm uwzględniający powyższe poprawki nazywany jest Algorytmem Genetycznym Lamarcka (Lamarckian Genetic Algorithm). Nawiązuje to do teorii dziedziczenia Lamarcka, która mówi, że dziedziczone są również cechy nabyte przez organizm w trakcie życia.

Osobiste