Алгоритмы глобальной оптимизации функций в пространстве непрерывных переменных при наличии ограничений-неравенств

• Автор: Кузнецов, Алексей Владимирович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Красноярск
• Количество страниц: 138 с. : ил.

Содержание
Содержание.
Введение.

Общие сведения о диссертации.

Краткий анализ подходов к решению задачи глобальной оптимизации

1 Алгоритмы на допустимых пробных точках

1.1 Базовый алгоритм безусловной глобальной оптимизации методом

усреднения координат

1.2 Генераторы последовательностей равномерно распределенных точек

1.3 Алгоритм глобальной оптимизации при ограниченияхнеравенствах.

1.4 Примеры.

1.5 Свойства алгоритма и влияние параметров на качество его работы
1.6 Алгоритм поиска главных экстремумов
2 Алгоритмы глобальной оптимизации при ограниченияхнеравенствах с использованием штрафных функций.
2.1 Прямая свертка ограничений в штрафную функцию.
2.2 Формирование штрафной функции с использованием относительных
значений оптимизируемой функции и ограничений
2.3 Примеры.
2.4 Свойства алгоритма и влияние параметров на качество его работы
3 Прямой алгоритм глобальной оптимизации при ограниченияхнеравенствах
3.1 Прямой алгоритм учета ограничений.
3.2 Примеры.
3.3 Свойства алгоритма и влияние параметров на качество его работы
4 Программный пакет глобальной оптимизации ii v 1.0.
4.1 Общее описание
4.2 Требования к ресурсам.
4.3 Математическое ядро и модуль исследования.
ф 4.4 Методика проведения интерактивных исследований.
4.5 Методика проведения пакетных исследований
4.6 Методика конструирования специальных программных стендов.
Выводы.
5 Решение практических задач.
5.1 Поиск оптимальных параметров эллипсов, аппроксимирующих произвольный контур
5.2 Поиск оптимального решения задачи распределения штатов.
Заключение.
Список использованных источников


Пусть /(х|0,ст) - плотность распределения, параметры которого определяются вектором 0, равным математическому ожиданию случайного вектора х и а - некоторой скалярной мерой рассеяния этого распределения (типа среднеквадратичного отклонения), такой, что при а = 0 распределение вырождается в 5-функцию и имеем х = 0, ас увеличением а область распределения пробных точек расширяется пропорционально а по всем направлениям пространства {х}. Алгоритм устроен таким образом, что он стремится «стянуть» наброс вокруг лучшей точки (которая, возможно, и будет глобальным экстремумом). Темп такого стягивания определяет степень глобальности алгоритма. Если стягивание происходит быстро, то, очевидно, будет найден ближайший локальный экстремум; если же медленно, то шансы найти экстремум лучше ближайшего локального, повышаются. Алгоритм глобального поиска с идентификацией распределении. Этот алгоритм связан с восстановлением (идентификацией) плотности распределения /(х) значений минимизируемой функции в случайных точках х,, равномерно распределенных в области поиска 5. Если область поиска произвольно разделить на две части и в каждой определить плотность /](х) и /2(х), то наиболее перспективной для изучения будет та область, для которой левый «хвост» распределения простирается дальше. Для широкого класса сложных объектов можно воспользоваться логнормальным распределением, левый «хвост» которого ограничен. Таким образом, рассекая область поиска на последовательно уменьшающиеся подобласти можно выйти в район глобального экстремума и найти его точное значение любым локальным методом. У1(хк) + сг? При а = О поиск является градиентным, и поэтому каждая его траектория приводит в ближайший локальный минимум, т. При а * 0 на эту локальную тенденцию накладывается случайное блуждание типа броуновского. Процесс такого поиска происходит следующим образом. Во время блуждания точка * попадает в локальные экстремумы функции 1(х) и задерживается в каждом из них тем дольше, чем меньше значение 1(х) в соответствующем экстремуме. Если теперь медленно уменьшать а, то точка х попадает в зону глобального экстремума и уже никогда из нее не выйдет. Как видно, этот алгоритм гарантирует отыскание глобального экстремума лишь при очень медленном уменьшении параметра а (строго говоря, для этого нужна нулевая скорость убывания а). Риск не найти глобальный экстремум тем выше, чем больше скорость уменьшения а. В работах В. П. Гергеля и Р. Затем для отыскания решения строится неравномерная сетка, у которой узлы располагаются чаще в тех областях, где минимизируемая функция имеет меньшие значения, это позволяет отыскать приемлемое решение с использованием значительно меньшего количества точек, как если бы использовалась равномерная сетка. На практике реализован только двумерный вариант. Наиболее перспективны при решении задачи глобальной оптимизации методы, основанные на усреднении во всей области поиска экстремума. За счет охвата пробными точками всей области поиска экстремума удается получить глобальные характеристики и организовать более надежное движение к глобальному экстремуму. В этом направлении существуют два принципиально отличающихся подхода. I. Первый подход основан на усреднении либо самой минимизируемой функции [, - ], либо её преобразования с помощью селективной функции [, , ]. Этот подход часто называют методом потенциальных функций. Цель подхода - устранить (сгладить) все локальные экстремумы, а далее для сглаженной функции использовать алгоритмы локального поиска. II. В основе второго подхода [6, 7, - ] лежит усреднение координат, в пространстве которых ведется поиск экстремума. В этом подходе используются усредненные инверсные характеристики. На каждом рабочем шаге осуществляется переход в точку, в среднем более близкую к глобальному экстремуму. Получаемые алгоритмы имеют чрезвычайно простую структуру и в них легко встраивать адаптацию. За счет этого от них удается добиться высокой эффективности и приспособить к решению более сложных задач глобальной оптимизации (например, задач поиска главных минимумов, задач оптимизации при наличии ограничений, минимаксных задач, многокритериальных задач) []. Кратко опишем основные работы, принадлежащие этим двум подходам. I. Работы А. А. Красовского [, ].