WYKŁAD 05: ALGORYTMY METAHEURYSTYCZNE

algorytm, który jest ponad podejściem związanym z rozwiązywanym podejściem. Strategia
przeszukiwania przestrzeni rozwiązań.

Stworzymy podstawowy schemat działania alg do przeszukiwania rozwiązań.

Startuje z rozwiązania i tworzymy jakąś trajektorie w przestrzeni stanów.
Ideałem byłoby, gdyby trajektoria trafiała do wyznaczonego celu.

Musimy wymyślić, jak przeszukać taką przestrzeń.

Wystartujemy z algorytmemm:

Startujemy z rozwiązania, zapamiętujemy jego wartość, śledzimy najlepszą znalezioną:

1. Wylosuj inne rozwiązanie i przejdź do niego i tyle iteracji ile mamy czasu.

Jeżeli się zastanowić, to jest on niegłupi. Jak można zdefiniować przestrzeń, aby statystycznie
alorytm znalazł rozwiązanie. Może on oczywiście znaleźć rozwiązań.

Problem kolekcjonowania kuponów to się nazywa.

Zakładamy, że rpzestrzeń jest nietrywialna, więc algorytm ma problemy ze znalezieniem
rozwiązania w sensownym czasie. po nlogn kroków mógłby znaleźć rozwiązanie. Więc lepiej
napisać algorytm sprawdzający wszystko. Musimy poprawić ten algorytm.

Wadą jest to, że on próbkuje różne elementy rozwiązań i są one bliskie rozwiązaniu. Można
spróbować zmienić ideę na taką, która dokonuje intensyfikacji poszukiwań. Gdy jesteśmy blisko
znalezienia rozwiązania można wprowadzić intensyfikację. Czyli przejrzeć otoczenie ostatnio
trafionego rozwiązania.

N(s): s należy do S

N: S -> 2^S
N(s) zawiera się w S.

Czyli mamy wektor zer i jedynek. Otoczenie definiuje podzbiór przestrzeni S. I mamy
przyporządkowanie otoczenie. W praktyce mamy algorytm, który mając zadanie stworzy otoczenie
rozwiązania.

Weźmy permutację

1 3 2 5 6 8 4

Jak zdefiniować otoczenie?
Np.

Wybieramy sobie (problem komiwojażera) jakieś miasto. Przez fragment otoczenie rozumiemy to,
że dane miasto zmieniamy jego położenie. Dla każdego obiektu permutacji wyznaczamy wszystkie
zadania, w której zmieniamy pozycję obiektu.
Wykonujemy np wszystkie możliwe permutacje, ale ponieważ tworzymy alg metaheurystyczny, to

dla na s to wygląda tak, że przestawiamy np to miasto, które generuje maksymalną wagę krawędzi
do wszystkich miast. W pewnym momencie będziemy zwracać na tpo uwagę, bo to robi różnicę
przy złożoności algorytmu.

010110101

Otoczenie można sprawdzać tak, że zmieniamy zera na jedynki itd.

Otoczenie będzie generowane przez wykonaniezbioru ruchów od rozwiązania początkowego.
Można też pozamieniać wszystkie sąsiednie.

Można wybrać dwa obiekty i zamienić je ze sobą.

1 3 2 5 6 8 4
1 8 2 5 6 3 4

Później się zastanowimi nad przykładami i optymalizacją.

Jak mamy zdefiniowane otoczenie, to można pomyleć o czymś takim, że:
Startujemy od s(0) i mając rozwiązanie bazowe sprawdzamy otoczenie rozwiązania i algorytm
wybiera kolejne rozwiązania bazowe. Z s(0) do s(1) i w jego otoczeniu do s(2) itd. Chcemy, aby po
kilku rozwiązaniach znalazł się w pewnym miejscu optymalnym, to musimy to jakoś
zaprojektować.

My z otoczenia jako najlepsze rozwiązanie wybieramy najlepsze z sąsiedztwa. W końcu zajdziemy
do ozwiązania optymalnego. Gdy nie będzie rozwiązania lepszego, to się zatrzymujemy.

Wybór lepszego można definiować różnie:

interesuje nas rozwiązanie najlepsze w sąsiedztwie kosztem przeszukania całego sąsiedztwa, co
może być kosztowne. Znalezienie najlepszego może być problematyczne.
Można jako nowe rozwiązanie bazowe to pierwsze napotkane niż to, z którego zaczniemy. Ale
mimo to jest to droga w dobrym kierunku.

Teraz pojawiają sie 2 problemy:
1. Mimo wszystko czas przeszukiwania jest duży, więc coś trzeba z tym zrobić.
2. Algorytm utyka w minimach lokalnych, bo nie wiadomo czy to co znajdziemy to optimum
globalne.

Aby szybko działało, to mamy usprawnienie: ten ruch będziemy chcieli wygenerować w czasie
O(1). Czyli mamy sąsiedztwo. Najprościej: losowo.
NP:

1 3 2 5 6 8 4
1 3 5 6 2 8 4

Trajektoria załóżmy, że będzie spójna.
Ucieczka z optimum lokalnego.
pozwólmy mu działać dalej. Na przykład niech on działa np 3mln razy. Może akurat mu się uda
wskoczyć gdzie indziej.
Ale przez losowość może też uciec z minimum.

<rysunek>

Najprościej:
Jeżeli dane rozwiązanie jest lepsze, to bezwzględnie do niego przechodzimy. Musimy podjąc
decyzję, czy przechodzimy do gorszego rozwiązania, czy szukamy dalej w tamtym optymalnym
otoczeniu. Najłatwiej: rzucamy monetą. Jeżeli przeprowadzić badania, to algorytm ten całkiem
rozsądnie daje radę. Musi ten algorytm jednak umieć wrócić do optymalnego lokalnego opimum.

Algorytm przypomina coś, co jest znane z metalurgii - proces termodynamiczny.
Bieżemy słoik z kamieniami. Chcemy, aby jak najmniej miejsca w słoiku zajmiemy. Może być tak,
że trzęsiemy słoikiem i randomowo same się dobrze ustawi.

Wyżażanie jest dobrym przykładem tego rozwiązania.

CZego oczekujemy od naszwego algorytmu?

Z jednej strony chcemy, aby każdy z obszarów był przeszukiwany/.

Intensyfikacja poszukiwania i ekstensyfikacja poszukiwania. Właściwie nic z tych rzeczy nie robi
nasz algorytm.

Kiedy algorytm przeszukuje różne fragmenty przestrzeni? Jesli prawdopodobieństwo zagęszczenia
ruchu jest duże.

Wprowadzić zmienne akceptacji pogarszania rozwiązania.

<rysunek 2>

Mamy monetę, która zmienia prawd tego, że wypadnie orzeł. Jak się przyjrzymy takim funkcjom,
to możemy różnie to rozwiązywać.Każde stworzenie takiej funkcji, to lagorytm metaheurystyczny,
który możemy nazwać swoim nazwiskiem:D

W symulowanym wyżażaniu.

pa (prawdopodobieństwo akceptacji)

<wzór>

Pojawia się pytanie: jak ta temperatura ma się zmieniać, aby schemat był porównywalny z
optymalnym?

<wzór 2>

Kiedy ten warunek spełniony?
Jeżeli :

<wazórn 3?>