Метаевристични алгоритми
From Wikipedia, the free encyclopedia
Метаевристичните алгоритми (на английски: metaheuristic algorithms, накратко: метаевристики, metaheuristics) в компютърните науки са алгоритми за математическа оптимизация, с които се решават реални задачи. Такива задачи обикновено се характеризират със силна нелинейност, множество параметри, разнообразни сложни ограничения за удовлетворяване и множество – често противоречащи си – оптимизационни критерии. Дори и при един оптимизационен критерий е възможно изобщо да не съществуват оптимални решения и като цяло откриването на оптимално или дори близко до оптималното решение е трудно постижимо.[1]
Терминът „метаевристика“ е въведен от Фред Глоувър в основополагащата му статия от 1986 г. като надграждане на термина „евристичен алгоритъм, с който в най-общ смисъл се разбира алгоритъм за търсене на решение, базиран на пробата и грешката. Частицата „мета“ означава „отвъд“, „свръх“, „на по-високо ниво“ и с метаевристичния алгоритъм се означава „по-висша стратегия, която напрвалява и модифицира други евристични алгоритми, за да постигне решения по-добри от тези, които нормално биха се получили при търсене на локален оптимум.[2][3] В допълнение, всички метаевристични алгоритми балансират между глобално и локално търсене. Качествените решения на трудни оптимизационни задачи могат да се постигнат в разумно (т.е. полиномиално) време, но без гаранция, че ще бъдат постигнати (глобално) оптималните решения.[1]
Двата основни компонента на всеки метаевристичен алгоритъм са: интензификация и диверсификация (intensification and diversification), или още изследване и експлоатация (exploration and exploitation). Диверсификацията означава да се генерират разнообразни решения, така че пространството на търсене да може да бъде проучвано в широк диапазон, докато интензификацията означава да се фокусира търсенето в локален регион, знаейки, че текущото най-добро решение се намира в този регион. При подбора на най-добрите решения трябва да се открие добър баланс между интензификацията и диверсификацията с цел да се подобри скоростта на сходимост на алгоритъм. Изборът на най-доброто текущо решение осигурява, че решенията ще схождат към оптимум, докато диверсификацията посредством рандомизация (т.е. избор на случайни стойности на променливи) позволява да се избегне попадането в локален екстремум и в същото време да се повиши разнообразието на решението. Добрата комбинация от тези два основни компонента обичайно води до намиране на глобален оптимум.[1]