Чем эволюционные алгоритмы отличаются друг от друга?
Познакомьтесь с Evolutionary Algorithm Playground, интерактивным веб-приложением для сравнения методов Genetic Algorithm и Particle Swarm.
Эволюционные вычисления — это собирательное название ряда методов решения проблем, основанных на принципах биологической эволюции, таких как естественный отбор и генетическое наследование. [1]
Двумя из этих методов являются генетические алгоритмы и оптимизация роя частиц.
Генетический алгоритм (ГА) основан на эволюционной теории, разработанной Чарльзом Дарвином. На протяжении поколений к популяции применяются процессы отбора, кроссовера, мутации и элитарности, чтобы найти наиболее приспособленного человека.
Оптимизация роя частиц (PSO) — это вычислительный метод, основанный на концепции роев, таких как косяки рыб и стаи птиц. Он итеративно ищет наиболее подходящего человека в кластере.
Оба алгоритма применяются к проблемам оптимизации. Задача оптимизации — это задача поиска лучшего решения из всех возможных решений. В зависимости от задачи лучшим решением могут быть аргументы, которые максимизируют или минимизируют результат целевой функции. Примерами максимизируемых количеств являются прибыль, производительность, продажи, рост и т. д. Минимизируемыми количествами могут быть потери, материальные затраты и многие другие.
С учетом этого была разработана Игровая площадка эволюционного алгоритма.
https://evo-algorithm-playground.herokuapp.com/
Это полностью основанное на Python веб-приложение, которое позволяет пользователям настраивать различные параметры и видеть, как работают алгоритмы. Алгоритмы были созданы с нуля с использованием Numpy. Приложение было разработано с использованием Streamlit и развернуто с помощью Heroku.
Цель приложения — улучшить понимание биологических алгоритмов в дружественной и интерактивной форме.
Давайте посмотрим на алгоритмы.
Генетический алгоритм
Интервал поиска (задается пользователем) преобразуется в двоичное представление (количество бит представления также задается пользователем). Новая популяция создается случайным образом. Помимо количества битов представления, он также учитывает количество людей и размер проблемы (оба устанавливаются пользователем). Популяция оценивается с помощью тестовой функции, и выполняются процедуры отбора, кроссовера, мутации и элитизма. Это повторяется итеративно, пока не будет достигнуто количество поколений.
В Evolutionary Algorithm Playground реализованы следующие методы:
Выбор:
- Рулетка;
- Журнал рулетки: в этом подходе вероятности рулетки обрабатываются функцией журнала. Это уменьшает разницу между индивидуальными баллами, обеспечивая большее разнообразие населения;
- Турнир;
Кроссовер:
- Единая точка
Мутация:
- Единая точка — метод А. этот подход касается каждого человека. Он оценивает каждый бит индивидуума и инвертирует его, если случайно сгенерированное число превышает вероятность мутации (ранее установленную пользователем). Этот подход допускает множественные мутации на человека;
- Единая точка — метод B: при этом подходе отбирается несколько человек. Количество особей — это размер популяции, умноженный на вероятность мутации (предварительно установленную пользователем). Позже случайно сгенерированная битовая позиция инвертируется;
Элитарность:
Количество особей (данное размером населения, умноженным на вероятность элитарности) останется для следующего поколения. Это самые близкие к оптимальным особи. Столько же особей будет отброшено. Это менее оптимальные особи.
Оптимизация роя частиц
Популяция строится в пределах интервала поиска (задается пользователем). В отличие от генетического алгоритма, популяция непрерывна. Он также учитывает количество людей и масштаб проблемы (оба значения устанавливаются пользователем).
Отдельные особи роеподобной популяции будут индивидуально оцениваться с помощью функции тестирования. После оценки они будут двигаться в соответствии с когнитивной и социальной скоростью. На скорость также влияет вес инерции (установленный пользователем), который обычно уменьшается в процессе эволюции. На когнитивную скорость влияет параметр доверия к себе, а на скорость общения — параметр социального доверия.
Это повторяется итеративно, пока не будет достигнуто количество поколений.
Лица, вышедшие за пределы максимального диапазона интервалов, обрезаются до пределов интервала.
Если вы хотите сотрудничать с проектом, не стесняйтесь обращаться.
Код проекта:
Мой профиль LinkedIn:
[1] А. Э. Эйбен, Джеймс Э. Смит, Введение в эволюционные вычисления (2003), Springer-Verlag Berlin Heidelberg.
