Имитация отжига в C#

Question

Я использую имитацию отжига для решения проблемы криптоанализа, и я столкнулся с кирпичной стеной. Я не могу на всю жизнь заставить свою функцию вероятности работать правильно, либо она слишком часто принимает худшее решение (поэтому я отскакиваю от 0,03 до 0,2), либо не достаточно часто (поэтому я застреваю в 0,35). Я просматривал Интернет, но я сталкивался только с примерами, когда проблемы связаны с поиском значения MINIMUM.... моей проблеме нужно найти значение MAXIMUM, худший результат - 0, лучший - 1.

Мне нужен совет по температуре и какой функции вероятности я должен использовать.

Answer 1

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

Как правило, алгоритмы оптимизации ищут минимум целевой функции. Если вы хотите использовать такой алгоритм как есть в вашей задаче максимизации, попросите оптимизатор минимизировать отрицание вашей целевой функции. Например, предположим, что целевая функция, для которой вы хотите найти максимум, f(x)=score, Затем вы должны запросить оптимизатор, чтобы свести кминимуму -f(x)т.е.-score(или, как вы указали в комментарии выше,1-score).

В Интернете доступно множество смоделированных отжигов и других глобальных алгоритмов оптимизации, см., Например, этот список в Дереве решений для программного обеспечения для оптимизации. К сожалению, эти коды обычно не пишутся на C#, но если коды написаны на Fortran или C, обычно довольно легко взаимодействовать с этими кодами черезP / Invoke.

Если вам не требуется, чтобы оптимизатор обязательно находил глобальный оптимум, здесь также перечислены некоторые оптимизаторы без производных. По крайней мере один из этих кодов доступен в версии C#, а именно BOBYQA (на самом деле этот алгоритм был адаптирован для C# мной:-).