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

Question

Отказ

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

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

/Отказ от ответственности

У меня есть n*2 слов длины п. Я должен сделать матрицу n^2, содержащую все эти слова. Слова могут быть тарабарщиной, но они должны иметь возможность соответствовать в этой матрице (это требование со стороны пользователя).

Таким образом AGE,AGO,BEG,CAB,CAD,DOG даст мне этот результат (1 из по меньшей мере 2 возможных):

C A B 
A G E 
D O G 

Я должен использовать эволюционный алгоритм. Таким образом, мне нужно найти способ закодировать мою информацию в хромосоме.

То, что я придумал:

Каждое слово появляется, имеет стартовую позицию в матрице и ориентации (слева направо или вверх-вниз). Таким образом, у меня есть [Word][Orientation][StartPosition], где начальная позиция [0][0]/[0][1]/[1][0] и т.п. (левая колонка и верхняя линия). Но у него есть ограничения, мне нужно подтвердить, что ориентация соответствует начальной позиции.

Проблема:

Хромосома должна быть возможно решением, тогда как это лишь часть раствора.

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

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

EDIT

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

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

Answer 1

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

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

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

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

Answer 2

Некоторые опции:

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

CABAGEDOG 

Тогда для фитнеса, просто дать на точки для каждого запрашиваемого слова, которые на самом деле в растворе.

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

CAB 
    AGE 
    DOG 

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