Метаевристични алгоритми
Метаевристичните алгоритми (на английски: 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 |
Източници
[редактиране | редактиране на кода]- ↑ а б в Xin-She Yang (2011) Metaheuristic Optimization. Scholarpedia, 6(8):11472., revision #91488
- ↑ 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).