tgoop.com/bminaiev_blog/35
Last Update:
Parallel Simulated Annealing
Недавно мы участвовали в Reply Challenge. Соревнование похоже по формату на Google HashCode. На 4 часа дают одну задачу, у которой нет оптимального решения, и несколько тестов к ней. Нужно как можно лучше решить эти тесты используя любые средства.
4 часа для такого типа задач это очень мало. Обычно первый час уходит на чтение условия и изучение тестов. Еще час на написание простого решения. Еще час на то, чтобы сделать что-то чуть более умное. И последний час, чтобы позапускать решение на всех тестах и подобрать константы в решении.
Самое первое решение это обычно какой-то жадный алгоритм. Пытаемся построить хоть какой-то ответ, каждый раз выбирая лучший вариант из локально возможных.
Когда у нас есть какое-то валидное решение, к нему можно применять локальные оптимизации (о которых я уже писал). Можно случайным образом совсем немного поменять решение, и проверить, улучшаются ли от этого набранные баллы. Если улучшаются — сохранить новое решение и продолжить.
Такой подход часто приводит к локально оптимальному ответу, который не получается улучшить. Чтобы этого избежать можно использовать отжиг (о нем тоже писал).
Если отжигу дать больше времени, то он найдет решение лучше. Но соревнование ограничено по времени, поэтому можно попробовать его распараллелить. В Rust есть библиотека rayon, которая позволяет распараллелить программу просто заменив слово iter на par_iter (магия!). Единственное условие — код внутри итераций не должен модифицировать одни и те же данные.
Проблема отжига в том, что он по своей сути однопоточный. Есть какой-то текущий ответ, для него генерируются случайные изменения, которые иногда применяются. Текущий ответ меняется со временем и поэтому его нельзя обновлять внутри par_iter.
Во время контеста я сделал следующее. Вместо выбора одного случайного изменения, давайте создадим 20 потоков, в каждом посмотрим 1000 случайных изменений и выберем лучшее из них. После этого есть 20 лучших изменений, их попробуем синхронно применить к решению как в обычном алгоритме отжига. Повторим. Отгадайте почему это плохо работает.
После конца контеста я подумал, что лучше просто запустить 20 абсолютно отдельных экземпляров отжига (можно с разными параметрами начальной температуры) на минуту и выбрать лучшее из получившихся 20 решений. А потом еще раз на минуту 20 отдельных экземпляров, и.т.д.
Понятно, что это решение не идеально, но оно точно лучше однопоточного кода. А может быть можно еще лучше?
BY Боря программирует
Share with your friend now:
tgoop.com/bminaiev_blog/35