Метаевристични алгоритми

от Уикипедия, свободната енциклопедия
(пренасочване от Метаевристичен алгоритъм)
Направо към навигацията Направо към търсенето

Метаевристичните алгоритми (на английски: metaheuristic algorithms, накратко: метаевристики, metaheuristics) в компютърните науки са алгоритми за математическа оптимизация, с които се решават реални задачи. Такива задачи обикновено се характеризират със силна нелинейност, множество параметри, разнообразни сложни ограничения за удовлетворяване и множество – често противоречащи си – оптимизационни критерии. Дори и при един оптимизационен критерий е възможно изобщо да не съществуват оптимални решения и като цяло откриването на оптимално или дори близко до оптималното решение е трудно постижимо.[1]

Терминът „метаевристика“ е въведен от Фред Глоувър в основополагащата му статия от 1986 г. като надграждане на термина „евристичен алгоритъм, с който в най-общ смисъл се разбира алгоритъм за търсене на решение, базиран на пробата и грешката. Частицата „мета“ означава „отвъд“, „свръх“, „на по-високо ниво“ и с метаевристичния алгоритъм се означава „по-висша стратегия, която напрвалява и модифицира други евристични алгоритми, за да постигне решения по-добри от тези, които нормално биха се получили при търсене на локален оптимум.[2][3] В допълнение, всички метаевристични алгоритми балансират между глобално и локално търсене. Качествените решения на трудни оптимизационни задачи могат да се постигнат в разумно (т.е. полиномиално) време, но без гаранция, че ще бъдат постигнати (глобално) оптималните решения.[1]

Двата основни компонента на всеки метаевристичен алгоритъм са: интензификация и диверсификация (intensification and diversification), или още изследване и експлоатация (exploration and exploitation). Диверсификацията означава да се генерират разнообразни решения, така че пространството на търсене да може да бъде проучвано в широк диапазон, докато интензификацията означава да се фокусира търсенето в локален регион, знаейки, че текущото най-добро решение се намира в този регион. При подбора на най-добрите решения трябва да се открие добър баланс между интензификацията и диверсификацията с цел да се подобри скоростта на сходимост на алгоритъм. Изборът на най-доброто текущо решение осигурява, че решенията ще схождат към оптимум, докато диверсификацията посредством рандомизация (т.е. избор на случайни стойности на променливи) позволява да се избегне попадането в локален екстремум и в същото време да се повиши разнообразието на решението. Добрата комбинация от тези два основни компонента обичайно води до намиране на глобален оптимум.[1]

Списък от метаевристични алгоритми[редактиране | редактиране на кода]

В литературата съществува голямо разнообразие от метаевристики и голям брой признаци, по които да бъдат класифицирани.

