ZP-wyklad4(1), 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 4: jeszcze o metaheurystykach1940195019601970Genealogia metaheurystykGenealogia wg [El-Ghazali Talbi,Metaheuristics: From Design toImplementation,2009]―wybórLS1947GA1962GREEDY1971EP1962dr hab. inż.Marta Kasprzak,prof. nadzw.Instytut Informatyki, Politechnika Poznańska198019902000TS1986GLS1995ILS1991GRASP1989ACO1992GP1992PSO19952Genealogia metaheurystykKlasyfikacja metaheurystykGenealogia wg [El-Ghazali Talbi,Metaheuristics: From Design toImplementation,2009]―legendaLS―local search,jako pierwszy algorytm tego typu zaliczona metodasimplex[Dantzig 1947], brak wskazania na pierwszą typową metodę LS►GA―genetic algorithms,pierwszy zarys metody [Holland, 1962]►EP―evolutionary programming,pierwszy zarys metody [Fogel, 1962]►GREEDY―greedy algorithm[Edmonds, 1971]►TS―tabu search,pierwszy zarys metody [Glover, 1986]►GRASP―greedy randomized adaptive search procedures[Feo, Resende,1989]►ILS―iterated local search[Martin, Otto, Felten, 1991]; także [Baum, 1986]►GP―genetic programming[Koza, 1992]►ACO―ant colony optimization[Dorigo, 1992]►GLS―guided local search[Voudouris, Tsang, 1995]►PSO―particle swarm optimization[Eberhart, Kennedy, 1995]►Klasyfikacja wg [F. Glover, M. Laguna,Tabu Search,1997]―uzupełnionaTabu searchScatter searchGenetic algorithmsGRASPAnt colony optimizationParticle swarm optimizationLegenda:A/N /1M/N/PM/S/PM/N/1A/S/PM/S/PA―adaptive memory,M―memorylessN―neighborhood search,S―random samplingP―population-based,1―single solution43GRASP[T.A. Feo, M.G.C. Resende,Operations Research Letters8, 1989,67–71;Journal of Global Optimization6, 1995, 109–133]Metaheurystyka GRASP (ang.greedy randomized adaptivesearch procedures)przypomina podejściemultistart localsearch.W kolejnych iteracjach najpierw konstruowane jestrozwiązanie początkowe heurystyką zachłanną, następniejest ono poprawiane metodą przeszukiwania lokalnegoHeurystyka zachłanna użyta w GRASP różni sięod zwyczajowego podejścia, gdyż zamiast wybieraćw każdym kroku element najbardziej poprawiającyw danym momencie funkcję celu, wybiera jeden z najbardziejobiecujących elementówGRASPWybór jednego z najbardziej obiecujących elementówdokonywany jest losowo, przez co w każdej iteracjitej metaheurystyki jest szansa na wygenerowanieinnego rozwiązania początkowegoParametry metaheurystyki:►liczba iteracji►liczność podzbioru najbardziej obiecujących elementów(może zmieniać się w kolejnych iteracjach)►ew. inne561Ogólny schemat metaheurystyki GRASPEvolutionary programming[L.J. Fogel,Proceedings of IFIPC,Munich 1962, 395–399;L.J. Fogel, A.J. Owens, M.J. Walsh,Artificial Intelligencethrough Simulated Evolution,Wiley, New York 1966]Evolutionary programmingjest metaheurystyką o schemaciezbliżonym do algorytmów genetycznych. Zmiennośćosobników opiera się tu jedynie na mutacjach i nie marekombinacjiW typowym podejściu każdy rodzic produkuje jednegopotomka poprzez losową mutację, po czym następną populacjęustala się wybierając połowę najlepszych osobników spośródpołączonej puli rodziców i potomków. Selekcja najlepszychosobników odbywa się z użyciem metody turniejowej(ang.tournament selection)78wygenerowanie rozwiązania początkowegoprobabilistycznym algorytmem zachłannymuruchomienie lokalnego przeszukiwaniaaktualizacja najlepszego rozwiązanianietakwarunekstopuEvolutionary programmingOgólny schemat metaheurystyki EPBrak operatora krzyżowania pozwala na dowolny sposóbreprezentacji osobnika, nie musi już być liniowaParametry metaheurystyki:►liczba iteracji lub inny warunek stopu►rozmiar populacji►stopień mutacji►rozmiar „drużyny” turniejowej►ew. innewygenerowanie populacji początkowejtakobliczenie wartości przystosowaniaaktualizacja najlepszego rozwiązaniawarunekstopunieselekcja populacji potomnejmutacja910Genetic programming[J. Koza,Genetic Programming,MIT Press, Cambridge, MA, 1992]Genetic programmingjest metaheurystyką przeznaczonądo automatycznego generowania programów rozwiązującychzadany problem. Jej schemat przypomina algorytmy genetyczne,z tym,żepopulacja składa się tutaj z zapisanych w postacidrzew programów komputerowych (podejście używane wAI)Zapis drzewiasty programów został zaczerpnięty ze strukturyjęzyka programowania LISP. Charakteryzuje się on jednolitąformą zapisu struktur danych i funkcji w notacji polskiejnawiasowej (tzw.S-wyrażenia).Funkcja jest listą z nazwąfunkcji jako pierwszym elementem i jej argumentami w dalszejczęści listy (ciało funkcji definiowane osobną funkcją). Opróczlist/funkcji podstawowym elementem składni języka są atomy(stałe, zmienne)11Genetic programmingPrzykładowy fragment kodu w języku LISP:wikipedia.org122Genetic programmingGenetic programmingPrzełożenie operacji z programu na postać drzewiastą:(= (- a b)(+ c (* 3 d)))=-c+*(define (counter) (set!count (+ count 1)) count)definecounterset!+113countabcountcount3dProgramy składane są z elementów zamieszczonychw predefiniowanych zbiorach dostępnych funkcji i atomów.Należy zapewnić kompletną z punktu widzeniarozwiązywanego problemu zawartość tych zbiorówPopulacja początkowa generowana jest w dużej mierzelosowo, zawiera drzewa o różnym kształcie. Wszystkiewygenerowane programy muszą być wykonywalne(poprawne syntaktycznie). Liczność populacji powinnabyć bardzo duża (tysiące osobników)Parametry tej metaheurystyki i jej schemat są takie same,jak w przypadku algorytmów genetycznych, z dodatkowymipredefiniowanymi zbiorami dostępnych składników koduźródłowegoprogramu oraz z dopuszczalną głębokościądrzewa14Genetic programmingGenetic programmingNależy w szczególny sposób zadbać o poprawność programu,utrzymującą się niezależnie od zastosowanych rekombinacjii mutacji, czyli:►wszystkie funkcje i argumenty powinny być tego samegotypu (np. liczby całkowite) lub ewentualnie należy zapewnićkonwersję typów►funkcje powinny być dostosowane do przyjęcia dowolnychargumentów i nie powinny zawieść wżadnymprzypadku(np. w dzieleniu przez 0)―należy w razie potrzeby zapewnićzastępczą wartość funkcji►dopuszczalna głębokość drzewa lub dopuszczalny rozmiarprogramu nie powinny zostać przekroczone15Selekcja w GP odbywa się na podstawie wartości funkcjiprzystosowania. Funkcję tę oblicza się uruchamiając programyi porównując wynik z oczekiwanym dla badanych instancjiKrzyżowanie to zamiana miejscami losowo wybranychpoddrzew u dwóch osobników w populacji (dwóch programów)Mutacja to losowa zmiana w drzewie osobnikaPrawdopodobieństwo krzyżowania jest często ustawianena wartość mniejszą niż 1 (czyli część osobników przechodzibez zmian do następnego pokolenia)Obecnie implementacje wychodzą poza tradycyjny język LISP,także dopuszcza się zamianę struktury drzewiastej na grafowąlub liniową16Scatter search[F. Glover,Decision Sciences8, 1977, 156–166;New Ideas inOptimization,McGraw-Hill, New York, 1999, 297–316]Scatter searchjest metaheurystyką opartą na populacji lecz— w przeciwieństwie do innych tego typu metod — w dużejmierze wykorzystującą deterministyczne wyboryPopulacja tworzona jest z najlepszych rozwiązań lub ichfragmentów, osiągniętych uprzednio przez zastosowanie innejheurystyki/metaheurystyki. Powinna charakteryzować siędużym zróżnicowaniem osobników. Osobniki nie muszątworzyć rozwiązań dopuszczalnychDodatkowo tworzony jestzbiór referencyjny(ang.referenceset),który zawiera wybrane z populacji najlepsze rozwiązaniaRozmiar zbioru referencyjnego jest niewielki (nie większyniż 20), populacja jest zazwyczaj ok. 10 razy liczniejsza17Scatter searchW „rekombinacji” uczestniczą jedynie osobniki ze zbiorureferencyjnego. Wewnątrz tego zbioru wybór zazwyczajnie opiera się już na ich wartości funkcji celu i wszystkieosobniki biorą udział w tworzeniu nowychPowyższe może odbywać się na zasadzie doboru wszystkichmożliwych par osobników. Liczba tak stworzonych nowychosobników może przekroczyć liczność populacji, wtedywybierane są jedynie najlepsze z nich, z dodatkowymwymogiem na zachowanie różnorodności populacjiWięcej niż dwa osobniki mogą zostać wybrane do rekombinacji.Rekombinacja może wyprodukować jednego lub większąliczbę nowych osobnikówNowe rozwiązania są następnie poprawiane heurystykąi zastępują te ze zbioru referencyjnego, jeśli są od nich lepsze183Scatter searchOgólny schemat metaheurystyki SSScatter searchjest tradycyjniełączonyz metaheurystykątabusearchi z inną metodą tego samego autora,path relinking.Wszystkie preferują determinizm nad losowościąParametry metaheurystyki:►liczba iteracji lub inny warunek stopu►rozmiar populacji►rozmiar zbioru referencyjnego►parametry heurystyki/metaheurystyki używanejdo poprawy osobników z populacji►ew. innewygenerowanie populacji początkowejtakpoprawa osobników heurystykąaktualizacja najlepszego rozwiązaniawybórpodzbiorówwarunekstopuniekrzyżowanieselekcja1920Ant colony optimization[M. Dorigo,Optimization, learning and natural algorithms,PhDthesis, Politecnico di Milano, 1992]Ant colony optimizationjest najbardziej znaną metaheurystykąz grupy metod opartych na inteligencji zbiorowej (inteligencjiroju, ang.swarm intelligence).Odzwierciedla zachowaniekolonii mrówek w procesie zdobywania pożywienia. Innemetody z tej grupy to np.bee colony optimizationiparticleswarm optimizationZaobserwowano,żepołączone działanie prostych obiektówprzekazujących sobie informacje może zostać z sukcesemwykorzystane do rozwiązywania problemów optymalizacyjnych.Ruch obiektów w naturze odpowiada w algorytmieprzemieszczaniu się w przestrzeni rozwiązań21Ant colony optimizationMrówki poprzez komunikację pomiędzy sobą odnajdująnajkrótszą drogę do pożywienia, dotyczy to także gatunkówo słabym wzroku. Idąc, pozostawiająśladferomonowy, którywskazuje kolejnym mrówkom trasę. Im większe stężenieferomonów na trasie, tym większe prawdopodobieństwo,żekolejna mrówka ją wybierze. Z czasemśladsłabnieDla dwóch tras pomiędzy dwoma punktami, dłuższej ikrótszej, prawdopodobieństwo ich wyboru przez mrówkijest początkowo takie same. Po dojściu do celu mrówkiwracają wybraną wcześniej trasą. Przejście trasy krótszejwymaga mniej czasu, w dłuższym okresie więcej mrówekzdąży więc zostawić na niej swójślad.Dodatkowo na krótszejtrasie mniejsza ilość feromonu zdąży się ulotnić22Ant colony optimizationAnt colony optimizationZachowanie mrówek w algorytmie imituje losowa heurystykazachłanna. Przestrzeń rozwiązań problemu jest modelowanaw postaci grafu, w którymścieżkaodpowiada trasie mrówki.Wierzchołkami są elementy składowe rozwiązaniaMrówka konstruuje rozwiązanie krok po kroku, wybierającnastępny wierzchołekścieżkiw oparciu ośladkrawędziwychodzących z bieżącego wierzchołka. Przykładowo, możnazastosować prawdopodobieństwo wyboru opisane wzorem:pij=τij/(kSτik),jSgdzieiorazjto odpowiednio wierzchołek bieżący i rozważany,τijjest feromonowymślademkrawędzi (i,j), aSjest zbioremwierzchołków spoza bieżącejścieżki.Stosując np. metodę ruletkilosuje się następnika bieżącego wierzchołka. Okresowo możnadopuścić zupełnie losowy wybór23Ścieżkaferomonowa jest rodzajem pamięci w algorytmie,magazynuje zdobytą przez mrówki wiedzęUlatnianie się feromonu jest realizowane poprzez zastosowaniew każdej iteracji wzoru:τij= (1–ρ)τij,i,j [1,n]gdzieρ[0,1]jest współczynnikiem redukcji feromonu,aτijjestślademkrawędzi pomiędzy wierzchołkamiiorazjWzmocnienie feromonu może zostać zrealizowane przezzastosowanie różnych strategii, np. po przejściu całejścieżkiprzez dodanie wartości proporcjonalnej do jakości rozwiązania,albo po przejściu wszystkichścieżekw danej iteracji przezuaktualnienie wartości tylkoknajlepszychścieżek244Ant colony optimizationOgólny schemat metaheurystyki ACOParametry metaheurystyki:►liczba iteracji lub inny warunek stopu►liczba mrówek►współczynniki redukcji i wzmocnienia feromonu,ew. liczbaknajlepszychścieżek►ew. innezainicjalizowanieścieżekferomonowychtakkonstrukcja rozwiązań dla każdej mrówkiaktualizacja najlepszego rozwiązaniaaktualizacjaścieżekferomonowych(wzmocnienie lub osłabienie feromonu)warunekstopunie2526Particle swarm optimization[J. Kennedy, R.C. Eberhart,Proceedings of IEEE InternationalConference of Neural Networks,Perth, 1995, 1942–1948]Particle swarm optimizationjest kolejną metaheurystykąz grupyswarm intelligence.Odzwierciedla sposób poruszaniasię obiektów w grupie (zwierząt w stadzie) w sposóbskoordynowany i bez centralnego sterowania. Przykładamitego typu ruchów może być lot ptaków w stadzie lub ruchryb wławicyw poszukiwaniu pożywieniaPotencjalne rozwiązania są w PSO nazywane cząsteczkami(ang.particles).Trajektoria najlepszych w danym momenciecząsteczek wyznacza trasę pozostałym. Wartość cząsteczkimierzona jest funkcją przystosowaniaParticle swarm optimizationW podstawowym modelu każda zNcząsteczek (potencjalnychrozwiązań) porusza się wD-wymiarowejprzestrzeni rozwiązań.Ruch cząsteczek opisany jest ich położeniem (wektorxi)i prędkością (wektorviwskazujący także kierunek/zwrot)Sąsiedztwo jest definiowane dla każdej cząsteczki w celuokreślenia wpływu otoczenia. W zależności od zastosowanegopodejścia, może obejmować cały zbiór, dużą część zbiorulub jedynie najbliższych sąsiadówCząsteczki zmieniają położenie w kierunku globalnegooptimum na podstawie informacji o najlepszym swoimwłasnym położeniupioraz najlepszym położeniupgspośródosiągniętych przez wszystkie cząsteczki z sąsiedztwa2728Particle swarm optimizationParticle swarm optimizationPrędkość cząsteczkivijest uaktualniana następującym wzorem:vi=vi′+ρ1C1(pi–xi′)+ρ2C2(pg–xi′)gdzievi′oznacza poprzednią prędkość,xi′poprzedniepołożenie,ρ1iρ2losowe wartości z przedziału [0,1], aC1iC2to stałe współczynniki uczenia się (ang.learning factors;wskazują, czy cząsteczka podąży raczej za własnym sukcesem,czy sukcesem swoich sąsiadów)Prędkość obliczana powyższym wzorem podlega korekcie,jeśli przekroczy zdefiniowany wcześniej dopuszczalny zakreswartości. Także można zwiększyć wpływ poprzedniej wartościvi′przez umieszczenie we wzorze tzw. współczynnika inercjiw(wvi′)29Położenie cząsteczkixijest uaktualniane następującym wzorem:xi=xi′+viW każdej iteracji uaktualniane są także wartościpiorazpgPSO jest metodą dedykowaną głównie problemomoptymalizacji ciągłej. W przypadku problemówkombinatorycznych należy zadbać o to,żebynowe położenieodpowiadało wartościom akceptowalnym w problemie.Nie zawsze jest tołatwe ―jeśliN-wymiarowymwektoremopisującym położenie cząsteczki w przestrzeni rozwiązańbyłaby permutacjaNelementów, nie wystarczy zaokrąglićwartości w tym wektorze do najbliższych całkowitych305zanotowane.pl doc.pisz.pl pdf.pisz.pl kachorra.htw.pl