Еволуциони алгоритам

У вештачкој интелигенцији, еволуцијски алгоритам (ЕА) је подскуп еволуцијског рачунарства, генеричких метахеуристика за оптимизацију заснованих на популацији. ЕА користи алгоритме засноване на биолошкој еволуцији, као што су репродукција, мутација, рекомбинација и селекција. Решење оптимизационог проблема је једна индивидуа из популације, а фитнес функција одређује квалитет решења (погледај функцију губитка). Еволуција популације се одиграва након поновне примене горенаведених операција. Вештачка еволуција (ВЕ) описује процес који обухвата појединачне еволуционе алгоритме.

Еволуциони алгоритми често апроксимирају решења за све врсте проблема зато што не праве никакве претпоставке о основи фитнес подручја; ова општост се показује успесима алгоритама у многим пољима, као што су инжињерство, уметност, биологија, економија, маркетинг, генетика, операциона истраживања, роботика, друштвеним наукама, физици, политици и хемији.^[1]

Технике из еволуционих алгоритама које се примењују у моделирању биолошке еволуције су углавном ограничене на истраживање микроеволуционарних процеса и планирању модела заснованих на ћелијским процесима. Компјутерске симулације Тиера и Авида покушавају да моделују микроеволуционарна кретања.

У већини реалних примена ЕА, комплексност алгоритма је највећи проблем. Заправо, сложеност је велика због комплексне фитнес функције. Фитнес апроксимације су једне од могућих решења за овај проблем. Међутим, наизглед прост ЕА може да реши веома сложене проблеме; стога, не постоји директна веза измедју сложености алгоритма и сложености проблема.

Могуће ограничење многих еволуцијских алгоритама је њихов недостатак разлике између генотипа и фенотипа. У природи, оплођена јајна ћелија пролази кроз сложен процес познат као ембриогенеза да би постала зрео фенотип. За овакво индиректно кодирање се верује да чини генетска истраживања робустнијим (нпр. Да смањи вероватноћу смртоносних мутација), и такође може побољшати еволутивност организама.^[2]^[3] Таква индиректна (звана геретаривна или развојна) кодирања омогућавају еволуцији да искористи правилности у окружењу.^[4] Скорошња истраживања на пољу вештачке ембриогенезе, тј. развоја вештачких развојних система, настоје да одговоре на ове забринутости. Генетско програмирање успешно истражује генотип-фенотип систем, где се генотип састоји од линеарних мултигенетских хромозома фиксне дужине а фенотип се састоји од више експресионих стабала или компјутерских програма различите величине и облика.^[5]

Имплементација биолошких процеса

Генериши почетну популацију индивидуа насумично (прва генерација)
Израчунај адаптивну вредност сваке од индивидуа у тој популацији.
Понављај ово генерисање до краја (временско ограничење, постигнута довољна адаптивна вредност, итд):
1. Изабери индивидуе са најбољом адаптнивном вредношћу за репродукцију (родитеље)
2. Креирај нове индивидуе на основу родитеља помоћу операција укрштања и мутације и тако створи потомство.
3. Израчунај адаптивну вредност нових индивидуа.
4. Замени најмање фит популацију са новим индивидуама.

Врсте еволуцијских алгоритама

Сличне технике се разликују у детаљима имплементације и природи одређених проблема.

Генетички алгоритам - Ово је најпопуларнији тип ЕА. Тражи решење у виду ниске бројева (обично бинарних, иако је најбоље да се представе тако да одражавају нешто о решењу проблема), применом оператора као сто су рекомбинација и мутација (некада један, некада оба). Ова врста ЕА се најчешће користе у проблемима оптимизације.
Генетичко програмирање - Овде су решења представљена компјутерским програмима, а њихов фитнес је одређен њиховом способности да реше неки проблем.
Еволуцијско програмирање - Слично генетичком програмирању, само што је структура проблема фиксна и њени нумерички параметри могу да еволуирају.
Генетско експресионо програмирање - Као и генетичко програмирање, код ГЕПа се такође развија компјутерски програм али он истражује генотип-фенотип систем, где су програми различитих величина кодирани линеарним хромозомима фиксне дужине.
Еволуциона стратегија - Ради са векторима реалних бројева као репрезентације решења, и обично користи само-прилагодиву брзину мутације.
Диференцијална еволуција - Заснована на вектору разлика и због тога се углавном користи за проблеме нумеричке оптимизације.
Неуроеволуција - Слично генетичком програмирању с тим што су геноми репрезентација неуралних мрежа описујући структуру и тежину конекције. Кодирање генома може бити директно или индиректно.
Системи за класификацију учења - Овде су решења класификације (правила или услови). Мичиген-ЛЦС ради са појединачним класификаторима док Питсбург-ЛЦС користи сетове класификатора популације. Првобитно, класификатори су били само бинарни, али сада садрже праву, неуронску мрежу или С-израз. Фитнес је одређен снагом или тачношћу заснованом на појачаном учењу.

Повезане технике

Технике роја, укључујући:

