Sztuczna inteligencja/SI Moduł 7

Złożoność obliczeniowa metod przeszukiwania

Dotychczas zadanie przeszukiwania rozwiązywaliśmy dotychczas w taki sposób, aby zagwarantować znalezienie maksimum bądź minimum globalnego funkcji. Przestrzeń przeszukiwań będąca drzewem, była przeszukiwana zgodnie z pewnym porządkiem. Określenie kolejności przeglądanych węzłów było elementem różnicującym odmiany algorytmu przeszukiwania. W efekcie prowadzi to do pełnego przeglądu przestrzeni. W tej lekcji zajmiemy się technikami, które wykorzystują elementy losowości. Prowadziło to do algorytmów przeszukiwania, które nie gwarantują pełnego przeglądu przestrzeni w skończonej liczbie kroków, za to są mniej kosztowne obliczeniowo.

Motywacją wykorzystania elementów losowości w procesie przeszukiwania przestrzeni jest teoria złożoności obliczeniowej. Zajmuje się ona określaniem ilości operacji, potrzebnych do rozwiązania problemu, przy czym ta ilość operacji jest wyrażana jako funkcja ilości danych (parametrów) opisujących problem.

Załóżmy, że problem przeszukiwania, który rozwiązujemy, jest wynikiem rozwiązywania zadania scharakteryzowanego $n\,$ parametrami (na przykład liczbą przedmiotów, które można spakować do plecaka). Liczba węzłów przestrzeń przeszukiwań, wynikająca z tej liczby parametrów, da się oszacować jako $ak^{n}\,$, gdzie $k\,$ jest współczynnikiem rozgałęziania (dla problemu plecakowego równym 2), zaś $a\,$ jest stałą proporcjonalności. Pełny przegląd przestrzeni wymaga zatem rzędu $k^{n}\,$ operacji – mówimy, że złożoność obliczeniowa zadania przeszukiwania wynosi $O(k^{n})\,$. Z punktu widzenia znajdowania węzła o najlepszej wartości funkcji oceny, oszacowanie powyższe ma pesymistyczny charakter – oznacza, że jeśli dane ułożą się niekorzystnie, metoda przeglądająca przestrzeń w sposób systematyczny natrafi na optymalny węzeł na końcu (co nie znaczy, że dla „korzystnych” danych nie natrafimy na węzeł optymalny nieco wcześniej niż po przejrzeniu wszystkich węzłów).

Zauważmy jednak, że jeśli rozwiązanie problemu wymaga określenia wartości $n\,$ parametrów, a przejście od jednego do drugiego węzła jest związane z określeniem wartości jednego parametru, wówczas węzeł optymalny od początkowego będzie dzielić $n\,$ krawędzi. Oznacza to, że gdybyśmy dysponowali „wyrocznią” wiedzącą z góry, na jakie wartości ustalać kolejne parametry, pesymistyczne oszacowanie liczby operacji wystarczających do wyznaczenia węzła optymalnego wynosiłoby $O(n)\,$. (W teorii złożoności obliczeniowej taki algorytm „z wyrocznią” ma swój odpowiednik w niedeterministycznej maszynie Turinga). Substytutem takiego algorytmu „z wyrocznią” jest algorytm, w którym wyrocznia jest zastąpiona sekwencją losowych decyzji. Siłą rzeczy, losowe decyzje jedynie z pewnym prawdopodobieństwem są zgodne z wyrocznią. Z tego względu należy powtarzać proces losowania aby zwiększyć prawdopodobieństwo, że choć raz uda się tę zgodność uzyskać.

Niniejsza lekcja jest poświęcona właśnie takim algorytmom z elementami losowości.

Algorytm losowego próbkowania

Przegląd metod zaczniemy od algorytmu losowego próbkowania. Algorytm ten tworzy zbiór węzłów $V\,$ używając poniższego schematu.

   ~~ Algorytm losowego próbkowania  ~~
$V=\phi \,$
powtarzaj $k$ razy
  generuj losowo $s_{k}\in D$
  $V_{k+1}=V_{k}\cup \{s_{k}\}$

Algorytm można kończyć albo po ustalonej liczbie kroków, albo po osiągnięciu zadowalającego poziomu wartości przez funkcję oceny węzła bieżącego.

