Как отладить симуляцию Монте-Карло быстрее?

Question

Я пишу программу имитации отжига, и у меня возникают проблемы с ее отладкой. Любой совет будет приветствоваться.

Прежде всего, вывод не является детерминированным, поэтому я взял его сто раз и посмотрел на среднее и стандартное отклонение.

Но тогда для завершения одного теста требуется возраст и возраст (> 30 минут).

Обычно я бы пытался сократить ввод, но уменьшение количества итераций напрямую снижает точность результата способами, которые не являются полностью предсказуемыми. Например, график охлаждения представляет собой экспоненциальный спад, масштабированный до количества итераций. Уменьшение количества отдельных прогонов делает вывод очень ненадежным (одна из ошибок, которую я пытаюсь выявить, - это огромная разница между прогонами).

Я знаю, что преждевременная оптимизация - корень всего зла, и, конечно, оптимизация должна быть преждевременной, прежде чем программа станет правильной, но я серьезно думаю о переписывании этого более быстрого языка (Cython или C), зная, что в конце я должен был перенести его обратно на Python для отправки.

Итак, есть ли способ протестировать алгоритм имитации отжига лучше, чем у меня сейчас? Или я должен просто работать над чем-то еще между тестами?

Раскрытие информации: это задание для курсовой работы, но я не прошу вас помочь мне с реальной симуляцией.

Answer 1

Вот несколько приемов отладки, которые я изучил при реализации метаэвристики (например, имитация отжига и поиск по табу) в Drools Planner (Java, с открытым исходным кодом):

1. Он поддерживает различные environmentMode с (DEBUG, REPRODUCIBLE (по умолчанию) и PRODUCTION).В режиме DEBUG и REPRODUCIBLE, весь код использует один и тот же случайный экземпляр, а Random экземпляр seed является фиксированным .Поэтому двойная реализация поиска в табу дает одинаковые ходы, шаги и результат.Реализация смоделированного отжига основывается на градиенте времени, поэтому в зависимости от процессора в данный момент может быть небольшая разница.Примечание: это не освобождает вас от статистических запусков, но делает воспроизводимым один прогон.
2. Хорошая, удобочитаемая запись в журнал.Используйте уровни регистрации.Не ведите слишком многословный журнал.
3. Наш сервер сборки (Hudson) ведет статистику производительности.
4. Существует инструмент Benchmarker, который выводит диаграммы, чтобы было легче увидеть, что сделал алгоритм.Так что не только посмотрите на результат, но и посмотрите, как он туда попал.Сначала он мог бы хорошо работать, но потом застрял в локальной оптиме.

Это такие вещи, которыедать вам представление о том, что на самом деле происходит в алгоритме.

Кроме того, см. статью моего блога по Имитация отжига .