Оптимизацију мравље колоније - Засноване на идеји мрава који траже пут између своје колоније и извора хране. Примарно се користи за комбинаторне оптимизације и проблеме графова.
Алгоритам корена је инспирисан улогом корена биљака у природи.^[6]
Алгоритам колоније пчела - Заснован на понашању пчела у потрази за храном. Примарно предложен за нумеричке оптимизације а касније проширен да решава комбинаторне проблеме, ограничене проблеме и проблеме са више циљева.
Пчелињи алгоритам - такође заснован на понашању пчела у потрази за храном. Користи се за проблеме рутирања и распоређивања активности.
Алгоритам кукавице - заснован на паразитизму кукавица. Користи Левијеве летове, и због тога је добар за глобалне проблеме оптимизације.
Алгоритам Рој честица - Заснован понашању животиња у крдима. Такође се примарно користи за проблеме нумеричке оптимизације.

Друге метахеуристичке методе засноване на популацији

Прилагодљива димензионална претрага - Алгоритам пролагодљиве димензионалне претраге се разликује од метахеуристичких техника заснованих на природи у смислу да не користи било коју метафору као основни принцип за његово спровођење. Уместо тога користи једноставну методологију засновану на ажурирању коефицијента димензионалне претраге (КДП) у свакој итерацији.^[7]
Алгоритам Свитац - инспирисан понашањем свитаца, који се привлаче међусобно трепћућим светлом. Ово је посебно корисно за мултимодалну оптимизацију.
Хармонија претрага - Заснована на идеји понашања музичара у потрази за бољом хармонијом. Овај алгоритам је погодан за комбинаторне оптимизаије и оптимизације параметара.
Гаусова адаптација - Заснована на теорији информација, адаптивној вредношћу и ентропији. Користи се за максимизацију приноса за производњу. На пример, погледати ентропију у термодинамици и теорији информација.
Меметички алгоритам - Хибридна форма метода заснованих на популацији. Инспирисан Докинсовим појмом мема, обично има облик алгоритма заснованог на популацији упарен са појединачним поступцима учења способним за обављање локалних прецизирања. Наглшава експлоатацију знања специфичних за проблем, и покушава да организује локалну и глобалну претрагу на синергичан начин.

Види још

Референце

^ Carlos M. Fonseca (1995). „An Overview of Evolutionary Algorithms in Multiobjective Optimization”. Evolutionary Computation. 3 (1): 1—16. doi:10.1162/evco.1995.3.1.1.
^ Hornby, G. S.; Pollack, J. B. (2002). „Creating high-level components with a generative representation for body-brain evolution”. Artificial Life. 8 (3): 223—246. PMID 12537684. doi:10.1162/106454602320991837.
^ Jeff Clune, Benjamin Beckmann, Charles Ofria, and Robert Pennock. „"Evolving Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding"” (PDF). Архивирано из оригинала (PDF) 03. 06. 2016. г. Приступљено 30. 05. 2016. . Proceedings of the IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics, 2009. Trondheim, Norway.
^ J. Clune, C. Ofria, and R. T. Pennock, "How a generative encoding fares as problem-regularity decreases," in PPSN (G. Rudolph, T. Jansen, S. M. Lucas, C. Poloni, and N. Beume, eds.), vol. 5199 of Lecture Notes in Computer Science. стр. 358–367, Springer, 2008.
^ Ferreira, C., 2001. „Gene Expression Programming: A New Adaptive Algorithm for Solving Problems”. Complex Systems. 13 (2): 87—129.
^ F. Merrikh-Bayat, The runner-root algorithm: A metaheuristic for solving unimodal and multimodal optimization problems inspired by runners and roots of plants in nature, Applied Soft Computing, Vol. 33. стр. 292–303, 2015
^ Hasançebi, O., Kazemzadeh Azad, S. (2015), Adaptive Dimensional Search: A New Metaheuristic Algorithm for Discrete Truss Sizing Optimization, Computers and Structures, 154, 1-16.

Литература

Ashlock, Daniel (2006). Evolutionary Computation for Modeling and Optimization. Springer. ISBN 978-0-387-22196-0.
Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press.
Bäck, T., Fogel, D., Michalewicz, Z. (1997), Handbook of Evolutionary Computation, Oxford University Press.
Banzhaf, W., Nordin, P., Keller, R., Francone, F. (1998), Genetic Programming - An Introduction, Morgan Kaufmann, San Francisco
Eiben, A.E., Smith, J.E. (2003), Introduction to Evolutionary Computing, Springer.
Holland, J. H. (1975), Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor
Michalewicz Z., Fogel D.B. (2004). How To Solve It: Modern Heuristics, Springer.
Benkő A., Dósa G., Tuza Z. (2010), Bin Packing/Covering with Delivery, Solved with the Evolution of Algorithms, Proc. 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA (2010). стр. 298-302.
Poli, R., Langdon, W. B., McPhee, N. F. A Field Guide to Genetic Programming. Lulu.com. 2008. ISBN 978-1-4092-0073-4. Архивирано из оригинала 27. 05. 2016. г. . Lulu.com, freely available from the internet. .
Price, K., Storn, R.M., Lampinen, J.A., (2005). "Differential Evolution: A Practical Approach to Global Optimization", Springer.
Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).
Simon, D. (2013): „Evolutionary Optimization Algorithms”. Архивирано из оригинала 10. 03. 2014. г. Приступљено 30. 05. 2016. , Wiley.
Kruse, Rudolf; Borgelt, Christian; Klawonn, Frank; Moewes, Christian; Steinbrecher, Matthias; Held, Pascal (2013). Computational Intelligence: A Methodological Introduction. Springer. ISBN 9781447150121. by Kruse, Borgelt, Klawonn, Moewes, Steinbrecher, Held, Springer, .