Эволюционный алгоритм – объяснение выборов

Эволюция выборов понимание с помощью эволюционного алгоритма

Понять, что происходит, с помощью визуализации и кода

Изображение, созданное DALL·E 3 на основе запроса «Нарисуйте научно-фантастическое изображение, которое отображает отбор родительских элементов в эволюционном алгоритме»

Задача коммивояжера (TSP) — хорошо известная np-сложная проблема, которая имеет очевидные практические применения в реальной жизни. Например, она полезна, если вы планируете поездку по Европе и оцениваете время путешествия от точки к точке между местами.

Только с 30 городами возможно более 1⁰³⁰ возможных перестановок. Решить TSP с 30 городами полным перебором не представляется возможным (количество зерен песка на Земле составляет «только» 1⁰¹⁹).

К концу этой статьи решение таких задач с помощью эволюционного алгоритма (EA) станет для вас простым. Вы сможете получить такой результат самостоятельно.

Более важно то, что вы поймете, что именно происходит за кулисами и как каждый компонент (в частности, различные типы мутаций) способствуют решению.

1. Предложение ценности

Многие руководства неправильно используют слова Генетический Алгоритм (GA) и Эволюционный Алгоритм (EA) взаимозаменяемо.

GA, в своей канонической форме, включает следующие элементы [1]:1. Представление — битовые строки2a. Отбор родителей — пропорционально приспособленности2b. Рекомбинация — одноточечное скрещивание3. Мутация — инверсия бита4. Отбор выживших — следующее поколение

GA — подмножество EA.

В данном руководстве мы рассмотрим аспекты EA, которые не обсуждаются в GA. В частности, мы сосредоточимся на аспектах, относящихся к представлению перестановок, объясняя с помощью наглядной визуализации и кода.

2. Определения

Прежде чем двигаться дальше, нам нужно четко понимать использование терминов [2].

Фенотипы

Решения в пределах исходного контекста проблемы. Они должны быть интерпретированы «как есть»…