Эволюционные алгоритмы

Эволюционные алгоритмы — это направление в компьютерных науках, которое использует принципы биологической эволюции для решения задач искусственного интеллекта. Основной принцип биологической эволюции — это сочетание мутаций, естественного отбора и воспроизводства. Хотя эволюционные алгоритмы и пытаются имитировать биологическую эволюцию, они более схожи с искусственным разведением животных, то есть скрещиванием самых лучших представителей, отбором их лучших потомков и повторным скрещиванием уже этих потомков.

Идея эволюционных алгоритмов была предложена в конце 1960-х — начале 1970-х годов, когда ученые впервые попытались симулировать биологическую эволюцию на компьютере и использовать ее принципы для решения задач. Было предложено четыре основных типа алгоритмов, и все они работали по схожей схеме: сначала оценивалась эффективность решений, а после этого самые эффективные решения «разводились», подобно домашним животным, в результате чего получалось следующее поколение. Более того, скрещивания и мутации решений позволяли им приспосабливаться к окружающей среде (целевой функции).

Проблемы, которые решаются при помощи эволюционных алгоритмов, — это проблемы оптимизации, то есть постепенного улучшения какой-то вещи исходя из заданных критериев. Эволюционные алгоритмы используются в ситуации, когда можно сформулировать критерии хорошего решения, но трудно его придумать. Каждая задача может быть оптимизирована через улучшение входящих в нее компонентов. Например, наша задача — сделать текст более грамотным. Грамотный текст — это тот, который соответствует набору грамматических правил (в нашем случае — компонентов). Таким образом, наша задача оптимизируется, когда текст становится более грамотным с точки зрения грамматики, орфографии и пунктуации.

Все начинается со случайного набора решений, все из которых оцениваются по заданным критериям, и из них отбираются лучшие, которые проходят на следующую фазу. Следующая фаза — это либо скрещивание, либо мутация этих решений. Скрещивание — это комбинация двух наилучших решений: первого, у которого самый лучший показатель — Х (например, пунктуация), со вторым, у которого самый лучший — Y (например, орфография). В свою очередь, мутация — это внесение случайно сгенерированного небольшого изменения в какую-либо характеристику. И скрещивание, и мутация повторяются до тех пор, пока каждое новое поколение становится лучше, чем предыдущее.

Основная проблема эволюционных алгоритмов — это определение того, какое решение можно назвать оптимальным. Обычно мы определяем это исходя из предположения о том, что новые хорошие решения будут похожи на уже известные хорошие решения. Эволюционные алгоритмы применяются, например, в гейм-дизайне, а также в так называемом эволюционном искусстве, где картины генерируются компьютером на основании того, что было отмечено пользователем как понравившееся.

Комментарии: