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

Question

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

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

#000
00#0
#000

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

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

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

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

Если я найду строку, которая является частью какого -то слова, то Fitness += Word.length / (buzzle_size*4). В любом случае, он должен дать значение от 0 до 1., поэтому он может найти «от« инструмента »и рекламы X к фитнесу, затем сразу после того, как он находит« тоже »из« инструмента »и добавляет еще один Y к фитнесу.

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

Answer 1

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

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();
    }
}