1. Wyjaśnienie pojęcia optymalizacja. Omówienie procesu optymalizacji. Podstawowe pojęcia i definicje. Podział zadań optymalizacji.

Optymalizacja jest to dziedzina nauki zajmująca się wyznaczaniem spośród wszystkich dopuszczalnych rozwiązań danego problemu optymalizacyjnego rozwiązania najlepszego, z określonego punktu widzenia. Wybór najlepszego rozwiązania zależy od celu i wymagań określonych w matematycznym sformułowaniu problemu.

Proces optymalizacji

- sformułowanie matematyczne postawionego problemu

- rozstrzygnięcie możliwości istnienia rozwiązania

- zbadanie własności zadania i na tej podstawie dobranie algorytmu rozwiązania

- interpretacja wyników obliczeń

Pojęcia:

Zadanie z ograniczeniami – jest to zadanie którego rozwiązanie musi spełniać pewne ściśle określone warunki (ograniczenia mogą być równościowe lub nierównościowe)

Zadanie programowania całkowitoliczbowego lub dyskretnego to zadanie w których występuje konieczność zachowania całkowitych wartości wektora x.

Zadanie (problem) optymalizacji – w sensie matematycznym jest to proces poszukiwania ekstremum pewnej funkcji, będącej matematycznym opisem badanych zjawisk, nazywaną funkcją celu, kryterium, bądź wskaźnikiem jakości. W większości zagadnień technicznych jest to funkcja wielu zmiennych, które nazywamy zmiennymi decyzyjnymi.

Podział zadań optymalizacji:

1. Zadania Programowania Liniowego. Metoda graficzna. Metoda Sympleks. Teoria dualności. 

Zadanie programowania liniowego (ZPL) jest to zadanie w którym definiująca je funkcja celu i ograniczenia są funkcjami liniowymi.

p.o.Ax = b ∖ nx ≥ 0,  m ≤ n

x – macierz kolumnowa zmiennych decyzyjnych

b – macierz kolumnowa prawych stron ograniczeń

c – macierz kolumnowa zawierająca współczynniki zwane cenami lub kosztami.

Metoda graficzna

Metoda graficzna to metoda rozwiązania ZPL polegająca na wyznaczeniu wierzchołków wielościanu wypukłego, tworzącego obszar możliwych rozwiązań Ω, a następnie wyznaczeniu wartości funkcji celu w tych wierzchołkach i wybraniu najlepszego rozwiązania.

Metoda sympleks

Metoda sympleks polega na przeszukiwaniu wierzchołków obszaru rozwiązań dopuszczalnych Ω w sposób uporządkowany, poprzez generowanie ciągu dopuszczalnych rozwiązań bazowych {x¹ , x² , … , x^k}, odpowiadających tym wierzchołkom, takich, aby kolejne rozwiązania były lepsze (lub przynajmniej nie gorsze) od poprzednich. Proces ten trwa tak długo, aż osiągnięte zostanie rozwiązanie optymalne. A zatem metoda sympleks jest metodą iteracyjną. W każdej z iteracji wyznacza się rozwiązanie bazowe a następnie sprawdza czy jest ono optymalne. Jeśli aktualne rozwiązanie bazowe jest rozwiązaniem optymalnym wówczas następuje zakończenie procesu optymalizacji. Wyniki poszczególnych iteracji zestawia się w kolejnych tablicach sympleksowych o wymiarach (m+l)x (n+1), gdzie m- liczba ograniczeń, n - liczba zmiennych decyzyjnych [1, 2, 3. 4. 5, 6],

Teoria dualności

