Что именно представляют собой генетические алгоритмы и для каких задач они хороши?

Я заметил, что несколько вопросов на этом сайте упоминают генетические алгоритмы, и это заставило меня понять, что я не очень много знаю о них.

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

Не могли бы вы дать мне краткое объяснение, желательно с каким-то практическим примером, иллюстрирующим основные принципы?

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

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

Индивидуум закодирован как генотип , который может иметь любую форму, такую ​​как ** битный вектор ( генетические алгоритмы ) или вектор реального (стратегии эволюции). Каждый генотип превращается в фенотип при оценке индивидуума, то есть, когда рассчитывается его приспособленность. В некоторых случаях фенотип идентичен генотипу: это называется прямым кодированием, В противном случае кодирование называется косвенным. Например, предположим, что вы хотите оптимизировать размер прямоугольного параллелепипеда, определяемого его длиной, высотой и шириной. Чтобы упростить пример, предположим, что эти три величины являются целыми числами от 0 до 15. Затем мы можем описать каждую из них с помощью 4-разрядного двоичного числа. Примером потенциального решения может быть генотип 0001 0111 01010. Соответствующий фенотип представляет собой параллелепипед длиной 1, высотой 7 и шириной 10.

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

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

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

Генетический алгоритм - это алгоритм, который случайным образом генерирует ряд попыток решения проблемы. Этот набор попыток решения называется «население».

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

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

Источником вдохновения для этого послужила теория эволюции; самые подходящие решения выживают и размножаются.

Пример 1

Предположим, вы искали наиболее эффективный способ вырезать несколько фигур из куска дерева. Вы хотите тратить как можно меньше древесины.

Ваша попытка решения будет случайным расположением этих фигур на вашем куске дерева. Пригодность будет определяться тем, как мало древесины останется после обрезки форм, следующих за этой договоренностью.
Чем меньше древесины осталось, тем лучше попытка решения.

Пример 2

Предположим, вы пытались найти многочлен, который проходит через несколько точек. Ваши попытки решения будут случайными полиномами.
Чтобы определить пригодность этих многочленов, вы определяете, насколько хорошо они соответствуют заданным точкам. (В этом конкретном случае вы, вероятно, использовали бы метод наименьших квадратов, чтобы определить, насколько хорошо полином соответствует точкам). В течение ряда испытаний вы получите многочлены, которые лучше соответствуют точкам, пока у вас не будет многочлена, который достаточно близко соответствует точкам.

Этот ответ требует практического примера того, как его можно использовать, и я постараюсь привести его в дополнение к другим ответам. Кажется, они очень хорошо объясняют, что такое генетический алгоритм. Итак, это даст пример.

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

Вот демонстрация, которую я сделал, которая, несмотря на то, что она плохо закодирована, может помочь вам понять. http://khrabanas.github.io/projects/evo/evo.html Нажмите кнопку эволюции и возитесь с целями.

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

Генетический алгоритм пытается создать своего рода «нейронную сеть», которая, принимая RGB, даст выходной цвет. Сначала это генерирует случайную популяцию. Затем берется 3 случайных члена из популяции, выбирается один с наименьшей пригодностью и удаляется из популяции. Пригодность равна разнице в квадрате верхней цели + разница в квадрате нижней цели. Затем он объединяет два оставшихся и добавляет ребенка в то же место в популяции, что и мертвый член. Когда происходит спаривание, есть вероятность мутации. Эта мутация изменит одно из значений случайным образом.

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

Здесь есть много хороших ответов, объясняющих, что такое генетические алгоритмы, и приводятся примеры приложений. Я добавляю несколько советов общего назначения о том, для чего они хороши, но также и о случаях, когда их НЕ следует использовать. Если мой тон кажется резким, то это потому, что использование GA в любом из случаев в разделе «Неправильно» приведет к тому, что ваша статья будет немедленно отклонена из любого журнала верхнего уровня.

Во-первых, ваша проблема ДОЛЖНА быть проблемой оптимизации. Вам нужно определить «фитнес-функцию», которую вы пытаетесь оптимизировать, и у вас должен быть способ ее измерить.

Хорошо:

• Функции кроссовера просты в определении и естественны : при работе с определенными видами данных функции кроссовера / мутации могут быть легко определены. Например, строки (например, последовательности ДНК или гена) можно легко мутировать, сращивая две строки-кандидата, чтобы получить новую (вот почему природа использует генетические алгоритмы!). Деревья (такие как филогенетические деревья или деревья разбора) также могут быть сращены путем замены ветви одного дерева веткой другого. Формы (например, крылья самолета или формы лодки) можно легко видоизменять, рисуя сетку на форме и комбинируя различные участки сетки от родителей, чтобы получить ребенка. Обычно это означает, что ваша проблема состоит из разных частей, и объединение частей из разных решений является верным подходящим решением.
  • Это означает, что если ваша задача определена в векторном пространстве, где координаты не имеют какого-либо особого значения, GA не являются хорошим выбором. Если вам трудно сформулировать вашу проблему как GA, это того не стоит.
• Оценка черного ящика : если для кандидата ваша физическая функция оценивается вне компьютера, ГА - хорошая идея. Например, если вы тестируете форму крыла в воздушном туннеле, генетические алгоритмы помогут вам создать хорошие формы-кандидаты, которые можно попробовать.
  • Исключение: симуляции . Если ваша функция пригодности измеряет, насколько хорошо работает конструкция форсунки и требует моделирования динамики жидкости для каждой формы форсунки, GA могут хорошо работать для вас. Они также могут работать, если вы моделируете физическую систему во времени и заинтересованы в том, насколько хорошо ваш проект работает в ходе операции, например. моделирование моделей локомоции . Однако методы, которые используют уравнения с частными производными в качестве ограничений, разрабатываются в литературе, например. Оптимизация PDE ограничена , так что это может измениться в будущем.

Не подходит:

• Вы можете рассчитать градиент для своей функции: если у вас есть доступ к градиенту вашей функции, вы можете выполнить градиентное снижение, что в целом гораздо эффективнее, чем GA. Градиентный спуск может иметь проблемы с локальными минимумами (как и ГА), но многие методы были изучены, чтобы смягчить это.
• Вы знаете фитнес-функцию в закрытом виде : тогда вы, вероятно, можете рассчитать градиент. Во многих языках есть библиотеки, поддерживающие автоматическое разграничение , поэтому вам даже не нужно делать это вручную. Если ваша функция не дифференцируема, то вы можете использовать субградиентный спуск .
• Ваша проблема оптимизации имеет известную форму, такую ​​как линейная или квадратичная программа : GA (и методы оптимизации черного ящика в целом) очень неэффективны с точки зрения количества кандидатов, которые они должны оценить, и их лучше избегать, если это возможно.
• Пространство вашего решения невелико : если вы можете эффективно распределить пространство поиска по сетке, вы можете гарантировать, что нашли лучшее решение, и можете сделать контурные графики пространства решения, чтобы увидеть, есть ли регион, который вам нужно изучить дальше.

Наконец, если вы рассматриваете GA, рассмотрите более позднюю работу в Evolutionary Strategies. Я склонен к CMA-ES , который, я думаю, является хорошим простым алгоритмом, который фиксирует понятие градиента в ландшафте фитнеса так, как это не делают традиционные GA.

Как отмечалось в другом ответе, все, что вам нужно для применения Генетических Алгоритмов (ГА), это представить потенциальное решение вашей проблемы в форме, которая подвержена кроссоверу и мутации. В идеале, функция фитнеса будет обеспечивать некоторую плавную обратную связь о качестве решения, а не просто «иголку в стоге сена».

Вот некоторые характеристики проблем, для которых подходят Генетические Алгоритмы (и вообще Метаэвристика в целом):

• NP-complete - число возможных решений проблемы является экспоненциальным, но проверка пригодности решения является относительно дешевой (технически, с полиномом времени в размере входных данных).
• Черный ящик - ГА работают достаточно хорошо, даже если у вас нет особенно информированной модели решаемой проблемы. Это означает, что эти подходы также полезны в качестве подхода «быстрого прототипирования» для решения проблем.

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

Более подробно о применимости ГА дано в известной ранней статье «Что делает проблему трудной для генетического алгоритма?»