vol. 6 6/2017 Inżynier i Fizyk Medyczny
374
artykuł
\
article
radioterapia
\
radiotherapy
W przypadku optymalizacji wielokryterialnej (16) funkcja celu
jest funkcją wektorową
f
= (
f
1
, f
2
, …, f
n
) przekształcającą prze-
strzeń decyzyjną w przestrzeń kryterialną, a jej poszczególne
składowe
f
i
to skalarne funkcje kryterialne. Rozwiązaniem pro-
blemu (16) jest zazwyczaj nieskończony zbiór rozwiązań Pare-
to-optymalnych. Optymalność jest tu rozumiana w sensie Pare-
to-optymalności, co oznacza, że rozwiązanie
x
jest optymalne
wtedy, gdy nie istnieje taki
x’
, że:
f
f
i
i
x
x
'
( )
≤
( )
(17)
dla
i = 1, …, n
ze ścisłą nierównością dla co najmniej jednej war-
tości indeksu
i
.
Zapis (16) oznacza w skrócie: „
znajdź wszystkie rozwiązania Pare-
to-optymalne, gdy funkcja celu ma n składowych f
i
(gdy i = 1, …, n)
”.
Rozwiązania Pareto-optymalne (dokładniej mówiąc – ich
obraz w przestrzeni kryterialnej rozpiętej przez poszczególne
kryteria składowe wektorowej funkcji celu) tworzą
front/po-
wierzchnię Pareto.
W wielokryterialnym podejściu do problemu planowania
leczenia techniką IMRT poszukuje się
wielu
wzajemnie równo-
ważnych, nieulepszalnych rozwiązań, które stanowią elementy
frontu (powierzchni) Pareto. Zbiór tych rozwiązań, czyli inten-
sywności (fluencji) beamletów, opiera się na definicji relacji
dominacji. Rozwiązania Pareto-optymalne, tj. rozwiązania nie-
zdominowane, mają taką cechę, że nie jest możliwe polepszenie
ich względem którejkolwiek skalarnej składowej
f
i
funkcji celu
bez pogorszenia pozostałych. Wyznaczenie całego frontu (po-
wierzchni) Pareto jest bardzo trudne i obciążające obliczeniowo,
a często wręcz niemożliwe, ponieważ niezdominowanych punk-
tów może być nieskończenie wiele. W praktyce uproszczenie
owego zadania polega więc na tym, aby znaleźć nie wszystkie
z tych punktów, lecz możliwie najwięcej rozwiązań reprezenta-
tywnych, stanowiących pewną bazę. Jej elementy powinny jak
najbardziej równomiernie pokrywać zbiór rozwiązań niezdomi-
nowanych – front Pareto [10].
Rolę silnika wyszukiwawczego i generującego zbiór rozwiązań
Pareto-optymalnych pełnią algorytmy optymalizacji. Można po-
dzielić je na dwie główne grupy: pierwsza to klasyczne metody
rozwiązywania problemów wielokryterialnych, oparte na skalary-
zacji zadania; drugą grupę stanowią metody, które „widzą” w peł-
ni wielokryterialność zadania (metody stochastyczne: wśród nich
algorytmy ewolucyjne, algorytmy symulowanego wyżarzania) [3].
Algorytmiczne metody rozwiązywania
problemów wielokryterialnych
Metody klasyczne: klasyczne algorytmy
optymalizacji wielokryterialnej
Ponieważ rozwiązanie problemu wielokryterialnego zwykle jest
trudne, to w praktyce często dąży się do zastąpienia zadania
wielokryterialnego zadaniem jednokryterialnym lub ciągiem za-
dań jednokryterialnych, a następnie rozwiązania takich zadań za
pomocą któregoś ze sprawdzonych algorytmów optymalizacji
jednokryterialnej. Klasyczne metody rozwiązywania wielokry-
terialnych zadań optymalizacyjnych są więc zazwyczaj dobrymi
metodami formułowania zastępczego skalarnego kryterium
optymalizacji.
Skalaryzacja zadania wielokryterialnego to zadanie optymali-
zacji jednokryterialnej z funkcją skalaryzującą [3]:
S : R R
m
→
(18)
min
,
, ,
:
S f
f
f
m
1
2
x x
x x
( ) ( )
…
( )
(
)
∈
{
}
Ω
W zależności od wyboru funkcji S można mówić o różnych me-
todach skalaryzacji. Do najczęściej wykorzystywanych metod
formułowania zastępczego, skalarnego kryterium optymalizacji
należą [3, 4]:
Metoda agregacji kryteriów optymalizacji
Powszechnie stosowaną techniką wyznaczania rozwiązań nie-
zdominowanych jest metoda ważonego sumowania składowych
wektorowej funkcji celu. Wówczas funkcja celu jest funkcją
sparametryzowaną o argumentach stanowiących wartości po-
jedynczych składowych wektorowej funkcji celu. Oparta jest na
skalaryzacji za pomocą liniowych kombinacji składowych funkcji
kryterialnych, czyli na wyznaczeniu rozwiązań optymalnych ska-
laryzacji o postaci [3]:
min
:
i
m
i i
w f
=
∑
( )
∈
1
x x
Ω
(19)
Jednak parametrów tej funkcji nie ustala decydent, lecz są
one systematycznie (metodycznie) zmieniane przez optyma-
lizator [11]. Optymalizacja uruchamiana jest wielokrotnie – dla
różnych ustawień parametrów – tak, aby otrzymać w efekcie
zbiór rozwiązań przybliżających front Pareto i rozwiązania Pa-
reto-optymalne (przy pojedynczym – dla konkretnych parame-
trów – uruchomieniu optymalizatora otrzymuje się pojedyncze
rozwiązanie). Zadanie optymalizacji w tym przypadku oznacza
znalezienie hiperpłaszczyzny, która będzie styczna do frontu
rozwiązań Pareto-optymalnych. Wartości współczynników wa-
gowych determinują nachylenie hiperpłaszczyzny. Zatem roz-
wiązaniem zadania (19) będą punkty, w których hiperpłaszczy-
zna jest styczna do zbioru rozwiązań niezdominowanych.
Metoda ta ma sporo zalet: jest szybka; ma dobrze poznany me-
chanizm działania; ponieważ funkcja skalaryzująca jest liniowa, to
nie wprowadza żadnych dodatkowych utrudnień obliczeniowych;
sprawdza się bardzo dobrze w przypadkach optymalizacji wypu-
kłej, dobrze współpracującej z algorytmem „sandwich” generują-
cym wewnętrzne i zewnętrzne przybliżenie frontu Pareto, kon-
trolując jednocześnie błąd tego przybliżenia [5].
Natomiast wadę jej stanowi to, że jest wrażliwa na kształt fron-
tu Pareto (którego struktura nie jest znana
a priori
), tzn. że nie
może wygenerować rozwiązań Pareto-optymalnych w niewypu-
kłych obszarach; zatem jej działanie ogranicza się do przypadku
optymalizacji wypukłej. Nadto w toku rozwiązywania proble-
mów wielokryterialnych optymalizator musi być uruchamiany
