Heurystyki przeszukiwania lokalnego
Sławomir Góra
Instytut Informatyki Uniwersytetu Wrocławskiego
Wrocław, 26 marca 2009
Sławomir Góra
Algorytm pełnego przeglądu
skończony zbiór rozwiązań
najprostsza koncepcja – sprawdzić wszystkie możliwe rozwiązania
generator + ewaluator
czas liniowy... ale względem liczby rozwiązań
Sławomir Góra
Liczba rozwiązań
Silnia
Zakładając, że potrafimy sprawdzić miliard rozwiązań na sekundę,
sprawdzenie 20! rozwiązań zajęłoby ok. 77 lat.
Komiwojażer
Liczba rozwiązań dopuszczalnych w problemie komiwojażera wynosi
n!
2
.
Praktyczne przykłady problemów komiwojażera:
zagadnienie z krystalografii rentgenowskiej – 14000 miast
wiercenie otworów w płytkach drukowanych – 17000 miast
projektowanie układów VSLI – około miliona miast
Sławomir Góra
Liczba rozwiązań c.d.
Problem
Ogólny (niepermutacyjny) problem przepływowy, liczba możliwych
rozwiązań – (n!)
m
Fisher, 1973
W 1973 roku Fisher podał przykład danych n = 10, m = 10 (ft10), czyli
przestrzeń rozwiązań równa (10!)
10
≈ 4 · 10
65
.
Rozwiązanie optymalne opublikowano po 25 latach.
Sławomir Góra
Definicje
Heurystyka
Heurystyka (gr. heuresis — odnaleźć, odkryć, heureka — znaleźć) –
w informatyce metoda znajdowania rozwiązań, dla której nie ma gwarancji
znalezienia rozwiązania optymalnego, a często nawet prawidłowego.
Intuicja
Nie jesteśmy w stanie przejrzeć całej przestrzeni rozwiązań, więc
zastosujmy jakąś praktyczną, „inteligentną”, opartą na doświadczeniu
bądź obserwacjach regułę postępowania, która skróci proces odkrycia
najlepszego lub przynajmniej zadowalającego nas rozwiązania.
Sławomir Góra
Definicje c.d.
Metaheurystyka
Metaheurystyka – heurystyka „nadrzędna”, sterująca w procesie
iteracyjnego przeszukiwania heurystykami niższego rzędu.
Sławomir Góra
Heurystyki przeszukiwania przestrzeni rozwiązań
zaburzeniowe i konstruktywne
systematyczne i lokalne
samotnego poszukiwacza i populacyjne
deterministyczne i losowe
Sławomir Góra
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy
Proste przeszukiwanie lokalne
Wybierz rozwiązanie początkowe x i określ jego jakość.
Przyjmij x za najlepsze dotychczasowe rozwiązanie: x* = x.
do {
Wygeneruj zbiór rozwiązań z sąsiedztwa x.
Wybierz x’ - najlepsze z wygenerowanego zbioru.
Przypisz x’ jako rozwiązanie bieżące: x = x’.
Jeśli jakość x jest wyższa od jakości x*: x* = x.
}
while (warunek_stopu_algorytmu)
Sławomir Góra
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy
Etapy przeszukiwania lokalnego
określanie rozwiązania początkowego – wiedza od eksperta lub
losowo
generowanie sąsiedztwa – ochrona przed cyklami
wybór bieżącego rozwiązania – funkcja kosztu
warunek końca algorytmu – kryterium akceptacji
Sławomir Góra
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy
Różne rodzaje sąsiedztw
wektory 0-1: zmiana pojedynczej współrzędnej
permutacje: operacje swap (transpozycje, inwolucje), insert
grafy: wymiana krawędzi
Sławomir Góra
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy
Metody ograniczania otoczeń
kryteria eliminacyjne, np. częściowy porządek na zbiorze elementów
bloki – podciągi elementów, w których zmiana kolejności nie
poprawia wartości funkcji celu
reprezentanci ruchów – pewne ruchy „lepsze” od innych
Sławomir Góra
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy
Dwa ważne terminy
Eksploracja
Eksploracja przestrzeni rozwiązań mówi o jak „najszerszym” przeszukaniu
zbioru wszystkich rozwiązań w sensie sąsiedztwa, czyli jak daleko
odchodzimy od rozwiązania początkowego i w jak wielu kierunkach.
Szeroka eksploracja zmniejsza ryzyko „wpadania” w minima lokalne, ale
wiąże się z mniej dokładnym badaniem poszczególnych obszarów.
Eksploatacja
Eksploatacja, czy też intensyfikacja przeszukiwania określa dokładność
badania konkretnego obszaru przestrzeni rozwiązań, czyli np. jak wiele
elementów sąsiedztwa danego elementu bierzemy pod uwagę przy
wyborze najlepszego. Mocna intensyfikacja zwiększa prawdopodobieństwo
znalezienia optymalnego rozwiązania, ale tylko jeśli znajdziemy się
odpowiednio „blisko” niego.
Sławomir Góra
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy
Funkcja kosztu
Standardowe funkcje kosztu
Do obliczania jakości danego rozwiązania używa się funkcji kosztu –
charakterystycznej dla problemu, np. dla problemu szeregowania zadań
będzie to termin zakończenia ostatniego zadania.
Optymalizacje
Częste obliczanie funkcji kosztu może negatywnie wpłynąć na złożoność.
W trakcie przeszukiwania sąsiedztwa często lepszym pomysłem, niż
sprawdzanie wartości funkcji kosztu dla każdego elementu jest
porównanie kosztu dwóch sąsiednich elementów.
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy
Strategie wielostartu
Wielostart (multi–start)
W przypadku problemów z dużą ilością minimów lokalnych, jeśli
zauważymy, że mimo upływu kolejnych iteracji nie poprawiamy
rozwiązania, to zaczynamy od nowa z losowym rozwiązaniem.
Wielostart ze zmodyfikowanego bieżącego rozwiązania (kick–start)
Jak wyżej, ale zaczynamy od nowa ze zmodyfikowanym rozwiązaniem.
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy
Schemat
Wybierz rozwiązanie początkowe x i określ jego jakość.
poprzednie_najlepsze = {}
x* = algorytm_przeszukiwania_lokalnego(x)
do {
x’ = perturbacja(x*, poprzednie_najlepsze)
x*’ = algorytm_przeszukiwania_lokalnego(x’)
x* = wybierz_najlepszy(x*, x*’, poprzednie_najlepsze)
}
while (warunek_stopu_algorytmu)
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy
Funkcja perturbacji
nowy x* – dla kolejnego uruchomienia algorytmu
średnie zaburzenie – nie za słabe, nie za mocne
dopełnienie algorytmu
wykorzystanie poprzednich rozwiązań do określenia siły perturbacji
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy
Funkcja wybierz najlepszy
wykorzystanie poprzednich rozwiązań
unikanie zapętlania i minimów lokalnych
wybór niekoniecznie lepszego rozwiązania
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy
Podsumowanie iteracyjnego przeszukiwania lokalnego
wybór początkowego rozwiązania nie powinien wpływać na jakość
kolenych wyników
przeszukiwanie powinno być dopasowane do problemu
przeszukiwanie lokalne, perturbacja i wybór najlepszego elementu z
sąsiedztwa powinny „współpracować”
zwłaszcza te dwa ostatnie
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Schemat
Wybierz rozwiązanie początkowe x i określ jego jakość.
k = 1
do {
Wygeneruj x’ z k-tego sąsiedztwa x.
if (jakość x’ jest wyższa od jakości x)
x = x’
k = 1
else
k = k + 1
}
while (k < k_max)
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Przeszukiwanie ze zmiennym sąsiedztwem
Idea
Przyjmujemy, że dla dowolnego punktu x z przestrzeni rozwiązań istnieje
zbiór sąsiedztw N
1
(x ), ..., N
k
max
(x ) takich, że każde poprzednie jest
podzbiorem następnego. Dzięki temu możemy rozszerzać krąg
poszukiwań w kolejnych krokach, jeśli nie znajdujemy lepszego
rozwiązania w obecnym sąsiedztwie.
Metaheurystyczne zastosowanie
Przedstawiony schemat stanowi punkt wyjścia do pełnego algorytmu
przeszukiwania ze zmiennym sąsiedztwem, gdzie wykorzystuje się dwa
zbiory sąsiedztw.
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Schemat
Wybierz rozwiązanie początkowe x i określ jego jakość.
l = 1
do {
Wygeneruj x’ z l-tego sąsiedztwa x.
przeszukaj_k_te_sasiedztwa(x’)
if (jakość x’ jest wyższa od jakości x)
x = x’
l = 1
else
l = l + 1
}
while (l < l_max)
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Pełne przeszukiwanie ze zmiennym sąsiedztwem
Idea
Pamiętamy, że N
1
(x ) ⊂ N
2
(x ) ⊂ ... ⊂ N
k
max
dla dowolnego x, gdzie N
k
max
stanowi całą przestrzeń rozwiązań. Zastosowanie dwóch zbiorów sąsiedztw
daje możliwość sprawdzania najbliższego sąsiedztwa kolejnych elementów,
nawet po przejście do sąsiedztw wyższego rzędu w pętli zewnętrznej.
Problem
Jeśli optima lokalne nie tworzą skupień, powyższy algorytm zbytnio
intensyfikuje przeszukiwania w jednym miejscu. W tego typu problemach
lepsze jest tzw. skrzywione przeszukiwanie ze zmiennym sąsiedztwem.
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Skrzywione przeszukiwanie ze zmiennym sąsiedztwem
rozluźnienie kryterium akceptacji:
F (x
00
) = f (x
00
) − α · distance(x , x
00
)
możliwe bardziej złożone wzory
przeglądanie odleglejszych regionów
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Schemat
Wybierz rozwiązanie początkowe x i określ jego jakość.
x_opt = x; f_opt = f(x_opt); l = 1
do {
Wygeneruj x’ z l-tego sąsiedztwa x.
x’’ = przeszukaj_k_te_sasiedztwa(x’)
if (jakość x’’ jest wyższa od jakości x)
x_opt = x’; f_opt = f(x_opt)
if (F(x’’) jest lepsze od f(x)
x = x’’; l = 1
else
l = l + 1
}
while (l < l_max)
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Przykładowe algorytmy przeszukiwania lokalnego
Lin-Kernighan (1973): operator k-zmiany, kumulatywny
współczynnik przyrostu jakości, tabu
2-opt, 3-opt: dodatkowe warunki akceptacji
cała gama algorytmów opartych lub wykorzystujących procedury
typu local search – symulowane wyżarzanie, tabu search itp.
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Bibliografia
Metaheurystyki praktycznie; Krzysztof Trojanowski ; WIT 2005
Metaheurystyki, notatki do wykładu; Kazimierz Grygiel ; UW
Metody przyśpieszania przeglądania otoczeń w algorytmach
lokalnych przeszukiwań; Wojciech Bożejko, Mieczysław Wodecki ;
Opole 2006
Sławomir Góra
Podstawowe informacje
Sąsiedztwo i koszt
Strategie wielostartu
Iteracyjne przeszukiwanie lokalne
Zmienne sąsiedztwo
Koniec
Dziękuję za uwagę.
Sławomir Góra
Document Outline
Wyszukiwarka
Podobne podstrony:
wspomnienia z przeszlosci www prezentacje org
wspomnienia z przeszlosci www prezentacje org
wspomnienia z przeszlosci www prezentacje org
wspomnienia z przeszlosci www prezentacje org
wspomnienia z przeszlosci www prezentacje org
Prezentacja przeszkód małżeńskich i zgody kl 3 i 4
Prezentacja Rozwój lokalny i regionalny
Środowisko lokalne struktura, funkcja i znaczenie PREZENTACJA
Przeszłość nie wraca jak żywe zjawisko, prezentacje
instrumenty polityki lokalnej, Greta Poszwa - prezentacje, polityka regionaln
Mięso i drób w przeszłości prezentacja
Prezentacja zarządzanie rozwojem lokalnym i regionalnym
Przeszczepy Narządów Unaczynionych 2
prezentacja finanse ludnosci
prezentacja mikro Kubska 2
Religia Mezopotamii prezentacja
Prezentacja konsument ostateczna
więcej podobnych podstron