Funkcja Kary

Programowanie nieliniowe

Programowaniem nieliniowym nazywamy zadanie o postaci:

gdzie przynajmniej jedna z funkcji f,g lub h nie jest funkcją liniową, przy czym zakłada się, że funkcje te są ciągłe.

W przeciwieństwie do programowania liniowego, gdzie uniwersalną metodą rozwiązywania jest algorytm simpleks nie ma ogólnej metody rozwiązywania programów nieliniowych. Metoda rozwiązywania zależy tu od postaci, jaką przyjmuje zadanie.
Przykładami zastosowań programowania nieliniowego są: wyznaczanie zysku ze sprzedaży, wyznaczanie awaryjnego poziomu zapasów lub wybór akcji do portfela.

Metoda Monte Carlo

Jest stosowana do modelowania matematycznego procesów zbyt złożonych (obliczania całek, łańcuchów procesów statystycznych), aby można było przewidzieć ich wyniki za pomocą podejścia analitycznego. Istotną rolę w metodzie MC odgrywa losowanie (wybór przypadkowy) wielkości charakteryzujących proces, przy czym losowanie dokonywane jest zgodnie z rozkładem, który musi być znany.

Przykład:

Metodą Monte Carlo można obliczyć pole figury zdefiniowanej nierównością:

czyli koła o promieniu R i środku w punkcie (0,0).

1. Losuje się n punktów z opisanego na tym kole kwadratu - dla koła o R = 1 współrzędne wierzchołków (-1,-1), (-1,1), (1,1), (1,-1).

2. Po wylosowaniu każdego z tych punktów trzeba sprawdzić, czy jego współrzędne spełniają powyższą nierówność (tj. czy punkt należy do koła).

Wynikiem losowania jest informacja, że z n wszystkich prób k było trafionych, zatem pole koła wynosi

gdzie P jest polem kwadratu opisanego na kole (Dla R = 1 : P = 4).

Dokładność wyniku uzyskanego tą metodą jest zależna od liczby sprawdzeń i jakości użytego generatora liczb pseudolosowych. Zwiększanie liczby prób nie zawsze zwiększa dokładność wyniku, ponieważ generator liczb pseudolosowych ma skończenie wiele liczb losowych w cyklu. Ta metoda całkowania jest używana w przypadkach, kiedy szybkość otrzymania wyniku jest ważniejsza od jego dokładności (np. obliczenia inżynierskie).

Metoda najszybszego spadku gradientu:

Gradient - w analizie matematycznej, a dokładniej rachunku wektorowym, pole wektorowe wskazujące kierunki najszybszych wzrostów wartości danego pola skalarnego w poszczególnych punktach

Na samym początku algorytmu wybierany jest punkt startowy
. W punkcie tym obliczany jest antygradient
funkcji celu, który będzie stanowił kierunek poszukiwań w procedurze. Następny punkt jest obliczany według wzoru:

jeśli obliczony punkt nie spełni warunku stopu algorytmu, całe postępowanie jest powtarzane.

Algorytm ogólnie można zapisać:

1. Wybierz punkt startowy
   

2. Dokonaj minimalizacji kierunkowej funkcji
   względem
   .

3. 
   

4. Sprawdź kryterium stopu, jeśli jest spełniony to STOP. W przeciwnym wypadku powtórz punkt 2.

Kryterium stopu

W celu określenia, czy punkt w danym kroku dostatecznie dobrze przybliża minimum funkcji celu w metodzie najszybszego spadku, można użyć następujących kryteriów stopu (dla zadanej precyzji
oraz normy
):

• 
  (test stacjonarności).

• 
  

Metoda speceru losowego:

Metoda tak zwanego „spaceru losowego” lub inaczej „spaceru pijaka” Technika ta polega na otrzymywaniu kolejnej wartości drogą dodania do poprzedniej niewielkiej liczby losowej, a więc wykonania przypadkowej długości kroku w przypadkowym kierunku.

Zagadnienie wielokryterialne

Występuje wówczas, jeżeli istnieje więcej niż jedna funkcja celu:

Qi(x) dla i = 1,2,…,m

W przeważającej liczbie przypadków nie istnieje taki wektor x w zbiorze rozwiązań dopuszczalnych X , który zapewniałby maksymalizację wszystkich funkcji celu Qi(x) równocześnie. Występują natomiast takie rozwiązania, które maksymalizują funkcje Qi(x) każde z osobna.

Pareto

Rozwiązanie xopt jest optymalne w sensie Pareto, jeżeli nie istnieje takie rozwiązanie x1, dla którego można zwiększyć wartość dowolnego z kryteriów Qi(xopt) bez równoczesnego zmniejszania wartości któregoś z pozostałych kryteriów.

Rozwiązanie uznaje się za optymalne w sensie Pareto, jeżeli nie można go polepszyć ze względu na żadne kryterium bez równoczesnego pogorszenia go ze względu na inne kryterium.

Algorytm min-max

Jest metodą w teorii decyzji do minimalizowania maksymalnych możliwych strat. Alternatywnie można je traktować jako maksymalizację minimalnego zysku (maximin).

Przykład

Kółko i krzyżyk

Prosta wersja algorytmu minimax, określona poniżej, dotyczy gier takich jak kółko i krzyżyk, gdzie każdy gracz może wygrać, przegrać lub zremisować. Jeśli gracz A może wygrać w jednym ruchu, jego najlepszym ruchem jest właśnie ten wygrywający ruch. Jeśli gracz B wie, że jeden ruch doprowadzi do sytuacji, gdzie gracz A może wygrać w jednym ruchu, podczas gdy inny ruch doprowadzi do sytuacji, gdzie gracz A może, w najlepszym wypadku zremisować, wtedy najlepszy ruch gracza B jest ruchem prowadzącym do remisu.

Później podczas gry łatwo zobaczyć, który ruch był najlepszy.

Algorytm Minimax pomaga znaleźć najlepszy ruch, pracując od końca gry. Na każdym kroku zakłada, że gracz A próbuje zmaksymalizować szanse na wygraną gracza A, podczas gdy w następnym ruchu gracz B stara się zminimalizować szanse na wygraną gracza A (tzn. zmaksymalizować swoje szanse wygrania).

Metoda Wagowa:

Kryterium zastępcze: Q(x) = Σ αi Qi(x)

αi - współczynniki wagowe dla odpowiednich kryteriów Qi(x)

Operacja ta sprowadza problem wielokryterialny do jednokryterialnego.

Jeżeli wyniki są zadowalające, to rozwiązanie można uznać za końcowe, jeżeli nie - to należy zmienić wartości współczynników wagowych i powtórzyć obliczenia.

Algorytm ewolucyjny.

Metody selekcji

Istnieje wiele metod selekcji. Dla przykładu można przedstawić tzw. metodę ruletki. Budujemy wirtualnie koło, którego wycinki odpowiadają poszczególnym osobnikom. Im lepszy osobnik, tym większy wycinek koła zajmuje. Rozmiar wycinków może zależeć od wartości funkcji oceny, jeśli wysoka wartość oceny oznacza wysokie przystosowanie. W takim układzie prawdopodobieństwo, że lepszy osobnik zostanie wybrany jako rodzic, jest większe. Niestety ewolucja przy takim algorytmie z każdym krokiem zwalnia. Jeżeli osobniki są podobne, to każdy dostaje równy wycinek koła fortuny i presja selekcyjna spada. Algorytm słabiej rozróżnia osobniki dobre od słabszych.

Krzyżowanie

Krzyżowanie polega na połączeniu niektórych (wybierane losowo) genotypów w jeden. Kojarzenie ma sprawić, że potomek dwóch osobników rodzicielskich ma zespół cech, który jest kombinacją ich cech (może się zdarzyć, że tych najlepszych).

Sposób krzyżowania jest zależny od kodowania chromosomów i specyfiki problemu. Jednak można wskazać kilka standardowych metod krzyżowania:

• rozcięcie dwóch chromosomów i stworzenie nowego poprzez sklejenie lewej części jednego rodzica z prawą częścią drugiego rodzica (dla chromosomów z kodowaniem binarnym i całkowitoliczbowym),

• stosowanie operacji logicznych (kodowanie binarne),

• obliczenie wartości średniej genów (kodowanie liczbami rzeczywistymi).

Mutacja

Mutacja wprowadza do genotypu losowe zmiany. Jej zadaniem jest wprowadzanie różnorodności w populacji, czyli zapobieganie (przynajmniej częściowe) przedwczesnej zbieżności algorytmu. Mutacja zachodzi z pewnym przyjętym prawdopodobieństwem - zazwyczaj rzędu 1%. Jest ono niskie, ponieważ zbyt silna mutacja przynosi efekt odwrotny do zamierzonego: zamiast subtelnie różnicować dobre rozwiązania - niszczy je. Stąd w procesie ewolucji mutacja ma znaczenie drugorzędne, szczególnie w przypadku długich chromosomów.

W przypadku chromosomów kodowanych binarnie losuje się zazwyczaj dwa geny i zamienia się je miejscami bądź np. neguje pewien wylosowany gen.

W przypadku genotypów zakodowanych liczbami całkowitymi stosuje się permutacje.

W przypadku genotypów zakodowanych liczbami rzeczywistymi wprowadza się do przypadkowych genów losowe zmiany o danym rozkładzie - najczęściej normalnym.

---