Методы неравномерных покрытий и их применение для решения задач глобальной оптимизации в диалоговом режиме

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

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

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

В теории методов решения многоэкстремальных задач можно выделить два основных направления: алгоритмы, основанные на использовании стохастических идей (случайный поиск, информационно-статистический подход [4], стохастической аппроксимации, усреднения, сглаживания и другие) и детерминированные алгоритмы (методы покрытия, траекторные методы). Достаточно полное представление о большинстве существующих подходов дают обзоры, представленные в ряде работ [2, 4, 5−7]. Поэтому остановимся лишь на анализе некоторых центральных цроблем.

На практике при решении оптимизационных задач наиболее распространены два основных подхода к оценке качества решения. В первом случае проводится поиск решения, удовлетворительного в некотором смысле, например, улучшающег®- 1фитерий, по сравнению с имеющимся значением в заданной степени на 5%, 10%, 50% и т. д. В другом случае требуется не только отыскание некоторого варианта решения, но и гарантия того, что найденное решение действительно оптимальное (естественно, в пределах некоторой заданной точности).

Опыт решения многоэкстремальных задач показал, что, если необходимо получить улучшенное в определенной степени решение, то наиболее эффективно применение стохастических алгоритмов. Однако, для получения гарантированного решения (а это требование во многих случаях необходимо), предпочтительным является, по-видимому, использование детерминированных алгоритмов.

Для большинства алгоритмов первого нацравления получены лишь асимптотические оценки сходимости [4]. Для достоверного решения задачи за конечное время необходимо располагать достаточной информацией о ее свойствах. Например, такой информацией может быть информация о том, что функция удовлетворяет условию Липшица. Детерминированные методы в этом случае позволяют получить решение с заданной точностью за конечное время. Кроме того, методы этого класса, например, рассматриваемые ниже, позволяют легко учесть и другую дополнительную информацию (принадлежность классу Липшице-евых: функций, определяющих допустимое множество, функций, описывающих частные производные и др.). Использование такого рода информации ускоряет расчеты. Сказанное, однако, не означает, что при поиске гарантированного решения следует отказаться от использования методов других классов. Напротив, наличие приближенных оценок решения, полученных за короткое время другими методами, может существенно ускорить расчеты с применением детерминированных методов для получения гарантированной оценки".

Сравнение методов двух различных классов: детерминированных и основанных на стохастических идеях, позволяет, по-видимому, сделать следующие выводы. Стохастические методы позволяют получать оценку решения, во многих случаях вполне достоверную, при сравнительно небольших затратах времени. Однако, для поиска гарантированного результата необходимо использовать детерминированные алгоритмы. Учитывая то обстоятельство, что при решении практических задач могут возникать разнообразные требования к точности и быстродействию алгоритмов, наиболее эффективной технологией решения сложных задач была бы такая организация процесса решения, при которой возможно использование большого набора алгоритмов разных классов: локальные, стохастические, детерминированные. Кроме того, как уже было отмечено, для повышения эффективности алгоритмов необходимо иметь максимально полную информацию о свойствах задачи. Такал информация может быть получена, как на основе предварительного анализа, так и в процессе решения задачи. Наиболее перспективным инструментом для реализации такой технологии в настоящее время являются прикладные диалоговые системы .

В настоящей работе, в рамках реализации подобной технологии, разработаны численные методы для решения задачи поиска глобального экстремума функции многих переменных и задачи построения множества Парето, на основе использования схем неравномерных покрытий. Такие алгоритмы, как уже отмечалось, позволяют учитывать, с целью ускорения расчетов, многообразную информацию о свойствах задачи, полученную как на основе предварительного анализа, так и в процессе решения. Последовательные методы неравномерных покрытий основаны на идее поиска решения путем исключения из допустимого множества подмножеств, для которых гарантируется выполнение определенных условий. Как только объединение таких подмножеств покроет заданное множество, процесс цре1фащается. В основе формальных схем таких методов лежит предположение, что функции, определяющие задачу, удовлетворяют условию Липшица. Принадлежность функции этому классу, как правило, можно установить из рассмотрения физической сути задачи. Однако оценка значения константы Липшица может стать сложной проблемой. Для преодоления этой трудности предложен ряд приемов II-]. Одним из наиболее известных и распространенных методов по1фытия является метод равномерного перебора. По-видимому, первый метод неравномерного покрытия был предложен в работе [12]. В дальнейшем описанию версий этого метода были посвящены работы [13−14]. Здесь следует заметить, что интерпретация этого метода, как метода покрытий, была дана значительно позже [~2]. Как отмечалось в [2,, этот метод малоэффективен цри решении многомерных задач. При решении таких задач память ЭВМ, необходимая для работы метода, и сложность внутренних вычислений резко возрастают.

Особое место занимают исследования, связанные с разработкой методов, осуществляющих построение оптимальных в некотором смысле покрытий ?16−17]. Эти методы существенно усложняются при попытке решения многомерных задач, и требования к объему памяти тавже резко возрастают. Это объясняется, в основном, тем, что для построения таких алгоритмов необходимо решать сложные задачи теории пощ) ытий.

