Перегляд вихідного коду сторінки Еволюційний алгоритм

{{Штучний інтелект (бічна панель)|Підходи}}
'''Еволюційні алгоритми'''&nbsp;— напрям в [[штучний інтелект|штучному інтелекті]] (розділ [[Еволюційне моделювання|еволюційного моделювання]]), що використовує і моделює [[Теорія еволюції|біологічну еволюцію]]. Розрізняють різні алгоритми: [[генетичний алгоритм|генетичні алгоритми]], [[еволюційне програмування]], [[Еволюційна стратегія|еволюційні стратегії]], [[системи класифікаторів]], [[генетичне програмування]] тощо. Всі вони моделюють базові положення в теорії біологічної еволюції&nbsp;— процеси відбору, мутації і відтворення. Поведінка агентів визначається довкіллям. Множину агентів прийнято називати популяцією. Така популяція еволюціонує відповідно до правил відбору відповідно до цільової функції, що задається довкіллям. Таким чином, кожному агентові (індивідуумові) популяції призначається значення його придатності в довкіллі. Розмножуються лише найпридатніші види. Рекомбінація і мутація дозволяють агентам змінюватись і пристосовуватися до середовища. Такі алгоритми належать до адаптивних пошукових механізмів.

__TOC__

== Класифікація алгоритмів ==

Моделювання еволюції можна розділити на дві категорії:{{джерело}}
# Системи, які використовують лише еволюційні принципи. Вони успішно використовувалися для завдань виду функціональної [[Оптимізація (інформатика)|оптимізації]] і можуть легко бути описані на математичній мові. До них належать еволюційні алгоритми, такі як еволюційне програмування, генетичні алгоритми, еволюційні стратегії.
# Системи, які є біологічно реалістичніші, але які не виявилися корисними в прикладному сенсі. Вони більше схожі на біологічні системи і менш направлені на вирішення технічних завдань. Вони володіють складною і цікавою поведінкою, і, мабуть, незабаром отримають практичне вживання. До цих систем відносять так зване [[штучне життя]].

Еволюційні алгоритми, в сучасному вигляді, з'явились наприкінці 1960-х на початку 1970-х (існують посилання на раніші дослідження). Еволюційні алгоритми можна поділити на три групи:<ref name="bioinsp">{{Cite book 
| author = Olariu Stephan, Zomaya Albert Y.
| title = Handbook of Bioinspired Algorithms and Applications (Chapman  Hall/Crc Computer  Information Science)
| date = 
| publisher = Chapman  Hall/CRC
| location = 
| isbn = 1-58488-475-4
| pages = 
}}</ref>
* [[Еволюційне програмування]]: фокусується більше на адаптації індивідів, аніж на еволюції генетичної інформації. Зазвичай, еволюційне програмування застосовує безстатеве розмноження та мутації, тобто, внесення невеликих змін в поточний розв'язок та методи селекції основані на прямій конкуренції.
* [[Еволюційна стратегія|Еволюційні стратегії]] (ЕС): Важливою особливістю еволюційних стратегій є використання само-адаптивних механізмів для контролю процесу мутації. Ці механізми зосереджені не лише на еволюції шуканих розв'язків, а й на еволюції параметрів мутації.
* [[Генетичний алгоритм]] (ГА): Основною особливістю генетичних алгоритмів є використання оператора рекомбінації (схрещення) як основного механізму пошуку. Це ґрунтується на припущенні, що частини оптимального розв'язку можуть бути знайдені незалежно та рекомбіновані для отримання кращого розв'язку.

== Застосування ==

Еволюційні алгоритми знайшли широке застосування. Однією з найпоширеніших галузей застосування є [[комбінаторна оптимізація]]. Так, еволюційні алгоритми з успіхом було застосовано для розв'язання класичних [[NP-повна задача|NP-повних проблем]], таких як [[задача комівояжера]], [[задача пакування рюкзака]], розбиття чисел, максимальна незалежна множина та [[розфарбовування графів]].<ref name="bioinsp" />

До інших не класичних задач, для розв'язання яких застосовано еволюційні алгоритми, належать планування, складання розкладів, обчислення маршрутів, задачі розташування та транспортування. Також еволюційні алгоритми використовують для оптимізації структур та [[електронна схема|електронних схем]], в [[медицина|медицині]] та в [[економіка|економіці]].

