Исследование процедур глобальной оптимизации с адаптивными стохастическими моделями

• Автор: Городецкий, Станислав Юрьевич
• Шифр специальности: 05.13.02
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Горький
• Количество страниц: 221 c. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА I. ЗАДАЧИ МНОГОЭКСТРЕМАЛЬНОЙ ОПТИМИЗАЦИИ И ПРОЦЕДУРЫ ПОИСКА С ВЕРОЯТНОСТНЫМИ МОДЕЛЯМИ ФУНКЦИЙ . з

1.1. Постановка задач многоэкстремальной поисковой

оптимизации.

1.2. Использование вероятностных моделей функций .

при решении многоэкстремальных задач . . .

1.3. Неполные стохастические модели при построении

поисковых процедур . . . . . .

1.3.1. Неполные стохастические модели некоторых многоэкстремальных задач

1.3.2. Построение поисковых процедур на основе неполных стохастических моделей . . . . 3
ГЛАВА 2. УСЛОВИЯ СХОДИМОСТИ И ОЦЕНКИ КОНЦЕНТРАЦИИ ИСПЫТАНИЙ ДЛЯ ОДНОГО КЛАССА ПРОЦЕДУР .
ПОИСКА.
2.1. Исследование сходимости для одного класса процедур поиска .
2.1.1. Класс Тпредставимых процедур поиска. Классификация. Типы поведения и сходимости. 4
2.1.2. Условия сходимости процедур К , и М типов
2.2. Асимптотическая динамика поиска для процедур со всюду плотной СХОДИМОСТЬЮ.5У
стр.
2.2.1. Постановка задачи.5
2.2.2. Метод аналитического исследования относительной концентрации испытаний .
ГЛАВА 3. ПРОЦЕДУРЫ БЕЗУСЛОВНОЙ МНОГОЭКСТРЕМАЛЬНОЙ
ОПТИМИЗАЦИИ С АДАПТИВНЫМИ СТОХАСТИЧЕСКИМИ МОДЕЛЯМИ
3.1. Неполные адаптивные стохастические модели для процедур поиска
3.2. Процедуры глобальной оптимизации общий случай
3.2.1. Построение процедур поиска и исследование сходимости.7
3.2.2. Аналитическое исследование относительной концентрации испытаний на кусочнолинейных
и кусочнопостоянных моделях функций . .
3.3. Процедуры глобальной оптимизации случай известного минимального значения функции . .
3.3.1. Учет информации о минимальном значении функции
3.3.2. Процедуры решения систем уравнений и неравенств .
3.4. Вычислительный эксперимент.
3.5. Организация останова поиска глобального экстремума
ГЛАВА 4. ПРОЦЕДУРЫ МНОГОЭКСТРЕМАЛЬНОЙ ОПТИМИЗАЦИИ
С НЕЛИНЕЙНОМ ограничениями на основе АДАПТИВНЫХ СТОХАСТИЧЕСКИХ МОДЕЛЕЙ . .
4Л. Подходы к учету нелинейных ограничений в процедурах с адаптивными стохастическими моделями .
4.2. Процедуры поиска, основанные на преобразовании задачи с ограничениями.
4.3. Процедуры поиска, основанные на стохастических моделях минимизируемой функции и функций ограничений .
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Чтобы определить то место,которое занимают исследования диссертационной работы в общем кругу исследований по этой проблематике, вначале кратко остановимся на других направлениях работ. Каждый метод решения многоэкстремальной задачи основывается на некоторых предположениях об ее свойствах и, тем самым, опирается на некоторую ее модель. Можно выделить два направления. Первое связано с использованием неформальных моделей и представлений о задаче. Второе- с построением оптимальных в том или ином смысле процедур поиска в рамках принятых математических моделей класса оптимизационных задач. Значительная часть работ по методам решения многоэкстремальных задач связана с первым направлением. Например, используемая во многих работах модель задачи поиска глобального минимума состоит в том, что область поиска представляется разбитой на конечное число /неизвестных/ подобластей G~0 , в каждой из которых целевая функция имеет один минимум. Методы поиска, основанные на этой модели, строятся так, чтобы по возможности обследовать каждую из подобластей Qtq или те из них, где предполагаются меньшие значения функции. Для этого используется"слепой”поиск [б6,] многократное применение процедуры локального поиска из многих начальных точек,построенных детерминированно или случайно [9,,5 и др. Способы выбора очередных точек могут перестраиваться,адаптироваться к задаче /например, [,0] ,а также [iOl] /, используются и другие способы обследования различных областей (jQ : случайные "толчки" текущей точки поиска [ ],кратковременное увеличение дисперсионности поиска, применение процедур перехода через седловые точки и максимумы ], схемы случайного блуждания за счет "инерционности" поиска [iOI] и другие приемы [8,,2] /Смотри также обзор в [в,III] /. Следует отдельно указать на различные алгоритмы случайного и автоматного поиска /смотри об -зор в [ 8б], а также [l0I,I] и др. Другим примером неформальной модели служит представление о минимизируемой функции как некоторой унимодальной, искаженной аддитивной осцилирующей добавкой. Методы поиска основываются в это? Сглаживание и локальный поиск могут совмещаться [ 7]. Иной способ сведения многоэкстремальной задачи к унимодальной основывается на методе ^ -преобразования [5]. Ряд методов исходит из моделей физического характера, когда траектория движения точки в области &0 при поиске глобального минимума задается дифференциальными уравнениями, зависящими от минимизируемой функции [ 0,3 J . В отличие от кратко рассмотренного выше первого направления в области разработки процедур глобальной оптимизации, второе направление, связанное с построением оптимальных процедур поиска, требует описания класса возможных процедур и класса решаемых задач с помощью некоторых математических моделей. Различные подходы к построению оптимальных процедур, постановки задач и обсуждение вопросов, связанных с оптимальностью, можно найти, например, в работах [8,,,,,,,,,,,-,,,-,, ,6,8-2,5-2,5,6,4,6,8,0 ] . Одна из возможных постановок состоит в следующем. Пусть многоэкстремальная задача определяется функцией У . У = С/ для задачи вида /1. У может быть вектор-функцией. Например, в задаче /1,5/$л)1» При поиске решения выполняются испытания I функции у в точках области . Пусть есть результат испытания /включающий координаты точки испытания/, а -множество результатов испытаний. Заметим, что испытание может состоять в вычислении значений функции J /как в [,,,1,7,2,6] и др. Иногда рассматриваются более общие случаи, в которых испытание состоит в применении к У функционала из некоторого класса [б2] или в использовании некоторой доступной возможности получения информации об У [ ] . Введем модель процедуры поиска. Для этого определим последовательность функционалов Кт, Ещ , Ут/ т-0,! Л(т*0 - Мт(и)т) /1. Мпг, Ет , У/п : т =0,/,. Класс процедур поиска [й] определяется ограничениями на функционалы Нт, Ет , Ут . В этих условиях обычно используются два основных подхода к определению оптимальной процедуры поиска. В соответствии с пер -вым считается, что единственной доступной информацией о функции ^ является ее принадлежность классу ^.