Sztuczne systemy immunologiczne -
zastosowanie w optymalizacji kombinatorycznej

Anna Świtalska

4a. PrzykŁadowy system immunologiczny dla problemu kolorowania grafu

Problem kolorowania grafu

Problem kolorowania grafu, określany w skrócie jako GCP (ang. Graph Colouring Problem), jest klasycznym NP-zupełnym problemem w teorii grafów. W ogólnym znaczeniu, polega na takim przypisaniu K-kolorów do wierzchołków grafu G=(V,E), aby żadne dwa sąsiadujące ze sobą (połączone krawędzią) nie posiadały tego samego koloru. Formalnie ujmując zadanie można określić następująco [2]: dla danego nieskierowanego grafu G=(V,E), gdzie V jest zbiorem wierzchołków, E jest zbiorem krawędzi i dodatniej całkowitej liczby kolorów K≤|V|, znaleźć funkcję f:V›{1,2,...,K} taką, że f(u)≠f(v).

Istnieje również odmiana problemu, w której kolorowane są krawędzie zamiast wierzchołków. W takim przypadku żadne dwie krawędzie połączone z tym samym wierzchołkiem nie mogą mieć tego samego koloru.

Optymalizacja problemu kolorowania grafu polega na znalezieniu minimalnej liczby, określanej jako liczba chromatyczna grafu χ(G), dla której istnieje pokolorowanie spełniające warunki zadania.

Problem ten jest blisko powiązany z zagadnieniem klik, czyli podgrafów, w których każde dwa wierzchołki są połączone ze sobą krawędzią. Rozmiar maksymalnej kliki ω(G) jest dolnym ograniczeniem dla liczby chromatycznej: χ(G)≥ω(G) [2]. Graf którego liczba chromatyczna jest równa rozmiarowi największej kliki (χ(G)=ω(G)) nazywa się grafem doskonałym (ang. perfect graph) [18].

Opis rozwiązania

Reprezentacja komórek immunologicznych

W systemie immunologicznym realizującym opproblem kolorowania grafu zastosowano tylko jeden typ komórek immunologicznych - B-komórki. Przyjęta została reprezentacja B-komórki w postaci wektora liczb całkowitych. Na taki wektor składają się wartości opisujące kolory kolejnych wierzchołków grafu (przeciwciało). Dodatkowo w tym samym wektorze, na pierwszych czterech pozycjach, znajdują się informacje o wartości funkcji dopasowania, wieku komórki oraz te same informacje o komórce macierzystej.

Pierwsze dwie wartości są ustanawiane w procesie ewaluacji i wiekowania, więc niekoniecznie odzwierciedlają aktualny stan komórki, a są wyznaczane jednorazowo przed każdą operacją wymagającą tych informacji. Wartości dotyczące komórki macierzystej ustanawiane są w procesie klonowania i nie podlegają późniejszym modyfikacjom.

Algorytm

Do rozwiązania problemu kolorowania grafu został zastosowany hybrydowy algorytm immunologiczny z operatorem wiekowania. Oparty został na klasycznym algorytmie selekcji klonalnej, uzupełnionym o mechanizmy lokalnego przeszukiwania i wiekowania. Proces lokalnego przeszukiwania wraz z hipermutacją odpowiadają za dojrzewanie przeciwciał, przy czym mechanizm hipermutacji odgrywa główną rolę w początkowych iteracjach. Natomiast mechanizm lokalnego przeszukiwania zapobiega zbytniej stabilizacji procesu przeszukiwania w jego końcowych iteracjach.

Wariant I:

Pt = inicjalizacja();
ewaluacja(Pt);
while (warunek_terminalny)
{
    Pclo = klonowanie(Pt,Cn);
    Pls = przeszukiwanie_lokalne(Pclo, R, p);
    ewaluacja(Pls);
    Phyp = hipermutacja(Pls);
    ewaluacja(Phyp);
    Pt+1 = wiekowanie(Pt+Pls+Phyp);
}

Wariant II:

Pt = inicjalizacja();
ewaluacja(Pt);
while (warunek_terminalny)
{
    Pclo = klonowanie(Pt,Cn);
    Pls = przeszukiwanie_lokalne(Pclo, R, p);
    ewaluacja(Pls);
    Phyp = hipermutacja(Pls);
    ewaluacja(Phyp);
    Pt+1 = wiekowanie(Phyp);
}

Inicjalizacja

