Исследование

Цель исследования

На примере конкреткой задачи научиться применять наборы алгоритмов.

Научиться искать объективную выборку тестов и сравнивать поведения алгоритмов на этой выборке.

Задача

Пример трассы	Описание
	Есть трасса с двумя машинками, наборами флагов и препятствий. Есть строгий порядок сбора флагов, но не имеет значения, какая из машинок возьмет флаг. Каждый ход машинка может изменить своё ускорение на (x,y) -1 ≤ x,y ≤ 1 или вызвать команду Exchange. Если обе машинки на текущем ходу вызвали команду Exchange, они обмениваются своими векторами скоростей. На каждый ход машинкам даётся 100ms. У команды Exchange есть cooldown – 20 ходов. Пояснения: Синие – флаги; Голубой – след. флаг; Зеленые – машинки; Серые – преграды

Пример трассы

Описание

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

Каждый ход машинка может изменить своё ускорение на (x,y) -1 ≤ x,y ≤ 1 или вызвать команду Exchange.
Если обе машинки на текущем ходу вызвали команду Exchange, они обмениваются своими векторами скоростей.

На каждый ход машинкам даётся 100ms.
У команды Exchange есть cooldown – 20 ходов.

Пояснения:
Синие – флаги; Голубой – след. флаг; Зеленые – машинки; Серые – преграды

Выбранные алгоритмы

Все подходы используют эмуляцию на несколько шагов вперед и оценивают решение одной из функций оценок, представленных в классе Emulator. В частности, по результатам тестрирования была выбрана функция GetScore_3.

Жадный поиск

GreedySolver

Классический жадный поиск, перебирающий все возможные ходы, и повторяющий один и тот же ход N раз.

Случайный поиск

RandomSolver

Алгоритм в течении всего допустимого времени на ход генерирует пары (command, repeat), из которых составляются решения. При помощи функции оценки выбирается лучшее.

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

Поиск восхождением

HillClimbingSolver

Поиск восхождением с использованием запоминанием последнего лучшего решения. Для получения первого решения использует GreedySolver или RandomSolver. Применяет несколько типов мутаций по принципу квот. Для распределения квот все мутаторы использовались одновременно и считалось, в какой доле случаев тот или иной мутатор выигрывал.

Мутации:

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

Статистика показала, что каждая из приведенных выше мутаций дает улучшение в 1/3 случаев.

Мутация переворачивания случайного сегмента. Принимает количество сегментов, на которые нужно разбить решение и количество мутируемых сегментов. Выбранные случайно сегменты переворачиваются.
Мутация замены двух соседних сегментов. Два случайно выбранных соседних сегмента меняются местами. Реализована техника использования последнего лучшего решения. Включается, если передать соответствующий флаг.

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

EvolutionSolver

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

Выбираются предки, которые будут изменяться За выбор предков ответственен IGeneticFilter. На текущий момент есть две реализации:
- HalfFilter сортирует решения по очкам и выбирает половину лучших решений
- В NormalizeFilter шанс выбора определенного решения равен нормализованному значению очков
Выбранные предки преобразовываются в потомков За это отвечает IGeneticApplier. Есть две реализации:
- MutationApplier позволяет использовать любую мутацию, совместимую с HillClimbingSolver
- SegmentCrossingOver рассматривает пары предков, разделяет их решения по случайному числу K (на первые K шагов и остальные), берет первую часть от первого предка, вторую - от второго
Из предков и потомков выбирается новая популяция За это отвечает IGeneticSelector. Есть две реализации:
- Elitism оставляет одного лучшего предка и выбирает лучших потомков
- ElitismRandom помимо этого добавляет еще одно случайное решение

Система тестов

Написать объективную выборку тестов, которая бы покрывала все реалии этой задачи, оказалось очень сложно.

Спустя пару недель мы сошлись на решении, в котором у нас есть несколько групп карт, и несколько отдельных обособленных случаев.

Группы карт

Группа Без препятствий	Группа Мало препятствий

Отдельные карты

Bottle Neck 1	Bottle Neck 2	Bottle Neck 3	Exchange

Cross	10_10_3	5_10	7_10

Sprint 1	Sprint 22	Snake

Оптимальные параметры

Запуская алгоритмы на выбранных картах, мы искали оптимальные параметры для них. Остановились на следующих:

Алгоритмы	Greedy	Random	Hill Climb	Evolution
Параметры	Глубина: 15 Стратегия: `Repeat` Оценка: `Max`	Глубина: 11 Макс.сегмент: 9	BaseSolver: `Greedy` Эвристика: `true` BaseSolverTime: 1/10	BaseSolver: `Greedy` Filter: `FilterHalf` Applier: `SegmentCrossingOver` Selector: `Elitism`

Результаты

Промежуточные вычисления

Алгоритмы		Greedy		Random		Hill Climbing		Evolution
Группа Без препятствий	🥇	792 ± 18.2	🥈	745 ± 17.6	🥉	647 ± 15.2	🥈	725 ± 21.5
Группа Мало препятствий	🥇	714 ± 34.2	👎	548 ± 39.6	🥉	596 ± 29.3	🥈	655 ± 31.7
Exchange	🥇	182 ± 13.5	👎	138 ± 17.6	🥉	167 ± 13.9	🥈	171 ± 14.4
Bottle Neck 1	🥇	312.4 ± 15.2	🥉	195.1 ± 35.7	🥈	288.5 ± 21	👎	179.2 ± 36.7
Bottle Neck 2	🥇	214.3 ± 10.5	👎	18.14 ± 58.4	🥈	174.4 ± 41.5	🥉	73.1 ± 48.6
Bottle Neck 3	👎	-380 ± 18.5	🥉	-192.8 ± 64.7	🥇	239.9 ± 17.2	🥈	-93.3 ± 55.2
Sprint 1	👎	-427 ± 20.8	🥈	145.4 ± 24.1	🥇	180.6 ± 11	🥉	-88 ± 34.3
Sprint 2	👎	-240 ± 11.7	🥈	152.8 ± 19.7	🥇	160.4 ± 21	🥉	-58.3 ± 24.6
Cross	🥇	95.2 ± 4.7	🥈	51 ± 5.9	🥉	43.6 ± 4.6	👎	35 ± 5.1
10_10_3	🥈	87.6 ± 4.3	🥇	105.5 ± 7.5	👎	54.8 ± 6.8	🥉	84.3 ± 6.9
5_10	🥈	228 ± 7.3	🥇	236 ± 2	🥉	202 ± 10.8	🥉	201 ± 13
7_10	🥇	41 ± 2	🥇	40.1 ± 3	👎	27.4 ± 2.5	🥇	38.6 ± 2.7
Snake	🥇	171.4 ± 8.3	🥈	121.5 ± 8.9	👎	78.6 ± 17.6	🥉	85.7 ± 21.5