Решите кроссворд с генетическим алгоритмом, фитнессом, мутацией

Question

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

Если у меня есть загадка (# - блок, 0 - пустое место)

#000
00#0
#000

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

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

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

Теперь функция пригодности: я пересекаю матрицу как по горизонтали, так и по вертикали: если ятогда найдите слово FITNESS + = word.lengh + 1

Если я найду строку, являющуюся частью некоторого слова, тогда FITNESS + = word.length / (puzzle_size * 4).В любом случае он должен давать значение от 0 до 1. Таким образом, он может найти «to» из «tool» и объявить X в FITNESS, а затем сразу после того, как найдет «too» из «tool» и добавить еще один Y в FITNESS.

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

Answer 1

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

Answer 2

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

Вы не указываете вероятность мутации, но когда вы делаете мутацию, 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();
    }
}