Содержание к диссертации
Стр.
ВВЕДЕНИЕ 4
ГЛАВА I. МЕТОДЫ НЕРАВНОМЕРНЫХ ПОКРЫТИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПОИСКА ГЛОБАЛЬНОГО ЭКСТРЕМУМА
ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ 13
I.I. Постановки задач. Общая схема организа
ции покрытий 13
1.2. Модифицированный метод на основе послойной схемы покрытия ........... 27
1.3. Метод с организацией покрытия по схеме
ветвления 33
1.4. Вычислительные аспекты ......... 41
ГЛАВА П. МЕТОДЫ НЕРАВНОМЕРНЫХ ПОКРЫТИЙ ДЛЯ ПРИБЛИЖЕННОГО ПОСТРОЕНИЯ МНОЖЕСТВА ПАРЕТО ... 46 2.1. Постановка задачи и общая схема
покрытий » 46
2.2. Метод на основе послойной схемы
покрытий 56
2.3. Метод покрытия по схеме ветвления ... 59
2.4. Условия согласования параметров при ис
пользовании приближенной исходной ин
формации 62
2.5. Вычислительные аспекты 64
ГЛАВА Ш. ДИАЛОГОВОЕ РЕШЕНИЕ ЗАДАЧ ГЛОБАЛЬНОЙ
ОПТИМИЗАЦИИ 67
3.1. Основные особенности диалоговой технологии при проведении оптимизационных расчетов ................. 67
Стр. 3,2. Диалоговая реализация алгоритмов
главы I 73
3.3. Диалоговая реализация алгоритмов
главы П 77
ГЛАВА ІУ. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ГЛОБАЛЬНОЙ
ОПТИМИЗАЦИИ 80
4.1. Задача о выборе параметров радиоэлемен
тов при проектировании радиосхем .... 80
4,2. Задача формирования облика крыла лета
тельного аппарата 83
ЗАКЛЮЧЕНИЕ 95
ЛИТЕРАТУРА 96
Введение к работе
В настоящее время методы системного анализа широко используются в различных областях человеческой деятельности. Важную роль в приложениях играют методы оптимизации, которые успешно применяются для выбора лучших решений в задачах планирования, проектирования, управления и др. [i] .
Наиболее существенные успехи в теории оптимизации связаны с разработкой методов поиска локально-оптимальных решений. Однако в последнее время первостепенное значение приобретает проблема наиболее полного использования имеющихся экономических, технических, технологических и других возможностей в условиях ограниченности ресурсов. Это приводит к необходимости разработки сложных математических моделей исследуемых систем с целью их максимальной адекватности реальным процессам. Кроме того, резко возрастают требования к точности решения задач оптимизации.
С точки зрения целей оптимизации усложнение моделей связано с увеличением числа постановок задач оптимизации с многоэкстремальными критериями, большой размерности, сложно-определимым многосвязным допустимым множеством. Для получения наилучших решений в таких задачах необходимо использовать методы глобального поиска. Однако, теория численных методов поиска глобальных решений многомерных задач развита недостаточно [2] . Это связано с чрезвычайно большой сложностью таких задач [3J . Тем не менее улучшение технических характеристик ЭВМ, разработка многопроцессорных систем, возможность использования параллельной и конвеерной обработки информации наряду с возрастающими потребностями практики стимулируют исследования в области разработки новых методов глобальной - 5 -оптимизации.
В теории методов решения многоэкстремальных задач можно выделить два основных направления: алгоритмы, основанные на использовании стохастических идей (случайный поиск, информационно-статистический подход [4], стохастической аппроксимации, усреднения, сглаживания и другие) и детерминированные алгоритмы (методы покрытия, траекторные методы). Достаточно полное представление о большинстве существующих подходов дают обзоры, представленные в ряде работ [29 4, 5-7 J . Поэтому остановимся лишь на анализе некоторых центральных проблем.
На практике при решении оптимизационных задач наиболее распространены два основных подхода к оценке качества решения. В первом случае проводится поиск решения, удовлетворительного в некотором смысле, например, улучшающег критерий, по сравнению с имеющимся значением в заданной степени на 5%, 10%, 50% и т.д. В другом случае требуется не только отыскание некоторого варианта решения, но и гарантия того, что найденное решение действительно оптимальное (естественно, в пределах некоторой заданной точности).
Опыт решения многоэкстремальных задач показал, что, если необходимо получить улучшенное в определенной степени решение, то наиболее эффективно применение стохастических алгоритмов. Однако, для получения гарантированного решения (а это требование во многих случаях необходимо), предпочтительным является, по-видимому, использование детерминированных алгоритмов.
Для большинства алгоритмов первого направления получены лишь асимптотические оценки сходимости [4] . Для достоверного решения задачи за конечное время необходимо располагать достаточной информацией о ее свойствах. Например, такой информацией может быть информация о том, что функция удовлетворяет условию Липшица. Детер- - б - минированные методы в этом случае позволяют получить решение с заданной точностью за конечное время. Кроме того, методы этого класса, например, рассматриваемые ниже, позволяют легко учесть и другую дополнительную информацию (принадлежность классу Липшице-евых: функций, определяющих допустимое множество, функций, описывающих частные производные и др.). Использование такого рода информации ускоряет расчеты. Сказанное, однако, не означает, что при поиске гарантированного решения следует отказаться от использования методов других классов. Напротив, наличие приближенных оценок решения, полученных за короткое время другими методами, может существенно ускорить расчеты с применением детерминированных методов для получения гарантированной оценки.
Сравнение методов двух различных классов: детерминированных и основанных на стохастических идеях, позволяет, по-видимому, сделать следующие выводы. Стохастические методы позволяют получать оценку решения, во многих случаях вполне достоверную, при сравнительно небольших затратах времени. Однако, для поиска гарантированного результата необходимо использовать детерминированные алгоритмы. Учитывая то обстоятельство, что при решении практических задач могут возникать разнообразные требования к точности и быстродействию алгоритмов, наиболее эффективной технологией решения сложных задач была бы такая организация процесса решения, при которой возможно использование большого набора алгоритмов разных классов: локальные, стохастические, детерминированные. Кроме того, как уже было отмечено, для повышения эффективности алгоритмов необходимо иметь максимально полную информацию о свойствах задачи. Такал информация может быть получена, как на основе предварительного анализа, так и в процессе решения задачи. Наиболее перспективным инструментом для реализации такой технологии в настоящее - 7 -время являются прикладные диалоговые системы [ 8-I0J .
В настоящей работе, в рамках реализации подобной технологии, разработаны численные методы для решения задачи поиска глобального экстремума функции многих переменных и задачи построения множества Парето, на основе использования схем неравномерных покрытий. Такие алгоритмы, как уже отмечалось, позволяют учитывать, с целью ускорения расчетов, многообразную информацию о свойствах задачи, полученную как на основе предварительного анализа, так и в процессе решения. Последовательные методы неравномерных покрытий основаны на идее поиска решения путем исключения из допустимого множества подмножеств, для которых гарантируется выполнение определенных условий. Как только объединение таких подмножеств покроет заданное множество, процесс прекращается. В основе формальных схем таких методов лежит предположение, что функции, определяющие задачу, удовлетворяют условию Липшица. Принадлежность функции этому классу, как правило, можно установить из рассмотрения физической сути задачи. Однако оценка значения константы Липшица может стать сложной проблемой. Для преодоления этой трудности предложен ряд приемов \Zt ИJ Одним из наиболее известных и распространенных методов покрытия является метод равномерного перебора. По-видимому, первый метод неравномерного покрытия был предложен в работе [l2J . В дальнейшем описанию версий этого метода были посвящены работы [13-I4J . Здесь следует заметить, что интерпретация этого метода, как метода покрытий, была дана значительно позже [~2j . Как отмечалось в [2, 15 J , этот метод малоэффективен при решении многомерных задач. При решении таких задач память ЭШ, необходимая для работы метода, и сложность внутренних вычислений резко возрастают.
Особое место занимают исследования, связанные с разработкой - 8 -методов, осуществляющих построение оптимальных в некотором смысле покрытий [_I6-I7J Эти методы существенно усложняются при попытке решения многомерных задач, и требования к объему памяти тавже резко возрастают. Это объясняется, в основном, тем, что для построения таких алгоритмов необходимо решать сложные задачи теории покрытий.
В работе [l8j впервые был предложен метод, где идея неравномерного покрытия была представлена в явном виде. Этот метод прост в реализации и предъявляет ограниченные требования к объему памяти при решении многомерных задач. Кроме того, схема метода такова, что позволяет использовать локальные методы и легко учитывать различную дополнительную информацию о свойствах минимизируемой функции и функций, определяющих допустимое множество. Эти свойства алгоритма открывают пути повышения его эффективности. В дальнейшем различные описания и варианты метода были приведены в ряде работ [2, 15,19 J . В [її] были предложены версии метода для решения: задачи поиска глобального экстремума функции многих переменных:. В [20J метод был обобщен для решения минимаксных задач. С применением метода были успешно решены практические задачи j_lj В основе этого алгоритма лежит идея послойного покрытия заданного п -мерного параллелепипеда [l8J . При этом предполагается,что решение задачи принадлежит некоторому заданному параллелепипеду. Толщина слоя покрытия, образованного из объединения шаров, определяется радиусом минимального шара из шаров, составляющих слой. Эта особенность схемы покрытия такова, что при росте размерности задачи эффективность алгоритма резко снижается [_IlJ .
В диссертационной работе предложена модификация схемы метода |_П, I8J и построена новая схема покрытия, основанная на принципе ветвления. На основе полученных схем разработаны алгоритмы для приближенного построения множества Парето. Предложены диалоговые - 9 -версии алгоритмов, реализованные в рамках диалоговой системы оптимизации ДИСО [_10, 22-25 J , созданной при участии автора в Вычислительном центре АН СССР. Система ДИСО включает библиотеки локальных методов: безусловной минимизации (БМ) |_23] и нелинейного программирования (НЛП) Г24 , а также методы поиска глобального экстремума функций многих переменных (ГЛОБ) [25 J . Использование системы дает возможность реализовать диалоговую технологию для проведения расчетов. Такая технология основывается на возможности прерывания процесса поиска на определенных итерациях. В моменты таких прерываний пользователь может выполнить ряд операций. Наиболее важными при этом являются: исследование текущего состояния (вычисление ограничений и функций в любой точке, их производных и т.д.), управление процессом (замена численного метода, анализ влияния управляющих параметров метода и их изменение, смена условий очередного прерывания и т.д.). При использовании тех методов, где предусматривается возможность применения локальных алгоритмов, может быть реализован многоуровневый диалоговый вычислительный процесс: двухуровневый ГЛ0Б<=}БМ и трехуровневый ГЛОБ=>НЛП<=>БМ. Таким образом, исследователю предоставлена возможность активного воздействия на процесс оптимизации с целью максимального учета специфики решаемой задачи и ее успешного решения.
Кроме диалогового управления пользователю предоставлена возможность формирования специальных "сценариев" для решения задачи в пакетном режиме. Все перечисленные операции реализуются с помощью специальной управляющей программы (монитора) пакета ГЛОБ, реализованной в рамках инструментальной системы ДИАЛОГ [26, 27]. Разработанные алгоритмы и их диалоговые реализации проверены при решении практических и тестовых задач.
Диссертация состоит из введения, четырех глав, заключения и списка литературы.
Опишем кратко содержание диссертации.
