Заинтересовался Алгоритмом отжига.
Вкратце - алгоритм, предназначенный для решения задач оптимизации.
Я использовал написанный ранее мною набор классов, предназначенных а общем случае для моделирования поведения агентов в какой-либо среде.
В качестве агентов выступают три решения - рабочий, текущий и лучший. Решение характеризуется набором параметров и значением энергии. Энергия - показатель степени решения задачи. Чем лучше решение, тем энергия меньше. Если решение имеет энергию. равную нулю, то решение найдено.
Перед прогоном инициируется рабочее решение и его состояние копируется в текущее и лучшее решения. На каждой итерации прогона происходит изменение параметров рабочего решения по каким либо алгоритмам (чаще всего случайное изменение одного или несколько параметров на дискретную величину в сторону уменьшения или увеличения), расчитывается энергия. Если рабочее решение лучше (энергия меньше), чем текущее, то состояние рабочего решения копируется в текущее.
Если рабочее решение лучше, чем лучшее решение, то состояние рабочего решения копируется в лучшее. Уже этот алгоритм прямого преимущества позволяет находить решения, если поверхность энергии без локальных минимумов. Если имеются множество локальных минимумов, то такой алгоритм застревает в каком либо минимуме и вероятность нахождения решения падает. Чтобы увеличить вероятность нахождения решения, и применяется алгоритм отжига. Подробнее - на википедии.
Тестовая задача, как всегда - задача расстановки 8 ферзей.
Количество ферзей принимаем 18.
Имеет большое значение количество итераций внутри эпохи. Эпоха в данном случае - количество итераций между изменениями температуры. При малом размере эпохи температура быстро спадет, количество принятия решений с большей энергией, а значит свобода выбора, упадет до нуля и алгоритм скатится до алгоритма простого преимущества. При этом велика вероятность попадания в локальный минимум. Если размер эпохи велик, то фактически будет производится случайный перебор вариантов, когда при каждой итерации текущее решение принимает значение рабочего. Вероятность нахождения решения при этом ненулевая, но количество итераций очевидно, больше.