Znaczenie metod (meta) heurystycznych

1. Do optymalizacji, z Wikipedii :

   W informatyce metaheurystyka wyznacza metodę obliczeniową, która optymalizuje problem poprzez iteracyjną próbę ulepszenia rozwiązania kandydującego w odniesieniu do danej miary jakości. Metaheurystyki przyjmują niewiele założeń lub nie przewidują optymalizacji problemu i mogą wyszukiwać bardzo duże przestrzenie kandydatów na rozwiązania. Jednak metaheurystyki nie gwarantują znalezienia optymalnego rozwiązania. Wiele metaheurystyk wdraża jakąś formę optymalizacji stochastycznej.

   Inne terminy mające znaczenie podobne do metaheurystycznego to: bez pochodnych, wyszukiwanie bezpośrednie, czarna skrzynka lub po prostu heurystyczny optymalizator. Na ten temat opublikowano kilka książek i artykułów ankietowych.

   • Zastanawiam się, jak powiedzieć, czy metoda optymalizacji jest metaheurystyczna, czy nie? Na przykład,

     (1) Czy metoda simpleksowa dla programowania liniowego jest metaheurystyczna?

     (2) Czy większość nieliniowych metod programowania, takich jak opadanie gradientu, metoda mnożnika Lagrangiana, metody kary, metody punktów wewnętrznych (metody barierowe), są metaheurystyczne?

     (3) Czy wszystkie metody bez gradientu, takie jak metoda Neldera-Meada lub metoda simpleks zjazdowa, są metaheurystyczne?

   • Jakie są metody optymalizacji, które nie są metaheurystyczne?

2. Bardziej ogólnie (wykraczając poza optymalizację) technik rozwiązywania problemów, z Wikipedii :

   Heurystyka odnosi się do opartych na doświadczeniu technik rozwiązywania problemów, uczenia się i odkrywania . Tam, gdzie wyczerpujące poszukiwanie jest niepraktyczne, stosuje się metody heurystyczne, aby przyspieszyć proces znajdowania zadowalającego rozwiązania. Przykłady tej metody obejmują stosowanie ogólnej reguły, wyuczonego domysłu, intuicyjnego osądu lub zdrowego rozsądku.

   Mówiąc dokładniej, heurystyka to strategie wykorzystujące łatwo dostępne, choć luźno stosowane, informacje do kontrolowania rozwiązywania problemów u ludzi i maszyn.

   Zastanawiam się, jak zrozumieć znaczenie „heurystyki”?

   • jak mogę stwierdzić, czy technika „rozwiązywania problemów, uczenia się i odkrywania” jest heurystyczna, czy nie?

   • Jakie są techniki „rozwiązywania problemów, uczenia się i odkrywania”, które nie są heurystyczne?

Dziękuję i pozdrawiam!

Heurystyka jest czymś, co sprawdza się w wielu przypadkach w praktyce, chociaż nie ma szczegółowych argumentów przemawiających za tym, dlaczego powinna działać dobrze.

Metaheurystyka nie jest algorytmem, ale ogólnym schematem lub pomysłem heurystycznym, który można zastosować w określonych algorytmach.

Na przykład algorytm simpleks dla programowania liniowego nie jest ani heurystyką, ani metaheurystyką, ponieważ ma ugruntowaną teorię konwergencji. Sqame obsługuje sekwencyjne programowanie kwadratowe lub metody punktów wewnętrznych. (Metody punktów wewnętrznych są schematem ogólnym, ale nie heurystycznym, a zatem nie metaheurystycznym, ponieważ wiąże się z nim dość silna teoria.)

Algorytmem Neldera-Meada = zjazdów simpleksowych służącym do minimalizacji funkcji jest heurystyka (w rzeczywistości może ona zawieść w przypadku dość prostych problemów w wyższych wymiarach), a wyszukiwanie tabu to metaheurystyka (ponieważ można napisać całkiem wiele różnych algorytmów, które wykorzystują wyszukiwanie tabu, ale poza tym mają zupełnie inną jakość.

Nie będę iterować w stosunku do simplex i Nelder-Mead, ponieważ @ArnoldNeumaier podał już bardzo dobre wyjaśnienie, ale chciałem dodać moje 2 centy.

Jeden z najlepszych cytatów, jakie słyszałem jakiś czas temu, aby opisać różnicę między heurystyką a metaheurystą: heurystyka jest całkiem dobrą regułą. Metaheurystyka jest całkiem dobrą zasadą znajdowania całkiem dobrych reguł.

Powinieneś po prostu postrzegać to jako sposób na znalezienie dobrej heurystyki dla konkretnych problemów; zasadniczo jeśli zadajesz sobie jedno z następujących pytań, mówisz o metaheurystyce:

• Jak powinienem ulepszyć parametry tej heurystyki, aby poprawić wydajność tego problemu?
• Czy ta heurystyka jest lepsza niż heurystyka?

Istnieje wiele metaheurystyk, których można użyć do rozwiązywania problemów, uczenia się i odkrywania , a mianowicie:

• Symulowane wyżarzanie : wykorzystałem ten problem do optymalizacji rozmieszczenia połączonych komponentów na siatce, aby na przykład zminimalizować całkowity koszt połączenia.
• Rój cząstek
• Kolonia mrówek
• Wyszukiwanie Tabu

Uważam, że większość metaheurystyk jest w pewnym stopniu inspirowana zjawiskami naturalnymi, które trudno jest rygorystycznie wyjaśnić, ale mają dobre właściwości zbieżności.

Oto dobry link, jeśli chcesz przeczytać więcej o innych technikach metaheurystycznych