В останні роки активно розвивається використання еволюційних алгоритмів для передбачення кристалічних структур з допомогою програмного забезпечення [https://web.archive.org/web/20180201112504/http://uspex.stonybrook.edu/uspex.html USPEX]. Приклади передбачених структур і матеріалів можна знайти на сайті [http://www.uspex-team.org/en/research] {{Webarchive|url=https://web.archive.org/web/20180214060237/http://uspex-team.org/en/research |date=14 лютого 2018 }}

Можливість використання еволюційних алгоритмів у галузі музики активно досліджується насамперед у [[Австрія|Австрії]], а саме при спробі моделювання та відтворення гри на музичних інструментах видатними особистостями різних епох.<ref>{{Cite web |url=http://www.insota.com/fileadmin/publications/Evolutionary-Search-for-Musical-Parallelism.pdf |title=Madsen, S. T. and Widmer, G.: ''Evolutionary Search for Musical Parallelism'', Applications of Evolutionary Computing, proceedings of the EvoWorkshops 2005, LNCS 3449 p. 488—497, Lausanne, Switzerland, 30 March — 1 April 2005. Springer Verlag. |accessdate=20 березня 2013 |archive-date=7 квітня 2014 |archive-url=https://web.archive.org/web/20140407064023/http://www.insota.com/fileadmin/publications/Evolutionary-Search-for-Musical-Parallelism.pdf }}</ref>

== Примітки ==
{{reflist}}
{{refbegin}}
{{refend}}

== Література ==

* {{книга
|автор          = Емельянов В. В., Курейчик В. В., Курейчик В. М.
|заголовок      = Теория и практика эволюционного моделирования
|відповідальний = 
|серія          = 
|посилання      = 
|видання        = 
|місце          = М
|видавництво    = Физматлит
|рік            = 2003
|том            = 
|сторінок       = 432
|isbn           = 5-9221-0337-7
|тираж          = 
}}
* {{книга
|автор          = Курейчик В. М., Лебедев Б. К., Лебедев О. К.
|заголовок      = Поисковая адаптация: теория и практика
|відповідальний = 
|серія          = 
|посилання      = 
|видання        = 
|місце          = М
|видавництво    = Физматлит
|рік            = 
|том            = 
|сторінок       = 272
|isbn           = 5-9221-0749-6
|тираж          = 
}}
* {{книга
|автор          = Гладков Л. А., Курейчик В. В., Курейчик В. М.
|заголовок      = Генетические алгоритмы: Учебное пособие
|відповідальний = 
|серія          = 
|посилання      = 
|видання        = 2-е изд.
|місце          = М
|видавництво    = Физматлит
|рік            = 2006
|том            = 
|сторінок       = 320
|isbn           = 5-9221-0510-8
|тираж          = 
}}
* {{книга
|автор          = Гладков Л. А., Курейчик В. В, Курейчик В. М. и др.
|заголовок      = Биоинспирированные методы в оптимизации: монография
|відповідальний = 
|серія          = 
|посилання      = 
|видання        = 
|місце          = М
|видавництво    = Физматлит
|рік            = 2009
|том            = 
|сторінок       = 384
|isbn           = 978-5-9221-1101-0
|тираж          = 
}}
* {{книга
|автор          = Рутковская Д., Пилиньский М., Рутковский Л.
|частина        = 
|заголовок      = Нейронные сети, генетические алгоритмы и нечеткие системы
|оригінал       = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte
|посилання      = 
|відповідальний = 
|видання        = 2-е изд.
|місце          = М
|видавництво    = Горячая линия-Телеком
|рік            = 2008
|том            = 
|сторінки       = 
|сторінок       = 452
|серія          = 
|isbn           = 5-93517-103-1
|тираж          = 
}}

== Посилання ==

* [http://cs.gmu.edu/~sean/book/metaheuristics/ Sean Luke, «Essentials of Metaheuristics»] {{Webarchive|url=https://web.archive.org/web/20111103010328/http://cs.gmu.edu/~sean/book/metaheuristics/ |date=3 листопада 2011 }}, 2009 (225 p). Free open text.
* [http://www.gp-field-guide.org.uk/ A Field Guide to Genetic Programming] {{Webarchive|url=https://web.archive.org/web/20150808114142/http://www.gp-field-guide.org.uk/ |date=8 серпня 2015 }} by Poli, Langdon, and McPhee. Available as a free PDF, or in printed form from Lulu.com.
* [http://www.csit.narod.ru/subject/mag_SShI/mono.pdf Субботін С. О., Олійник А. О., Олійник О.&nbsp;О.&nbsp;Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С.&nbsp;О.&nbsp;Субботіна.&nbsp;— Запоріжжя: ЗНТУ, 2009.&nbsp;— 375 с.] {{Webarchive|url=https://web.archive.org/web/20131105131336/http://www.csit.narod.ru/subject/mag_SShI/mono.pdf |date=5 листопада 2013 }}
* [http://algolist.manual.ru/ai/ga/ga1.php Популярно о генетических алгоритмах] {{Webarchive|url=https://web.archive.org/web/20080616064508/http://algolist.manual.ru/ai/ga/ga1.php |date=16 червня 2008 }}
* [https://web.archive.org/web/20100614094926/http://www.artint.com.ua/index_a.htm Основи теорії й застосування еволюційних алгоритмів у практичних застосунках]

== Див. також ==
{{Портал|Математика}}

* [[Багатокритеріальна оптимізація]]
* [[Еволюція]]

{{Штучний інтелект}}
{{Методи оптимізації}}
{{Math-stub}}

[[Категорія:Еволюційні алгоритми]]
[[Категорія:Штучний інтелект]]