- Принцип генетических алгоритмов
- Области применения ГА
- Плюсы и минусы ГА
- Примеры формирования ботов
- Примеры различных функций скрещивания и мутации
- Что влияет на сходимость ГА
- Особенности подбора архитектуры нейронной сети с помощью ГА
Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Области применения генетических алгоритмов:
• автоматизации решения оптимизационных задач науки и техники
• изучение и моделирования процессов естественной эволюции
• алгоритмизация перебора гиперпараметров нейросетей
• боты, роботы, агенты (обучение)
• предобработка данных
• планирование
Преимущества ГА
1. ГА работают с кодами, представляющих собой формализованный вид набора параметров, являющихся аргументами целевой функции. Интерпретация этих кодов происходит только перед началом работы алгоритма и после его завершения. В процессе работы ГА манипуляции с кодами происходят независимо от их смыслового содержания, т.е. код рассматривается просто как битовая строка.
2. При реализации процедуры поиска ГА обрабатывает одновременно несколько точек поискового пространства, а не переходит последовательно от точки к точке, как в традиционных методах. Это позволяет преодолеть опасность попадания в локальный экстремум полимодальной целевой функции. Использование нескольких точек одновременно значительно снижает вероятность такого события.
3. В процессе работы ГА не используют никакой дополнительной информации кроме данных об области допустимых значений параметров и целевой функции в произвольной точке, что повышает скорость их работы.
4. Для порождения новых точек поискового пространства одновременно ГА использует как вероятностные, так и детерминированные правила, что дает значительно больший эффект, чем каждый из этих методов в отдельности.
К недостаткам ГА следует отнести следующее:
· не гарантируется получение оптимального решения;
· эффективно сформулировать задачу, определить критерий отбора хромосом (задать код) и другие параметры ГА может только специалист;
· постановка задачи в терминах ГА не дает возможности проанализировать статистическую значимость получаемого с их помощью решения;
· достаточно высокая вычислительная ресурсоемкость ГА приводит к тому, что в ходе моделирования эволюции многие решения отбрасываются как неперспективные;
· при временной сложности в среднем ниже, чем у лучших конкурирующих алгоритмов, но не более (получено на основе экспериментальных данных), чем на один порядок;
· невысокая эффективность на заключительных фазах моделирования эволюции, объясняемая тем, что механизмы поиска ГА не являются жестко ориентированными на скорейшее попадание в локальный оптимум;
· не решенными остаются и некоторые другие вопросы, например проблема самоадаптация ГА.
Говоря об эволюционных вычислениях в целом, следует отметить, что они, как и всякий метод, использующий элемент случайности, не гарантируют обнаружения глобального экстремума целевой функции (или оптимального решения) за определенное время. Основное их преимущество состоит в том, что они позволяют найти более «хорошее» решение трудной задачи за меньшее время, чем другие методы. Эволюционные вычисления не являются оптимальным средством для решения любых задач, тем не менее, они достаточно эффективны в области инженерного проектирования, планирования, маршрутизации, прогнозирования и др.
Следует отметить, что эволюционные вычисления представляют собой скорее подход к решению задач оптимизации, чем алгоритм. Вследствие этого они требуют адаптации к каждому конкретному классу задач путем выбора определенных характеристик и параметров. В настоящее время наблюдается взаимное проникновение различных парадигм эволюционных вычислений и их сращивание в единую концепцию.
Изначально боты формируются из случайных значений. В процессе эволюции образуются новые боты путем скрещивания. Выбор родителей опять таки может быть случаен.
если значения одинаковые, выбор будет из одного значения;
а если значения разные, то будет выбрано случайное значение гена из 2х значений.
Таким образом от двух родителей мы создадим нового бота
Мутация – замена определенных процентов генов на противоположный.
На сходимость алгоритма влияет размер популяции и решаемая задача (?)
Для подбора нейросети создаются боты гены в которых отвечают за какие-либо параметры нейросети, например наличие отсутствие слоя, количество нейронов в слое, количество фильтров и т.д.
Литература
http://lc.kubagro.ru/aidos/aidos04/1.3.6.htm
https://www.keldysh.ru/pages/BioCyber/Lectures/Lecture10/Lecture10.html
https://habr.com/ru/post/128704/
0