Twierdzenie o dualności. Jeśli zadanie pierwotne ZPL (bądź dualne) ma skończone rozwiązanie optymalne, to odpowiadające mu zadanie dualne ZPL (bądź pierwotne) również posiada skończone rozwiązanie optymalne a optima funkcji celu są sobie równe. tj. $_{x}^{\min}{f(x)} =_{\lambda}^{\max}{f'(\lambda)}$

1. Zadania Programowania Nieliniowego bez ograniczeń. Metody poszukiwania prostych. Metoda Najszybszego Spadku. 

Metody poszukiwania prostych (metoda Gaussa-Seidla, Hooka-Jeevesa, Rosenbrocka, metoda sympleksu Neldera-Meada)

Metoda Hooka Jeevesa

W metodzie Hooka Jeevesa w każdym kroku iteracyjnym występują dwa rodzaje ruchów, a mianowicie ruch próbny i ruch roboczy. Ruch próbny służy do badania przebiegu funkcji celu w niewielkim obszarze, wokół punktu startowego, wyznaczanym za pomocą parametru omawianej metody, jakim jest długość kroku. Badanie to polega na wykonywaniu kroków próbnych wzdłuż n-kierunków ortogonalnej bazy (gdzie n - oznacza liczbę zmiennych decyzyjnych) i sprawdzeniu wartości funkcji celu w wyznaczonych punktach. Następnie wykonuje się krok roboczy, którego wektor odpowiada sumie geometrycznej wszystkich pomyślnych kroków próbnych. Krokiem pomyślnym nazywany jest krok, w wyniku którego następuje zmniejszenie wartości funkcji celu [3, 6], Inaczej mówiąc krok roboczy polega na przejściu, w sposób ściśle zdeterminowany, do kolejnego obszaru badania przebiegu funkcji celu. W nowo wyznaczonym obszarze powtarza się kroki próbne, ale tylko w sytuacji, gdy przynajmniej jeden z kroków próbnych, wykonanych w poprzedniej iteracji, był pomyślny. W przeciwnym razie pozostaje się w poprzednio badanym obszarze i cykl poszukiwania rozpoczyna od nowa zmniejszając długość kroku.

Jako kryterium zatrzymania w metodzie Hooka Jeevesa przyjmuje się warunek, że aktualna długość kroku a jest mniejsza od założonej liczby e, określającej wymaganą dokładność obliczeń.

Metoda Rosenbrocka

Metoda Rosenbrocka jest metodą podobną do metody omawianej poprzednio. Jednak w metodzie tej kierunki poszukiwań nie pozostają stałe, ale w niektórych przypadkach ulegają zmianom w wyniku obrotu. Dlatego to metoda ta często nazywana jest metodą obrotu układu współrzędnych. W metodzie Rosenbrocka ruchy próbne tworzą cykle, a te z kolei tworzą etapy. Cykl tworzą ruchy próbne wykonane w ustalonych kierunkach, przy czym kierunki początkowe są zgodne z kierunkami kartezjańskiego układu współrzędnych [3].

Na wstępie w każdym z kierunków kartezjańskiego układu współrzędnych wykonuje się kolejno po jednym kroku o długości α. Jeśli ruch próbny prowadzi do zmniejszenia wartości funkcji celu, to mówi się o sukcesie. Jeśli nic, to mówi się o porażce. W przypadku sukcesu w następnym cyklu długość kroku a w danym kierunku mnoży się przez γ (gdzie γ to współczynnik korekcyjny zwiększający długość kroku a; γ>l), a w przypadku porażki długość kroku a mnoży się przez β (gdzie β to współczynnik korekcyjny zmniejszający długość kroku a; 0<β<1). Etap składa się z ilości cyklów niezbędnych do uzyskania w każdym kierunku przynajmniej jednego sukcesu i jednej porażki. Następny etap rozpoczyna się od określenia nowego zbioru ortogonalnych kierunków, przy czym pierwszy kierunek jest wyznaczany przez punkt początkowy i punkt końcowy poprzedniego etapu. Pozostałe kierunki są wyznaczane za pomocą algorytmu obrotu współrzędnych. W metodzie Rosenbrocka stosuje się następujące kryteria zatrzymania:

• z góry narzuconą ilości iteracji;

• z góry założoną wielkość różnicy pomiędzy punktem początkowym a końcowym.

Metoda Powella

Metoda Powella polega na poszukiwaniu minimum funkcji celu poprzez przeszukiwanie przestrzeni n - wymiarowej w kolejnych iteracjach, wzdłuż n wyznaczonych kierunków, stanowiących bazę tej przestrzeni, gdzie n oznacza liczbę zmiennych decyzyjnych. Na zakończenie każdej iteracji dokonywana jest minimalizacja wzdłuż nowo wyznaczonego (n+l)-go kierunku poszukiwań.

W przeciwieństwie do poprzednio omawianych metod, w metodzie Powella kierunki poszukiwań są ze sobą powiązane, bowiem w każdej następnej iteracji do zbioru kierunków poszukiwań dodawany jest nowo wyznaczany kierunek dⁿ⁺¹ , wyznaczany ze wzoru [4]:$d^{n + 1} = \frac{x^{n} - x^{0}}{\left\| x^{n} - x^{0} \right\|}$,a usuwanu jest kierunek d¹. W tej metodzie jako kryterium zatrzymania wykorzystuje się warunek: ∥x_n + 1^k−x₀^k∥ ≤ ε

x₀^k −  przyjety punkt bazowy k − tej iteracji

x_n + 1^k − punkt dla ktorego funkcja celu osiaga najmniejsza wartosc wzdluz n + 1 kierunku w iteracji k − tej ∖ n

Metoda Najszybszego Spadku.

Jest to najprostsza metoda oparta na modelu liniowym minimalizowanej funkcji, jako kierunek wybiera się: d^(k) = −∇f(x^(k)). Punkt x^(k+1) znajdujemy z zależności: x^(k+1) = x^(k) + α^* • d^(k)

W metodzie najszybszego spadku wartość α_k^* wybierana jest tak, aby funkcja f(x) osiągała w punkcie x^(k) + 1 minimum w kierunku: d^(k) = −∇f(x^(k))

1. Zadania Programowania Nieliniowego bez ograniczeń. Metoda Newtona i jej modyfikacja. Metody quasi-newtonowskie.

Metoda Newtona i jej modyfikacja

W metodzie Newtona zakłada się, że funkcja celu f(x^k), która jest ściśle wypukła w dół, posiada ciągłe pochodne cząstkowe do drugiego rzędu włącznie. Wówczas przy założeniu, iż punkt x^k jest pewnym przybliżeniem poszukiwanej wartości minimalnej x^* funkcji celu f(x) oraz znając wartości gradientu ∇f(x^k) i hesjanu H(x^k) funkcji celu w tym punkcie, można na podstawie szeregu Taylora funkcję celu f(x) aproksymować w otoczeniu punktu x^k funkcją kwadratową F_k(x), opisaną następująco:

$$F_{k}\left( x \right) = f\left( x^{k} \right) + \nabla f\left( x^{k} \right) \bullet \left( x - x^{k} \right) + \frac{1}{2} \bullet \left\lbrack H\left( x^{k} \right) \bullet {(x - x^{k})}^{2} \right\rbrack$$

gdzie:

x - minimum funkcji kwadratowej F_k(x) aproksymującej funkcję celu f(x) w punkcie x^k;

∇f(x^k)− gradient funkcji celu /(x) w punkcie x*;

H(x^k)− macierz hesjanu funkcji celu f(x) w punkcie x^k

Zakładając, iż kolejnym przybliżeniem poszukiwanej wartości minimalnej x^* funkcji celu f(x) jest punkt x^k+1, będący punktem minimum funkcji kwadratowej F_k(x), a więc spełniający warunek:

∇F(x^k + 1) = ∇f(x^k) − H(x^k) • (x^k + 1−x^k) = 0

uzyska się wzór na wyznaczanie wartości przybliżeń x^k+1 poszukiwanego minimum x^* funkcji celu f(x) w kolejnych iteracjach [4, 8]:

x^k + 1 = x^k − H(x^k)⁻¹ • ∇f(x^k)

Kryterium zatrzymania w metodzie Newtona przyjmuje postać:

∥x^k + 1−x^k∥ ≤ ε

gdzie ε jest przyjętą żądaną dokładnością obliczeń, a ||.|| oznacza normę euklidesową wektora.

Metody quasi-newtonowskie

W zadaniach praktycznych metoda Newtona nie znajduje szerokiego zastosowania ze względu na jej małą efektywność i trudności obliczeniowe związane z koniecznością wyznaczania w każdej iteracji macierzy drugich pochodnych (hesjan H(x^k )) oraz obliczania macierzy odwrotnej do macierzy hesjanu H(x^k)^-1 i mnożenia jej przez wektor gradientu∇f(x^k) (H(x^k)⁻¹ • ∇f(x^k)). W metodach quasi - newtonowskich, zwanych również metodami zmiennej metryki, powyższe niedogodności eliminuje się zastępując bądź to macierz hesjanu H(x^k), bądź to macierz do niego odwrotną H(x^k)^-1 odpowiednimi przybliżeniami. Różnice występujące pomiędzy poszczególnymi metodami zmiennej metryki polegają jedynie narożnym sposobie konstruowania uaktualnienia macierzy D^k+1, będącej aproksymacją odwrotności macierzy hesjanu H(x^k)^-1 bądź konstruowania uaktualnienia macierzy B^k+1. będącej aproksymacją macierzy hesjanu H(x^k)

Główną zaletą metod quasi newtonowskich jest wykorzystywanie informacji wyłącznie o wartości gradientu funkcji celu ∇f(x^k) w aktualnym punkcie poszukiwań x^k oraz kolejnym po nim następującym x^k+1.

Do grupy metod zmiennej metryki zalicza się m.in.: metodę Davidona (w skrócie D), metodę Pearsona (w skrócie P), metodę Wolfe'a-Broydena-Davidona (w skrócie WBD), metodę Davidona-Fletchera-Powella (w skrócie DFP), metodę Broydena-Fletchera- Goldfarba-Shanno (w skrócie BFGS).

1. Zadania Programowania Nieliniowego z ograniczeniami. Metody Funkcji Kary. Metoda Mnożników Lagrange’a.

Metoda mnożników Lagrange’a, stosowana do rozwiązywania zadań programowania nieliniowego z ograniczeniami, polega na wprowadzeniu do postaci funkcji celu f(x) dodatkowych mnożników, zależnych od typu ograniczeń nałożonych na funkcję celu. Polega ona na wyznaczeniu pary $\left( \hat{x},\bigwedge \right)$, gdzie ⋀ ≡ (λ,μ) stanowiącej punkt siodłowy funkcji Lagrange’a, tj. punktu w którym funkcja ta osiąga minimum względem x i maksimum względem ⋀, przy μ>0.

Zaletą metody mnożników Lagrange'a jest możliwość dokonywania w dość łatwy i w miarę szybki sposób obliczeń analitycznych oraz możliwość dostosowania wprowadzanych modyfikacji w zależności od typu ograniczeń występujących w zadaniu, co pozwala na uzyskiwanie dokładnych wyników.

1. Zadania Programowania Nieliniowego z ograniczeniami. Metody Funkcji Kary. Metoda Transformacji Zmiennych.

Metodę transformacji zmiennych decyzyjnych można stosować tylko w przypadku, gdy pewne zmienne decyzyjne (czasami wszystkie) są ograniczone z dołu i z góry przez stałe wartości liczbowe, co zapisano zależnościami.

W metodzie zamiany (transformacji) zmiennych przyjmuje się, iż zmienna decyzyjna x_n jest zastępowana przez nową zmienną:x_n ≡ γ_n(u_n)

która może przyjmować dowolne wartości z zakresu:

u_n ∈ ( − ∞, +∞)

W zależności od rodzaju ograniczeń nałożonych na poszczególne zmienne decyzyjne stosuje się odpowiednie podstawienia.

Następnie do funkcji celu f(x) w miejsce poszczególnych zmiennych decyzyjnych x_n. podstawia się wartość wyrażoną zależnością x_n ≡ γ_n(u_n). W ten sposób otrzymywane jest zadanie optymalizacyjne bez ograniczeń równoważne zadaniu z ograniczeniami.

Należy jednak podkreślić, że funkcje γ_n(u_n) muszą być takie, aby w nowo utworzonej funkcji kryterialnej F(u)=f[γ₁(u₁), …, γ_n(u_n)] nie pojawiły się nowe ekstrema lokalne.

Metoda polegająca na transformacji zmiennych decyzyjnych jest metodą mało efektywną ponieważ zmodyfikowana funkcja kryterialna na ogół staje się bardzo złożona.

1. Algorytmy genetyczne. Optymalizacja wielokryterialna.

Algorytmy genetyczne to algorytmy oparte na naśladowaniu natury, bowiem ewolucja naturalna jest swoistym procesem optymalizacyjnym. Sposób działania algorytmów genetycznych nieprzypadkowo przypomina zjawisko ewolucji biologicznej i doboru naturalnego bowiem ich twórca, John Holland, opierając się właśnie na teorii Darwina stworzył algorytmy genetyczne. Według darwinowskiej teorii walki o życie z wielu osobników żyjących w danym środowisku przeżyją ci, którzy posiadają cechy czyniące ich najlepiej przystosowanymi do środowiska. Oni to mają większe szanse na przeżycie i szybciej rozmnażają się powodując dalsze rozpowszechnianie się ich cech. Osobniki słabsze, tzn. gorzej przystosowane, zostają wyparte przez inne i giną. A zatem natura również poszukuje rozwiązania optymalnego

Dodatkowo w algorytmach genetycznych występuje zrandomizowana wymiana informacji, konieczna do otrzymania najlepszych wyników optymalizacji.

Schemat algorytmu genetycznego i jego podstawowe operacje

Na klasyczny algorytm genetyczny, choć całkiem wystarczający dla wielu praktycznych zagadnień, nazywany także elementarnym lub prostym algorytmem genetycznym, składają się następujące kroki:

- Inicjacja czyli wybór populacji początkowej;

- Ocena przystosowania osobników;

- Sprawdzenie warunku zatrzymania;
- Selekcja osobników;
- Zastosowanie operatorów genetycznych;
- Utworzenie populacji potomnej;
- Wynik w postaci „najlepszego" osobnika.

Inicjacja, czyli utworzenie populacji początkowej, polega na wyborze żądanej liczby chromosomów (osobników) reprezentowanych przez ciągi binarne określonej długości.

Selekcja polega na wybraniu, na podstawie obliczonych wartości funkcji przystosowania, osobników przeznaczonych do reprodukcji. Najczęściej stosowaną metodą selekcji jest metoda ruletki. Metoda ta dokładnie zostanie omówiona w części praktycznej.

Reprodukcja jest procesem, w którym osobnik jest kopiowany bez zmian do następnego pokolenia w stosunku zależnym od wartości jego przystosowania do środowiska. Osobniki o wyższym przystosowaniu posiadają większe prawdopodobieństwo wprowadzenia jednego lub więcej potomków do następnego pokolenia.

Krzyżowanie odpowiada rozmnażaniu płciowemu, gdyż polega na wymianie części materiału genetycznego między parą osobników. Operacja ta przebiega w dwóch etapach. W pierwszym etapie losowo wybiera się pary rodzicielskie. Następnie każda z par ulega krzyżowaniu.

Mutacja polega na zachodzącej z niewielkim prawdopodobieństwem zamianie losowo wybranego pojedynczego bitu w chromosomie i skopiowaniu tak zmienionego osobnika do następnej populacji. Operacja ta zapobiega ewentualnej utracie interesującego materiału genetycznego, względnie pozwala na pojawienie się nowego.