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

Метаевристичните алгоритми (, накратко: метаевристики, metaheuristics) в компютърните науки са алгоритми за математическа оптимизация, с които се решават реални задачи. Такива задачи обикновено се характеризират със силна нелинейност, множество параметри, разнообразни сложни ограничения за удовлетворяване и множество – често противоречащи си – оптимизационни критерии. Дори и при един оптимизационен критерий е възможно изобщо да не съществуват оптимални решения и като цяло откриването на оптимално или дори близко до оптималното решение е трудно постижимо.Xin-She Yang (2011) Metaheuristic Optimization. Scholarpedia, 6(8):11472., revision #91488

Терминът „метаевристика“ е въведен от Фред Глоувър в основополагащата му статия от 1986 г. като надграждане на термина „евристичен алгоритъм, с който в най-общ смисъл се разбира алгоритъм за търсене на решение, базиран на пробата и грешката. Частицата „мета“ означава „отвъд“, „свръх“, „на по-високо ниво“ и с метаевристичния алгоритъм се означава „по-висша стратегия, която напрвалява и модифицира други евристични алгоритми, за да постигне решения по-добри от тези, които нормално биха се получили при търсене на локален оптимум. Glover F., (1986). Future paths for integer programming and links to artficial intelligence, Computers and Operations Research,13, 533-549 (1986).Glover F. and Laguna M., Tabu Search, Kluwer, Boston, (1997). В допълнение, всички метаевристични алгоритми балансират между глобално и локално търсене. Качествените решения на трудни оптимизационни задачи могат да се постигнат в разумно (т.е. полиномиално) време, но без гаранция, че ще бъдат постигнати (глобално) оптималните решения.

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

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

Име (на английски) Име Автор Година 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

Източници

Категория:Математическо оптимиране Категория:Евристика