3. Algorytm selekcji klonalnej - zastosowanie w optymalizacji kombinatorycznej

Algorytm selekcji klonalnej

Algorytm selekcji klonalnej jest realizacją podstawowego mechanizmu systemu immunologicznego (przedstawionego w rozdziale 1), mającego na celu adaptację zdolności immunologicznych. Głównie te adaptacyjne własności decydują o wykorzystaniu tego mechanizmu w realizacji różnych systemów obliczeniowych, których działanie opiera się na takiej ewolucji potencjalnych rozwiązań, aby dopasować je do określonego celu. Ponadto zastosowanie w tym algorytmie mechanizmu hipermutacji somatycznej gwarantuje zachowanie odpowiedniej różnorodności przeciwciał, a co za tym idzie bardziej efektywne przeszukiwanie przestrzeni rozwiązań.

Algorytm selekcji klonalnej CLONALG [6][8]:

generacja nowej populacji P osobników (komórek) - rozwiązań kandydujących, zawierającej podzbiór komórek pamięciowych + pozostała populacja.
wybór n-osobników z najwyższym stopniem dopasowania
reprodukcja (klonowanie) każdego z wybranych osobników w ilości proporcjonalnej do jego stopnia dopasowania
hipermutacja sklonowanych osobników (mutacji o wysokim współczynniku) odwrotnie proporcjonalnie do stopnia dopasowania (osobniki z wysokim stopniem dopasowania są poddawane mniejszej ilości mutacji, osobniki z niskim stopniem dopasowania są poddawane większej ilości mutacji)
ponowny wybór ulepszonych osobników, utworzenie z nich zbioru komórek pamięciowych M.
zastąpienie określonej liczby d osobników z populacji P lepszymi klonami, osobniki z niższym stopniem dopasowania mają większe prawdopodobieństwo zastąpienia.

W niektórych implementacjach tego algorytmu nie wyróżnia się populacji komórek pamięciowych lecz operuje się na jednorodnej populacji.

Operator klonowania

Operator klonowania odpowiedzialny jest za reprodukcję komórek z wysokim stopniem dopasowania. W tym procesie n wybranych komórek, z najwyższym stopniem dopasowania, wytwarza określoną ilość swoich kopii, określanych jako klony. Liczba klonów wytwarzana przez pojedynczą komórkę jest zazwyczaj proporcjonalna do jej stopnia dopasowana, jednakże istnieją także rozwiązania, w których ilość ta jest stała dla każdej z wybranych komórek [5]. Takie podejście zapobiega niekontrolowanemu rozrostowi populacji, produkując zawsze stałą ilość klonów. W przypadku, gdzie ilość klonów jest dynamicznie ustalana na podstawie wartości stopnia dopasowania, muszą istnieć mechanizmy podtrzymujące rozmiar populacji na względnie równym poziomie.

Operator hipermutacji

Istotnym elementem tego algorytmu jest mechanizm hipermutacji, którego efektem działania jest powstanie nowych komórek, zróżnicowanych i często wykazujących wyższy stopień dopasowania niż ich poprzednicy. Operator hipermutacji wykorzystuje zazwyczaj te same mechanizmy co mutacja genetyczna - jego działanie obejmuje wprowadzanie losowych modyfikacji w konfiguracji osobnika.

Ze względu na charakter tych modyfikacji można wyróżnić kilka typów mutacji [16]:

mutacja punktowa - zmiana pojedynczego, losowo wybranego elementu;
mutacja wielopunktowa - zmiana kilku losowych pozycji;
mutacja probabilistyczna - każda pozycja jest mutowana z określonym prawdopodobieństwem;

Mechanizmy mutacji mogą brać pod uwagę efekt działania i wprowadzać zmiany, tylko jeśli powodują one poprawę stopnia dopasowania. Mechanizm taki określa się jako mutacja użyteczna - sprawdza jakość osobnika przed mutacją oraz po jej wykonaniu i wybiera osobnika o wyższym dostosowaniu. Natomiast mutację, która nie wprowadza zmian określa się jako mutację pustą [16].

Podstawowa różnica między hipermutacją immunologiczną a mutacją genetyczną dotyczy jej intensywności. Podczas gdy w przypadku mutacji genetycznej zmiany wprowadzane są z bardzo małym prawdopodobieństwem, hipermutacja dokonuje znacznej ilości zmian (mutacji), najczęściej zależnej od stopnia dopasowania przeciwciała.

Ze względu na stosunek stopnia dopasowania do ilości mutacji istnieje kilka podejść [3]:

hipermutacja statyczna - liczba mutacji jest stała i niezależna od stopnia dopasowania;
hipermutacja proporcjonalna - liczba mutacji jest wprost proporcjonalna do stopnia dopasowania (wysoki stopień dopasowania - duża liczba mutacji, niski stopień dopasowania - mała liczba mutacji);
hipermutacja odwrotnie proporcjonalna - liczba mutacji jest odwrotnie proporcjonalna do stopnia dopasowania (wysoki stopień dopasowania - mała liczba mutacji, niski stopień dopasowania - duża liczba mutacji);
hipermakromutacja [4] - liczba mutacji jest niezależna od stopnia dopasowania, operator dokonuje M=j-i+1 mutacji kolejnych receptorów na pozycjach i..j, gdzie i,j są losowo wybierane, tak że i+1 ≤ j ≤ l ( l - ilość receptorów). Jeśli przed osiągnięciem krańca przedziału mutacja okaże się użyteczna, proces dla danej komórki jest kończony.

