Еволюційний алгоритм

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Класифікація алгоритмів[ред.ред. код]

Моделювання еволюції можна розділити на дві категорії:[Джерело?]

  1. Системи, які використовують лише еволюційні принципи. Вони успішно використовувалися для завдань виду функціональної оптимізації і можуть легко бути описані на математичній мові. До них відносяться еволюційні алгоритми, такі як еволюційне програмування, генетичні алгоритми, еволюційні стратегії.
  2. Системи, які є біологічно реалістичніші, але які не виявилися корисними в прикладному сенсі. Вони більше схожі на біологічні системи і менш направлені на вирішення технічних завдань. Вони володіють складною і цікавою поведінкою, і, мабуть, незабаром отримають практичне вживання. До цих систем відносять так зване штучне життя.

Еволюційні алгоритми, в сучасному вигляді, з'явились в кінці 1960-тих на початку 1970-тих (існують посилання на раніші дослідження). Еволюційні алгоритми можна поділити на три групи:[1]

  • Еволюційне програмування: фокусується більше на адаптації індивідів, аніж на еволюції генетичної інформації. Зазвичай, еволюційне програмування застосовує безстатеве розмноження  та мутації, тобто, внесення невеликих змін в поточний розв'язок та методи селекції основані на прямій конкуренції.
  • Еволюційні стратегії (ЕС): Важливою особливістю еволюційних стратегій є використання само-адаптивних механізмів для контролю процесу мутації. Ці механізми зосереджені не лише на еволюції шуканих розв'язків, а й на еволюції параметрів мутації.
  • Генетичні алгоритми (ГА): Основною особливістю генетичних алгоритмів є використання оператора рекомбінації (схрещення) в якості основного механізму пошуку. Це грунтується на припущенні, що частини оптимального розв'язоку можуть бути знайдені незалежно та рекомбіновані для отримання кращого розв'язку.

Застосування[ред.ред. код]

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

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

Можливість використання еволюційних алгоритмів у галузі музики активно досліджується насамперед у Австрії, а саме при спробі моделювання та відтворення гри на музичних інструментах видатними особистостями різних епох. [2]

Примітки[ред.ред. код]

Література[ред.ред. код]

  • Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М: Физматлит, 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

Посилання[ред.ред. код]

Дивіться також[ред.ред. код]