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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Погледати још

• Адаптивна димензионална претрага
• Вештачки развој
• Развојна биологија
• Дигитални организам
• Процена дистрибутивних алгоритама
• Еволуцијско рачунарство
• Еволуциона роботика
• Адаптивна функција
• Фитнес подричја
• Фитнес апроксимација
• Генетички оператори
• Интерактивно еволуцијско рачунарство
• Листа симулатора дигиталних организама
• Мапа еволуционих алгоритама
• Претрага Нема бесплатног ручка претрага и оптимизација
• Синтеза програма
• Тест функција за оптимизације

Литература

• Ashlock, D. (2006), Evolutionary Computation for Modeling and Optimization, Springer, ISBN 0-387-22196-4.
• Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford Univ. Press.
• Bäck, T., Fogel, D., Michalewicz, Z. (1997), Handbook of Evolutionary Computation, Oxford Univ. 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. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4.
• 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, Wiley.
• Computational Intelligence: A Methodological Introduction by Kruse, Borgelt, Klawonn, Moewes, Steinbrecher, Held, 2013, Springer, ISBN 9781447150121.