2020-01-14
130
Стохастическими методами для глобальной оптимизации называются бесконечные процессы, для которых вероятность посетить глобальный минимум достигает 1 при стремлении числа шагов к бесконечности. Наиболее простой из таких методов следующий:
Алгоритм 1: Случайный поиск
Инициализация: ¦ min = ¥, xmin = any_number, и i = 0.
шаг 1: xi = случайное число.
шаг 2: если ¦(xi ) < ¦ min установить xmin = xi, ¦ min =¦(xi ).
шаг 3: увеличить i на 1 и перейти к шагу 1.
Если ¦ хотя бы кусочно непрерывна, то при i ® ¥, ¦ min ® min ¦ на выбранной области. Этот процесс будет сходиться к глобальному минимуму не только на Rn, но и на любом множестве машинно-представимых чисел в случае реализации этой процедуры на компьютере.
Этот метод был изучен несколькими исследователями. Они показали, что если функция вычисляется в точках, равномерно распределенных в области W, то поиск наименьшего значения функции таким методом сходится к глобальному минимальному значению ¦* с вероятностью 1.
Моделируемый Отжиг
Моделируемый отжиг (simulated annealing - SA) - это другой стохастический метод, дающий хорошие результаты в целочисленной оптимизации, и, с недавнего времени, в общей глобальной оптимизации.
|
|
|
SA базируется на физической идее отжига (остывания) металлов в смысле поиска состояния наименьшей энергии этого металла. По этой причине SA оперирует такими словами как температура, соотносясь с физической интерпретацией. Математической интерпретацией отжига является процедура остывания, которая есть убывающая функция времени. Для целочисленной оптимизации SA можно трактовать как случайное блуждание со смещением. В общем, SA алгоритм может быть описан следующим образом:
