WYKŁAD 07

GRASP

CZasami w wyżarzaniu jeżeli zastosujemy losowość, to całkiem fajne wyniki nam wychodzą.
Można to wykorzystać.

Wyobraźmy sobie, że mmy algorytm zachłanny konstrukcyjny.
Komiwojażer budując prefiks bedąc w mieście wybiera to, do którego ma najbliżej. Ruch
zachłanny.

Załóżmy, że iteracyjnie tworzymy rozwiązanie danego problemu. W taki sposób, że z każdym
komponentem usatwiamy priorytet. I np ten który ma najniższy, to zostanie wybrany przez
komiwojażera.
Rozszeerzzamy rozwiązanie o nowy komponent. Wybór na podstawie priorytetu.

Algoryytmy statyczne - każdy komponent ma od początku stały priorytet
Dynamiczne - w momencie dołączenia komponentu przeliczamy rpiorytety kolejnych elementów.

My zakładamy, ze mamy zachłanny dynamiczny algorytm. Tutaj wybiera sie najniższy priorytet.
Wprowadzamy "zaburzenie". Czyli mamy priorytety":
k1, k2, ...kn

mamy stałą alfa, która mówi, że jak ułożymy priorytetami elementów, to będzie to decyzja
podejmowana nie zachłannie, ale losowo. Nie jest to algorytm deterministyczny. Odziedziczy
jednak dobre cechy od zachłannych algorytmów i dobrą cechę z wyżarzania.

Mamy taki algorytm. Jak go wykorzystać? mamy pętlę, która działa programie. Jak stwierdzamy,
że coś jest nie tak (nie znajdujemy lepszeo rozwiązania, to )) to zastanawiamy sioę, czy nie zmienić
tego alfa? Jeżeli alfa = liczności całego zbioru komponentół, to algorytm jest losowy. Alfa będzie
się zmianiać. W jaki sposób? do ustalenia przez nas.

Ideą takich metaheurystycznych jest zaproponowanie algorytmu, któ¶y działa dobrze dla
konkretnego problemu i konkretnych instancji. Bo nie musimy sprawdzać na wszystkich
instancjach problemu pisząc program do konkretnego zastosowania przemysłowego.

Pojawiło sie zagadnienie sąsiedztwa. Musieliśmy przeglądać w określony sposób sąsiedztwo. Jak
wydostać się z minimum lokalnego. Zaczęto sie zastanawiać. Dane minimum jest rozwiazaniem w
przypadku konkretneo otoczenia.

VNS

przeszukiwanie ze zmiennm sąsiedztwem. Definiujemy szerereg sąsiedztw, w którym pierwsze
sąsiedztwo jest mniej liczne od drugiego itd. Niby większa moc obliczeniowa może być potrzebna
dla większego sąsiedztwa, ale moze sie to opłacić.

Można też zmodyfikować funkcję celu. Że nasza funkcja, to prawdziwa funkcja celu + czynnik
szwiązany z oceną składowych rozwiązania. Np jeżeli jakaś krawędź znajduje sie na drodze
komiwojażera, to koszt jej jest dodawany do danej krawędzi. Można zatem często "wypłycać
otoczenie".

Wyobraźmy sobie, że mamy klasyczny algorytm zachłanny. Nasz alg konstruuje rozwiazanie przez

dodawanie kolejnych skłądowych rozwiązania w iteracji. Wyglada to tak, że jeżeli mamy dodać
komponent, to bierzemy taki o najniższym priorytecie. Weżmy permutację

1 5 3 2 4

i dodajemy komponent 6. Priorytet będzie wyliczasny w zależności od pozycji, na jaką tę 6
wstawimy. Algorytm wybierze już najlepszą uzyskaną wartość. Teraz założymy sobie, ze nie
wiemy jak dobierać priorytety. Nie potrafimy powiedzieć jak ocenić tyo, gdzie ma zostać 6 rzycona.

Czy mozemy przyjąć, że istnieje funkcja, która dla dodawanego komponentu dla każdej
możliwośćci wyliczy priorytet? Załóżmy, że istnieje. Więc może uda nm się stworzyć jakąś jej
aproksymację. JAk sprawdzić, czy ansza wymyślona funkcja jest dobra. Czy dla dowolnego
problemu da się skonsturować instancje, dla którego wiemy jakie bedzie rozwiązanie? Tak.

Np losujemy graf i ustawiamy, ze rozwiązanie minimalne ma 1. Wtedy jest łatwo. Można też
ustawiać sobie kwadrat. Orzeł - tniemy w poziomie, reszka w pionie. Potem losujemy 0 lub 1 i
wybieramy jedną z czesci. i rekurencja. Więc da sie stworzyć dowolnie dużą instancję..

Nasz algorytm jest fajny, ale nie potrafimy dla każdej instancji wybrać własciwego ruchu. Ale
mamy instancję, dla której mamy rozwiazanie idealne. Co więc mozemy zrobić?

Można użyć sieć neuronową (funkcja, która dostaje coś na wejściu, stroimy ją i tworzy wyjście, ale
trzeba poczytać.). JAk znaleźć naszą funkcję. Czy potrafimy wskazać reprezentację w przerstrzeni
rozwiazań, w której każde roziwązanie definiuje funkcję.

Ale nikt tego nie zrobił. Można to spróbować tak za pomocą sieci neuronowej.

Wejście to to rozwiazanie częściowe, wejście to komponent k, o który chcemy rozbudować
komponent, a wyjście to rozwiązanie najlepsze w sąsiedztwie. jest to czarna skrzynka. Trzeba
znaleźć funkcję, któ¶a znajdzie związek miedzy wejściem a wyjściem. Skąd wziąć przykłady
testowe dla naszej sieci? Mamy deterministyczny algorytm. Jeżeli sieć byłaby idealna, to algorytm
skończyłby z rozwiązaniem idealnym. Znając rozwiązanie próbujemy dopasować działanie.
Czy możemy stworzyć zbioór danych wyjściowych jako pożądaną wartość?

Dla uproszenia: robimy trzecie wejście - rozwiązanie z sąsiedztwa. A wynik bedzie zero-
jedynkowy. Sieć neuronowa nam odpowiada czy to co dostaniemy, to jest rozwiazaniem najlepszym
w sąsiedztwie. Mając rozwiązanie częściowe możemy stworzyć ciąg uczący. Jeżeli na wejście
podamy, że na danej pozycji znajdzie sie 6, to ma nam po drugiej stronie wyjść zero. itd. I mamy
pewien ciąg uczący. Mozna dać takie przypadki, dla których sieć ma zwrócić 0 lub 1. Dalej,.
Wyrzucamy 6, następna jest trójka. Usuwamy iją i sprawdzamy wszytskie możliwości gdzie
możemy wstawić trójkę. Można stworzyć nowy ciąg uczący tak jak poprzednio. Losując b. duzo
instancji, dla których znamy rzowiaanie możemy tworzyć sieć neuronową.

1 , 5 , 2 , 4 //3

Jeżeli wylosujemy dostatecznie duże ciągi uczące, to to nam przybliży bardzo dobrze funkcję i
algorytm. Wówczas możemy stosować to roziwązanie na nieznanych nam danych. I to działa tak, że
w 50% przypadków daje rozwiazanie optymalne a w 50% najgorsze;)Ale to też jest algorytm
heurystyczny ;) Wiedza oparta na doświadczeniach.

Teraz ten algorytm można budować w tabu search, rozbudowywać alfę aby to nie był o najniższym
priorytecie element, lub np losowy... itd ;)