Построение единой программной среды для решения задач глобальной оптимизации — страница 3

  • Просмотров 752
  • Скачиваний 7
  • Размер файла 266
    Кб

оптимизации) есть черный ящик, на вход которого подается описание функции, ее связи, границы переменных и требуемая точность. Этот черный ящик генерирует на выходе одно из следующих состояний: Приближенные значения переменных, в которых функция достигает минимума с математически рассчитанными границами ошибок. Значения, которые аппроксимируют глобальный минимум с математически рассчитанной максимальной ошибкой. Функция не

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

по завершению стохастического алгоритма соответственно. В следующих параграфах мы изучим такие алгоритмы подробнее. Для более детального рассмотрения этих алгоритмов можно обратится к работе [1], откуда и почерпнута значительная часть из ниже приведенных материалов. Стохастические методы Стохастическими методами для глобальной оптимизации называются бесконечные процессы, для которых вероятность посетить глобальный

минимум достигает 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, но и на любом множестве машинно-представимых чисел в случае реализации этой процедуры на компьютере. Этот метод был изучен несколькими исследователями. Они показали, что если функция вычисляется в точках, равномерно распределенных в области , то поиск наименьшего значения функции таким методом сходится к глобальному минимальному значению * с вероятностью 1. Моделируемый Отжиг Моделируемый отжиг (simulated annealing - SA) - это

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