Генетический алгоритм

[Minoru]

Akon32 в начале контеста предлагал вместо A* использовать генетический алгоритм. Мы таки реализовали A*, но мне уже надоело бесуспешно тюнить его целевую функцию, так что я подумал-таки и про ГА.

Что нам понадобится:

• генератор решений
• мутатор решений
• скрещивалка решений
• функция починки решений, поломанных мутациями
• управляющая функция, которая будет скрещивать и мутировать топовые решения в надежде получить ещё лучшие

Генератор решений

В первом приближении просто random walk — на каждом шаге делает первое попавшееся действие, приводящее его в новое валидное состояние. Будет генерировать огромные решения, зато быстро.

Также при наличии решения от A* (файла .sol) можно подгружать и его — оно наверняка гораздо оптимальнее и будет отличной основой для мутаций и скрещиваний.

Мутатор решений

Делает одно из:

• удаляет произвольное количество действий с произвольной позиции в решении
• добавляет в произвольную позицию решения произвольное количество произвольных действий.

В результате не обязательно получится валидное решение, но на это у нас будет фиксер.

Скрещивалка решений

• Берёт два существующих валидных решения
• для каждого решения строит множество точек, через которые проходит центр бота
• ищет пересечение этих множеств
• для каждого элемента пересечения:
  • находит все разбиения первого решения этой точкой (например, решение AAAAAFDDDFWWWW разбивается элементом F на пары (AAAAAF,DDDFWWWW) и (AAAAAFDDDF,WWWW))
  • находит такие же разбиения для второго решения
  • склеивает все возможные пары разбиений, чтобы получить новые валидные решения

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

Функция починки мутированных решений

Следует решению, пока не наткнётся на невалидное действие. Вместо этого действия запускает генерилку, чтобы "дорешать" уже имеющееся решение до конца

Управляющая функция

Принимает на вход массив лучших решений, скрещивает несколько из них, мутирует какие-то другие, возвращает массив такого же размера, но обновлённый лучшими решениями. Будет вызываться в цикле, пока не надоест.

[Akon32]

Дополнения:

• В мутациях можно использовать ещё и перемещения цепочек или отдельных действий во времени. Например, активировать бустеры раньше или позже. (особенно бустеры клонирования)
• Предполагаю, не обязательно (хотя и желательно), чтобы все решения были валидными, их можно оценивать ещё и по IoU обработанных клеток. Фиксер всё равно нужен, наверно.
• Величина мутаций должна падать со временем. Тогда, по идее, в итоге будут появляться валидные решения (типа алгоритмов отжига). В крайнем случае, будет работать фиксер.

[Minoru]

Поправка к моему посту: после скрещивания вовсе не обязательно получится валидное решение. Нужно обязательно применять фиксер.

[Minoru]

По-моему, IoU нам не нужен. Во-первых, задача у нас бинарная: либо мы всё закрасили, либо нет. Union всегда будет включать в себя все клетки поля, т.к. валидное решение закрашивает их все. Intersection же будет определяться оцениваемым решением (т.к. пересечение любого множества с универсумом — это исходное множество).

В общем, IoU в нашей задаче сводится к отношению закрашенных клеток к их общему количеству.

Drills могут добавлять в множество новые клетки, но они сразу автоматически закрашиваются, поэтому на мои рассуждения выше они никак не повлияют.