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

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

Вы спрашиваете о «массиве символов» и о том, кто ваши родители и потомство, как бы вы сделали скрещивание, мутацию и т. Д. Я думаю, что, возможно, вас смущает этот набор символов. Не думайте об этом как о массиве символов — это массив слов. Это важно, потому что вы не хотите пересекать границы слов или менять буквы внутри слова посредством мутации. Вы хотите перетасовать слова. Итак, вместо того, чтобы иметь дело со словами, давайте воспользуемся несколько иным (но эквивалентным) подходом.

Пронумеруем каждое из ваших 2n слов от 1 до 2n. Чтобы сгенерировать решение-кандидат, мы просто выбираем n случайных чисел от 1 до 2n (без замены). Случайно выбранные слова становятся строками вашей матрицы. Итак, если это слова AGE,AGO,BEG,CAB,CAD,DOG, мы выбираем три случайным образом и получаем, например, 2, 3 и 5 (что дает хромосому 235) или AGO,BEG,CAD.

Это дает матрицу

AGO
BEG
CAD

Теперь подсчитаем, сколько из 2n входных слов встречается в матрице. В данном случае их всего три, так как ни один из столбцов не содержит правильных слов. Ваша пригодность для ввода 235 равна 3. Однако ввод 416 работает — его пригодность равна 6.

Чтобы сгенерировать популяцию, вы просто генерируете N случайных наборов из трех чисел (без повторения) от 1 до 2n. При численности населения 4 вы можете получить

142
354
624
241

Это дает вам четыре различных возможных решения:

142 = AGE
      CAB
      AGO

354 = BEG
      CAD
      CAB

624 = DOG
      AGO
      CAB

241 = AGO
      CAB
      AGE

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

Мутация — это просто замена одного числа другим или перестановка двух чисел местами в кодировке.

Вы говорите, что должны использовать GA, так что вы можете остановиться здесь и попробовать что-то подобное. Это вряд ли будет работать очень хорошо по нескольким причинам. Во-первых, в фитнес-функции будет много плато. Почти каждый возможный ответ одинаково неверен, поэтому для ГА не существует большого градиента. Это иголка в стоге сена. Вы можете попытаться изменить способ оценки значений пригодности, чтобы несколько облегчить это. Например, я знаю, что в вашем наборе примеров только одно слово начинается с D, поэтому любое решение с DOG в первой строке автоматически неверно. Я мог начислять баллы решениям, которые давали более «правдоподобные» неправильные ответы. Однако, в целом, ГА будет сложно решить эту проблему эффективно.

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

Некоторые варианты:

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

CABAGEDOG

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

Или пусть представление состоит из трех слов, по одному на каждую строку.

   CAB
   AGE
   DOG

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