Разрешить несовместимые изменения кроссовера генетического алгоритма

Question

Я пытаюсь написать генетический алгоритм для фрагментов дорожки и думать о том, как реализовать мутацию/кроссовер. Цель состоит в том, чтобы развиваться: a) полный цикл и b) захватывающая поездка (у меня есть критерии для этого).

У меня есть около шестидесяти штук на выбор, но не все они совместимы друг с другом. Например, часть дорожки может быть оставлена ​​налево, а другая часть трека может быть заправлена ​​вправо.

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

Параллель для the popular "Hello World" example будет, вы пытаетесь сгенерировать любое действительное слово или любое действительное предложение. У английского есть правило (составленное для этого примера, не знаю, верно ли это), что согласный никогда не может следовать за Z. Должны ли вы разрешать только гласные мутировать после Z?

В этом смысл? Или вы должны просто разрешить все виды мутаций и отказаться от плохих?

Answer 1

Два подхода, которые Вы могли бы попробовать:

• управление «требование совместимости частей» как ограничение и использовать би-мерный вектор в качестве значения пригодности.

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

  Второго элемент стандартная базовая целевая функция.

  При сравнении двух значений пригодности:

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

  Таким образом, вы применили бы выборочное давление для решения невостребованных решений и внутри допустимой области (но для разведки допускается неосуществимое решение).

  Это подход, описанный в An Efficient Constraint Handling Method for Genetic Algorithms - Кальянмой Деб

• попробовать подход, аналогичный automated synthesis of analog electrical circuits by means of genetic programming.

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

  Возможно, функции в программе построения схемы деревья могут быть сгруппированы по совместимым сигнатурам, а метод strongly typed genetic programming может быть жизнеспособным.

Answer 2

Другой способ, на который ответил манлио, - использование косвенного кодирования. Вы можете спроектировать такую ​​кодировку, которая гарантирует достоверность всех решений. Посмотрите на Grammatical Evolution и способ кодирования решений или даже используйте его напрямую с грамматикой, которая описывает ваши решения.