Блог

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

Если у меня есть головоломка (# — блок, 0 — пустое пространство)

 #000
00#0
#000
  

и коллекция слов, которые являются кандидатами на решение этой головоломки.
Моя ДНК — это просто матрица в виде одномерного массива.

Моя первая группа людей имеет случайно сгенерированные ДНК из пула букв, который содержит my words.

Я делаю выбор с помощью roulette-selection. Есть некоторые параметры, касающиеся вероятности сочетания и мутаций, но если мутация произойдет, я всегда буду изменять 25% ДНК. Я заменяю его случайными буквами из моего пула писем.(это может иметь негативные последствия, поскольку мутации могут разрушить уже сформированные слова)

Теперь функция пригодности: я просматриваю матрицу как по горизонтали, так и по вертикали: если я нахожу слово, то ПРИГОДНОСТЬ = word.длина 1

Если я нахожу строку, которая является частью некоторого слова, тогда ПРИГОДНОСТЬ = word.длина / (puzzle_size*4) . В любом случае это должно давать значение от 0 до 1. Таким образом, он может найти «to» из «tool» и добавить X в FITNESS, затем сразу после этого он находит «too» из «tool» и добавляет еще один Y в FITNESS.

Мои поколения на самом деле не улучшаются с течением времени. Они кажутся случайными. Таким образом, даже после 400 поколений с пулом 1000-2000 (эти цифры на самом деле не имеют значения) я получаю решение с 1-2 словами (из 2 или 3 букв), когда в решении должно быть 6 слов.

Я думаю, что ваша функция пригодности может быть нечетко определена. Я бы настроил это так, чтобы каждая строка имела двоичный уровень пригодности. Либо строка подходит, либо нет. (например, строка является словом или это не слово) Тогда общая пригодность решения будет равна #fit rows / всего строк (как по горизонтали, так и по вертикали). Кроме того, возможно, вы меняете слишком много днк, я бы ввел эту переменную и поэкспериментировал с ней.

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

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

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

 for(i=0; i<chromosome.length();   i) {
    // random generates double in the range [0, 1)
    if(random() < 1.0/chromosome.length()) {
       chromosome[i] = pick_random_letter();
    }
}