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

Эволюционные алгоритмы — направление в искусственном интеллекте (раздел эволюционного моделирования), которое использует и моделирует процессы естественного отбора.

Виды алгоритмов

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

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

Эволюционные алгоритмы успешно использовались для задач типа функциональной оптимизации и могут легко быть описаны на математическом языке.

Отрасли использования

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