Решаем головоломки шаманов в World of Warcraft генетическим алгоритмом07.09.2016 02:03

82678d0867cb401e93b78fc35d8275ee.png Привет, Хабражитель!
Не так давно, вышло очередное дополнение 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);
   } );
}

Выживание


Селекция индивидов по приспособленности в результате которой, остается ограниченное число наиболее приспособленных. В нашем случае мы сортируем всех индивидов по убыванию значения фитнесс функции и оставляем первых L 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 );
}

Вооружившись Webpack, React-Redux и, Material-UI за пару часов получилось, вот такое простенькое веб приложение:


bbc42f0274d045ba89e7fa2ec87a04fb.png

Вычисления происходят на стороне Web Worker в файле breeder.js, что бы снять нагрузку с UI.


  • Посмотреть на готовое решние можно здесь
  • Исходники на GitHub
  • Все замеченные и не замеченные ошибки сюда

Комментарии (0)

© Habrahabr.ru