Оптимизация моделированием отжига

Оптимизаторы, основанные на моделировании отжига, воспроизводят термодинамический процесс замерзания жидкостей и отжига металлов.

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

Как и генетическая оптимизация, моделирование отжига — очень мощная стохастическая методика, основанная на естественном явлении, которое может находить глобально оптимальные решения и работать с неупорядоченными функциями эффективности. Моделирование отжига эффективно решает комбинаторные проблемы, включая известную задачу о коммивояжере или проблему оптимального расположения миллионов элементов современных интегральных микросхем, например компьютерных процессоров. Методы, основанные на моделировании отжига, не следует ограничивать комбинаторной оптимизацией; они могут быть легко применены для оптимизации параметров с реальными значениями. Следовательно, оптимизаторы, основанные на моделировании отжига, применимы к широчайшему кругу задач, включая задачи, интересующие трейдеров.

Поскольку генетические оптимизаторы столь эффективны, мы не столкнулись с необходимостью широко исследовать оптимизаторы, основанные на моделировании отжига. Кроме того, поступали сообщения, что во многих случаях алгоритмы отжига уступают генетическим, таким образом, не было необходимости давать примеры метода моделирования отжига и рассматривать его далее.

Аналитические оптимизаторы

Анализ (в смысле математический или комплексный анализ) является расширением классического исчисления. Аналитические оптимизаторы используют наработанные методы, в особенности методы дифференциального исчисления и исследования аналитических функций для решения практических задач. В некоторых случаях анализ дает прямой (без перебора вариантов) ответ на задачу оптимизации. Так происходит при использовании множественной регрессии, где решение находится с помощью нескольких матричных вычислений. Целью множественной регрессии является подбор таких весов регрессии, при которых минимизируется сумма квадратов ошибок. В других случаях требуется перебор вариантов, например невозможно определить напрямую веса связей в нейронной сети, их требуется оценивать при помощи алгоритма обратного распространения.

Многие методы перебора данных, используемые для решения многовариантных проблем оптимизации, применяют в том или ином виде метод сопряженных градиентов (максимальной крутизны). В общем виде оптимизация методом сопряженных градиентов ведется следующим образом. Некоторым образом выбирается точка на поверхности функции пригодности. Вектор градиента поверхности в данной точке оценивается с помощью дифференцирования функции пригодности по каждому из параметров. Полученный градиент указывает направление максимального роста функции пригодности в n- мерном пространстве параметров. В направлении градиента делаются шаги до тех пор, пока функция пригодности не перестанет расти. Затем расчет градиента повторяется, движение начинается в новом направлении, и так раз за разом, пока не будет достигнута вершина, т.е. точка с нулевым градиентом.