Wraz z kolejnymi iteracjami algorytmu, zbiór odwiedzonych węzłów $V\,$ będzie coraz większy, a prawdopodobieństwo, że pokryje się on ze zbiorem wszystkich węzłów $D\,$, wzrasta do jedności.

W przestrzeni $R^{n}\,$ jesteśmy w stanie stosunkowo łatwo generować punkty rozkładem jednostajnym w kostce, czyli zbiorze spełniającym dla każdego $i\,$ warunek: $l_{i}\leq x_{i}\leq h_{i}$.

Generacja punktu z rozkładem jednostajnym w takiej kostce odbywa się poprzez $n\,$-krotną realizację zmiennej losowej o rozkładzie jednostajnym na odcinku $\mathbf {(} 0,1)\,$ (można użyć wbudowanego generatora liczb losowych), co prowadzi do uzyskania zbioru wartości $u_{i}\,$. Aby uzyskać wartość $x_{i}\,$ z dowolnego przedziału, np. $\mathbf {(} l_{i},h_{i})\,$ na podstawie tak uzyskanych liczb losowych $u_{i}\,$ należy wyznaczyć wartości $x_{i}\,$ jako $x_{i}=l_{i}+u_{i}(h_{i}-l_{i})\,$.

W przestrzeni wektorów bitowych, w których węzły terminalne są osiągalne poprzez podanie ich numeru, generacja węzła terminalnego może być wykonana poprzez losowanie z rozkładem jednostajnym wartości z zakresu $\mathbf {1} ...N\,$ (gdzie $\mathbf {N} \,$ jest liczbą węzłów terminalnych) i odczytanie węzła o wylosowanym numerze.

Pewien kłopot może natomiast sprawić wygenerowanie węzłów terminalnych w przestrzeniach przeszukiwań takich jak rozważane wcześniej przy okazji heurystycznych metod przeszukiwania. Wzmiankowany kłopot wynika z faktu, że dla każdego węzła umiemy jedynie wygenerować jego najbliższych sąsiadów. A zatem wygenerowanie węzła terminalnego musi być wieloetapowe poprzez generowanie kolejnych nieterminalnych węzłów pośrednich, poczynając od węzła $s_{0}\,$ według poniższej metody.

   ~~ Metoda generowania losowego węzła terminalnego  ~~
$k=0\,$
$V_{0}=\{s_{0}\}\,$
$A_{0}=N(s_{0})\,$
powtarzaj
  wybierz losowo $s_{k+1}{\mbox{ z }}A\,$
  $V_{k+1}=V_{k}\cup \{s_{k+1}\}$
  $A_{k+1}=N(s_{k+1})-V_{k}\,$
  $k=k+1\,$
dopóki $s_{k}\,$ nie jest węzłem terminalnym

Gdzie $A$ jest zbiorem węzłów, zaś $N(s)$ - sąsiedztwem węzła $s$.

Zauważmy, że jeśli:

• do każdego węzła terminalnego prowadzi dokładnie jedna ścieżka,
• współczynnik rozgałęzień jest jednakowy dla wszystkich węzłów o tej samej wysokości,
• wszystkie węzły terminalne mają tę samą wysokość,

to rozkład prawdopodobieństwa osiągnięcia dowolnego węzła terminalnego jest rozkładem jednostajnym. W przeciwnym przypadku może się okazać, że rozkład ten jest niejednostajny .

Niejednostajność rozkładu osiągalności węzłów terminalnych oznacza, że realizując algorytm generowania losowej ścieżki, będziemy osiągać te węzły niejednakowo często – niektóre z nich będą „preferowane”, a niektóre „pokrzywdzone” przez proces przeszukiwania.

Algorytm losowego próbkowania nie generuje ścieżek w sposób systematyczny. Dlatego może się zdarzyć, że w kolejnych iteracjach będą wielokrotnie generowane te same ścieżki. Jednak wraz ze wzrostem liczby iteracji zbiór $V\,$ będzie coraz lepiej „wypełniać” zbiór $D\,$, a prawdopodobieństwo, że dowolny podzbiór $D\,$ zawiera choć jeden element zawarty w zbiorze $V\,$, wzrasta do jedności.

Algorytm błądzenia przypadkowego

