ZP-wyklad2, informatyka, PROGRAMOWANIE(1), wykłady
Poza tym na świecie jest niewiele istot groźniejszych od kobiety.
//-->.pos {position:absolute; z-index: 0; left: 0px; top: 0px;}Zaawansowane programowaniewykład 2: metoda przeszukiwania tabuMetoda przeszukiwania tabu[Fred Glover: Tabu Search — Part I,ORSA Journal on Computing1(1989) 190–206; Tabu Search — Part II,ORSA Journal onComputing2 (1990) 4–32]Metoda przeszukiwania tabu(ang.tabu search)jestmetaheurystyką realizującą heurystyczną proceduręprzeszukiwania lokalnego, wychodzącą jednak pozaobszar lokalnego optimumW tym podejściureguły deterministycznesą preferowanenad probabilistycznymiMetoda przeszukiwania tabu operuje napojedynczymrozwiązaniu,które iteracyjnie jest poprawiane pod kątemoptymalizacji funkcji celu2dr hab. inż.Marta Kasprzak,prof. nadzw.Instytut Informatyki, Politechnika PoznańskaRozwiązanie początkoweSąsiedztwoBieżące rozwiązanie,na którym dokonywane są operacjew metodzie, jest — niekoniecznie liniowym — zapisemrozwiązania problemu. Może to być np. ciąg indeksówelementów, dwuwymiarowa lista następników elementów,kwadratowa macierz sąsiedztwa grafu, itp. Zazwyczaj im większastruktura, tym większe zużycie pamięci i czasu w algorytmieRozwiązanie początkowe,od którego rozpoczynane sąobliczenia, może być losowe, choć zwykle lepszy efektuzyskuje się generując je wstępną heurystyką (np. zachłanną)W razie stosowania restartów procedury przeszukiwania, kolejnerozwiązanie „początkowe” można wygenerować w oparciuo dotychczasowe obserwacje. Przykładowo, można je złożyćz najrzadziej używanych dotąd elementów (aby wystartowaćz innego obszaru przestrzeni rozwiązań) albo korzystaćz fragmentów najlepszych (zróżnicowanych) rozwiązań3Każde rozwiązaniexX przestrzeni rozwiązań(ang.solutionspace)ma przypisanesąsiedztwo(ang.neighborhood) N(x)X,którego każdy elementx′N(x)jest osiągany zxprzez operacjęzwanąruchem(ang.move)Ruch ma na celu zwykle niedużą zmianę w obrębie rozwiązania.Może być np. wstawieniem, usunięciem, przesunięciem elementurozwiązania, zamianą miejscami pary elementów, itp.Xstanowi zazwyczaj zbiór rozwiązań dopuszczalnych (gdy ruchysą ograniczone do dopuszczalnych), ale można stosować wyjątkix1x6x5x4xx2x3x,xi―elementy przestrzeni rozwiązańN(x) = {x1,x2,x3,x4,x5,x6}―ruch4SąsiedztwoSąsiedztwoZastosowanie wszystkich zdefiniowanych ruchów w stosunkudo bieżącego rozwiązania może zaowocować zbyt dużymsąsiedztwem. Przegląd takiego sąsiedztwa wraz z wyliczeniemwartości funkcji celu może zająć zbyt wiele czasuSąsiedztwo można ograniczyć do krótszej listy kandydatów(ang.candidate list),biorąc pod uwagę jedynie najbardziejobiecujące ruchyPrzykładowo, można wybierać ruchy zapamiętane jakonajskuteczniejsze w przeszłości lub ruchy odnoszące siędo najsłabszych fragmentów rozwiązaniaSkrócenie obliczeń uzyskuje się także poprzez ewaluacjęfunkcji oceny prostszej niż funkcja celu dla całego rozwiązania,np. pewnego jej przybliżenia albo przez oszacowanie względnejwartości lokalnej zmiany wywołanej przez ruch5Zazwyczaj wybierany jest taki ruch, który prowadzido największej poprawy wartości funkcji celu (ew. jejprzybliżenia) lub do najmniejszego pogorszenia jej wartości,gdy poprawa w obrębie sąsiedztwa nie jest możliwaTa zasada dążenia do optimum lokalnego jest elementemstrategiiintensyfikacjiw metodziemaksimum globalnemaksimum lokalne61Lista tabuLista tabuPo osiągnięciu w wyniku serii ruchów lokalnego optimumkolejny ruch może spowodować jedynie pogorszeniebieżącego rozwiązania (chwilowe). Zgodnie z przyjętą zasadąwybierany jest ruch skutkujący najmniejszym pogorszeniemBardzołatwow ten sposób cofnąć się do obszaru jużprzeszukanego. W konsekwencji można zapętlić poszukiwaniaw obrębie stale tego samego obszaruStrukturą uniemożliwiającą powrót do ostatnio odwiedzonychpunktów przestrzeni rozwiązań jestlista tabu(ang.tabu list).Zamieszczone na niej ostatnio osiągnięte fragmentyrozwiązania czy ostatnio wykonane ruchy blokują ichponowne osiągnięcie/wykonanie przez zadaną liczbę iteracjiDopuszczalne sąsiedztwo jest teraz zdefiniowane jakoN*(x)=N(x)\T,gdzieTto rozwiązania ze statusem tabu7Listę tabu realizuje się najczęściej jako listę/tablicę typu FIFO(ang.first-in-first-out).Zawiera ona wszystkie bieżące atrybutyo statusie tabuAtrybut najczęściej opisuje ruch (np. wstawienie czy usunięcieelementu), także fragment rozwiązaniaInną postacią listy tabu jest tablica o liczbie pól równej liczbieatrybutów, każde jej pole zawiera wartość równą liczbie iteracji,przez którą dany atrybut będzie posiadał status tabu. Tablicataka zajmuje więcej pamięci niż tradycyjna lista tabu, ale za toumożliwia sprawdzenie statusu atrybutu w stałym czasie123 45 6 7 89 10 11 123 8 5 9 1 4lista FIFO5 0 1 6 3 0 0 2 4 0 0 0tablica wszystkich atrybutów8Lista tabuLista tabu — przykładZbyt krótka lista tabu może spowodować cykliczne powracaniedo już wygenerowanych rozwiązań. Zbyt długa możezablokować zbyt wiele ruchówW ogólności krótkie listy tabu skutkują przeszukiwaniemokolicy lokalnego optimum, długie umożliwiają wyjście pozatę okolicę. Długość listy można zmieniać w trakcie działaniaalgorytmu w zależności od przyjętej w danej chwili strategiiintensyfikacji czy dywersyfikacjiDługość listy tabu jest często stała w trakcie działania algorytmu.Długość najwłaściwszą dla danego problemu i danego rozmiaruinstancji można w pewnym stopniu oszacować teoretycznie,lecz zazwyczaj na jej dobór wpływa seria wstępnych testówMoże być więcej niż jedna lista tabu w algorytmie, wtedypamiętają one różnego rodzaju atrybuty9Minimum k-tree problem:poszukiwanie w grafienieskierowanym drzewa złożonego zkkrawędzi takiego,żesuma wag tych krawędzi jest minimalnaRuch zdefiniowany jest jako równoczesne wstawienie dorozwiązania jednej krawędzi i usunięcie innejv1Można przykładowo nadać status tabuna tę samą liczbę iteracji obu operacjom:v2v6dla krawędzi wstawianej będzie to zakazusuwania, dla usuwanej — wstawianiav5v3Ponieważ jednak krawędzi w grafie mamyv4zazwyczaj dużo więcej niżk,warto rozważyćimplementację dłuższej listy tabu dlak=4krawędzi usuwanych niż wstawianychwagi:1,2,310Kryterium aspiracjiKryterium aspiracjiWybierany ruch (lub jego konsekwencje) nie powinienzawierać atrybutów znajdujących się na liście tabu.Nie zawsze jednak można lub należy zachowaćtę prawidłowość. Zasadę pozwalającą pominąć status tabunazywa siękryterium aspiracji(ang.aspiration criterion)Przykłady kryterium aspiracji:►ruch ze statusem tabu może być wybrany, gdy prowadzido poprawy najlepszego rozwiązania (najlepszej wartościfunkcji celu) otrzymanego do tej pory►gdy w pewnym momencie obliczeń sąsiedztwo danegorozwiązania okaże się zbyt małe, lub lista tabu zbyt długa,wszystkie możliwe ruchy będą miały przydzielony statustabu; wykonuje się wtedy ruch z początku listy, tzn.o najmniejszym okresie oczekiwania na opuszczenie listy11Przykłady kryterium aspiracji cd.:►gdy jesteśmy na etapie wychodzenia z obszaru lokalnegooptimum, statusu tabu można pozbawić ruch o znaczącymwpływie na postać bieżącego rozwiązania, powodujący skokw odległy punkt przestrzeni rozwiązań►można także usunąć status tabu z ruchu o małym wpływiena postać rozwiązania, jeśli od czasu umieszczenia go(lub jego atrybutów) na liście tabu wykonany został skokdo innego obszaru przestrzeni rozwiązań►gdy w trakcie stałego poprawiania jakości rozwiązaniapewien ruch otrzyma status tabu i późniejsze jego wykonanienie zakłóci tendencji wzrostu, to można go wykonać, gdyżnie spowoduje powrotu do ostatnio otrzymanych rozwiązań122Dywersyfikacja rozwiązańPodział pamięci ze względu na czasStrategiadywersyfikacjirealizowana jest poprzez czynnościmające na celu skok do innego obszaru przestrzeni rozwiązańElementem tej strategii może być długa lista tabu,wyprowadzająca poszukiwanie poza dotychczasowy obszarMożna dopuścić wykonanie co jakiś czas ruchów bardziejwpływających na postać rozwiązania niż standardowe.Dopuszcza się w tej metodzie elementy losowościInnym sposobem mogą być restarty procedury poszukiwania,czyli rozpoczynanie całego procesu od nowego rozwiązaniapoczątkowego, zlokalizowanego w innej części przestrzenirozwiązań. Często pamięć i zmienne są wtedy zerowaneDo dywersyfikacji można wykorzystać także niektórez rodzajów pamięci zdefiniowanych w metaheurystyce13Pamięć krótkotrwała(ang.short-term memory)służyzapamiętywaniu ostatnio wykonanych ruchów czy atrybutówrozwiązań w celu uniknięcia odwrócenia ruchu orazwpadnięcia w cykle ruchówPamięć długotrwała(ang.long-term memory)służyzapamiętywaniu ruchów/rozwiązań w dłuższym okresieczasu, w celu wynagradzania ruchów najlepszych bądźwykonywanych rzadko, albo karania ruchów najgorszychbądź występujących często (lub fragmentów rozwiązańzamiast ruchów). Pamięć może gromadzić informacjeprzez cały czas obliczeń algorytmu albo pomiędzy restartami,może być o stałej długości (FIFO) lub obejmować wszystkiezdarzenia w zadanym przedziale czasu14Podział pamięci ze względu na zawartośćPodział pamięci ze względu na funkcjęLista tabu jest rodzajempamięci określającej(ang.attributivememory),tzn. zapamiętuje informacje o atrybutach/cechachruchów prowadzących do rozwiązaniaDrugim typem pamięci w metaheurystyce jestpamięćbezpośrednia(ang.explicit memory),pamiętająca kompletnerozwiązania, zazwyczaj najlepsze dotychczas odwiedzonePamięć bezpośrednia może także zapamiętywać atrakcyjnych,lecz nieodwiedzonych dotąd sąsiadów najlepszych rozwiązań(do intensyfikacji poszukiwań). Może służyć unikaniuodwiedzania rozwiązań więcej niż raz, osiąga jednak wtedyduże rozmiaryRecency-based memory— pamięć gromadząca informacjeo ostatnio wykorzystanych atrybutach, np. lista tabuFrequency-based memory— pamięć oparta na częstościwykorzystania atrybutów, może korzystać z miar:►transition measure— liczba iteracji, w których danyatrybut został użyty do wykonania ruchu, czyli wpłynąłna postać rozwiązania►residence measure— liczba iteracji, podczas którychatrybut należał do rozwiązania; wysoka wartośćresidencemeasuremożeświadczyćo atrakcyjności atrybutu,gdy otrzymujemy rozwiązania wysokiej jakości, lub wręczprzeciwnie, gdy rozwiązania są słabe1615Podział pamięci ze względu na funkcjęPamięć a strategie — przykłady użyciaQuality-based memory— pamięć oparta na jakości, używanado zidentyfikowania elementów wspólnych dla dobrychrozwiązań lubścieżekprowadzących do dobrych rozwiązań.Na jej podstawie preferuje się czynności skutkujące dobrymirozwiązaniami albo obarcza karami czynności prowadzącedo słabych rozwiązańInfluence-based memory— uogólnieniequality-basedmemory;zapamiętuje wpływ dokonanych wyborówna rozwiązania, nie tylko pod względem wartości funkcji celu,lecz także struktury rozwiązania. Pamięć ta może wspomagaćnp. badanie dopuszczalności generowanych rozwiązańczy ich regionalności (gdy chcemy skoczyć w inny obszarprzestrzeni rozwiązań)17Frequency-based memorymożna użyć w strategiidywersyfikacji, np. przy restarcie procesu obliczeniowego,do złożenia nowego rozwiązania z najrzadziej używanychdotąd elementów. Można też, w trakcie procesuobliczeniowego, w mniejszym stopniu wpłynąć na postaćrozwiązania poprzez wykorzystanie w części rzadkoużywanych atrybutówQuality-based memorymożna użyć w strategii intensyfikacji,np. składając nowe rozwiązania z fragmentów dobrychrozwiązań. Aby wpłynąć na postać rozwiązania w mniejszymzakresie, można wybierać pojedyncze ruchy prowadzącew przeszłości do dobrych rozwiązań183Ogólny schemat metodytabu searchwygenerowanie rozwiązania początkowegozainicjalizowanie struktur pamięciprzegląd sąsiedztwa bieżącego rozwiązaniawybór najlepszego sąsiadaaktualizacja najlepszego rozwiązaniaaktualizacja struktur pamięciew. dywersyfikacja rozwiązania, także restartew. inna modyfikacja procesu podstawowegowarunekstopunietakMetoda przeszukiwania tabu — parametryParametrami tej metaheurystyki umożliwiającymi dostosowaniejej do indywidualnych potrzeb są:►►►długość listy taburozmiar innych rodzajów pamięciużywanych w algorytmieliczba iteracji;można przyjąć z góry zadaną liczbę iteracjialbo np. liczbę iteracji bez poprawy funkcji celu; częstodefiniowane są dwie lub więcej wartości składające sięna liczbę iteracji, np. liczba kroków intensyfikacji, następującapo nich liczba kroków dywersyfikacji, liczba takich cyklii liczba restartów►19inne20Metoda przeszukiwania tabu a losowośćLiteratura — cd.Metaheurystykatabu searchdopuszcza losowość, przy czymautor metody sugeruje minimalne jej użycie. Prawie zawszezastosowanie przemyślanej strategii deterministycznejprowadzi do lepszych wyników niż zastosowanie losowościNawet słaba deterministyczna strategia daje więcej informacjiniż losowa, gdyż jest skonstruowana z uwzględnieniem cechdanego problemu w celu poprawienia jakości rozwiązania(czego nie można powiedzieć o wyborach losowych).Słabą zasadę wyboru deterministycznego można poprawićna podstawie uzyskiwanych wynikówWybory deterministyczne są preferowane wtabu searchtakżeze względu na pojedyncze rozwiązanie, na którym operujemy.Losowe wybory lepiej sprawdzają się, gdy mamydo dyspozycji dużo więcej „materiału eksperymentalnego”21Fred Glover, Manuel Laguna,Tabu Search,Kluwer AcademicPublishers, Boston, 1997.http://spot.colorado.edu/~glover/224zanotowane.pl doc.pisz.pl pdf.pisz.pl kachorra.htw.pl