В работе [l8] впервые был предложен метод, где идея неравномерного по1фытия была представлена в явном виде. Этот метод прост в реализации и предъявляет ограниченные требования к объему памяти при решении многомерных задач. Кроме того, схема метода такова, что позволяет использовать локальные методы и легко учитывать различную дополнительную информацию о свойствах минимизируемой функции и функций, определяющих допустимое множество. Эти свойства алгоритма открывают пути повышения его эффективности. В дальнейшем различные описания и варианты метода были приведены в ряде работ [2, 15,19^. В [п] были предложены версии метода для решения: задачи поиска глобального экстремума функции многих переменных:. В [20] метод был обобщен для решения минимаксных задач. С применением метода были успешно решены практические задачи [21J. В основе этого алгоритма лежит идея послойного покрытия заданного пмерного параллелепипеда [l8j. При этом предполагается, что реш: ение задачи принадлежит некоторому заданному параллелепипеду. Толщина слоя покрытия, образованного из объединения шаров, определяется радиусом минимального шара из шаров, составляющих слой. Эта особенность схемы покрытия такова, что при росте размерности задачи эффективность алгоритма резко снижается? ll] .

В диссертационной работе предложена модификация схемы метода [il, 18] и построена новая схема покрытия, основанная на принципе ветвления. На основе полученных схем разработаны алгоритмы для приближенного построения множества Парето. Предложены диалоговые.

— 9 версии алгоритмов, реализованные в рамках диалоговой системы оптимизации ДИСО [l0, 22−25 ], созданной цри участии автора в Вычислительном центре АН СССР. Система ДИСО включает библиотеки локальных методов: безусловной минимизации (БМ) ^2з] и нелинейного программирования (НЛП) [^24 J, а также методы поиска глобального экстремума функций многих переменных (ГЛОБ) [25 ]. Использование системы дает возможность реализовать диалоговую технологию для цроведения расчетов. Такая технология основывается на возможности прерывания процесса поиска на оцределенных итерациях. В моменты таких прерываний пользователь может выполнить ряд операций. Наиболее важными при этом являются: исследование текущего состояния (вычисление ограничений и функций в любой точке, их производных и т. д.), управление процессом (замена численного метода, анализ влияния управляющих параметров метода и их изменение, смена условий очередного црерывания и т. д.). При использовании тех методов, где предусматривается возможность применения локальных алгоритмов, может быть реализован многоуровневый диалоговый вычислительный процесс: двухуровневый ГЛ0Б<=}БМ и трехуровневый ГЛОБНЛП?=>БМ. Таким образом, исследователю предоставлена возможность активного воздействия на процесс оптимизации с целью максимального учета специфики решаемой задачи и ее успешного решения.

Кроме диалогового управления пользователю цредоставлена возможность формирования специальных «сценариев» для решения задачи в пакетном режиме. Все перечисленные операции реализуются с помощью специальной уцравляющей программы (монитора) пакета ГЛОБ, реализованной в рамках инструментальной системы ДИАЛОГ [26, 27]. Разработанные алгоритмы и их диалоговые реализации проверены при решении практических и тестовых задач.

— 10.

Диссертация состоит из введения, четырех глав, заключения и списка литературы.

ЗАКЛЮЧЕНИЕ

.

В диссертационной работе получены следующие основные результаты:

1. На основе новых схем покрытия разработаны численные методы решения задачи поиска глобального экстремума функции многих переменных, показавшие высокую эффективность,.

2. Разработан численный метод для приближенного построения множества Парето, основанный на однократном неравномерном по1фы-тии допустимого множества,.

3. Решены воцросы согласования значений параметров при решении задач с использованием неточной исходной информации,.

4. Предложены диалоговые версии алгоритмов и осуществлена их программная реализация. Программы включены в систему ДИСО,.

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

Разработанные алгоритмы включены в систему ДИСО и внедрены в ЦКБ Института космических исследований (г.Фрунзе), ВДИИ «Монолит», (г.Москва), Машиностроительный завод им. П. О. Сухого (г, Москва). (Справки о внедрении представлены).