Sztuczne systemy immunologiczne -
zastosowanie w optymalizacji kombinatorycznej
Anna Świtalska
| << poprzedni rozdział | >> Spis treści << | następny rozdział >> |
Struktura sztucznego systemu immunologicznego opiera sie na definicji trzech podstawowych elementów [8]:
W zależności od dziedziny zastosowania powyższe elementy mogą być realizowane różnymi dostępnymi sposobami. Ogólna struktura sztucznego systemu immunologicznego może mieć charakter warstwowy przedstawiony na rysunku 2.1.
Rys. 2.1. Warstwowa struktura sztucznego systemu immunologicznego [8]
Podobnie jak w naturalnym systemie immunologicznym podstawowymi składnikami sztucznego SI są struktury reprezentujące komórki B i T, najczęściej jednak występuje tylko jeden rodzaj - komórki B, bądź też nie wprowadza się szczególnego rozróżnienia stosując mechanizmy dotyczące komórek B i T jednocześnie na tej samej populacji. W odróżnieniu od naturalnego systemu odpornościowego, sztuczne komórki B posiadają tylko jedno przeciwciało, toteż często utożsamia się te dwa pojęcia i mimo, iż z punktu widzenia biologii operowanie mechanizmami immunologicznymi na populacji przeciwciał jest błędne, tak w sztucznych systemach immunologicznych często przyjmowana jest właśnie taka koncepcja.
Naturalne struktury molekularne przeciwciał zostały tu przedstawione jako struktura elementów ze zbioru cech stanowiącego dziedzinę problemu. Najczęściej są to wektory liczb całkowitych lub rzeczywistych, ciągi binarne, a także bardziej złożone struktury tj. listy obiektów, a nawet sieci neuronowe [8] . Wektory liczb całkowitych i rzeczywistych są stosowane w większości sztucznych systemów immunologicznych, realizujących problemy obliczeniowe. Są wykorzystywane w takich dziedzinach jak optymalizacja problemów kombinatorycznych, optymalizacja wielokryterialna, interpolacja funkcji, niektóre systemy bezpieczeństwa. Ciągi binarne stanowią podstawę reprezentacji obiektów w systemach rozpoznawania wzorców [7], jako opis matrycy pikseli, z których złożony jest wzorzec. Reprezentacja ta także stosowana jest w systemach bezpieczeństwa [10] (kontrola wtargnięć, wykrywanie wirusów), gdzie opis zawierający np. takie dane jak adres IP, numer portu, czy struktury charakterystyczne dla wirusów są zapisywane właśnie przy pomocy ciągów binarnych. Natomiast złożone struktury znajdują bardzo szerokie zastosowanie w różnorodnych systemach data mining. Przykładowo listy adresów URL wykorzystywane są w systemach rekomendacyjnych bazujących na ścieżkach odwiedzin [14]. W przypadku reprezentacji opartej na sieciach neuronowych poszczególne elementy, zamiast prostego uporządkowania, są połączone wiązaniami, do których przypisuje się wagi.
W przypadku opisu antygenów została przyjęta taka sama koncepcja jak dla przeciwciał. Opis antygenu powinien być adekwatny do reprezentacji przeciwciała. Jednakże w niektórych przypadkach w sztucznym systemie immunologicznym nie występują jawnie antygeny, a miara dopasowania jest wyznaczana przez funkcję, której argumentami są wyłącznie składowe przeciwciała.
W zależności od charakterystyki problemu i reprezentacji komponentów systemu immunologicznego stosuje się różne miary dopasowania. Część z nich nawiązuje do zaproponowanej przez Perelsona i Ostera koncepcji przestrzeni kształtów [8], będącej sformalizowanym opisem interakcji przeciwciało-antygen. Według niej pojęcie kształtu jest określane jako punkt w L-wymiarowej przestrzeni. Wymiarami tej przestrzeni jest zbiór L-cech opisujących przeciwciało lub antygen. Zbiór ten określany jest jako uogólniony kształt przeciwciała (lub antygenu). W związku z tym, że ilość cech i zakres ich wartości jest ograniczony, przyjmuje się, że przestrzeń kształtów ma również ograniczoną objętość V. Populacja N-osobników tworzy zbiór punktów w tej przestrzeni. W przypadku antygenów, w przestrzeni kształtów są one reprezentowane przez punkty opisujące dopełnienie ich kształtu, w związku z tym, że wiązanie przeciwciała z antygenem polega na dopełnianiu się tych dwóch struktur. Ponadto w koncepcji tej funkcjonuje również pojęcie progu dopasowania ε, czyli określenie stopnia tolerancji niedoskonałości podobieństwa antygen-przeciwciało. Oznacza to, że wszystkie punkty, opisujące antygeny, leżące w sąsiedztwie o promieniu ε od punktu opisującego przeciwciało, powodują aktywację tego przeciwciała. Może się też tak zdarzyć, że dwa różne przeciwciała są aktywowane przez ten sam antygen.
Rys. 2.2. Graficzna reprezentacja koncepcji przestrzeni kształtów dla przestrzeni dwuwymiarowej.
W oparciu o ten opis łatwo zdefiniować metody pomiaru stopnia dopasowania bazujące na definicji odległości. Są one stosowane tam, gdzie interakcja przeciwciało-antygen bazuje na prostym podobieństwie dwóch struktur np. w systemach rozpoznawania wzorców, wykrywania anomalii, wirusów, czy wtargnięć intruzów do systemu informatycznego. W tym przypadku reprezentacja przeciwciał i antygenów jest kodowana w postaci wektorów liczb lub ciągów binarnych.
Metody te mogą bazować na różnych miarach odległości np. euklidesowej, Hamminga lub Manhattan.
Inne miary dopasowania bazują na specyficznych funkcjach, opisujących określony problem. Argumentem jest przeważnie para obiektów reprezentujących przeciwciało i antygen lub tylko obiekt opisujący przeciwciało. Natomiast wartości funkcji, adekwatne do opisywanego problemu, przeważnie są liczbami rzeczywistymi bądź całkowitymi. Dla problemów optymalizacji taką miarą jest funkcja celu.
Algorytmy immunologiczne stanowią główny trzon sztucznego systemu immunologicznego. Są realizacją procesów adaptacji i dywersyfikacji naturalnego systemu immunologicznego. To one odpowiadają za takie sterowanie populacją przeciwciał, aby doprowadzić do otrzymania rozwiązania. Najczęściej realizowanymi procesami systemu immunologicznego są selekcja klonalna i selekcja negatywna. Niekiedy również stosuje się metody hybrydowe, łączące realizację mechanizmów systemu immunologicznego z innymi metodami sztucznej inteligencji np. algorytmami genetycznymi.
Każdy algorytm immunologiczny operuje na populacji przeciwciał i antygenów lub samych przeciwciał. Na wstępie jest generowana populacja początkowa przeciwciał. Najczęściej proces ten ma charakter losowego doboru elementów tworzących przeciwciało, niekiedy ograniczanego przez określone warunki. Przy doborze tych elementów są często stosowane modele inspirowane naturalnymi procesami powstawania konfiguracji początkowych przeciwciał, tworzone w oparciu o strukturę reprezentacji przeciwciał. Najprostszy, stosowany do generowania prostych ciągów, polega na losowym doborze elementów z określonego przedziału. Bardziej zaawansowane stosują biblioteki genów, przy czym struktura przeciwciała powstaje poprzez połączenie losowo wybranych elementów z każdej biblioteki [8].
Rys. 2.3. Proces generowania początkowego repertuaru przeciwciał.
Algorytm selekcji klonalnej można podzielić na dwa etapy: etap ekspansji klonalnej, bazujący na naturalnym mechanizmie selekcji klonalnej opisanym w rozdziale 1 ("Mechanizm selekcji klonalnej") oraz etap hipermutacji. Pierwszy etap jest odpowiedzialny za wyselekcjonowanie najlepiej dopasowanych przeciwciał i namnożenie ich proporcjonalnie (ale niekoniecznie) do ich stopnia dopasowania. Natomiast hipermutacja realizuje proces dojrzewania przeciwciał, przekształcajac namnożone klony w taki sposób, by niektóre z nich osiagnęły lepszy stopień dopasowania niż ich poprzednicy.
Szczegółowy opis algorytmu znajduje się w rozdziale: Algorytm selekcji klonalnej - zastosowanie w optymalizacji kombinatorycznej
Algorytm selekcji negatywnej opiera się na mechanizmie eliminacji tych komórek, które rozpoznają własne struktury. Stąd też jego zastosowanie ogranicza się głównie do problemów detekcji anomalii np. w systemach bezpieczeństwa.
Algorytm selekcji negatywnej operuje na dwóch zbiorach wejściowych: zbiorze wzorców własnych struktur i zbiorze losowo wygenerowanych przeciwciał. Natomiast na wyjściu jest otrzymywany zbiór A przeciwciał (określanych tu jako detektory), które mogą rozpoznawać tylko obce struktury.
Ogólny schemat algorytmu jest następujący [8]:
Algorytm w podstawowej wersji jest bardzo prosty, jednak często jest uzupełniany o dodatkowe mechanizmy mające na celu usprawnienie pokrycia całej przestrzeni potencjalnych obcych struktur.
Klasyczne algorytmy immunologiczne tj. algorytm selekcji klonalnej czy selekcji negatywnej są często łączone z innymi metodami z zakresu sztucznej inteligencji w szczególności z algorytmami genetycznymi, tworząc w ten sposób hybrydowe algorytmy immunologiczne. Niektóre z nich zostały scharakteryzowane w kolejnych podrozdziałach.
Algorytmy immunogenetyczne są połączeniem realizacji mechanizmów genetycznych i immunologicznych. Jako że algorytmy immunologiczne i algorytmy genetyczne mają wiele wspólnych cech (operują na populacji osobników, wykorzystują mechanizmy selekcji itp.) mogą być ze sobą w prosty sposób wiązane. W algorytmach immunogenetycznych adaptowane są operatory genetyczne: krzyżowania, mutacji i selekcji, przy zachowaniu podstawowych składników systemu immunologicznego tj. populacji antygenów i przeciwciał. Wiele rozwiązań używa algorytmów genetycznych do generowania populacji przeciwciał, po czym są one poddawane immunologicznej selekcji negatywnej. Jako funkcję przystosowania w takich algorytmach stosuje się zazwyczaj miary typowe dla systemów immunologicznych, bazujące na stopniu dopasowania przeciwciała do antygenu.
Ze względu na to, że operator wiekowania nie jest składnikiem klasycznych algorytmów immunologicznych, lecz jest stosowany łącznie z nimi, toteż algorytmy z tym operatorem uważa się za algorytmy hybrydowe [2]. Operator wiekowania jest realizacją naturalnego mechanizmu śmierci komórek systemu immunologicznego. Jest uzupełnieniem algorytmów selekcji, które z zasady bazują głównie na wartości stopnia dopasowania. Zastosowanie strategii wiekowania pozwala na eliminację rozwiązań, które zbyt długo nie wykazują tendencji poprawy stopnia dopasowania, a także zapobiega przedwczesnej konwergencji (zbieżności do optimum lokalnego) [3]. Istotną cechą tego procesu eliminacji jest wiek komórki. Podczas tworzenia populacji początkowej wszystkie komórki otrzymują wiek równy 0. W kolejnych generacjach wiek komórek jest modyfikowany według ustalonej strategii. Przykładowa strategia może zakładać, że sklonowane komórki otrzymują wiek komórki macierzystej. Jeśli w procesie dojrzewania komórka zwiększy swój stopień dopasowania, to przypisywany jest jej wiek 0. Należy zaznaczyć, że w takim przypadku wszystkie komórki populacji macierzystej na początku generacji zwiększają swój wiek o 1. Operator wiekowania może dokonywać eliminacji probabilistycznej, gdzie prawdopodobieństwo usunięcia jest określane przez funkcję bazującą na wieku komórki, bądź też usuwać komórki po przekroczeniu pewnej stałej wartości progowej. Dodatkowo można wprowadzić ograniczenie nie pozwalające na usuwanie komórek z najwyższym stopniem dopasowania. W związku z tym wyróżnia się dwa typy operatorów wiekowania [2]:
| << poprzedni rozdział | >> Spis treści << | następny rozdział >> |
Copyright © 2006 AIS at ICS PAS, Warsaw, Poland. All rights reserved.
Information about this page format is available HERE.