Innym sposobem losowego przeglądu przestrzeni jest wykonanie błądzenia przypadkowego. Metoda ta, w porównaniu z metodą losowego próbkowania charakteryzuje się tym, że kolejne odwiedzane węzły skupiają się w swoich sąsiedztwach. Algorytm metody jest następujący:

   ~~ Algorytm losowego próbkowania ~~ 
wyznacz $s_{0}\in D\,$
$V_{0}=\{s_{0}\}\,$
powtarzaj k razy
  generuj losowo $s_{k}\in N(s_{k-1})\,$
  $V_{k}=V_{k-1}\cup \{s_{k}\}$

Gdzie $N(s)\,$ jest sąsiedztwem węzła $s\,$.

Algorytm można kończyć albo po ustalonej liczbie kroków, albo po osiągnięciu zadowalającego poziomu wartości przez funkcję oceny węzła bieżącego.

W przestrzeni $R^{n}\,$ sąsiedztwem punktu $\mathbf {x}$ są punkty odległe o nie więcej niż promień sąsiedztwa $r\,$. Generowanie losowego punktu (np. z rozkładem jednostajnym) z sąsiedztwa jest pewnym problemem technicznym, którego rozwiązanie pozostawiamy Czytelnikowi.

Łatwiej jeszcze metodę błądzenia przypadkowego zrealizować w przestrzeniach dyskretnych o zdefiniowanej relacji sąsiedztwa między węzłami. Wystarczy przyjąć jednakowe wartości prawdopodobieństwa wyboru każdego węzła z sąsiedztwa $N(s_{k-1})\,$, a następnie dokonać losowego wyboru.

Algorytm błądzenia przypadkowego jest, jak mogliśmy się przekonać, nieco prostszy w realizacji od losowego próbkowania. Algorytm ten, podobnie jak metodzie losowego próbkowania, generuje węzły niesystematycznie, możliwe są więc wielokrotne odwiedziny tego samego węzła. W kolejnych iteracjach można się jednak spodziewać, że zbiór odwiedzonych węzłów $V\,$ coraz lepiej będzie wypełniając $D\,$.

Algorytm wspinaczkowy

Algorytm wspinaczkowy (algorytm wzrostu) jest „ulepszoną” metodą błądzenia przypadkowego. Zmiana polega na tym, że losowo wybrany węzeł z otoczenia węzła bieżącego staje się bieżącym jedynie wówczas, gdy jego wartość funkcji oceny jest lepsza niż węzła bieżącego: wyższa w przypadku maksymalizacji albo niższa przy minimalizacji. Można by powiedzieć, że algorytm ten realizuje „poinformowaną.” wersję metody błądzenia przypadkowego. Algorytm można kończyć albo po ustalonej liczbie kroków, albo po osiągnięciu zadowalającego poziomu wartości przez funkcję oceny węzła bieżącego. Obowiązują uwagi, poczynione przy algorytmie błądzenia przypadkowego, dotyczące sposobu realizacji etapu losowej generacji węzła z sąsiedztwa węzła bieżącego.

 ~~ Algorytm wspinaczkowy ~~ 
wyznacz $s_{0}\in D\,$
$V=\{s_{0}\}\,$
powtarzaj k razy
  generuj losowo $t_{k}\in N(s_{k-1})$
  jeśli $g(t_{k})\geq g(s_{k-1})$ to
    $s_{k}=t_{k}\,$
    $V_{k}=V_{k-1}\cup {s_{k}}$
  w przeciwnym przypadku $s_{k}=s_{k-1}\,$

Zauważmy, że poczynione w porównaniu z metodą błądzenia przypadkowego „ulepszenie” wprawdzie gwarantuje, że funkcja oceny węzła bieżącego nie będzie maleć w kolejnych iteracjach, jednak sprawia, że metoda wspinaczkowa nie ma możliwości osiągnięcia dowolnego węzła terminalnego przy ustalonym węźle początkowym. Aby to wykazać, wystarczy rozważyć następujący przykład. Jeśli maksymalizujemy funkcję oceny, a węzłem roboczym stanie się węzeł o ocenie 13, wówczas osiągalne są wyłącznie węzły o wartości oceny 14 i 15.

