CZĘŚĆ I

Wykład 1.
W poszukiwaniu optimum...

W tym wykładzie omówiono zadanie optymalizacji, wprowadzono pojęcia funkcji celu i zbioru dopuszczalnego. Przedstawiono klasyfikację funkcji celu i ograniczeń, uwzględniającą wymagania stawiane metodom optymalizacji; metody te skrótowo omówiono. Podano sposoby uwzględniania ograniczeń. Naszkicowano również zadanie optymalizacji wielokryterialnej.

1.1. Wstęp

W technice, ekonomii i innych dziedzinach pojawia się konieczność poszukiwania coraz lepszych rozwiązań konieczność ich optymalizacji. Optymalizacja, ściśle rozumiana, dotyczy poszukiwania najlepszego rozwiązania*. W praktyce chodzi często o znalezienie rozwiązania lepszego niż znane dotychczas.
Zadanie optymalizacji, które będziemy rozważać w dalszej części książki, można sformułować w sposób następujący. Jest
dana metryczna przestrzeń poszukiwań Q = (U, jest zbiorem wartości, a
gdzie U
metryką, oraz podzbiór D C U. Dana jest także funkcja celu /(x): U > R (zwana także wskaźnikiem jakości). Zadanie optymalizacji polega na znalezieniu takiego x* 6 D, że
x* = argmin/(x)
(1.1)
Jak łatwo zauważyć, zadanie minimalizacji można łatwo sprowadzić do zadania maksymalizacji, zmieniając znak funkcji łQ (jmus ",
Celu. '�' lepszy.
naj-
.30.
1. W poszukiwaniu optimum...
J
i
Zadania optymalizacji mogą być rozwiązywane metodami analitycznymi lub numerycznymi. Wykorzystanie metod pierwszego rodzaju jest jednak możliwe tylko w przypadku klasy funkcji przedstawionych analitycznie. Najczęściej jednak rzeczywiste problemy są na tyle skomplikowane, że albo analityczna postać uniemożliwia lub znacznie utrudnia znalezienie minimum, albo funkcja celu jest wynikiem symulacji komputerowej, tak więc zadanie może być rozwiązywane numerycznie poprzez przeszukiwanie zbioru dopuszczalnego w poszukiwaniu jak najlepszego punktu.
1.2. Rodzaje zadań
globalnej omówiono w dal-szej części wykładu.
W zależności od przestrzeni poszukiwań, mówimy o różnych rodzajach optymalizacji.
W optymalizacji parametrycznej zakłada się, że punkt x e U jest wektorem zmiennych niezależnych, z których każda przyjmuje pewną wartość. Oznacza to, że przestrzeń przeszukiwań jest iloczynem kartezjańskim zbiorów wartości zmiennych niezależnych. W zależności od typu tych zbiorów, dokonuje się klasyfikacji zadań optymalizacji parametrycznej.
Zadania ciągłe charakteryzują się tym, że przestrzeń przeszukiwań jest iloczynem kartezjańskim zbioru liczb rzeczywistych U = Rn. Wśród zadań optymalizacji ciągłej wyróżnia się zadania wypukłe (gdy zbiór dopuszczalny i funkcja celu są wypukłe) i zadania optymalizacji globalnej (niewypukła funkcja celu lub zbiór dopuszczalny)*. O optymalizacji dyskretnej mówimy, gdy wartości zmiennych niezależnych x^ należą do zbioru dyskretnego (skończonego lub przeliczalnego) U = Zn. W zadaniach optymalizacji kombinatorycznej każda ze zmiennych niezależnych przyjmuje wartość logiczną prawda albo fałsz, czyli U = Z%. Są też przypadki mieszane część zmiennych niezależnych przyjmuje wartości ze zbioru liczb rzeczywistych, część zaś całkowitych.
Zbiór (obszar) dopuszczalny D może być tożsamy z przestrzenią przeszukiwań U mówi się wówczas o optymalizacji bez ograniczeń, w przeciwnym przypadku o optymalizacji z ograniczeniami.
Nie wszystkie zadania są jednakowo trudne. Stopień skomplikowania zadania zależy zarówno od postaci funkcji celu, jak również od kształtu zbioru dopuszczalnego. Poniżej scharaktery-optymalizacji zowano kilka najczęściej wykorzystywanych właściwości funkcji
i . i � j i
Celu 1 zblOHI dopUSZCZaln6gO.
1.2. Rodzaje zadań
.31.
1.2,1. Właściwości funkcji celu
Zadania w Zn będące dyskretną wersją z Rn. Niektóre z zadań całkowitoliczbowych można uzyskać, formułując zadanie ciągłe i przyjmując dodatkowo ograniczenie, że zbiór dopuszczalny zawiera wektory, których wartości zmiennych niezależnych są liczbami całkowitymi. Zadania takie można próbować rozwiązywać w sposób przybliżony, stosując metodę relaksacji ograniczenia o całkowitoliczbowości. Wówczas, rozwiązanie odpowiedniego problemu ciągłego może stanowić oszacowanie problemu dyskretnego lub przynajmniej (po przybliżeniu do najbliższego rozwiązania dyskretnego) służyć jako punkt początkowy poszukiwań*.
Proste przeniesienie właściwości zadań ciągłych na ich wersje dyskretne może prowadzić do pochopnych uogólnień. Nie sposób zagwarantować, że nieskomplikowany problem ciągły prowadzi do równie łatwego zadania dyskretnego. W znacznej mierze zależy to od sposobu dyskretyzacji im jest ona "gęstsza"**, tym łatwiej możemy przenieść właściwości wersji uciąglonej na oryginalną wersję dyskretną.
Liniowość. Funkcja liniowa ma postać
L / \ ___ 7 I 1 ' / T C\ \
J(*-) a x + � U-^J
gdzie a jest n-wymiarowym wektorem, b stałą. Jeśli funkcja celujest liniowa, to rozwiązanie zadania (1.1) wypadnie zawsze na granicy obszaru dopuszczalnego (jeśli jest domknięty). Jeśli zbiór dopuszczalny D jest nieskończonej miary, to nie można wykluczyć sytuacji, że rozwiązanie nie będzie istniało.
Wypukłość. Funkcja wypukła (rys. 1.1) spełnia warunek a/(x1) + (1 - a)/(x2) > /(ax1 + (1 - a)x2) (1.3)
dla dowolnych x1 e D, x2 e D, 0 < a < 1. Zakładamy przy tym, że D jest wypukły, czyli dla dowolnych x1, x2 e D każdy punkt
x = ax1 + (1 - a)x2
gdzie
Orównież do niego należy. Jeśli wypukłe są funkcja celu i zbiór dopuszczalny, to istnieje dokładnie jedno minimum. Właściwość ta bardzo ułatwia proces optymalizacji, można go bowiem ograniczyć do przeszukiwania sąsiedztwa punktu roboczego i wybierania zeń nowego punktu roboczego. Do stwierdzenia znalezienia minimum wystarczy wówczas upewnić się, że w sąsiedztwie nie istnieje punkt o mniejszej wartości funkcji celu.
Różniczkowalność. Kolejną właściwością, która może być wykorzystana w optymalizacji funkcji, jest jej różniczkowalność. Jeśli w każdym punkcie istnieje pochodna funkcji, to po pierwsze
*Nalezyjednak pamiętać, że rozwiązanie problemu uciąglonego może po zaokrągleniu znajdować się dowolnie daleko od poszukiwanego rozwiązania problemu dyskretnego. **Gęstość próbkowania należy oczywiście odnieść do szybkości zmienności funkcji, np. do stałej Lipschitza (jeśli istnieje dla tej funkcji).
.32.
1. W poszukiwaniu optimum.
(a)
(b)
RYSUNEK 1.1. Ilustracja wypukłości (a) i niewypukłości funkcji (b)
1.2. Rodzaje zadań
.33.
łatwo znaleźć kierunek zmniejszania się wartości funkcji (kierunek poprawy), po drugie zerowanie gradientu może wskazywać na znalezienie minimum.
Warunek Lipschitza. Warunek Lipschitza jest związany z istnieniem górnego ograniczenia szybkości zmienności funkcji. Funkcja spełnia ten warunek, jeśli istnieje taka wartość L < oo, że dla każdego x1, x2 e D zachodzi
|/(x1) f(x2)| < L|x1 x2| (1 4)
Wartość L jest zwana stałą Lipschitza. Jeśli jest znana, to może być podstawą konstruowania algorytmów optymalizacji korzystających z szacowania od dołu wartości minimum funkcji celu, a także umożliwić oszacowanie dokładności wyniku optymalizacji.
Właściwość dekompozycji. Niekiedy zdarzr, się, że funkcja celu ma właściwość dekompozycji. Oznacza to, że funkcja taka jest złożeniem wielu funkcji; wartość każdej z nich można obliczyć na podstawie znajomości części zmiennych niezależnych
f / \ sr~ / f / \ \ / ^ -. \
J(x) =J~ \Ji(x(i))) l^-3j
gdzie /i(x(j)) są funkcjami, których wektor argumentów X(,ź) zawiera elementy z wektora x, T jest operatorem złożenia, którym może być na przykład funkcja liniowa.
Właściwość dekompozycji oznacza, że zadanie znalezienia minimum funkcji /(x) można zastąpić wieloma zadaniami wyznaczenia minimów funkcji /,(x(j)), które z reguły są prostsze do rozwiązania. Dekompozycja może prowadzić do zmniejszenia wy-miarowości wektora argumentów lub też uczynić funkcję mniej skomplikowaną (na przykład dekompozycja na funkcje wypukłe). W obu przypadkach, dekompozycjaprowadzi z reguły do uproszczenia metody rozwiązania.
Wiele minimów lokalnych. Istnieją funkcje, które mają wiele minimów lokalnych (tzw. funkcje wielomodalne) (rys. 1.2). Minimum lokalne to taki punkt, w którego sąsiedztwie o niezerowym promieniu nie istnieje inny punkt o mniejszej wartości funkcji celu
35 > 0 Vr < S Vy e JVP(x) n D /(x) < /(y)
(1.6)
Może się zdarzyć, że istnieje spójny zbiór punktów o jednakowej wartości funkcji celu, spełniających warunek (1.6). Zbiór taki traktuje się tak, jakby był jednym punktem i nazywa się go minimum niewłaściwym. W przypadku ostrej nierówności, istnieje dokładnie jeden punkt spełniający warunki (1.6), który nazywa się minimum właściwym.
.34
l.Wposzukiwaniuoptimum..
f(x)
Minima lokalne
RvsuNEK 1.2. Funkcja z minimami lokalnymi
Minimum funkcji bez ograniczeń
Obszar dopuszczalny
Minima funkcji z ograniczeniami
0 xi
RYSUNEK 1.3. Minima lokalne wynikające z niewypuktosci zbioru dopuszczalnego
1.2. Rodzaje zadań
.35.
Istnienie minimów lokalnych wynika najczęściej z postaci funkcji celu, jednakże może być także spowodowane właściwościami zbioru dopuszczalnego, na przykład jego niewypukłością. W takich przypadkach, minimum lokalne wypadnie często na brzegu obszaru dopuszczalnego (rys. 1.3).
Zbiory przyciągania minimów lokalnych. Wyobraźmy sobie idealny algorytm optymalizacji (lokalnej) realizujący odwzorowanie, przypisujące każdemu punktowi x 6 D punkt y G D w następujący sposób:
takie, że Vz e A^(x) n D
/(z*) < /(z) oraz w przeciwnym przypadku
/(z*) < /(x)
(1.7)
Rozważmy ciąg punktów x\x2,..., taki, że xł+1 jest obrazem x* w opisywanym odwzorowaniu i załóżmy, że zbiór D jest zwarty. Załóżmy teraz, że wartość r jest dodatnia i dowolnie bliska zeru. Wówczas, zbiór wszystkich punktów, które są elementami początkowymi opisanego wyżej ciągu zbieżnego do minimum lokalnego x, nazywamy obszarem przyciągania tego minimum i oznaczamy D(x). Podział zbioru dopuszczalnego na obszary przyciągania generuje rodzinę zbiorów (rys. 1.4) o następujących właściwościach: , ;
i ' :. ' ...... ' ^
1) suma obszarów przyciągania równa jest zbiorowi dopuszczalnemu D (z dokładnością do zbioru miary zero),
2) obszary przyciągania dwóch różnych minimów lokalnych są rozłączne (z dokładnością do zbioru miary zero).
RYSUNEK 1.4. Podział zbioru dopuszczalnego D na obszary przyciągania minimów lokalnych
Wśród funkcji z wieloma minimami można wyróżnić takie, dla których obszary przyciągania minimów lokalnych są zbiorami wypukłymi właściwość taka gwarantuje, że punkt leżący na *Ta właściwość może być odcinku łączącym dwa punkty, należącym do zbioru przyciągania rSr^rfkSa^ tego samego minimum lokalnego, również do niego należy*. uśredniającego (P. 4.4.2).
.36 l.Wposzukiwaniuoptimum...
1.2.2. Ograniczenia funkcji celu
Zbiór dopuszczalny może być zdefiniowany za pomocą zbioru funkcji ograniczeń* c^, hj, spełniających warunek, że dla każdego xeDzachodzi v."-:;Tt<:;' !, : :�-.'.
5i(x) <0 ;i , , (1.8)
fy(x) = 0 '. " . ', ~\ (l.9)
Omówimy różne rodzaje zbiorów dopuszczalnych wprowadzanych przez funkcje ograniczeń.
Ograniczenia kostkowe. Ograniczenia kostkowe (rys. 1.5) mają postać
k Liczby li, ui ograniczają z dołu i z góry wartości, które może przyjmować zmienna niezależna Xi.
RYSUNEK 1.5. Obszar dopuszczalny z ograniczeniami kostkowymi; widoczne również poziomice funkcji celu
**�...
Ograniczenia liniowe. Ograniczenia liniowe mają postać funkcji liniowej
<7;(x) = a
(1.11)
*Funkcje **Fakt ten wykorzystamy przy omawianiu operatora krzyżowania uśredniające-go (p. 4.4.2).
***Tu również obowiązuje właściwość zachowania dopuszczalności potomstwa powstałego w wyniku krzyżowania uśredniającego dwojga dopuszczalnych rodziców.
gdzie a jest wektorem, b zaś stałą. W przestrzeni Rn, jeśli w zadaniu występują wyłącznie ograniczenia liniowe, zbiór dopuszczalny (jeśli jest niepusty) jest wypukły**.
Wypukły obszar dopuszczalny. Kolejnym przypadkiem ograniczeń są takie, które dają wypukły obszar dopuszczalny (rys. 1.6)***. W przypadku ograniczeń nierównościowych istnieje możliwość dokonania takiej transformacji zmiennych niezależnych, w wyniku której w przestrzeni nowych zmiennych uzyskuje się ograniczenia kostkowe.
1.2. Rodzaje zadań
.37.
RYSUNEK 1.6. Wypukły obszar dopuszczalny; widoczne również poziomice funkcji celu
Niewypukły i niespójny obszar dopuszczalny. Niewypuk-łość obszaru dopuszczalnego (rys. 1.7) może stanowić utrudnienie dla zastosowania algorytmów optymalizacji, gdyż na ograniczeniach może występować jedno lub więcej minimów lokalnych.
RYSUNEK 1.7. Niewypukły obszar dopuszczalny; widoczne również poziomice funkcji celu. Niewypukłość zbioru dopuszczalnego wprowadza minima lokalne na ograniczeniach
RYSUNEK 1.8. Niespójny obszar dopuszczalny; widoczne również poziomice funkcji celu. Istnieją pary punktów, których nie da się połączyć krzywą w całości zawartą w zbiorze dopuszczalnym
1. W poszukiwaniu optimum...
Z jeszcze trudniejszą sytuacją mamy do czynienia wówczas, gdy obszar dopuszczalny nie jest spójny (rys. 1.8), lecz składa się z odizolowanych podzbiorów. Oznacza to, że dla każdego punktu dopuszczalnego istnieje co najmniej jeden punkt dopuszczalny, którego nie sposób osiągnąć dowolnie małymi krokami, nie pozostając przejściowo w obszarze zabronionym.
1.2.3.Znaczenieliczbywymiarow
Zarówno w przypadku ciągłych, jak i dyskretnych zmiennych niezależnych, wraz ze wzrostem ich liczby (czyli wymiarowości zadania) zwiększa się stopień komplikacji rozwiązywanego problemu. Na przykład w zadaniach kombinatorycznych, uzupełnienie wektora zmiennych niezależnych o jedną zmienną powoduje podwojenie liczby różnych wartości, które może on przyjąć. W zadaniach dyskretnych dodanie zmiennej niezależnej mogącej przyjąć k wartości będzie skutkować fc-krotnym zwiększeniem liczby różnych wartości. Z kolei w zadaniach ciągłych, zbiory "chudną" wraz ze wzrostem liczby wymiarów: zbiór miary różnej od zera staje się zbiorem miary zero, natomiast miary sąsiedztw o tym samym promieniu są coraz mniejsze w stosunku do miary zbioru D.
PRZYKŁAD. Rozważmy kwadrat z wpisanym weń kołem. Jeśli losujemy punkt z rozkładem jednostajnym w tym kwadracie, to jak łatwo sprawdzić prawdopodobieństwo trafienia w koło wynosi 7T/4. Jeśli kwadrat ten jest ścianą sześcianu, to prawdopodobieństwo trafienia w koło w wyniku wylosowania punktu należącego do tego sześcianu jest równe zero, gdyż wszystkie figury płaskie są miary zero w przestrzeni R3. Z kolei, jeśli spróbujemy uogólnić przypadek kwadratu i okręgu na bryły w R^, to okaże się, że prawdopodobieństwo trafienia w kulę wpisaną w sześcian losując z rozkładem jednostajnym punkt należący do sześcianu wyniesie 7T/6. Łatwo sprawdzić, że wraz ze zwiększaniem liczby wymiarów, prawdopodobieństwo to będzie coraz mniejsze.
Liczba wymiarów a stopień komplikacji zadania. Koło i kula z powyższego przykładu sa kształtami sąsiedztw (przy metryce euklidesowej) w przestrzeni Rn. Jeśli przyjmiemy prosty przypadek istnienia ograniczeń kostkowych, to wraz ze wzrostem liczby wymiarów, miara sąsiedztwa o promieniu r stanowi coraz mniejszy ułamek miary zbioru dopuszczalnego. Oznacza to, że coraz trudniej "trafić" w to sąsiedztwo, losując przypadkowe punkty z tej kostki, czyli mniejsze jest prawdopodobieństwo wyznaczenia prostą metodą Monte Carlo punktu będącego przybliżeniem poszukiwanego minimum globalnego.
1.2. Rodzaje zadań
.39.
Większość funkcji, które są wykorzystywane do testowania metod optymalizacji, jest zdefiniowana w sposób umożliwiający zwiększanie liczby wymiarów (np. funkcja Ackleya, Griewarika itp.)*. Wraz ze wzrostem liczby wymiarów, wzrasta liczba minimów lokalnych tych funkcji, a zatem również stopień komplikacji zadania. Taka korelacja liczby minimów lokalnych i liczby wymiarów nie jest jednak regułą może się na przykład zdarzyć, że funkcja celu mająca większą liczbę wymiarów będzie miała mniejszą liczbą minimów lokalnych.
Asymptotyczne właściwości problemów; złożoność obliczeniowa. Podejmując próby rozwiązywania problemów kombi-natorycznych, dość szybko zauważono, że niektóre z nich są szczególnie trudne. Obserwowano, że złożoność problemu zależna od zwiększenia liczby danych powodowała zwielokrotnienie liczby obliczeń. Teoria złożoności obliczeniowej stanowi próbę udzielenia odpowiedzi na pytanie: jak będzie się zmieniać liczba operacji, potrzebnych do rozwiązania problemu, wraz ze zmianami liczby danych, opisujących ten problem? Złożoność algorytmu wynika ze sposobu jego konstrukcji, natomiast złożoność problemu jest miarą jego trudności; nie jest możliwe skonstruowanie algorytmu o złożoności mniejszej niż rozwiązywanego problemu. Tak więc znając złożoność problemu, możemy oszacować od dołu właściwości dowolnego algorytmu, który będzie go rozwiązywać.
Rozważa się oszacowania złożoności dolne, oczekiwane (średnie) i górne, oznaczane odpowiednio o, O, 0. Złożoność @(n2logn) oznacza, że wraz ze wzrostem liczby wymiarów problemu, najszybciej zwiększający się czynnik w funkcji określającej złożoność problemu będzie wzrostał proporcjonalnie do n2 log n. Warto pamiętać, że wymienione oszacowania mają charakter asymptotyczny: zwraca się uwagę na najszybciej zwiększający się czynnik, choć dla małych n może się zdarzyć, że decydujące znaczenie będą mieć czynniki o mniejszym tempie wzrostu (np. duży koszt stały).
Problemy, których pesymistyczna złożoność obliczeniowa (górne ograniczenie złożoności) jest funkcją wielomianową, są uważane za łatwe i nazywane klasą P (ang. polynomial wielomian). Z praktycznego punktu widzenia, wskazane jest, aby stopień wielomianu nie był zbyt duży. Kolejną klasą, którą się wyróżnia, są problemy NP (nondeterministic polynomial), dla których pesymistyczna złożoność obliczeniowa niedeterministycznego algorytmu jest funkcją wielomianową.
Ważne miejsce wśród problemów NP zajmują problemy NP--zupełne. Charakteryzują się one tym, że
1) dla żadnego z nich nie udało się wykazać istnienia deterministycznego algorytmu o wielomianowej złożoności,
*Opisy tych funkcji można znaleźć w dodatku B.
l.Wposzukiwaniuoptimum...
2) każdy z nich można przekształcić do każdego innego za pomocą deterministycznego algorytmu o złożoności wielomianowej.
Z kolei problemy 7VP-trudne to takie, do których da się (za pomocą algorytmu deterministycznego o wielomianowej złożoności) sprowadzić dowolny problem z NP.
1.3. Metody optymalizacji
Znanych jest wiele metod optymalizacji dostosowanych do szczególnych przypadków zadań. Szczegółowe ich omówienie jest przedmiotem niejednego podręcznika, poniżej przedstawię te metody jedynie pobieżnie.
Zadania ciągłe. Liniowość funkcji celu oraz ograniczeń umożliwia wykorzystanie metody liniowego sympIeksu, poszukującej rozwiązań na brzegu obszaru dopuszczalnego.
Dla zadań z wypukłą funkcją celu opracowano wiele różnych metod. Najczęściej wyznacza się jak najlepszy kierunek poszukiwań rozpoczynający się w aktualnym punkcie roboczym, a potem znajduje minimum wzdłuż "przekroju" funkcji celu w tym kierunku, które staje się nowym punktem roboczym. Czynności te są powtarzane cyklicznie aż do osiągnięcia kryterium zatrzymania. W zależności od sposobu wyznaczania kierunku, mówi się o metodach bezgradientowych, gradientowych i (pseudo)-newtonowskich. Do pierwszej grupy należą metody poszukiwań prostych (kolejne kierunki są równoległe do osi układu współrzędnych) i kierunków sprzężonych (kolejne kierunki wynikają z historii poszukiwań). W drugiej grupie wyróżnia się metody największego spadku (kierunkiem jest minus gradient funkcji w punkcie) i gradientów sprzężonych. W trzeciej grupie wykorzystywana jest dodatkowo macierz odwrotna do macierzy pochodnych cząstkowych (metoda Newtona) lubjej aproksymacja (metody pseudonewtonowskie, w tym zmiennej metryki); iloczyn tej macierzy i gradientu funkcji określa nowy kierunek poszukiwań.
Opracowano także metodę sympleksu nieliniowego, która polega na analizowaniu zbioru punktów dziedziny funkcji celu rozpinających w niej sympleks (zbiór niezerowej miary o minimalnej liczbie wierzchołków, tj. n + 1). W każdym kroku sympleks podlega przekształceniom, przemieszczając się w dziedzinie oraz kurcząc się lub rozszerzając. , ,� .. , ,
Optymalizacja globalna. O zadaniach optymalizacji globalnej mówi się wówczas, gdy funkcja celu ma w obszarze dopuszczalnym
1.3. Metody optymalizacji
.41,
więcej niż jedno minimum lokalne. Wielość minimów lokalnych stanowi utrudnienie w konstruowaniu algorytmu optymalizacji nie może on polegać na lokalnych właściwościach funkcji celu, a kolejne modyfikacje poprawiające nie zawsze prowadzą do rozwiązania globalnie optymalnego.
Znanych jest wiele metod optymalizacji globalnej; dają one najczęściej rozwiązania przybliżone.
Wiele metod polega na modyfikacji algorytmu optymalizacji lokalnej. Należą do nich metody wielostartowe z modyfikacją funkcji celu, polegającą na "zasypywaniu" obszarów przyciągania minimów lokalnych znalezionych w kolejnych uruchomieniach algorytmu losowego. Inne metody bazują z kolei na symulacji ruchu punktu materialnego, który ma pewną bezwładność. Dodanie bezwładności sprawia, że oprócz ruchu w kierunku minimum lokalnego, punkt ma także składową "szybkości" wynikającą z ruchu wykonanego w poprzednim kroku, dzięki czemu jest możliwe opuszczenie "płytkich" minimów funkcji celu.
Zasygnalizowane powyżej metody charakteryzują się tym, że naraz przetwarzany jest tylko jeden punkt roboczy. Są również metody populacyjne, które badają całą populację punktów. Należą do nich metody bazujące na grupowaniu, w których wykonuje się naprzemiennie optymalizację lokalną i grupowanie punktów. Zakłada się, że punkty znajdujące się w otoczeniu tych samych minimów lokalnych będą w kolejnych krokach optymalizacji lokalnej zbliżać się do siebie. Identyfikacja takich grup pozwala usunąć część punktów z dalszych rozważań, gdyż ich istnienie przyczynia się co najwyżej do zwiększenia obliczeń. Połączeniem popula-cyjnej metody sympleksu nieliniowego z symulowanym wyżarzaniem* jest grupa algorytmów sterowanego przeszukiwania losowego.
W kolejnej grupie metod, tzw. metodach pokryć przyjmuje się założenie, że funkcja celu spełnia warunek Lipschitza. Obszar dopuszczalny pokrywa się siatką, po czym w każdym oczku siatki sprawdza się oszacowanie rozwiązania. Jeśli jest ono lepsze niż wartość funkcji w najlepszym punkcie znalezionym do tej pory przez algorytm, wówczas zagęszcza się takie oczko siatki.
Zadania dyskretne. W zadaniach dyskretnych dużą rolę ma złożoność obliczeniowa rozwiązywanego problemu. Metody rozwiązywania można podzielić na dokładne, przybliżone i losowe.
Metody dokładne gwarantują wyznaczenie rozwiązania. Najprostszą, a zarazem najbardziej nieefektywną metodą, jest algorytm pełnego przeglądu. Sprowadza się on do zanalizowania wszystkich rozwiązań i wybrania najlepszego. Jego usprawniona wersja metoda podziałów i ograniczeń umożliwia pominięcie *Meto części rozwiązań, chociaż w pesymistycznym przypadku sprowa- wyżar dza się również do pełnego przeglądu. dziatu
symulowanego
i jest omówiona
części podroz-
.42.
1. W poszukiwaniu optimum...
Metody przybliżone wyznaczają przybliżone rozwiązania. Pozwalają na określenie dokładności przybliżenia. Algorytmy aprok-symacyjne, znane dla niektórych problemów, pozwalają ograniczyć błąd wyznaczenia wartości funkcji celu w minimum globalnym (np. zagwarantować, że wartość funkcji celu w minimum globalnym jest co najwyżej dwa razy mniejsza niż w znalezionym rozwiązaniu). Z kolei metody k-opt gwarantują, że w otoczeniu rozwiązania o promieniu k nie można znaleźć innego minimum lokalnego.
Metody losowe nie dają gwarancji uzyskania rozwiązania, a nawet oszacowania przybliżenia tego rozwiązania. Umożliwiają natomiast odnalezienie rozwiązania z pewnym prawdopodobieństwem, najczęściej rosnącym wraz z liczbą kroków metody. Istotą tych metod jest losowe próbkowanie przestrzeni rozwiązań.
Istnieje też grupa heurystycznych metod poszukiwania. Charakteryzują się one tym, że odzwierciedlają ,>rozsadne" strategie, czyli takie, dla których w większości przypadków można oczekiwać nie najgorszego rozwiązania. Z metod heurystycznych korzystają najczęściej twórcy algorytmu mający intuicję co do regularności rozwiązywanego problemu.
Metody niedeterministyczne. Omówione poniżej niedeter-ministyczne algorytmy optymalizacji dają się zastosować zarówno w zadaniach ciągłych, jak i dyskretnych. Charakteryzują się wykorzystaniem losowości zarówno w procesie poszukiwań nowych rozwiązań, jak też w procesie przechodzenia między kolejnymi rozwiązaniami roboczymi. Sposób losowego generowania rozwiązań zależy od dziedziny zadania i wykorzystuje ciągłe lub dyskretne zmienne losowe, natomiast sama konstrukcja algorytmu jest niezależna od dziedziny problemu.
Najprostsza jest metoda Monte Carlo, gdzie z rozkładem jednostajnym dokonuje się szeregu losowań punktu z przestrzeni rozwiązań, pamiętając najlepszy dotychczas znaleziony. W metodzie błądzenia przypadkowego przetwarza się jeden punkt roboczy. Punkt ten jest wartością oczekiwaną rozkładu prawdopodobieństwa, wykorzystywanego do generowania kolejnego punktu, który staje się punktem roboczym niezależnie od wartości funkcji celu. Podobnie jak przedtem, pamiętane jest rozwiązanie ,,rekor-dowe".
Metoda symulowanego wyżarzania jest modyfikacją
*Koncepcja metody symu- błądzenia przypadkowego, w której nowo wygenerowany punkt bwanego wyżarzania po- nje zawsze gtaje się rozwiązaniem roboczym: dzieje się tak wów-
wstała z inspiracji proce- J Ł c
sem krzepnięcia substancji, czas, gdy poprawia on wartość funkcji celu, natomiast w przeciw-wktórym wtaściwy spo- nym prZypadku, akceptacja następuje z prawdopodobieństwem
sóbobnizaniatemperatury J ^ jr J r J ^ J *\ *^ ,. .
pozwala na utworzeniedu- równym pa = exp(-|A/|/T), gdzie |A/| jest modułem roznicy żych kryształów, stanowią- funkcii Celu w starym i nowo wygenerowanym punkcie, T > 0
cych uktad o małej energii J J J � i . . ^~
wewnętrznej. zaś jest parametrem zwanym temperaturą*. Niezwykle istotną
1.4. Jak oceniać algorytmy optymalizacji
.43.
sprawą w symulowanym wyżarzaniu jest odpowiednie dobranie sposobu obniżania temperatury w kolejnych generacjach. Zbyt szybkie obniżanie odbija się negatywnie na dokładności algorytmu, zbyt powolne zaś wydłuża znacznie czas obliczeń.
Poszukiwanie z tabu. Trudną do zaklasyfikowania metodę stanowi poszukiwanie z tabu. Jest ona sposobem uniknięcia niebezpieczeństwa wielokrotnego powracania do tego samego rozwiązania, co może się często zdarzać w niesystematycznych metodach poszukiwania, na przykład w metodzie błądzenia przypadkowego. Idea poszukiwania z tabu polega na tym, że algorytm jest wyposażony w pamięć dotychczas odwiedzonych punktów. Punkty znajdujące się w pamięci są tabu ich ponowne odwiedzenie jest zakazane. Aby uniknąć problemów z nadmiernym zwiększeniem zajętości pamięci, tabu jest zorganizowane na zasadzie buforu cyklicznego (tak jak kolejka FIFO)*. W ten sposób, jeśli właściwie dobierze się pojemność pamięci, można liczyć na to, że po pewnym czasie przeszukiwanie z tabu dotrze do rozwiązania.
1.4. Jak oceniać algorytmy optymalizacji
Podczas rozwiązywania praktycznych zadań (na przykład projektowania wspomaganego komputerowo, wspomagania decyzji itp.) stajemy często przed problemem dobrania takiego algorytmu optymalizacji, który prowadziłby do rozwiązania zadaniajak naj-mniejszyrn kosztem.
1.4.1. Dokładność przybliżenia rozwiązania
O dokładności algorytmu świadczy jakość uzyskiwanych rozwiązań. Przed analizą konkretnych metod skupmy uwagę na samym sposobie określenia jakości przybliżenia maksimum globalnego. Dokładność rozwiązania można wyznaczyć**, oceniając:
� odległość od poszukiwanego minimum
x*-x| ; (1.12)
� przybliżenie wartości funkcji celu w poszukiwanym minimum
l/(x*)-/(x)l (1-13) *Oczywisciezakazponow-
t ... nego odwiedzenia punktu
� miarę zbioru poziomicowego otaczającego minimum (możliwe obowiązuje dopóty, dopóki
Są dwie Wersie): stanowi on tabu, czyli prze-
bvw3 w buforze
dokładność odniesiona do miary zbioru poziomicowego wy- łłZak)adam ie funkc-a
ciętegO Ze zbiorU dopUSZCZalnegO celu jest mierzalna.
.44_ l.Wposzukiwaniuoptimum...
[xGD:/(x)>/(x*)}||
\\D\\
(1.14)
dokładność odniesiona do miary zbioru poziomicowego wyciętego z obszaru przyciągania poszukiwanego minimum
{x6fl*:/(x)>/(x*)}|| \\D*\\
(1.15)
gdzie D* oznacza zbiór przyciągania minimum globalnego, zaś jest symbolem miary zbioru (np. miara Lebesgue'a).
Zauważmy, że powyższe określenia dokładności przybliżenia nie są równoważne. W zależności od różnego rozumienia dokładności przybliżenia, ocena algorytmu bywa różna decyduje o tym funkcja celu. Przykładowo, dla dwóch różnych funkcji celu, rozwiązanie o jednakowej dokładności według kryterium (1.12) może mieć różną dokładność ocenianą według (1.13) i (1-14). Ważne jest jednak to, że zwiększenie dokładności według każdego kryterium powoduje zwiększenie (a przynajmniej nigdy nie powoduje zmniejszenia) dokładności według pozostałych kryteriów.
Zauważmy, że w przypadku płaskich obszarów przyciągania minimum funkcji celu, dokładność według (1.12) jest znacznie "ostrzej" rozumiana niż według (1.13); podobnie, dla funkcji celu mającej ostro zarysowaną dolinę, dokładność według (1.13) jest bardziej restrykcyjna. Przyjęciejako miary dokładności (1-14) lub (1.15) jest dobrym kompromisem, mówi bowiem tyle, że zbiór rozwiązań, które są lepsze od znalezionego, nie powinien być zbyt duży, abstrahując od tego, jak znaczne są różnice w wartościach funkcji celu. Niestety, kryteria (1.14) i (1.15) są mało praktyczne, gdyż wymagają znacznej wiedzy o funkcji celu.
1.4.2. Odporność
Oceniając algorytm pod kątem przydatności do rozwiązywania zadań z wieloma lokalnie optymalnymi rozwiązaniami, należy uwzględnić odporność algorytmu na ekstrema lokalne. W tym celu należałoby sprawdzić, czy metoda jest w stanie "opuszczać" obszary przyciągania minimum lokalnego. Wiązałoby się to ze stwierdzeniem, jak często (jeśli w ogóle) znajdowane są punkty . . należące do obszaru przyciągania minimum globalnego, mimo że
*Wymagałoby to bowiem " ^ J ^o o _ _ o >
znajomości nie tylko mak- żaden taki punkt me był wygenerowany w razie inicjacji algo-giobainego funkcji rytmu. Stwierdzenie teeo faktu iest iednak niemożliwe w zada-
.nuuama pr7 taK7P J *^ '' J
przystosowania, lecz także jego obszaru przyciągania.
i dość trudne dla funkcji testowych.
1.4. Jak oceniać algorytmy optymalizacji
.45.
Odporność algorytmu można więc próbować określić w sposób pośredni. Można liczyć, że odporny algorytm powinien generować rozwiązania, których położenie zależałoby w jak najmniejszym stopniu od stanu początkowego. Oznacza to, że w wyniku wielu niezależnych uruchomień należy oczekiwać uzyskania zbliżonych do siebie rozwiązań.
1.4.3. Koszt symulacji
Koszt symulacji wiąże się z nakładem obliczeń potrzebnych do osiągnięcia rozwiązania.
Koszt symulacji utożsamia się często z czasem procesora potrzebnym do wykonania obliczeń; może być również określony przez pewien wskaźnik uwzględniający liczbę obliczeń wartości funkcji celu oraz czynności pomocniczych związanych z organizacją samego algorytmu.
Koszt symulacji a liczba iteracji algorytmu. W przypadku wielu metod optymalizacji koszt jest utożsamiany z liczbą iteracji metody. Jest to dosyć wygodna konwencja, gdyż w pojedynczej iteracji wykonuje się nie tylko obliczenie wartości funkcji celu, lecz również wiele absorbujących obliczeniowo czynności, na przykład wyznaczenie nowego kierunku poszukiwań. Koszt czynności pomocniczych może być nawet w niektórych przypadkach wyższy niż koszt związany z wyznaczeniem wartości funkcji celu.
Obliczenie kosztu symulacji algorytmu nie nastręcza wielu kłopotów. Należy się jedynie zdecydować, czy jako koszt przyjmuje się liczbę wywołań wartości funkcji przystosowania, czy też raczej czasu procesora. Pierwszy wybór jest bardziej uniwersalny, gdyż abstrahuje się od sposobu implementacji samego algorytmu, natomiast w drugim przypadku na czas symulacji w istotny sposób wpływa czas wyliczania wartości funkcji przystosowania.
Dodatkowo, można wyróżnić koszt symulacji do momentu znalezienia rozwiązania (koszt "netto") od kosztu symulacji do osiągnięcia zbieżności (koszt "brutto"). W pierwszym przypadku nie bierze się pod uwagę obliczeń związanych z kryterium zatrzymania algorytmu, które czasami rnogą być dość znaczące.
Złożoność obliczeniowa. Z pojęciem kosztu symulacji algorytmu w ścisły sposób wiąże się zagadnienie jego złożoności obliczeniowej .
Jeśli algorytm ma zostać użyty do rozwiązania problemu należącego do pewnej klasy zadań, to oceniając koszt symulacji, nie bierze się pod uwagę jego wartości bezwzględnej, lecz zwiększenie zależne od wzrostu wielkości problemu (na przykład zwiększenia liczby parametrów do optymalizacji). Uważa się, że jeśli sposób
.46.
1. W poszukiwaniu optimum...
narastania kosztu (nazywany także skalowaniem algorytmu) nie jest wielomianową funkcją skończonego stopnia, to algorytm nie może zostać efektywnie użyty do rozwiązania problemów rozważanej klasy. Oczywiście, w praktyce najcenniejsze są algorytmy skalujące się liniowo lub z wielomianem niewielkiego stopnia.
Zauważmy, że w przypadku kosztu obejmującego wszystkie czynności wykonywane w algorytmie (mierzonego czasem procesora), złożoność algorytmu obliczania wartości funkcji celu jest czynnikiem wpływającym na złożoność obliczeniową.
PRZYKŁAD. Zalóżmy, że dla pewnego problemu liczba wyliczeń wartości funkcji przystosowania wzrasta jak n log n, natomiast wyliczenie wartości funkcji przystosowania zajmuje n operacji. Wówczas, koszt mierzony czasem procesora będzie wzrastał jak ?i3 logn. i; ;. ,. : ,
Należy pamiętać o podstawowej różnicy między złożonością obliczeniową algorytmu, którą szacuje się przez jego wielokrotne uruchomienie, a złożonością dla najgorszego przypadku (pesymistyczną), gdyż problemy o pesymistycznej złożoności niewielo-mianowej mogą być w sensie oczekiwanym rozwiązywalne w czasie wielomianowym. Rzecz jasna, pomiar złożoności wynikłej z wielokrotnej symulacji komputerowej algorytmu prowadzi do szacowania złożoności w sensie oczekiwanym, nie pesymistycznym2.
1.5. Metody eliminowania ograniczeń funkcyjnych
Jak wspomniano wcześniej, obecność ograniczeń kostkowych może być ułatwieniem dla algorytmu optymalizacji, natomiast ograniczenia funkcyjne, mimo że ograniczają przestrzeń przeszukiwań, mogą stanowić utrudnienie z punktu widzenia realizacji procesu przeszukiwania. Wymagają one zatem zastosowania specjalnych metod ich uwzględniania.
Metody te można podzielić na kilka kategorii w zależności od sposobu, w jaki ograniczenia wpływają na zadanie i algorytm. Dla wygody prowadzonych dalej rozważań metody podzielono na sprowadzające zadanie z ograniczeniami do zadania bez ograniczeń i modyfikujące algorytm. Te ostatnie omówiono w dalszej części książki, natomiast poniżej przedstawiono metody należące
2Zatarcie różnicy między tymi dwiema miarami może prowadzić do wielu nieporozumień znane są doniesienia (np. o "algorytmie rozwiązywania problemu komiwojażera w czasie wielomianowym"), w których wyciąga się zbyt daleko idące wnioski, interpretując obserwowaną eksperymentalnie, wielomianową zależność czasu symulacji algorytmu od złożoności problemu, jako rozwiązanie problemu A^P-zupełnego w czasie wielomianowym.
1.5. Metody eliminowania ograniczeń funkcyjnych
.47.
do pierwszej z wymienionych grup. Należy podkreślić, że mają one zastosowanie nie tylko do algorytmów ewolucyjnych, lecz również do innych metod optymalizacji.
1.5.1. Metody transformacji zmiennych niezależnych
Metody transformacji polegają na zastąpieniu wektora zmiennych niezależnych x wektorem L,. W tym celu definiuje się transformację T (która powinna być przekształceniem odwracalnym) i dokonuje się odwzorowania
L, = T(x)
(1.16)
Oryginalna funkcja celu /(x) zostaje zastąpiona funkcją /'(L)� Zadanie optymalizacji rozwiązuje się w dziedzinie zmiennych niezależnych L, samo zaś rozwiązanie L,* retransformuje, otrzymując rozwiązanie oryginalnego zadania x* = T~1(^*).
Metody transformacji zmiennych niezależnych są stosowane w celu uproszczenia zadania, które może polegać na zmniejszeniu wymiarowości zadania (poprzez redukcję liczby zmiennych niezależnych), zmniejszeniu liczby ograniczeń funkcyjnych lub też uzyskaniu wygodniejszej postaci ograniczeń (np. kostkowych). Poniżej omówiono dwie techniki transformację zmniejszającą wy-miarowość zadania przez eliminację równościowych ograniczeń liniowych oraz przekształcenie zmieniające charakter funkcyjnych ograniczeń nierównościowych na kostkowe, nie wpływające na wy-miarowość zadania.
Zmniejszenie liczby zmiennych niezależnych. Jako reprezentacyjną dla pierwszej grupy omawianych technik rozważmy metodę zamiany zmiennych niezależnych polegającą na wyznaczeniu nowej bazy w przestrzeni przeszukiwań. Przyjmijmy założenie, że zbiór dopuszczalny D � Rn jest niepusty, jest zerowej miary w Rn i ma niezerową, skończoną miarę w Rm (m < n). Oznacza to, że do jego pełnego opisu wystarczy nie n, lecz tylko m zmiennych niezależnych. Przyjmijmy też, że istnieją ograniczenia równościowe liniowe, dane w postaci analitycznej. Założenie to umożliwia określenie analitycznej postaci transformacji T.
Dane jest k ograniczeń liniowych równościowych /ij(x). Jeśli zapiszemy zbiór funkcji hj(x) w postaci macierzowej, otrzymamy równanie , ....
^x+b=0
(1.17)
gdzie macierz A (o wymiarach fcxn) oraz wektor b (fc-wymiarowy) są tworzone na podstawie współczynników poszczególnych funkcji hj(x). Metoda transformacji zmiennych polega na wyznaczeniu (n &)-wymiarowej bazy macierzy A. Baza ta stanowi zbiór
1. W poszukiwaniu optimum...
wersorów w Rn~ z wektorem nowych zmiennych niezależnych [Ci>^2) � � � ,Ln-fc]T, PrzY czym funkcja celu w tej przestrzeni jest tworzona na podstawie oryginalnej /'(L) = /(T~1(^)).
Jeśli liniowe, znane analitycznie ograniczenia równościowe nie są jedynymi występującymi w problemie, można mimo to skorzystać z opisanej metody, gdyż (jako przekształcenie liniowe) nie wprowadza ona zniekształceń do proporcji w przestrzeni argumentów funkcji celu. Jedynym, niezbyt uciążliwym utrudnieniem wjej stosowaniu jest konieczność wyznaczenia bazy. Tak więc metoda wydaje się godna polecenia zwłaszcza w zadaniach ze stosunkowo dużą liczbą liniowych ograniczeń równościowych, a co za tym idzie istnieje możliwość znacznej redukcji wymiarowości zadania.
�'.'�s. . ; * :: � ' ;
Transformacja ograniczeń do postaci kostkowych. Jeśli istnieją funkcje ograniczeń nierównościowych, a ponadto zbiór dopuszczalny jest wypukły i skończonej miary, mamy możliwość wykorzystania pewnego nieliniowego przekształcenia, którego celem jest nie redukcja wymiarowości zadania, lecz sprowadzenie funkcyjnych ograniczeń nierównościowych do najwygodniejszej postaci ograniczeń kostkowych.
Metoda omówiona poniżej polega na rzutowaniu punktów z obszaru dopuszczalnego na hiperkostkę opisaną na tym obszarze (rys. 1.9). Należy określić punkt stały przekształcenia x� G D, dla którego
,� = T(x�) = x�
(1.18)
Należy także określić hiperkostkę, która będzie stanowić nowy obszar dopuszczalny; zbiór D powinien w całości zawierać się w tej hiperkobtce.
Idea metody polega na tym, że prowadzi się półprostą o początku w punkcie x�, przechodzącą przez x i znajduje się punkt x5 jej przecięcia z granicą zbioru dopuszczalnego. Następnie znajduje się przekształcenie liniowe, przekształcające x5 w punkt L, leżący na przecięciu omawianej półprostej z granicą nowego zbioru dopuszczalnego (hiperkostki, do której dążymy). Proporcję odległości |xs x� oraz |L, L wykorzystujemy do wyznaczenia punktu 7"(x). Szczegółowy opis transformacji znajduje się poniżej.
Oznaczmy d = x x�. Rozważa się półprostą opisaną równaniem x = x� + dr, gdzie r e [0, oo). Punkt xs znajduje się, wyznaczając dla każdego ograniczenia pi(x) rozwiązania x5'1 układu
1.5. Metody eliminowania ograniczeń funkcyjnych
.49.
RYSUNEK 1.9. Ilustracja metody transformacji zmiennych niezależnych przez rzutowanie na ograniczenia
i wybierając x spośród nich
x5-x�
= mn
(1.19)
Punkt L,s wyznacza się w podobny sposób, znajdując rozwiązania L,S>1 układów (li, Ui oznacza ograniczenia kostkowe dla zmiennej Xi]:
i k
,r > 0 oraz
kr > 0 � .' � ,-,;,; ,�/.; �-. . i wybierając punkt L, , taki że
(1.20)
.50.
1. W poszukiwaniu optimum...
RYSUNEK 1.10. Ilustracja zniekształceń wprowadzanych przez transformację zmiennych. Zaburzeniu ulegają zarówno proporcje miar zbiorów przyciągania ekstremów lokalnych, jak również ich wypukłość
Punkt L, = T(x) jest wyznaczany w następujący sposób:
(1.21)
Zdefiniowane powyżej przekształcenie zniekształca wzajemne proporcje miar zbiorów (rys. 1.10), niejest również zachowana wypukłość zbiorów. Stopień zniekształcenia zależy od wyboru punktu stałego x�.
1.5.2. Metody funkcji kary :
Metody funkcji kary polegają na wyeliminowaniu ograniczeń poprzez włączenie ich do funkcji celu.
Zmodyfikowana funkcja celu jest tworzona w następujący sposób:
/'(x) =
(1.22)
1.5. Metody eliminowania ograniczeń funkcyjnych
.51.
gdzie /f(x) jest funkcją kary związaną z ograniczeniem nierówno-ściowym W zależności od sposobu określenia funkcji /?(x), wspomniane metody można podzielić na dwie podstawowe kategorie: z zewnętrzną i z wewnętrzną funkcją kary. W pierwszym przypadku, karane jest wykroczenie poza obszar dopuszczalny, w drugim zaś zbliżenie się do jego granic (od strony wnętrza). Istnieją również funkcje mieszane, które łączą cechy obu kategorii.
Zewnętrzna funkcja kary. Metody z zewnętrzną funkcją kary polegają na modyfikacji funkcji celu w taki sposób, aby punkty poza obszarem dopuszczalnym (rys. 1.11) miały jak "najgorszą" wartość zmodyfikowanej funkcji. Ma to wpłynąć na algorytm optymalizacji w taki sposób, aby zapobiec generowaniu punktów niedopuszczalnych. Aby spełnić powyższe zadanie, funkcja /f(x) ma następujące właściwości*:
/f(x) = 0 /f(x) > 0
jeśli &(x) < 0 jeśli &(x) > 0
(1.23)
W praktyce, wskazane jest jeszcze, aby funkcja kary zwiększała swoją wartość wraz z oddalaniem się punktu x od granicy obszaru dopuszczalnego. Ze względu na wygodę obliczeń, rozwiązaniem często stosowanymjest przyjęcie wartości /f(x) = 0 /f(x) =
fp(*)
jeśli 0
(1.24)
Obszar
dopuszczalny
RYSUNEK 1.11. Zewnętrzna funkcja kary
*Nietrudno zauważyć, że stosowanie zewnętrznej funkcji kary ma sens jedynie wówczas, gdy funkcja celu jest zdefiniowana również poza obszarem dopuszczalnym.
.52.
1. W poszukiwaniu optimum...
Funkcja P(z] decyduje o charakterze funkcji kary. Często można spotkać rozwiązania z liniową funkcją kary P(z} = az, chętniejest też stosowana funkcja kwadratowa P(z] = az. Druga z wymienionych możliwościjest szczególnie wygodna w przypadku stosowania gradientowych metod poszukiwania minimum, gdyż zapewnia różniczkowalność funkcji /'(x) (również w miejscu "sklejenia" z funkcją kary). Niestety, wspomniana zaleta wiąże się ze stosunkowo powolnym narastaniem funkcji kary w pobliżu ograniczenia, co może prowadzić do tego, że minimum funkcji /'(x) wypadnie poza obszarem dopuszczalnym. Dlatego też w przypadku algorytmów, które nie wymagają różniczkowalności /'(x), bardziej dogodne wydają się być funkcje kary /f(x), które silnie narastają już w okolicy ograniczeń. Stosunkowo wygodnym rozwiązaniem będzie przyjęcie wspomnianej funkcji liniowej lub na przykład logarytmicznej P(z) = alog(l + z).
f(*)
Zmodyfikowana funkcja celu
RYSUNEK 1.12. Po uwzględnieniu funkcji kary minimum zmodyfikowanej funkcji celu znajduje się poza obszarem dopuszczalnym
Często okazuje się, że mimo starannego doboru funkcji kary, wynikiem minimalizacji /'(x) jest punkt poza obszarem dopuszczalnym (rys. 1.12). W takiej sytuacji należy powtórzyć optymalizację, zwiększając funkcję kary aż do momentu, gdy wynikiem optymalizacji /'(x) będzie punkt położony w obszarze dopuszczał-
1.5. Metody eliminowania ograniczeń funkcyjnych
.53.
nym. Tworzy się w ten sposób ciąg funkcji kary f? (x), który powinien spełniać następujące warunki dla każdego x ^ D:
lim
(1.25)
Spełnienie powyższych warunków gwarantuje, że będzie istnieć takie fcmm, że dla każdego k > kmin funkcja /'(x) = /(x) + 4-/f (x) będzie miała minimum w obszarze dopuszczalnym.
Stosowanie zewnętrznej funkcji kary może być wskazane zwłaszcza w przypadku niewypukłych i niespójnych obszarów dopuszczalnych, gdyż pozwala ona na czasowe przebywanie rozwiązań poza ograniczeniami.
Szczególnym przypadkiem zewnętrznej funkcji kary jest "kara
śmierci". Polega ona na tym, że funkcja /f(x) = 00 dla każdego x ^ D. Nie ma więc potrzeby obliczania wartości funkcji celu poza obszarem dopuszczalnym, a ponadto, wynikiem minimalizacji /'(x) zawsze będzie punkt spełniający ograniczenia*.
Wewnętrzna funkcja kary. Niekiedy może się zdarzyć, że funkcja /(x) nie jest zdefiniowana poza obszarem dopuszczalnym. Wówczas należy zapobiegać generowaniu punktów poza ograniczeniami, wprowadzając wewnętrzną funkcję kary, określoną wyłącznie na zbiorze dopuszczalnym. Powinna ona spełniać następujące założenia dla każdego x e D:
Q Obszar dopuszczalny
RvsUNEK 1.13. Wewnętrzna funkcja kary
*Takie rozwiązaniejestjed-nak dość niewygodne, gdyż uniemożliwia uzyskanie rozwiązania dopuszczalnego poprzez serię przekształceń poprawiających rozwiązania niedopuszczalne.
.54______ 1. W poszukiwaniu optimum...
/fW>0
lim /f(x) = 00
/ (1.26) " (1-27)
W ten sposób definiuje się pewnego rodzaju "barierę", która nie pozwala na opuszczenie zbioru dopuszczalnego, jeśli optymalizacja rozpoczęła się w jego wnętrzu*.
Stworzona w powyższy sposób wewnętrzna funkcja kary ma poważną wadę może powodować, że minima bliskie ograniczeniom nie zostaną odnalezione (rys. 1.14). Aby uniknąć tego nie-
Zmodynkowana funkcja celu
RvsuNEK 1.14. Minimum funkcji celu zmodyfikowanej wewnętrzną funkcją kary jest położone w innyrr miejscu niż oryginalnej funkcji celu
korzystnego zjawiska, a przy tym zachować "łagodne włączenie"
kary, należy zdefiniować ciąg wewnętrznych funkcji kary /? (x) o następujących właściwościach:
< 0
fP,(*i-i|/\ ^ fP,(k)(\
Ji \^-) :^ Ji \^-)
lim /f(x) = 0 dla
Ciąg ten ma tę właściwość, że dla wszystkich punktów z wnętrza
obszaru dopuszczalnego funkcja kary się "wyłącza", upodobniając
zmodyfikowaną funkcję celu /'(x) do oryginalnej funkcji /(x).
*stadnazwa,,funkcjibarie- Oznacza to, że rozwiązanie zadania optymalizacji funkcji zmo-
rowej" wykorzystywana me- dyfikowanei będzie zdążać do rozwiązania oryginalnego zadania
kiedy na określenie we- J J x ^ ^ J � �
wn?trznej funkcji kary. optymalizacji w zbiorze dopuszczalnym.
1.6. Zadania wielokryterialne
1.6. Zadania wielokryterialne
1.6.1. Sformułowanie zadania
Wiele problemów podejmowania decyzji, projektowania itp. trudno jest niekiedy sformułować jako zadanie optymalizacji funkcji celu zwracającej jedną wartość, gdyż zamiast jednego liczbowego kryterium oceny, musimy uwzględniać cały ich zbiór. Nierzadko też jednoczesna minimalizacja tych kryteriów jest niemożliwa z powodu ich wzajemnej sprzeczności.
PRZYKŁAD. Załóżmy, że gramy na giełdzie papierów wartościowych. Akcje firm będące przedmiotem obrotu różnią się m.in. poziomem ryzyka i przynoszonym zyskiem. Inwestor dąży zazwyczaj do kupowania akcji charakteryzujących się jak najmniejszym ryzykiem i mających jak największą rentowność. Ponieważ z reguły nie ma akcji, które spełniałyby oba kryteria, należy najpierw odrzucić z dalszych rozważań takie, dla których istnieje co najmniej jeden papier wartościowy charakteryzujący się jednocześnie mniejszym ryzykiem i wyższą rentownością. Papiery wartościowe, które pozostały po takiej selekcji, są równoprawnymi rozwiązaniami zadania jednoczesnej minimalizacji ryzyka i współczynnika cena/zysk. Na rysunkul.l5problemprzedstawionograficznie.
.55.
0
cena/zysk
RvsuNEK 1.15. Ilustracja zadania wielokryterialnego na przykładzie zadania inwestowania w papiery wartościowe. Celem jest inwestowanie w papiery o jak najmniejszym ryzyku i jak najmniejszej wartości współczynnika cena/zysk. Wyróżniono zbiór papierów niezdominowanych
u Naszkicowany powyżej problem da się sformułować w następujący sposób. Dany jest zbiór m funkcji (możemy go sobie wyobrażać również jako wektor) f(x) = [/i(x),...,/m(x)]. Celem jest jednoczesna minimalizacja wszystkich kryteriów /j(x). Ponieważ z reguły kryteria nie są ze sobą zgodne (minimalizacja
.56.
1. W poszukiwaniu optimum...
jednego z nich może powodować wzrost innych), wprowadza się relację dominacji, oznaczaną >~, określoną następująco:
Vfc = l,...,m /fc(x)x >- y wtedy i tylko wtedy, gdy 3k /fc(x) < /fc(y)
(1.28)
Zadanie optymalizacji wielokryterialnej polega na poszukiwaniu zbioru P punktów niezdominowanych*. Wśród zadań optymalizacji wielokryterialnej możemy wyróżnić dwa przypadki szczególne:
1) poszukiwanie niezdominowanego punktu,
2) poszukiwanie zbioru punktów niezdominowanych.
Pierwsze z postawionych zadań wydaje się być znacznie łatwiejsze i da się niekiedy sprowadzić do problemu optymalizacji ze skalarnym wskaźnikiem jakości (np. poprzez obliczenie sumy poszczególnych kryteriów przy założonych współczynnikach wagowych).
Z kolei drugie zadanie jest bardzo trudne i w ogólnym przypadku niemożliwe do rozwiązania ze względu na fakt, że niezdominowanych punktów dopuszczalnych może być nieskończenie wiele.
W literaturze dotyczącej algorytmów ewolucyjnych spotyka się uproszczenie tego zadania polegające na wymaganiu, aby znaleźć nie wszystkie, lecz możliwie najwięcej rozwiązań niezdominowanych. Dodatkowo, powinny one jak najbardziej równomiernie pokrywać zbiór rozwiązań niezdominowanych**.
Poniżej omówiono metody sprowadzenia zadania wielokryte-rialnego do skalarnego. Pozostałe metody rozwiązywania zadań wielokryterialnych omówiono w dalszej części książki.
1.6.2.Skalaryzacjazadania
Zadanie wielokryterialne można sprowadzić do skalarnego poprzez wprowadzenie dodatkowego kryterium, porządkującego punkty niezdominowane.
Najprostszą metodą skalaryzacji jest potraktowanie poszczególnych składników wektorowego wskaźnika jakości jako ograniczeń poprzez określenie ich maksymalnych dopuszczalnych wartości. W ten sposób, problem wielokryterialny można sprowadzić do *zbiór ten często jest na- zagadnienia znalezienia dowolnego punktu dopuszczalnego i roz-zywany zbiorem Pareto, od wiązywać metodami właściwymi dla problemów z ograniczeniami.
nazwiska włoskiego mate- T , . , . , . , , . 1 , . i , . ,
matyka. Jedno z kryteriów moze byc wiodące, wówczas me wchodzi ono do
**Takie równomierne po- zadania skalarnego jako ograniczenie, lecz jako (skalarna) funkcja krycie ułatwia decydentowi ceju prowadzi to do klasycznej postaci problemu optymalizacji
wybramejednegozrozwią- f . . J *" * f * J
zańniezdominowanych. ZOgraniCZeniami. ,,;t ;!
1.6. Zadania wielokryterialne
.57.
Inną metodąjest wprowadzenie funkcji agregującej, której argumentami są wartości poszczególnych składników wektorowego wskaźnika jakości. Otrzymuje się zagregowany, skalarny wskaźnik jakości /s(x), który jest przedmiotem optymalizacji
gdzie y>s oznacza funkcję agregującą. W zależności od wyboru funkcji tps mówi się o różnych metodach skalaryzacji. Należą do nich między innymi:
� ważone sumowanie kryteriów,
� metoda punktu idealnego,
� metoda punktu najgorszych oczekiwań.
Ważone sumowanie składników wektorowego wskaźnika jakości. Jest to chyba najczęściej stosowana metoda skalaryzacji. Funkcja agregująca ,/m(x)) =
(1.30)
gdzie Wk � K+ są współczynnikami wagowymi. Omawiana metoda polega na znalezieniu hiperpłaszczyzny stycznej do zbioru rozwiązań niezdominowanych, której nachylenie jest określone przez wartości współczynników wagowych. Rozwiązaniem zadania wielokryterialnego są punkty styczności tej hiperpłaszczyzny ze zbiorem rozwiązań niezdominowanych (rys. 1.17).
Ważone sumowanie mo/na rozumiećjako określenie "wyceny" poszczególnych elementów wektorowego wskaźnikajakości. Można je interpretować w ten sposób, że jesteśmy skłonni zaakceptować pogorszenie kryterium /i(x) o pewną wielkość, jeśli skompensują nam to korzyści wynikające z poprawy wartości innych kryteriów; wzajemne proporcje korzyści i strat wynikają z przyjętych współczynników wagowych w^.
Metody punktu idealnego i punktu najgorszych oczekiwań. W metodzie punktu idealnego decydent podaje punkt, zwany idealnym, znajdujący się poza obszarem dopuszczalnym. Punkt ten to idealne wartości wektorowego wskaźnika jakości. Zadanie optymalizacji wielokryterialnej sprowadza się wówczas do znalezienia rozwiązań niezdominowanych, znajdujących się najbliżej punktu idealnego. Funkcja agregująca ma postać
.58.
1. W poszukiwaniu optimum...
Rozwiązania dopuszczalne
Punkt idealny
Rozwiązanie zadania po skalaryzacji
(a)
Rozwiązania dopuszczalne
\
Punkt idealny
Rozwiązanie zadania po skalaryzacji
-' Punkty
niezdominowane
/i(*)
(b)
RvsuNEK 1.16. Metoda punktu idealnego. Widoczne kształty zbiorówjednakowej wartości zagregowanej funkcji celu: a) norma euklidesowa, b) norma maksimum
, 1.6. Zadania wielokryterialne
.59.
gdzie f* oznacza punkt idealny, � | zaś jest symbolem normy wektora. Najbardziej "naturalna" jest norma euklidesowa
z =
(1.32)
W tym przypadku metoda punktu idealnego wyraża tendencję, aby jak najbardziej zbliżyć się do f*, manipulując w dowolny sposób wartościami poszczególnych elementów wektorowego wskaźnika jakości.
Równie przydatna może być np. norma maksimum
z = rnaxz,;
(1.33)
wyrażająca chęć uzyskania takiego rozwiązania, którego wartość najgorszego kryterium jest jak najbliższa idealnemu (pozostałe kryteria nie wpływają na ocenę rozwiązania). Interpretację geometryczną omawianych kryteriów przedstawiono na rys. 1.16.
Z kolei metoda punktu najgorszych oczekiwań jest dualna do metody punktu idealnego. Różnica polega na tym, że w metodzie punktu idealnego minimalizuje się odległość od tego punktu, w przypadku zaś punktu najgorszych oczekiwań, odległość od niego jest przedmiotem maksymalizacji.
Minima lokalne skalarnej funkcji celu. Zastosowanie metody skalaryzacji może prowadzić do funkcji celu mającej więcej
h(x)
Rozwiązania dopuszczalne
Rozwiązania zadania po skalaryzacji
Punkty
n iezdominowane
RYSUNEK 1.17. Minima lokalne wprowadzane przez metodę skalaryzacji przy niewypu-kłym zbiorze punktów niezdominowanych
.60.
1. W poszukiwaniu optimum...
niż jedno minimum. Sytuacja taka może mieć miejsce wówczas, gdy np. zastosuje się metodę ważonego sumowania, a zbiór rozwiązań niezdominowanych jest niewypukły. Wówczas, dla pewnych wartości wag, zbiór punktów optymalnych w sensie wartości wskaźnika skalarnego /5(x) zawiera więcej niż jeden element (rys. 1.17). W takiej sytuacji wskazane jest zastosowanie jednej z metod optymalizacji wielomodalnej*, tak aby móc zlokalizować więcej niż jeden punkt.
1.7. Środowisko dynamiczne
O środowisku dynamicznym3 mówimy wówczas, gdy poszukiwane jest minimum funkcji celu /(x, t) zmiennej w czasie. Zmienne w czasie mogą być również funkcje ograniczeń, co skutkuje zmiennością w czasie zbioru rozwiązań dopuszczalnych D(t) (możemy mówić o zmienności w czasie funkcji charakterystycznej zbioru rozwiązań dopuszczalnych XD(t)}-
W takim środowisku celem jest śledzenie położenia minimum globalnego, czyli adaptacja do zmieniającego się środowiska. W dalszym ciągu rozważań przyjmiemy założenie upraszczające, że wszelkie zmiany (zarówno funkcji celu, jak i zbioru rozwiązań dopuszczalnych) następują w sposób dyskretny w czasie.
Zadanie adaptacji możemy więc sformułować w następujący sposób. Dla każdego t znaleźć takie x*(i), że
x*(i) = arg min /(x,i)
(1.34)
Zauważmy, że zależna od czasu może być zarówno funkcja celu, jak i zbiór rozwiązań dopuszczalnych. W przypadku zbioru dopuszczalnego, zdefiniowanego za pomocą funkcji ograniczeń równościowych i nierównościowych, oznacza to zależność tych funkcji od czasu, jak również możliwość zmiany ich liczby w czasie. Zadanie adaptacji polega więc nie na jednorazowym znalezieniu punktu, dla którego funkcja celu przyjmuje minimum, lecz raczej na każdorazowym wyszukiwaniu tego punktu.
3W niektórych publikacjach zadanie ze zmienną w czasie funkcją celu lub zbiorem ograniczeń jest nazywane zadaniem optymalizacji dynamicznej. Może to być źródłem nieporozumień, gdyż terminem optymalizacji dynamicznej obejmuje się również zadanie optymalizacji scenariuszy sterowań. Różnica polega na tym, że Zagadnieniuoptyrnalizacji . wielomodalnej poświęcimy J � ' ^J J ^ , . ..
więcej uwagi w części trze- na pewnym horyzoncie czasowym, podczas gdy w zadaniu optymalizacji w srodowi-
ciej. sku dynamicznym chodzi o znalezienie minimum dopiero co zastanej funkcji celu.
1.7. Środowisko dynamiczne
.61,
1.7.1. Kryteriaocenyalgorytmu !
Podstawowym kryterium oceny stosowanym w wielu pracach jest zdolność algorytmu do nadążania za zmianami środowiska. W zależności od tego, czy dostępna jest informacja o zajściu takich zmian, możemy przyjąć następujące kryteria oceny algorytmu:
� niedostępna informacja o zmianach środowiska błąd nadążania za tymi zmianami jest najczęściej definiowany jako
(1.35)
gdzie e(r} jest wartością błędu zadania (statycznego) w chwili r; � znane momenty zmian środowiska w tym przypadku możemy złagodzić kryterium oceny, wymagając aby adaptacja nastąpiła przed kolejną zmianą środowiska
e = \ E r6{ti,...,tfc}
gdzie ti,..., tk są momentami zmian w środowisku.
Dostępność informacji o zmianach środowiska pozwala algorytmowi zmniejszyć szybkość nadążania za zmianami; jest to zatem "łagodniejsze" kryterium oceny.
1.7.2. Rodzaje zmian środowiska
Aby mówić o zmianach środowiska, należy poczynić założenie o istnieniu pewnych podobieństw między kolejnymi funkcjami celu /(x,i). Ze względu na możliwość konstruowania metod adaptacji, kilka rodzajów zmian ma szczególne znaczenie:
a) położenia minimów lokalnych nie ulegają zmianie, natomiast zmieniają się wartości funkcji celu w tych minimach; w ten sposób minimum lokalne może stać się globalnym i odwrotnie;
b) położenie minimum globalnego zmienia się w sposób okresowy;
c) minimum globalne x*(t + 1) znajduje się w otoczeniu o promieniu r minimum globalnego x*(t).
.62.
1. W poszukiwaniu optimum...
1.7.3. Adaptacja do zmian środowiska .;:V- �
Podstawową metodą adaptacji jest każdorazowe wznawianie algorytmu optymalizacji po zajściu zmiany. Wymaga to oczywiście odpowiedniej szybkości algorytmu powinien on dać rozwiązanie nie później, niż przed zajściern kolejnej zmiany.
Jeśli zmiany w środowisku zachodzą zgodnie z wariantem c) wydaje się wskazane rozpocząć optymalizację w punkcie, będącym poprzednim minimum globalnym, a przynajmniej w jego otoczeniu o promieniu mniejszym niż r. Z kolei w wariancie b) wystarczy zapamiętywać położenia dotychczas znalezionych minimów*. Z kolei przy zmianach opisanych w wariancie a) można usiłować wyznaczyć położenia wszystkich minimów lokalnych (jest to praktycznie wykonalne tylko przy niewielkiej ich liczbie), a następnie przeliczać jedynie wartość funkcji celu w tych punktach, wybierając najlepszy z nich.
1.8. Uwagi bibliograficzne
Zadania i metody optymalizacji parametrycznej doczekały się wielu opracowań książkowych (zarówno monografii, jak i podręczników).
Przegląd metod optymalizacji ciągłej liniowej i wypukłej, a także metod funkcji kary, można znaleźć na przykład w pracach [21, 93, 99, 110]. Pogłębioną analizę formalną metod optymalizacji wypukłej zawiera książka [66]. Zwięzły przegląd metod wraz z dużą liczbą zadań znajduje się w [11].
Jedną z pierwszych książek poświęconych optymalizacji globalnej jest praca [102]. Zamieszczono tam także zestaw funkcji testowych, które do dzisiaj służą do porównywania szybkości i dokładności działania różnych metod. Nieco nowszy przegląd algorytmów i ich krótką charakterystykę można znaleźć w [103]. Metodom losowym, przede wszystkim metodzie Monte Carlo, poświę-conajest pozycja [112].
Spójne ujęcie problemów kombinatorycznych i ich złożoności obliczeniowej przedstawiono w książce [27]. Do prac w języku polskim można sięgnąć do [7, 8]. Wykład o złożoności obliczeniowej opierający się na teorii języków formalnych można znaleźć np. w [39]. Metody rozwiązywania problemów kombinatorycznych w [101]. Szczególne miejsce wśród metod rozwiązywania proble-�Znajomość okresu zmian mów 7VP-zupelnych zajmują metody aproksymacyjne, o których
jest wówczas bardzo po- mozna prZeczytaĆ W [l4]. mocna, gdyz moze posłu- x l J
żyć do ograniczenia iio- Ogólne omówienie metod symulowanego wyzarzama i tabu
śdpamieciwykorzystywa- w zadaniach kombinatorycznych można znaleźć w [58] (tam rów-
nejdoprzecnowywaniazna- ^ ^ l J x .
iezionych minimów. nicż dość specyficzne przedstawienie algorytmów genetycznych).
1.9. Pytania i ćwiczenia
.63.
O symulowanym wyżarzaniu można więcej przeczytać w pracy [106]. Z kolei poszukiwaniu z tabu poświęcona jest pozycja [30].
Metodę eliminacji funkcyjnych ograniczeń nierównościowych przedstawiono w [42, 43].
Metodom optymalizacji parametrycznej poświęcone jest czasopismo Journal oj Optimization Theory and Applications (JOTA), natomiast o rozwoju metod optymalizacji globalnej można przeczytać w Journal of Global Optimization (JGO). Warto też sięgnąć do Journal of Heuristics, gdzie można znaleźć artykuły poświęcone metodom optymalizacji dyskretnej.
1.9. Pytania i ćwiczenia
1. Załóżmy, że funkcja celu spełnia warunek Lipschitza i znana jest wartość L. Przyjmijmy, że istnieją ograniczenia kostkowe li, Ui dla każdej zmiennej niezależnej x-, (i = l,...,n). Poszukujemy punktu x, takiego że /(x) < /(x*) + e, gdzie x* jest minimum globalnym. Załóżmy, że próbkujemy punkty rozmieszczone na równomiernej siatce prostokątnej. Jaki warunek powinna spełniać ta siatka i ile punktów należy próbkować, aby zagwarantować znalezienie minimum z założoną dokładnością?
2. Rozwiąż poprzednie zadanie, zakładając dodatkowo, że funkcja celu ma właściwość dekompozycji
i=l
i każda z funkcji fi(xi) spełnia warunek Lipschitza ze stałą Lj.
3. Zbadaj kształt zbioru punktów w R3
(v/x'f + 4 - 3)2 + (z3)2 < 1
Czy jest to zbiór spójny? Czy jest wypukły? Czy te właściwości nadal zachodzą dla zbiorów będących wynikiem przekroju płaszczyzną: a) x\ = 0, b) x\ = r, c) L3 = 0?
4. Rozważmy wypukłą funkcję f(x} w Rn. Z czego wynika, że nie jest ona wypukła w niewypukłym zbiorze D C Rnl Czy nie-wypukłość funkcji zawsze pociąga za sobą fakt istnienia więcej niż jednego minimum?
5. Rozważmy dwa kwadraty o następujących wierzchołkach:
tfi = {(-l,-l),(-l,l),(l,l),(l,-l)}, #2 = {(0,-l),(-l,0),(0,l),(l,0)} v oraz dwa zbiory:
.64.
1. W poszukiwaniu optimum...
trójkąt T = {(l/4,1/4), (1/4, 3/4), (3/4,1/4)} i kwadrat K3 = {(l/4,1/4),(3/4,1/4),(3/4,0), (1/4,0)}. Jakie będą obrazy tych figur w wyniku transformacji zbioru K% na zbiór K\ z punktem stałym (0,0)?
6. Czy liczba minimów lokalnych funkcji powstałej ze skalaryzacji zadania wielokryterialnego zależy od wybranej funkcji skalary-zującej?
7. Podaj miarę zbioru przyciągania minimum globalnego funkcji Ackleya dla dowolnej liczby wymiarów. Jak zmienia się wraz ze wzrostem liczby wymiarów stosunek miary tego zbioru do miary zbioru dopuszczalnego, jeśli 10 < Xi < 10 dla każdego n?
8. Jak zmienia się liczba minimów lokalnych w funkcji liczby wymiarów dla funkcji Griewanka?
9. Określ zbiór punktów niezdominowanych dla następujących zadań minimalizacji wielokryterialnej: , , j
(a) /i(x) = 5-
przy ograniczeniach -1 < xi < 1
-1 (b) /i(x) = sinxi + cosx2
/2(x) = COSX2 -
przy ograniczeniach
7T/2 < X\ < TT 0 < X2 < 7T
(c) /i(x) = l.lx1 -O.5o: /2(x) = Ą - O.4o^ -
(xa - l)2
0.8x3
przy ograniczeniach 0 < xi < 10 0 < x2 < 10 0 < x3 < 10