Zastosowanie w optymalizacji kombinatorycznej

Optymalizacja kombinatoryczna

Dziedzina optymalizacji kombinatorycznej stanowi szczególny przypadek problemów optymalizacyjnych, w których przestrzeń rozwiązań jest zbiorem dyskretnym. Przestrzeń rozwiązań jest opisywana najczęściej przez ciągi liczbowe o określonej długości, bedącej jednocześnie wymiarem przestrzeni. Każdy element ciągu, określający jeden wymiar w przestrzeni, może przyjmować wartości z określonej dziedziny, która może być różna, dla różnych elementów. Ponadto wszystkie rozwiązania muszą spełniać warunek wykonalności, określajacy dziedzinę problemu (tylko rozwiązania spełniające ten warunek tworzą zbiór rozwiązań prawidłowych dla określonego problemu). Zadaniem optymalizacji kombinatorycznej jest znalezienie takich rozwiązań, należących do zbioru rozwiązań prawidłowych, które są dla określonego problemu optymalne (funkcja/e celu przyjmuje/ą dla tych rozwiązań wartości optymalne).

Formalnie zadanie optymalizacji kombinatorycznej stanowi krotkę (X,P,Y,f,extr), gdzie:
• X oznacza przestrzeń rozwiązań (na której f i P są określone)
• P - warunek wykonalności
• Y - zbiór rozwiązań prawidłowych (spełniających warunek wykonalności)
• f - funkcja celu
• extr - ekstremum funkcji celu (minimum lub maksimum), stanowiące rozwiązanie zadania

Niektóre klasyczne zadania optymalizcji kombinatorycznej:

Problem komiwojażera (TSP - Traveling Salesman Problem)
Problem kolorowania grafu (GCP - Graph Colouring Problem)
Szeregowanie zadań

Adaptacja algorytmu selekcji klonalnej do potrzeb optymalizacji kombinatorycznej

Reprezentacja przeciwciał dla problemów optymalizacji kombinatorycznej jest przeważnie adaptacją opisu problemu, w szczególności opisu rozwiązania, do postaci ciągów liczbowych lub binarnych, z ewentualnym uwzględnieniem powiązań między elementami. Inne reprezentacje (opisane w rozdziale Reprezentacja komponentów systemu) w tego typu systemach są rzadziej spotykane, ze względu na dość prosty opis rozwiązań problemów kombinatorycznych. Przykładowo dla problemów wykorzystujących reprezentację grafową, przeciwciała mogą przyjąć postać ciągu liczb, w którym każdy element na określonej pozycji odwzorowuje jeden ustalony wierzchołek grafu. Przykład reprezentacji wektorowej grafu przedstwia rysunek 3.1. Krawędzie grafu, o ile nie stanowią elementu podlegającego zmianom, zazwyczaj nie są implementowane w ramach reprezentacji przeciwciała, lecz jako oddzielna statyczna struktura.

Rys. 3.1. Przykład przekształcenia grafu do reprezentacji wektorowej przeciwciała. Czerwone strzałki pokazują, które pola w wektorze przypisano odpowiednim węzłom. Numery #1, #2, #3, itd. znajdujące się obok węzłów, to numery pól wektora przypisanych tym węzłom. Np. zapis wartości '4' w pierwszym polu wektora oznacza, że węzłowi #1 przypisano kolor o indeksie '4'.

W przypadku optymalizacyjnych systemów immunologicznych zazwyczaj nie istnieje jawna struktura antygenu. Jego rolę spełnia funkcja (lub funkcje) celu, dokonująca obliczeń wyłącznie na elementach przeciwciała. Funkcja celu jest jednocześnie miarą dopasowania przeciwciała do rozwiązywanego problemu.
W problemach optymalizacji najszersze zastosowanie mają algorytmy immunologiczne oparte na mechanizmach selekcji klonalnej, algorytmy genetyczne, a także hybrydowe algorytmy immunogenetyczne. Najważniejszą rolę w tym przypadku odgrywają mechanizmy mutacji i selekcji. Zadaniem mutacji (hipermutacji) jest wprowadzanie modyfikacji w przeciwciele, mających na celu udoskonalenie rozwiązania, które z założenia ma dążyć do osiągnięcia optimum. Selekcja z kolei ma na celu dobór tych przeciwciał, które są najbliższe optimum, zakładając, że w ten sposób kolejne pokolenia na bazie tych przeciwciał wykształcą populację zbiegającą do optimum.
W przypadku zadań optymalizacyjnych istotnym problemem są optima lokalne. Proces przeszukiwania może zbiegać do takiego minimum (maksimum) lokalnego nie znajdując rozwiązania globalnego. Temu problemowi zapobiega utrzymanie odpowiedniego stopnia dywersyfikacji przeciwciał. Jest to realizowane głownie przez mechanizmy selekcji, które powinny być tak skonstruowane, aby zapobiegać dominacji populacji przez komórki podobne, często będące potomkami jednej komórki macierzystego.

<< poprzedni rozdział

>> Spis treści <<

następny rozdział >>