Вирішуємо головоломки шаманів в World of Warcraft генетичним алгоритмом

Привіт, Хабражитель!
Не так давно, вийшло чергове доповнення 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 за пару годин вийшло ось таке простеньке веб додаток:

Обчислення відбуваються на стороні Web Worker у файлі
breeder.js
, що б зняти навантаження з UI.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.