
Ave $USER!
Не так давно, вышло очередное дополнение World of Warcraft Legion. Первым делом я принялся прокачивать шамана и был приятно удивлен получив артифактное оружие в оплоте шаманов. Я забрел к Мастеру головоломок Ло и увидел то, что вы подумали - головоломку.
Передо мной был квадрат из огненных и водных тотемов 5 на 5, после того как кликаешь на тотем, он меняется на противоположный, например водный на огненный или огненный на водный и так же меняет сверху, снизу, слева и справа. Необходимо сделать так, что бы все тотемы стали водными. После первого клика я понял, что срочно нужно написать решение для этой головоломки.
Задача стояла следующая: Дана матрица размерности N на M, каждая ячейка матрицы содержит либо 0 либо 1. При изменении значения ячейки матрицы на противоположное, автоматически меняются на противоположные значения на соседних ячейках сверху, снизу, слева и справа. Найти последовательность изменений ячеек, что бы матрица состояла только из нулей.
Сначала в голову пришла мысль о переборе всех возможных комбинаций с оптимизацией. Но это все скучно. И я решил написать генетический алгоритм решения задачи.
Немного теории
Для написания алгритма нам понадобится ввести поняия генов, генотипа, фитнес функции, мутация, поколения и выживания поколения.
Гены
Геном будем называть значение ячейки матрицы, т.е. это либо 1 либо 0
Генотип
Генотипом будем называть матрицу представленную в виде строки длинной L = N x M, которая будет содержать последовательно объединенные строки матрицы, каждый символ строки - это ген
Пример
[
[0,0,0,0,0],
[1,1,1,1,1],
[0,0,0,0,0],
[1,1,1,1,1],
[0,0,0,0,0]
]
Генотипом будет строка 0000011111000001111100000
, где L = 25
Фитнесс функция
Фитнесс функцией (Функцией приспособленности) назовем функцию, которая возвращает число от 0 до 1, чем ближе значение к 1 тем лучше преспособленность индивида. Остается вопрос, что же считать приспособленностью индивида. Для простоты можем обойтись количеством нулевых генов в генотипе разделенное на длину генотипа
function fitness(genotype) {
return genotype.replace(/1/g,'').length / genotype.length;
}
Мутация
Изменение одного гена в генотипе индивида. Т.к. по правилам игры меняются 5 ячеек матрицы (целевая и соседние), то одна мутация будет давать 5 новых индивидов.
const DIRECTIONS = [
{x: 0, y: 0},
{x: 1, y: 0},
{x:-1, y: 0},
{x: 0, y: 1},
{x: 0, y:-1}
];
function mutate(genotype) {
return DIRECTIONS.map( direction => {
const nextX = x + direction.x;
const nextY = y + direction.y;
return genotype.flip(nextX, nextY);
} );
}
Выживание
Селекция индивидов по приспособленности в результате которой, остается ограниченное число наиболее приспособленных. В нашем случае мы сортируем всех индивидов по убыванию значения фитнесс функции и оставляем первых N x M x 8
const maxGenerationSize = 400; // 5 * 5 * 8
function surviving(populations) {
return populations.sort( (a, b) => {
return b.fitness - a.fitness;
}).slice(0, maxGenerationSize);
}
Поколение
Множество индивидов оставшихся после “Выживания”. Причем самый первый индивид поколения и будет решением, если его приспособленость равна единице
Еще немного теории
Можно заметить, что после мутации очень часто можно получить ранее известный геном либо геном, полученный меньшим количеством мутаций, но с такой же или лучшей приспособленностью. Что бы такого не происходило, создадим хэш-таблицу геномов, ключом которой будет сам геном, а значением, массив из ячеек мутаций. В случае если этот геном уже встречался и количество ячеек мутаций не превосходит уже встречавшейся, создаем из него покаление.
Также легко заметить, что мы меняем на всем поле либо 3 либо 5 ячеек, т.е. фитнесс функция возвращает 1 только после значений
L - 3
и L - 5
. Для них, можно возращать значения фтнесс функции 0.999
, что бы увеличить их приспособленность
Пример Для марицы 5x5 значение фитнесс функции 1 будет при наличии всех 25 нулей в геноме, а им предшедствуют только либо 20 нулей либо 22
Весь цикл поиска решения можно представить в виде следующего кода
while ( generation++ < maxGenerationsCount && populations[0].fitness !== 1 ) {
populations = mutating( populations );
populations = surviving( populations );
}
В итоге получилось такое вот приложение