Име (на английски) Име (на български) Автор Година
Ant Colony Optimization Алгоритъм за оптимизация по метода на мравките Dorigo 1992
Amoeba Based Algorithm Zhang et al. 2013
Ant Lion Optimizer Seyedali Mirjalili 2015
Artificial Bee Colony Algorithm Алгоритъм на изкуствените пчелни семейства Karaboga 2005
Artificial Immune System (AIS) Изкуствена имунна система Farmer et al. 1986
Artificial Plant Optimization Cui & Cai 2013
Bacterial Foraging Algorithm Passino 2002
Bat Algorithm Алгоритъм на прилепа Yang 2010
Bean Optimization Algorithm Zhang et al. 2010
Bee Colony Optimization (BCO) Nakrani & Tovey 2004
Biogeography-based Optimization (BBO) Simon 2008
Bootstrap Algorithm (BA) Hanseth & Aanestad 2001
Brain Storm Optimization Algorithm (BSO) Yuhui Shi 2011
Cat Swarm Optimization Shu-Chuan Chu et al. 2006
CMA-ES Hansen & Ostermeier 1996
Cross Entropy Method (CEM) Rubinstein 1997
Crow Search Algorithm Alireza Askarzadeh 2016
Cuckoo Optimization Algorithm, Cuckoo Search Algorithm Алгоритъм на кукувицата Yang & Deb 2009
Differential Evolution Диференциална еволюция Storn and Price 1997
Differential Search Algorithm (DSA) Çivicioglu 2012
Doves Based Algorithm Su et al. 2009
Dragonfly Algorithm (DA) Seyedali Mirjalili 2016
Eagle Based Algorithm Yang & Deb 2010
Earth-worm Optimization Algorithm (EWA) Gai-Ge Wang et al. 2014
Elephant Herd Algorithm (EHO) Gai-Ge Wang et al. 2015
Evolutionary Computation Algorithms, Evolutionary Strategy (ES) Еволюционни алгоритми -- --
Firefly Algorithm Алгоритъм на светулката Yang 2009
Flower Pollination Algorithm (FPA) Алгоритъм на опрашването Yang 2012
Free Search Penev & Littlefair 2003
Fruit Fly Algorithm Pan 2012
Galaxy-based Search Algorithm (GbSA) Shah-Hosseini 2011
Genetic Algorithms (1) Генетични алгоритми Goldberg 1989
Genetic Algorithms (2) Генетични алгоритми Holland 1992
Genetic Programming (GP) Генетично програмиране Smith 1980
Glow-worm Swarm Optimization Krishnanand & Ghose 2005
Gravitational Search Algorithm Esmat Rashedi et al. 2009
Grey Wolf Optimizer, Grey Wolf Algorithm Mirjalili et al. 2014
Grouping Evolution Strategies (GES) Husseinzadeh Kashan 2013
Harmony Search Хармонично търсене Geem et al. 2001
Honey-bee Mating Optimization (HMO) Haddad et al. 2006
Imperialist Competitive Algorithm (ICA) Алгоритъм на империалистическата конкуренция Atashpaz-Gargari and Lucas 2007
Intelligent Water Drops Hamed Shah-Hosseini 2007
Interior Search Algorithm (ISA) Gandomi 2014
Keshtel Algorithm (KA) Hajiaghaie-Keshteli & Aminnayeri 2012
Krill Herd Algorithm (KH) Gandomi & Alavi 2012
League Championship Algorithm (LCA) Husseinzadeh Kashan 2009
Leaping Frog Algorithm Snyman 1982, 2000
Lightning Search Algorithm (LSA) Hussain Shareef et al. 2015
Lion Algorithm Yazdani & Jolai 2015
Memetic Algorithm Moscato 1989
Monkey Search Algorithm Mucherino & Seref 2007
Monarch Butterfly Optimization (MBO) Gai-Ge Wang et al. 2015
Moth-flame Optimization Algorithm (MFO) Seyedali Mirjalili 2015
Multi-objective GA (MOGA) Многообектен генетичен алгоритъм Fonseca & Fleming 1993
Multi-verse Optimizer Seyedali Mirjalili et al. 2016
NSGA for Multi-Objective Optimization Fonseca 1994
NSGA-II for Multi-Objective Optimization Deb et al. 2002
Optics Inspired Optimization (OIO) Husseinzadeh Kashan 2013
Particle Swarm Optimization Оптимизация в рояк от частици Eberhart and Kennedy 1995
Population-based Incremental Learning (PBIL) Shumeet Baluja 1994
Reactive Search Optimization (RSO) Battiti & Tecchiolli 1994
Red Deer Algorithm (RDA) Fathollahi Fard et al. 2016
Shark Algorithm Hersovici et al. 1998
Shuffled Complex Evolution Q. Y. Duan et al. 1993
Simulated Annealing Симулирано закаляване Metropolis et al. 1953
Sine Cosine Algorithm (SCA) Seyedali Mirjalili 2016
Sperm Whale Algorithm Ebrahimi & Khamehchi 2016
Spiral Optimization (SO) Tamura and Yasuda 2011
Stochastic Fractal Search (SFS) Стохастично фрактално търсене Salimi 2014
Tabu Search Табу търсене Glover and McMilan 1986
Teaching-learning-Based Optimization R.V. Rao et al. 2011
Wasp Algorithm Алгоритъм на осата Theraulaz et al. 1991
Water Wave Optimization (WWO) Zheng 2015
Whale Optimization Algorithm (WOA) Lewis and Mirjalili 2016
Wolf Algorithm Liu et al. 2011
Worm Optimization Jean-Paul Arnaout 2014

Източници[редактиране | редактиране на кода]

  1. а б в Xin-She Yang (2011) Metaheuristic Optimization. Scholarpedia, 6(8):11472., revision #91488
  2. Glover F., (1986). Future paths for integer programming and links to artficial intelligence, Computers and Operations Research,13,533-549 (1986).
  3. Glover F. and Laguna M., Tabu Search, Kluwer, Boston, (1997).