Populacja początkowa ma ustaloną wielkość. Poszczególne przeciwciała są inicjalizowane poprzez przypisanie do kolejnych wierzchołków losowych liczb z przedziału [1,l], gdzie l określa ilość wierzchołków w grafie, a jednocześnie długość przeciwciała. Przed każdym przypisaniem jest sprawdzany warunek kolorowania grafu, czyli czy przypisanie danej liczby (koloru) nie wprowadza konfliktu. W wyniku inicjalizacji powstaje populacja przeciwciał o dużym stopniu dywersyfikacji i średnim stopniu dopasowania w przybliżeniu równym l/2.

Ewaluacja

Proces ten polega na przeliczeniu stopnia dopasowania wszystkich przeciwciał w populacji. Stopień dopasowania jest tu odwrotnie proporcjonalny do funkcji celu, która określa ilość kolorów użytych do pokolorowania grafu. Funkcja celu w tym przypadku jest minimalizowana, więc wartości małe wskazują na wysoki stopień dopasowania, natomiast duże na niski stopień dopasowania. Dla uproszczenia obliczeń jako miara dopasowania zastosowana została funkcja celu a nie jej odwrotność.

Klonowanie

Intensywność tego procesu, czyli ilość reprodukowanych osobników, jest zależna od współczynnika klonowania C_n. Przed przystąpieniem do klonowania przeciwciał populacja jest sortowana w porządku rosnącym. Następnie wybieranych jest C_n pierwszych osobników z najmniejszą wartością funkcji celu i każde przeciwciało jest klonowane w następującym porządku: pierwsze jest klonowane C_n razy, kolejne C_n-1 itd. Przykładowy schemat klonowania dla C_n=5 został przedstawiony na rysunku 12. W wyniku klonowania powstaje nowa populacja P_clo o rozmiarze .

Jeżeli przeciwciał o najwyższym stopniu dopasowania jest więcej niż C_n, to proste wybieranie C_n-pierwszych zostało zastąpione losowym wybieraniem ze zbioru najlepszych przeciwciał. Ten mechanizm zapobiega znacznemu obniżeniu stopnia zróżnicowania przeciwciał i dominacji populacji przez potomków jednego najlepszego rozwiązania.

Przeszukiwanie lokalne (localsearch)

Przeszukiwanie lokalne jest mechanizmem opierającym się na definicji sąsiedztwa. Dla problemu kolorowania grafu sąsiedztwo wyznaczają połączenia wierzchołków krawędziami. W opisywanym tu algorytmie przeszukiwanie lokalne jest realizowane poprzez rekurencyjne modyfikacje kolorów wierzchołków w promieniu sąsiedztwa R, według schematu przedstawionego na rysunku 13.

Hipermutacja

W algorytmie została zastosowana hipermutacja statyczna, czyli w w każdej iteracji dla każdego osobnika jest wykonywane nmut mutacji na losowo wybranych elementach. Mutacja polega na próbie zmiany koloru na losowy z przedziału [1,f-1], gdzie f oznacza najwyższy kolor w grafie, co jest równoznaczne z wartością funkcji celu. Jeśli zmiana koloru powoduje konflikt, operacja ta jest anulowana. Przy zastosowaniu takiego mechanizmu hipermutacji mimo, iż założona ilość mutacji jest stała, to rzeczywista ilość mutacji użytecznych maleje w miarę zbliżania się do optimum.

Wiekowanie (aging)

W rozwiązaniu został zastosowany operator wiekowania, zaproponowany w [2], gdzie poszczególne etapy (klonowania, hipermutacji i lokalnego przeszukiwania) produkują odrębne podpopulacje, które są łączone w fazie wiekowania po dokonaniu eliminacji. Zaletą takiego rozwiązania jest zachowanie naturalnego zróżnicowania przeciwciał w związku z tym, że nową populację nie tworzą tylko zmodyfikowane klony komórek, ale również komórki macierzyste, które mogą utrzymywać się w populacji przez pewna ilość generacji, produkując od czasu do czasu nowe klony. Szczególne znaczenie ten mechanizm ma w przypadku, gdy powstała populacja klonów po hipermutacji nie wygeneruje żadnych lepszych rozwiązań. W takim przypadku sklonowane komórki przyjmują wiek rodziców i komórki macierzyste mogą z nimi konkurować na etapie wiekowania, a następnie tworzyć powtórnie w następnej generacji swoich potomków. Eliminuje to możliwość zdominowania populacji przez nieefektywne klony, dając, ograniczaną przez wiek, możliwość powtórnej reprodukcji komórek z poprzedniego pokolenia.

Operator wiekowania odpowiada za eliminację starych i nieefektywnych komórek. Podstawowym parametrem procesu jest wiek komórki, który jest ustanawiany według następującej strategii:

• na wstępie wszystkie komórki otrzymują wiek równy 0;
• w procesie klonowania wszystkie klony otrzymują wiek rodzica + 1;
• w procesie hipermutacji, jeśli zmutowane przeciwciało komórki jest lepsze od rodzica, otrzymuje wiek 0, w przeciwnym razie wiek pozostaje bez zmian.
• w procesie lokalnego przeszukiwania, podobnie jak przy hipermutacji lepsze od rodziców komórki otrzymują wiek 0, natomiast jeśli proces przeszukiwania wymagał zmiany koloru na wyższy, powstała komórka otrzymuje także wiek 0.

Uzyskane wyniki

Wyniki zostały uzyskane w drodze eksperymentów, dla których warunkiem terminalnym była znana wartość liczby chromatycznej dla poszczególnych grafów lub limit liczby generacji. Szybkość rozwiazywania problemu była szacowana na podstawie liczby generacji potrzebnych do osiągnięcia znanej wartości liczby chromatycznej. Natomiast zdolność znajdowania przez algorytm optymalnej liczby kolorów określona została jako efektywność i ozncza procent wykonań, w których znaleziona została wartość optymalna w zadanym limicie generacji.

Konfiguracja parametrów:
1) k=0.5; R=2; p=1; Cn=2; Nmut=50; Wiekość początkowa populacji=10
2) k=0.5; R=2; p=1; Cn=8; Nmut=50; Wiekość początkowa populacji=50
3) k=0.5; R=2; p=1; Cn=5; Nmut=50; Wiekość początkowa populacji=30

Opis testowanych grafów

Myciel - Grafy Mycielskiego
Graf Mycielskiego jest grafem bez trójkątów o określonej liczbie chromatycznej χ [19] tzn. żadne trzy wierzchołki nie są połączone w trójkąt jak przedstawione zostało to na rysunku 4a.1. Z powyższego założenia wynika, że maksymalny rozmiar kliki dla grafu Mycielskiego wynosi zawsze 2 (za wyjątkiem grafu dla liczby chromatycznej 1, który stanowi pojedynczy wierzchołek).

Rys 4a.1. Trójkąt w grafie.

Grafy te są generowane w drodze tzw. konstrukcji Mycielskiego [1]. Mając dany prosty graf G={v1,v2, ... , vn} dodawane są kolejne wierzchołki U={u1, u2, ... , un} i jeden dodatkowy wierzchołek w. Następnie dodawane są krawędzie w taki sposób, aby każdy wierzchołek ui był połączony krawędziami z wierzchołkami sąsiadującymi z vi. Na zakończenie wszystkie wierzchołki łączone są krawędziami z w. Kolejne grafy powstałe w wyniku konstrukcji Mycielskiego przedstawia rysunek 4a.2. Odpowiadające sobie wierzchołki ui i vi oznaczone zostały jednakowym kolorem.

Rys 4a.2. Kolejne konstrukcje Mycielskiego dla liczby chromatycznej a) 2, b) 3, c) 4.

Queen - Grafy królowych
Kolorowanie grafu królowych jest realizacją takiego ustawienia n figur hetmanów (królowych) na szachownicy o rozmiarach n x n, że żadna nie znajduje się w polu bicia innej (nie stoi na tej samej przekątnej, wierszu lub kolumnie). Każdy wierzchołek grafu odpowiada jednemu polu szachownicy. Ilość wierzchołków jest równa n2. Dwa wierzchołki są połączone krawędzią, jeśli odpowiadające im pola na szachownicy leżą w tym samym wierszu, kolumnie lub na przekątnej.

Rys. 4a.3. Graf królowych dla szachownicy 3x3.

Anna, David - Grafy książkowe
Grafy te są tworzone na podstawie wybranych pozycji z literatury. Dla poszczególnych książek grafy są tworzone w ten sposób, że wierzchołki określają postaci występujące w danej książce. Każde dwa wierzchołki są łączone jeśli odpowiadające im postaci spotkały się w fabule książki. Zastosowane w eksperymentach grafy odpowiadają następującym książkom:
anna - Anna Karenina, Tołstoja,
david - David Copperfield Dickens'a.

Zeroin
Grafy wygenerowane z problemu alokacji rejestrów bazującego na rzeczywistym kodzie.

Miles - Grafy milowe
Grafy te są podobne do grafów geometrycznych, w których każdy wierzchołek jest położony w określonym miejscu w przestrzeni geometrycznej, a wierzchołki są ze sobą połączone, jeśli znajdują się w mniejszej niż zadana odległości od siebie. Grafy milowe są reprezentacją zbioru miast w Stanach Zjednoczonych i odległości między nimi, wyznaczonej długością drogi prowadzącej z jednego miasta do drugiego w 1947 roku (w milach).

Copyright © 2006 AIS at ICS PAS, Warsaw, Poland. All rights reserved.
Information about this page format is available HERE.