Zauważmy, że jeśli funkcja oceny jest monotoniczna, wówczas kolejne węzły robocze algorytmu wspinaczkowego utworzą losowo wybraną jedną ze ścieżek od węzła początkowego do terminalnego; w tym przypadku więc wynik działania algorytmu wspinaczkowego będzie identyczny z wynikiem algorytmu generowania dowolnego węzła terminalnego. Natomiast przy niemonotonicznej funkcji oceny, algorytm wspinaczkowy osiągnie wyłącznie ścieżkę, wzdłuż której funkcja oceny jest monotoniczna (przy czym nie sposób zagwarantować, że ta ścieżka zakończy się w węźle terminalnym) .

Załóżmy, że w fazie wyznaczania początkowego węzła roboczego wyznaczono węzeł o wartości funkcji oceny równej 9. W kolejnych etapach algorytmu wspinaczkowego, generowane są kolejne węzły z drzewa. Jednak z uwagi na sposób generowania węzłów, węzeł o wartości 8 nie stanie się nigdy węzłem bieżącym, a tylko wtedy mogłyby się stać osiągalne węzły o wartościach 4 i 16.

Algorytm symulowanego wyżarzania

Algorytm wspinaczkowy i błądzenia przypadkowego stoją na „przeciwstawnych biegunach” – wadą pierwszego jest niemożność znalezienia węzła o najlepszej wartości funkcji oceny, wadą drugiego jest bardzo mała efektywność. Pośredni wariant postępowania polega na tym, aby wybór kolejnego węzła roboczego $s_{k}$ następował w sposób nieco bardziej „liberalny” niż w algorytmie wzrostu, ale nie tak dowolny jak w algorytmie błądzenia przypadkowego. Jedną z możliwych realizacji takiego kompromisu stanowi algorytm symulowanego wyżarzania, działający według poniższego schematu

 ~~ Algorytm symulowanego wyżarzania ~~ 
wyznacz $s_{0}\in D\,$
$V=\{s_{0}\}\,$
powtarzaj k razy
  generuj losowo $t_{k}\in N(s_{k-1})$
  jeśli $g(t_{k})\geq g(s_{k-1})$ to
    $s_{k}=t_{k}\,$
    $V_{k}=V_{k-1}\cup \{s_{k}\}$
  w przeciwnym przypadku
    jeśli $u_{k}<{exp}\left(-{\frac {\left|g(t_{k})-g(s_{k-1})\right|}{T_{k}}}\right)$ to
      $s_{k}=t_{k}\,$
      $V_{k}=V_{k-1}\cup \{s_{k}\}$
    w przeciwnym przypadku
      $s_{k}=s_{k-1}\,$

Algorytm można kończyć albo po ustalonej liczbie kroków, albo po osiągnięciu zadowalającego poziomu wartości przez funkcję oceny węzła bieżącego.

Wartości $T_{k}\,$ są parametrem algorytmu, natomiast $u_{k}\,$ są wartościami zmiennej losowej o rozkładzie jednostajnym na odcinku $\mathbf {(} 0,1)$.

Tak więc algorytm symulowanego wyżarzania akceptuje węzeł $t_{k}\,$ jako nowy węzeł roboczy zarówno wtedy, gdy ma on wyższą ocenę niż $s_{k-1}\,$ jak i niekiedy wówczas, gdy jego ocena jest niższa. W tym drugim przypadku jednak, prawdopodobieństwo tego zdarzenia ma tym mniejszą wartość, im większy jest stopień pogorszenia – różnica $g(t_{k})-g(s_{k-1})\,$. Stopień „liberalności” algorytmu – skłonności do akceptacji gorszego węzła roboczego – jest parametryzowany wartościami $T_{k}\,$. Im większa wartość $T_{k}\,$, tym wyższe prawdopodobieństwo akceptacji gorszego węzła jako węzła bieżącego. W skrajnym przypadku, gdy $T_{k}\,$ ma wartość bliską nieskończonej, prawdopodobieństwo akceptacji gorszego węzła jest bliskie jedności, a algorytm staje się algorytmem błądzenia przypadkowego. W drugim skrajnym przypadku, gdy $T_{k}=0\,$, otrzymujemy algorytm wspinaczkowy.

Algorytm symulowanego wyżarzania będzie błądzić w przestrzeni węzłów $D\,$. Jednak częściej niż w algorytmie błądzenia przypadkowego (i tym częściej, im niższa temperatura) stan $s_{k}\,$ będzie miał wysoką wartość funkcji oceny.