Содержание к диссертации
ВВЕДЕНИЕ 5
ГЛАВА I. ЗАДАЧИ МНОГОЭКСТРШАЛЬНОЙ ОПТИМИЗАЦИИ й
ПРОЦЕДУРЫ ПОИСКА С ВЕРОЯТНОСТНЫМИ МОДЕ
ЛЯМИ ФУНКЦИЙ /3
Постановка задач многоэкстремальной поисковой оптимизации /3
Использование вероятностных моделей функций ,
при решении многоэкстремальных задач . . ,17
1.3. Неполные стохастические модели при построении
поисковых процедур . 27
Неполные стохастические модели некоторых многоэкстремальных задач %$
Построение поисковых процедур на основе неполных стохастических моделей , . . . 35"
ГЛАВА 2. УСЛОВИЯ СХОДИМОСТИ И ОЦЕНКИ КОНЦЕНТРАЦИИ
ИСПЫТАНИЙ ДШ ОДНОГО КЛАССА ПРОЦЕДУР .
ПОИСКА 38
2.1, Исследование сходимости для одного класса проце
дур поиска 39
Класс Т-представимых процедур поиска. Классификация. Типы поведения и сходимости. 4/
Условия сходимости процедур К , & и М -типов 45"
2.2, Асимптотическая динамика поиска для процедур со
"всюду плотной" сходимостью 5У
Постановка задачи ...... ^"g
Метод аналитического исследования относительной концентрации испытаний ... 58
ГЛАВА 3. ПРОЦЕДОЫ БЕЗУСЛОВНОЙ МНОГОЭКСТМАЛЬНОЙ
ОПТИМИЗАЦИИ С АДАПТИВНЫМИ СТОХАСТИЧЕСКИМИ
МОДЕЛЯМИ 63
Неполные адаптивные стохастические модели для процедур поиска 6S
Процедуры глобальной оптимизации /общий случай/ 71
Построение процедур поиска и исследование сходимости 7/
Аналитическое исследование относительной концентрации испытаний на кусочно-линеИных
и кусочно-постоянных моделях функций . . 79
3.3. Процедуры глобальной оптимизации /случай из
вестного минимального значения функции/ . , g$
Учет информации о минимальном значении функции 36
Процедуры решения систем уравнений и неравенств gj
Вычислительный эксперимент gf
Организация останова поиска глобального экстремума //g
ГЛАВА 4. ПРОЦЕДУРЫ МНОГОЭКСТШШЪНОЙ ОПТИМИЗАЦИИ С НЕЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ НА ОСНОВЕ АДАПТИВНЫХ СТОХАСТИЧЕСКИХ МОДОЕЙ . . m
стр.
Подходы к учету нелинейных ограничений в процедурах с адаптивными стохастическими моделями . 1Z8
Процедуры поиска, основанные на преобразовании задачи с ограничениями . . . . * /32
Процедуры поиска, основанные на стохастических моделях минимизируемой функции и функций ограничений J42
ЗАКЛЮЧЕНИЕ /ИЗ
ЛИТЕРАТУРА - К7
ПРШЮЖЕНИЕ 18$
П.І. Примеры Т-представимых процедур . . . * 18Н П.2. Примеры і асимптотических оценок относительной
концентрации испытаний трех "всюду плотно"
сходящихся процедур j$
П.З. Вывод верхних и нижних оценок числа испытаний
до останова поиска в одном простом случае . , ЮЪ П.4. Акты и справки об использовании результатов
работы < Z10
Введение к работе
Методы оптимизации функций У1 переменных составляют важный раздел системного анализа и являются средством решения различных прикладных задач.
При проектировании динамических и статических конструкций, при выборе условий, режимов и параметров функционирования машин и механизмов, протекания процессов, при статистическом оценивании и в других важных практических задачах принятие оптимальных решений часто сводится к решению задач оптимизации. В общем случае возникающие в приложениях оптимизационные задачи являются многоэкстремальными. Причем, достоверная априорная информация об их свойствах может быть весьма незначительной, а определение значений оптшлизируемых показателей - весьма сложным, требующим значительных /вычислительных/ затрат.
В настоящее время методам и разработке методов оптимизации функций ҐІ переменных посвящена обширная литература, результаты вошли во многие монографии и продолжают публиковаться в научной периодике. Большая часть результатов при этом относится к одновкстремальному случаю.
Многоэкстремальные задачи менее исследованы как в прикладном, так и в теоретическом отношениях и их дальнейшее изучение является актуальным. Особенно это относится к зада -чам, в которых определение оптшлизируемых показателей связано со значительными вычислительными затратами и,следовательно, требу -ется оптимизация самого процесса поиска оптимального решения. Проблематика, связанная с многоэкстремальными задачами, активно разрабатывается советскими и зарубежными авторами. Результаты в этой области получены в работах Д.И.Батищева, ВЛ.Вулатова,
Р.П.Брента, Г.С.Ганшина, Ю.Б.Гермейера, В.А.Гришагина,Ю.М.Лани-лина, Ю.Г.Евтушенко, А.Г.Жилинскаса, В.В.Иванова, В.Я.Катковни-ка, А.Г.Коротченко, Х.Д.Кушнера, В.В.Леонова, Г.С.Лбова, А.В.Медведева, Г.А.Медведева, В.С.Михалевича, Н.Н.Моисеева, Й.Б.Моцкуса, Ю.И.Неймарка, Б.Т.Поляна, С.А.Пиявского, Л.А.Раст-ригина, Й.М.Соболя, Р.Г.Стронгина, А.Г.Сухарева, А.А.Фельдбаума, Д.С.Хилла, В.К.Чичинадзе, Ф.Л.Черноусько, В.Р.Шалтяниса, Д.Б.Юдина И'многих других авторов.
Основные результаты в области разработки процедур многоэкстремальной оптимизации связаны с использованием неформальных подходов /распространением на многоэкстремальный случай методов локального поиска, применением сглаживания и' фильтрации, случайным поиском и др./, построением покрытий, оптимальными процедурами поиска и их упрощениями. Распространенным общим способом учета нелинейных ограничений является метод штрафов,
В математическом отношении построение процедур глобального поиска, экономно использующих поисковые возможности, во многом связано с созданием оптимальных процедур для различных классов оптимизируемых функций. К настоящему времени в этом направлении более разработан максиминный подход. С его позиций основные результаты получены для класса функций, удовлетворяющих условию Липшица, его аналогам и модификациям.
Всего несколько десятков публикаций посвящено другому /вероятностному/ подходу -построению и исследованию оптимальных в среднем процедур на основе вероятностных моделей многоэкстремальных функций.В этом направлении удается получить процедуры,применимые при различных /в том числе,весьма слабых/ предположениях,
что адекватно сложным прикладным задачам с малой априорной ин -формацией. Основные успехи в создании поисковых вычислительных процедур в рамках вероятностного подхода достигнуты в задачах с одной оптимизируемой переменной. Использование этих вычисли -тельных процедур в случае П> переменных связано с методами редукции размерности /многошаговая схема, отображения типа кривых Пеано и др./, при этом вероятностные модели исходных fl -мерных задач не используются. Непосредственное построение поиска по п переменным в рамках вероятностного подхода предполагает задание вероятностных моделей многоэкстремальных функций /ь переменных. Вопрос создания таких процедур при П> I менее разработан по сравнению с одномерным случаем. Практически не исследован вопрос о специальных способах учета нелинейных ограничений в рамках вероятностного подхода. Такие способы предложены только для от -дельных классов ограничений. В исследованиях по сходимости процедур /при числе переменных большем единицы/ до настоящего времени отсутствовали результаты, позволяющие с общих позиций анализировать сходимость и ее тип для некоторых разрабатываемых процедур глобальной оптимизации. Отсутствовали также способы аналитического изучения свойств относительного сгущения точек испытаний для ряда существующих и разрабатываемых процедур.
Диссертационная работа посвящена дальнейшим ис -следованиям на основе вероятностного подхода актуальной задачи создания новых процедур глобальной оптимизации и, таким образом, выполнена в малоизученном направлении разработок в этой области. Основной целью работы является построение и исследование с единых позиций процедур решения задач глобальной оптимизации П переменных, применимых при весьма слабых предположениях о
классе минимизируемых функций и функций ограничений. При этом основное внимание уделяется указанным выше малоисследованным вопросам.
В работе использованы следующие методы и подходы. Построение процедур поиска в диссертационной работе основано на понятиях и подходах теории оптимальных решений и исследования операций, информационно-статистической теории поиска, некоторых разделах теории вероятности. При численном исследовании построенных процедур используется метод математического мо -делирования.
Ниже дается краткое изложение основных новых научных результатов, содержащихся в диссертации.
В работе выделен новый класс Т -представимых процедур поиска решения задач глобальной оптимизации. Процедуры этого класса размещают точку каждого очередного испытания задачи в максимуме специально построенного /характеристического/ функционала, зависящего от предыстории поиска. Данный класс включает в себя многие известные процедуры поиска одного и tv переменных, а также разработанные в диссертации процедуры с неполными /адаптивными/ стохастическими моделями. Б одношагово-оптимальных процедурах характеристический функционал совпадает с функцией среднего или гарантированного выигрыша на шаге. Рассмотрено несколько типов сходимости к глобальному минимуму /связанных с различ -ной априорной информацией о задаче/ и установлены условия их существования для V -представимых процедур в виде требований к характеристическому функционалу и классу функций. Тем самым установлена связь типа сходимости с типом процедуры поиска в рамках выделенного класса процедур.
Б работе предложены конкретные неполные вероятностные описания /модели/ многоэкстремальных функций /названные адаптивными стохастическими моделями/, построенные так, что основанные на них процедуры глобальной оптимизации обладают сходностью одного из рассмотренных типов.
На основе неполных адаптивных стохастических моделей получены новые процедуры решения для задач глобальной оптимизации с нелинейными ограничениями в форме неравенств, а также задач без таких ограничений, когда область поиска имеет простой вид /на -пример, является гиперкубом/. Б последнем случае рассмотрено несколько новых процедур, обладающих сходностью на различных, в том числе достаточно широких классах функций, включающих непрерывные и некоторые кусочно-непрерывные функции. Такие классы являются моделями реальных задач, в которых сложность вычислительных процессов, определяющих значение /и, быть может, другие характеристики/ многоэкстремальной функции, делает свойства этих функций плохо предсказуемыми. Показано, что сходимость построенных процедур поиска достигается за счет всюду плотного в пределе размещения точек испытаний функции в области поиска /таким же типом сходности обладают известные байесовские процедуры глобальной оптимизации/.
Для анализа поведения поисковых последовательностей "всюду плотно"сходящихея процедур введены новые понятия относительной концентрации испытаний и порядка относительной концентрации,описывающие сгущение точек испытаний в одной части области поиска по отношению к другой ее части. Предложена математическая постановка задачи исследования относительной концентрации испытаний "всюду плотно" сходящихся процедур. При некоторых предположениях
-/0-
о характеристическом функционале Т -представимой процедуры поиска предложена и теоретически обоснована общая методика ее решения. Тем самым впервые получен способ теоретического обоснования эффективности "всюду плотно" сходящихся процедур. Эта методика применена к исследованию построенных в диссертационной работе процедур с адаптивными стохастическими моделями и к некоторым известным процедурам других авторов /на кусочно-линейных и кусочно-постоянных моделях многоэкстремальных функций одного и
У1 переменных/. Получены явные аналитические оценки асимптотической /при достаточно большом числе испытаний/ зависимости относительной концентрации от минимизируемой функции.
Предложен способ останова поиска по значению характеристического функционала в точке текущего испытания, гарантирующий отыскание глобального минимума. При этом предполагается известной верхняя оценка /заданного вида/ значений минимизируемой функции и радиус шаров с центрами в точках глобального минимума, содержащихся в областях притяжения этих точек.
Б диссертационной работе рассмотрены также задачи глобальной оптимизации специального вида, когда известно значение минимизируемой функции в глобальном минимуме /они могут порождаться,на-пример, задачами решения систем уравнений и неравенств/.Получены модификации рассмотренных в диссертационной работе процедур, учитывающие дополнительную известную информацию таким образом,что изменяется тип сходимости. Найдены достаточные условия,при которых все предельные точки последовательности точек испытаний принадлежат множеству глобальных минимумов. Построены также специальные процедуры решения систем уравнений и неравенств в исходной форме /без сведения их к оптимизационным задачам/. При этом ис-
пользованы адаптивные стохастические модели левых частей систем. Получены условия сходаозти полученных процедур только ко мнокест-ву решений.
В задаче глобальной оптимизации с нелинейными ограничениями /в форяе неравенств/ предложены новые способы их учета. При этом используются вероятностные модели не только минимизируемой функции, но и функций ограничений. Построено несколько процедур,обладающих сходщсстью на весьма широких классах задач. В отличие от общего метода штрафов условный глобальный минимум отыскивается в ходе однократного решения задачи. Получены асимптотические оценки относительной концентрации испытаний на кусочно-постоянных моделях этих задач. В частности, показано, что для нескольких из предложенных процедур расстояние между точками испытаний имеет в допустимой области более высокий порядок малости по сравнению с областью, где ограничения не выполняются, в самой допустимой области границы относительной концентрации испытаний принимают максимальные значения на множестве условных глобальных минимумов.
На защиту выносятся следующие основные результаты :
I. Выделен новый класс Т -представимых процедур, включающий процедуры поиска глобального минимума по ґь переменным с адаптивными стохастическими моделями, а также ряд известных процедур. В его границах определено несколько подклассов, относи -тельно которых установлены условия для сходимости различных типов. 2. Дня описания поведения поисковых последовательностей "всюду плотно" сходящихся процедур введено новое понятие относительной концентрации испытаний, предложен и теоретически обоснован
-1Z~
метод получения аналитических оценок относительной концентрации
для класса процедур глобального поиска.
Предложен новый способ учета нелинейных граничений, основанный на использовании неполных адаптивных стохастических моде -лей минимизируемых функций и функций ограничений. В соответствии с ним построены новые процедуры поиска. На защиту также выносятся методы и результаты их исследования.
Получены новые процедуры для поиска глобального минимума /с адаптивными стохастическими моделями/ в задачах без нелинейных ограничений, построенные и изученные на основе результатов теоретического исследования сходимости, аналитических оценок относительной концентрации испытаний и результатов экспериментального исследования на ЭВМ.
Диссертационная работа имеет следующую с тр у к туру и объем. Основной текст диссертации состоит из введения, четырех глав, заключения и занимает 148 машинописных страниц. Кроме того, в работе имеется 22 рисунка, 3 таблицы, список литературы из 150 наименований и приложение объемом 3 & машинописных страниц.
Б заключение выражаю благодарность моему научному руководителю ЇОрию Исааковичу Неймарку за ценные научные консультации, внимание и поддержку в работе.
Похожие диссертации на Исследование процедур глобальной оптимизации с адаптивными стохастическими моделями
