Metaheurystyka - Metaheuristic

W informatyce i optymalizacji matematycznej , A metaheurystyka jest wyższy poziom procedura lub heurystyczny przeznaczony do znalezienia, generować lub wybierz heurystyki (częściowe algorytm wyszukiwania ), które mogą zapewnić wystarczająco dobre rozwiązanie do problemu optymalizacji , zwłaszcza z niekompletnych lub niepełnych informacji lub ograniczona zdolność obliczeniowa. Metaheurystyki próbują podzbioru rozwiązań, który w innym przypadku jest zbyt duży, aby można go było całkowicie wyliczyć lub zbadać w inny sposób. Metaheurystyki mogą przyjmować stosunkowo niewiele założeń dotyczących rozwiązywanego problemu optymalizacji, a zatem mogą być przydatne do różnych problemów.

W porównaniu z algorytmami optymalizacji i metodami iteracyjnymi , metaheurystyka nie gwarantuje znalezienia globalnie optymalnego rozwiązania dla jakiejś klasy problemów. Wiele metaheurystyk implementuje pewną formę optymalizacji stochastycznej , tak aby znalezione rozwiązanie było zależne od zestawu wygenerowanych zmiennych losowych . W optymalizacji kombinatorycznej , przeszukując duży zestaw wykonalnych rozwiązań , metaheurystyki często mogą znaleźć dobre rozwiązania przy mniejszym wysiłku obliczeniowym niż algorytmy optymalizacji, metody iteracyjne lub proste heurystyki. Jako takie są użytecznym podejściem do rozwiązywania problemów optymalizacyjnych. Na ten temat opublikowano kilka książek i artykułów ankietowych.

Większość literatury dotyczącej metaheurystyki ma charakter eksperymentalny, opisując wyniki empiryczne oparte na eksperymentach komputerowych z algorytmami. Ale dostępne są również pewne formalne wyniki teoretyczne, często dotyczące zbieżności i możliwości znalezienia globalnego optimum. Opublikowano wiele metod metaheurystycznych z twierdzeniami o nowości i praktycznej skuteczności. Chociaż dziedzina obejmuje również badania wysokiej jakości, wiele publikacji było słabej jakości; wady obejmują niejasność, brak opracowania koncepcyjnego, słabe eksperymenty i nieznajomość wcześniejszej literatury.

Nieruchomości

Oto właściwości charakteryzujące większość metaheurystyk:

  • Metaheurystyki to strategie, które kierują procesem wyszukiwania.
  • Celem jest efektywne zbadanie przestrzeni wyszukiwania w celu znalezienia prawie optymalnych rozwiązań.
  • Techniki składające się na algorytmy metaheurystyczne obejmują zarówno proste procedury wyszukiwania lokalnego , jak i złożone procesy uczenia się.
  • Algorytmy metaheurystyczne są przybliżone i zwykle niedeterministyczne.
  • Metaheurystyki nie dotyczą konkretnych problemów.

Klasyfikacja

Diagram Eulera różnych klasyfikacji metaheurystyk.

Istnieje wiele różnych metaheurystyk i szereg właściwości, w odniesieniu do których można je klasyfikować.

Wyszukiwanie lokalne a wyszukiwanie globalne

Jednym z podejść jest scharakteryzowanie rodzaju strategii wyszukiwania. Jednym z rodzajów strategii wyszukiwania jest ulepszenie prostych algorytmów wyszukiwania lokalnego. Dobrze znanym algorytmem wyszukiwania lokalnego jest metoda wspinaczki górskiej , która służy do znajdowania lokalnych optimum. Wspinaczka górska nie gwarantuje jednak znalezienia globalnych optymalnych rozwiązań.

Zaproponowano wiele metaheurystycznych pomysłów, aby ulepszyć lokalną heurystykę wyszukiwania w celu znalezienia lepszych rozwiązań. Takie metaheurystyk obejmują symulowane wyżarzanie , tabu wyszukiwania , potwierdzili lokalnego wyszukiwania , zmienny wyszukiwanie sąsiedztwa i pojąć . Te metaheurystyki można sklasyfikować zarówno jako metaheurystyki oparte na wyszukiwaniu lokalnym, jak i metaheurystyki globalne.

Inne metaheurystyki globalne wyszukiwania, które nie są oparte na wyszukiwaniu lokalnym, to zazwyczaj metaheurystyki populacyjne. Takie metaheurystyki obejmują optymalizację kolonii mrówek , obliczenia ewolucyjne , optymalizację roju cząstek , algorytm genetyczny i algorytm optymalizacji jeźdźców .

Pojedyncze rozwiązanie a oparte na populacji

Innym wymiarem klasyfikacji jest pojedyncze rozwiązanie w porównaniu z wyszukiwaniem opartym na populacji. Podejścia oparte na pojedynczym rozwiązaniu koncentrują się na modyfikowaniu i ulepszaniu pojedynczego kandydata na rozwiązanie; pojedyncze metaheurystyk rozwiązania obejmują symulowane wyżarzanie , potwierdzili lokalnego wyszukiwania , zmienny wyszukiwanie sąsiedztwa i przewodnikiem wyszukiwania lokalnego . Podejścia oparte na populacjach utrzymują i ulepszają wiele potencjalnych rozwiązań, często wykorzystując charakterystykę populacji do kierowania wyszukiwaniem; Metaheurystyki populacyjne obejmują obliczenia ewolucyjne , algorytmy genetyczne i optymalizację roju cząstek . Inną kategorią metaheurystyki jest inteligencja roju, która jest zbiorowym zachowaniem zdecentralizowanych, samoorganizujących się agentów w populacji lub roju. Mrówka kolonia optymalizacja , optymalizacja rojem cząstek , społecznej optymalizacji poznawcze są przykładami tej kategorii.

