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 ;)