Jaka jest różnica między heurystykami a metaheurystyką?

Question

Po kilku badaniach dotyczących algorytmów znalazłem dwa pojęcia, które mnie mylą. Przeczytałem przynajmniej 20 artykułów, a jednak nie ma żadnej jasnej definicji. Mam nadzieję, że ktoś może mi pomóc odróżnić algorytmy heurystyczne od metaheurystycznych. I jeśli to możliwe, dodaj jego źródło.

ps: Już wiem, jakie znaczenie mają te słowa, ale nie wiem, jaka jest między nimi różnica w informatyce.

góry dzięki

Answer 1

Można myśleć o heurystyki jak przybliżonej (przybliżenie) nie rozwiązanie problemu. Różnica między przybliżeniem a przybliżeniem polega na tym, że pierwsza polega na trafnym odgadnięciu rozwiązania problemu, ale tak naprawdę nie wiesz, jak to dobrze. Drugi polega na uzyskaniu rozwiązania, w którym można udowodnić, jak bliskie jest optymalne rozwiązanie.

Tak więc heurystyka często zależy od problemu, czyli definiuje heurystykę dla danego problemu. Meta-heurystyki są technikami niezależnymi od problemu, które można zastosować w szerokim zakresie problemów. Heurystyka to na przykład wybór losowego elementu do obracania w Quicksorcie. Meta-heurystyka nie wie nic o problemie, w którym zostanie zastosowany, może traktować funkcje jako czarne skrzynki.

Można powiedzieć, że heurystyka wykorzystuje zależne od problemu informacje, aby znaleźć "wystarczająco dobre" rozwiązanie konkretnego problemu, podczas gdy meta-heurystyki są, podobnie jak wzorce projektowe, ogólnymi pomysłami algorytmicznymi, które można zastosować w szerokim zakresie problemy.

Answer 2

W celu zapewnienia właściwego cytatu, w stosunku do Alejandro odpowiedź:

«a metaheurystyka jest wysoki poziom problemem niezależne algorytmiczne ramy, które zawiera zestaw wytycznych lub strategii w celu opracowania algorytmów optymalizacji heurystyczne [ ...] implementacja specyficznych problemów z heurystycznego algorytmu optymalizacji zgodnie z wytycznymi wyrażonymi w metaheurystyka ram jest również określana jako metaheurystyka »(Sorensen, Glover na http://scholarpedia.org/article/Metaheuristics)

aby być w pełni zakończona. Powinniśmy rozróżnić między algorytmami dokładnymi, przybliżonymi i heurystycznymi. Dokładny algorytm znajduje dokładne rozwiązanie. Przybliżony algorytm powinien znaleźć przybliżone rozwiązanie w akceptowalnym czasie, a także wskazać jego zakres rozbieżności z domniemanym optymalnym rozwiązaniem. Heurystyki po prostu znajdują wystarczająco dobre rozwiązanie w rozsądnym czasie.

Przy okazji przykład Alejandro quicksort nie wydaje się w pełni adekwatny z dwóch lub trzech różnych powodów.

1. W rzeczywistości, heurystyka i metaheurystyk są częścią pola w optymalizacji. Problem, z którym próbują się uporać, polega zatem na szukaniu optimum, a nie sortowania.
2. Heurystyki są na ogół używane, gdy problemy, które chcesz rozwiązać, są zbyt złożone, w sensie obliczeniowym - co nie jest problemem przy sortowaniu.
3. Co zostało wskazane w przykładzie quicksort, jeśli dobrze to rozumiem, jest elementem losowym. Zasadniczo możesz mieć deterministyczną heurystykę - nigdy nie spotkałem się z deterministyczną metaheurystyką, ale prawdopodobnie można ją zakodować. Może to być trochę "bawienie się słowami", ale losowy element bardziej poprawnie charakteryzuje "wyszukiwanie stochastyczne" niż heurystyki (meta).

Answer 3

uzyskać szczegółowe wyjaśnienie, zobacz:

Sörensen, K. (2015). Metaheuristics—the metaphor exposed. International Transactions in Operational Research, 22(1), 3-18.

metaheurystyka jest wysoki poziom problemem niezależne algorytmiczne ramy, które zawiera zestaw wytycznych lub strategii rozwijać heurystycznej optymalizacji algorytmy. Termin ten jest również używany w odniesieniu do specyficznej dla danego problemu implementacji heurystycznego algorytmu optymalizacji zgodnie z wytycznymi wyrażonymi w takich ramach (Sörensen, 2015).

Heurystyki są wytycznymi, metaheurystyka jest ramą, która je wykorzystuje.