Hybrydyzacja i algorytmy memetyczne

Hybryda metaheurystyka to taki, który łączy w sobie metaheurystyka z innymi optymalizacja podejścia, takie jak algorytmy z programowania matematycznego , programowania więzów i uczenia maszynowego . Oba składniki metaheurystyki hybrydowej mogą działać jednocześnie i wymieniać informacje w celu kierowania wyszukiwaniem.

Z drugiej strony, algorytmy memetyczne reprezentują synergię podejścia ewolucyjnego lub dowolnego podejścia populacyjnego z odrębnymi procedurami indywidualnego uczenia się lub lokalnego doskonalenia w poszukiwaniu problemów. Przykładem algorytmu memetycznego jest zastosowanie lokalnego algorytmu wyszukiwania zamiast podstawowego operatora mutacji w algorytmach ewolucyjnych.

Metaheurystyki równoległe

Metaheurystyka równoległy to taka, która wykorzystuje techniki programowania równoległego uruchamiania wielu metaheurystyka wyszukiwań równolegle; mogą one obejmować zarówno proste schematy rozproszone , jak i współbieżne przebiegi wyszukiwania, które współdziałają w celu ulepszenia ogólnego rozwiązania.

Metaheurystyka inspirowana naturą i oparta na metaforach

Bardzo aktywnym obszarem badań jest projektowanie metaheurystyk inspirowanych naturą. Wiele ostatnich metaheurystyk, zwłaszcza ewolucyjnych algorytmów opartych na obliczeniach, jest inspirowanych systemami naturalnymi. Natura działa jako źródło pojęć, mechanizmów i zasad projektowania sztucznych systemów obliczeniowych do radzenia sobie ze złożonymi problemami obliczeniowymi. Takie metaheurystyki obejmują symulowane wyżarzanie , algorytmy ewolucyjne , optymalizację kolonii mrówek i optymalizację roju cząstek . Duża liczba nowszych metaheurystyk inspirowanych metaforami zaczęła przyciągać krytykę społeczności naukowej za ukrywanie braku nowości za skomplikowaną metaforą.

Aplikacje

Metaheurystyki są wykorzystywane do optymalizacji kombinatorycznej, w której poszukiwane jest optymalne rozwiązanie w dyskretnej przestrzeni poszukiwań. Przykładowym problemem jest problem komiwojażera, w którym przestrzeń poszukiwań potencjalnych rozwiązań rośnie szybciej niż wykładniczo wraz ze wzrostem rozmiaru problemu, co sprawia, że wyczerpujące poszukiwanie optymalnego rozwiązania jest niewykonalne. Ponadto wielowymiarowe problemy kombinatoryczne, w tym większość problemów projektowych w inżynierii, takich jak znajdowanie form i znajdowanie zachowań, cierpią z powodu przekleństwa wymiarowości , co czyni je również niewykonalnymi w przypadku wyczerpujących poszukiwań lub metod analitycznych . Metaheurystyki są również szeroko stosowane do planowania warsztatów i problemów z wyborem pracy. Popularne metaheurystyki dla problemów kombinatorycznych obejmują symulowane wyżarzanie Kirkpatricka i in., algorytmy genetyczne Hollanda i in., przeszukiwanie rozproszone i przeszukiwanie tabu autorstwa Glovera. Przegląd literatury dotyczący optymalizacji metaheurystycznej sugerował, że to Fred Glover ukuł słowo metaheurystyka.

Ramy optymalizacji metaheurystycznej (MOF)

MOF można zdefiniować jako „zestaw narzędzi programowych, które zapewniają poprawną i wielokrotnego użytku implementację zestawu metaheurystyk oraz podstawowych mechanizmów przyspieszających implementację podrzędnych heurystyk partnera (ewentualnie obejmujących kodowanie rozwiązań i operatory specyficzne dla techniki) , które są niezbędne do rozwiązania konkretnego problemu za pomocą dostarczonych technik”.

Istnieje wiele potencjalnych narzędzi optymalizacyjnych, które można uznać za MOF o różnej funkcji: Comet, EvA2, evolvica, Evolutionary::Algorithm, GAPlayground, jaga, JCLEC, JGAP, jMetal, n-genes, Open Beagle, Opt4j, ParadisEO/EO , Pisa, Watchmaker, FOM, Hypercube, HotFrame, Templar, EasyLocal, iOpt, OptQuest, JDEAL, Optimization Algorithm Toolkit, HeuristicLab, MAFRA, Localizer, GALIB, DREAM, Discropt, MALLBA, MAGMA, UOF i OptaPlanner.

Składki

Istnieje wiele różnych metaheurystyk i ciągle proponowane są nowe warianty. Niektóre z najbardziej znaczących wkładów w tę dziedzinę to:

Zobacz też

Bibliografia

Dalsza lektura

Zewnętrzne linki