Замечания по реализации:
График охлаждения - в конце каждой эпохи значение температуры умножается на параметр Альфа. Итерации заканчиваются, когда текущая температура становится меньше конечной.
Поиск является, по сути, основанный на случайном переборе вариантов. Для случаев оптимизации гладких и непрерывных функций он нееффективен. Лучше использовать градиентный спуск. Каждый прогон алгоритма может как дать решение, так и не дать. При заданных в первый раз параметрах алгоритма - размер эпохи, альфа, сложно сказать, насколько эффективно алгоритм решит задачу и решит ли вообще. Несколько прогонов дадут информацию о наилучшем наборе параметров алгоритма, но тогда смысл алгоритма отжига как метода искусственного интеллекта теряется. Искусственный интеллект подразумевает, что достаточно задать только исходную информацию, в нашем случае это функция зависимости энергии от параметров решения, алгоритм должен с первого прогона либо найти решение, либо улучшить исходное, либо указать о невозможности найти решение.
Методы типа алгоритма отжига подходят для решения таких задач оптимизации, когда значения целевой функции от параметров рваное, параметры дискретные. Для реализации поиска достаточно только значения целевой функции от параметров.
Если задать конечную температуру слишком низкой (в моем случае оптимальным является 0.5), да еще и охлаждение быстрое (низкий размер эпохи), то если решение попалол в локальный минимум, в конце охлаждения новые решения находится не будут. При этом в каждой эпохе количество принятых решений будет равно нулю. Поэтому введен еще один признак окончания прогона - количество подряд идущих эпох, в которые количество принятых решений будет равно нулю.
Несколько прогонов дают возможность экспериментально определить размер эпохи, при котором решение находится за один прогон (в большинстве случаев), при этом конечная температура опускается достаточно низко, но не меньше заданной, при этом итерации не заходят в область пустых эпох.
Для 18 ферзей удалось подобрать значения:
Размер эпох: 30000,
Начальная температура: 100,
Конечная температура: 0.5,
Альфа: 0.8
При таких условиях суммарное количество итераций, необходимое для гарантированного получения решения является самым низким.
Критерием эффективности является количество итераций, необходимых для гарантированного получения решения. Организуется серия прогонов. Если в одном прогоне решение на найдено, начинается новых прогон с температурой 100 и с другим начальным значением исходного решения. Прогоны повторяются до тех пор, пока решение не будет найдено.
Если размер эпохи мал, то вероятность нахождения решения за один прогон низок, и количество прогонов до нахождения решения будет больше 1.
Вследствие того, что алгоритм имеет стохастический характер, то для адекватной оценки необходимо собрать статистику по множеству серий. В данной эксперименте используется 20 серий прогонов. ...