vol. 6 4/2017 Inżynier i Fizyk Medyczny
222
artykuł
\
article
radioterapia
\
radiotherapy
złożoności obliczeniowej. W przypadku optymalizacji wielokry-
terialnej MCO dla tylko dwóch kryteriów już samo ustalenie, czy
dany punkt należy do frontu Pareto, może być problememnależą-
cym do klasy złożoności obliczeniowej problemów NP-trudnych
(
nondeterministic polynomial
) [4]. Dlatego bardziej niż ścisłe wyty-
czenie frontu Pareto rozsądne staje się zaprojektowanie takich
metod rozwiązywania, które w dostatecznie dobry sposób będą
w stanie ów front przybliżyć [3]. Trafnym sposobem okazało się
zastosowanie metaheurystyk (czyli najprościej mówiąc, schema-
tów przybliżonego rozwiązywania problemów), które stanowią
swoisty zbiór ram i zasad definiowania reguł poszukiwania roz-
wiązania dla konkretnych algorytmów heurystycznych wówczas,
gdy ścisła metoda rozwiązywania jest zbyt złożona, czasochłonna
lub gdy w ogóle nie jest znana [19].
Spośród wielu różnych metaheurystyk do najbardziej popu-
larnych metod należą
wielokryterialne
algorytmy ewolu-
cyjne MOEA (
Multiobjective Evolutionary Algorithms
)
. Ich
praktyczne zastosowanie jako narzędzi o wysokiej efektywności
stało się możliwe dzięki między innymi zwiększeniu mocy obli-
czeniowych komputerów. Schemat działania algorytmów ewo-
lucyjnych wzorowany jest na teorii doboru naturalnego i ewolu-
cji, stąd naśladują one procesy ewolucyjne i Darwinowską walkę
o przetrwanie, w której przeżywają osobniki najlepiej adaptują-
ce się do środowiska [4, 14]. W algorytmach tych stosuje się te
same terminy, co w teorii ewolucji, a rozumie się je
per analogiam
następująco:
•
osobnik
to przykładowe rozwiązanie
zadania (wektor w przestrzeni decyzyj-
nej); każdy osobnik reprezentuje moż-
liwe rozwiązanie zadania optymalizacji
wielokryterialnej;
•
populacja
to zbiór rozwiązań zadania
optymalizacyjnego;
•
fenotyp
to parametry (cechy) rozwiązania
podlegające ocenie;
•
genotyp
to cechy danego rozwiązania ko-
dowane w określony sposób, na przykład
w postaci ciągu bitów; każdemu genoty-
powi musi odpowiadać pewne rozwiązanie
zadania, czyli wektor decyzyjny w prze-
strzeni decyzyjnej;
•
chromosom
to miejsce, w którym przecho-
wywany jest genotyp osobnika [20, 21].
Analogicznie do procesów zachodzących
wprzyrodzie – środowisko, wktórymfunkcjonuje
określona populacja osobników (rozwiązań), jest
determinantem problemu optymalizacyjnego
(ściślej: definiuje ten problem).
Metody numeryczne oparte na algorytmach
ewolucyjnych zakładają dowolną reprezentację
zadania optymalizacyjnego oraz pewną stra-
tegię ewolucyjną (stąd termin
algorytmy ewo-
lucyjne
dotyczy pojęcia szerszego niż termin
Rys. 6
Geneza algorytmów ewolucyjnych
Źródło: [20].
algorytmy genetyczne
). Przez
strategię ewolucyjną
rozumie się
to, w jaki sposób operatory ewolucyjne oddziałują na populację
(czyli jak jest ukierunkowany cały proces ewolucji) [14].
W toku ewolucji zmienia się na skutek mutacji i krzyżowania
genotyp osobników. Na jego bazie formuje się fenotyp, tj. zbiór
cech poddawanych ocenie funkcji celu podczas działania algoryt-
mu, co daje odpowiedź na pytanie, jak dobre jest to rozwiązanie.
Osobniki wykazujące lepsze przystosowanie mają większą szansę
na rozmnożenie, natomiast gorzej przystosowane giną (Rys. 7).
Istotę ewolucji stanowi synteza nieukierunkowanych zmian
genotypu z jednoznacznie ukierunkowanym oddziaływaniem
środowiska na fenotyp, czyli na rozwiązanie problemu optymali-
zacyjnego posiadające określone cechy [20, 21].
Rys. 7
Zasada działania algorytmu ewolucyjnego
Źródło: Opracowano na podstawie L. Rutkowski, Metody i
techniki sztucznej inteligencji, Wyd. Naukowe PWN, War-
szawa 2005.
