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

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

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА I. МЕТОДЫ НЕРАВНОМЕРНЫХ ПОКРЫТИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПОИСКА ГЛОБАЛЬНОГО ЭКСТРЕМУМА

ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ.

1.1. Постановки задач. Общая схема организации покрытий

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

1.3. Метод с организацией покрытия по схеме

ветвления.

1.4. Вычислительные аспекты .

ГЛАВА П. МЕТОДЫ НЕРАВНОМЕРНЫХ ПОКРЫТОЙ ДЛЯ ПРИБЛИЖЕННОГО ПОСТРОЕНИЯ МНОЖЕСТВА ПАРЕТО .

2.1. Постановка задачи и общая схема

покрытий
2.2. Метод на основе послойной схемы
покрытий
2.3. Метод покрытия по схеме ветвления .
2.4. Условия согласования параметров при использовании приближенной исходной информации
2.5. Вычислительные аспекты
ГЛАВА Ш. ДИАЛОГОВОЕ РЕШЕНИЕ ЗАДАЧ ГЛОБАЛШОЙ
ОПТИМИЗАЦИИ.
3.1. Основные особенности диалоговой технологии при проведении оптимизационных расчетов.
Стр.
3.2. Диалоговая реализация алгоритмов
главы I
3.3. Диалоговая реализация алгоритмов
главы П
ГЛАВА 1У. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ГЛОБАЛЬНОЙ
ОПТИМИЗАЦИИ.
4.1. Задача о выборе параметров радиоэлементов при проектировании радиосхем
4.2. Задача формирования облика крыла летательного аппарата
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Учитывая то обстоятельство, что при решении практических задач могут возникать разнообразные требования к точности и быстродействию алгоритмов, наиболее эффективной технологией решения сложных задач была бы такая организация процесса решения, при которой возможно использование большого набора алгоритмов разных классов: локальные, стохастические, детерминированные. Кроме того, как уже было отмечено, для повышения эффективности алгоритмов необходимо иметь максимально полную информацию о свойствах задачи. Такгл информация может быть получена, как на основе предварительного анализа, так и в процессе решения задачи. В настоящей работе, в рамках реализации подобной технологии, разработаны численные методы для решения задачи поиска глобального экстремума функции многих переменных и задачи построения множества Парето, на основе использования схем неравномерных покрытий. Такие алгоритмы, как уже отмечалось, позволяют учитывать, с целью ускорения расчетов, многообразную информацию о свойствах задачи, полученную как на основе предварительного анализа, так и в процессе решения. Последовательные методы неравномерных покрытий основаны на идее поиска решения путем исключения из допустимого множества подмножеств, для которых гарантируется выполнение определенных условий. Как только объединение таких подмножеств покроет заданное множество, процесс прекращается. В основе формальных схем таких методов лежит предположение, что функции, определяющие задачу, удовлетворяют условию Липшица. Принадлежность функции этому классу, как правило, можно установить из рассмотрения физической сути задачи. Однако оценка значения константы Липшица может стать сложной проблемой. Для преодоления этой трудности предложен ряд приемов [*2, И*] . Одним из наиболее известных и распространенных методов покрытия является метод равномерного перебора. По-видимому, первый метод неравномерного покрытия был предложен в работе [] . В дальнейшем описанию версий этого метода были посвящены работы [-] . Здесь следует заметить, что интерпретация этого метода, как метода покрытий, была дана значительно позже [г] . Как отмечалось в [2, ] , этот метод малоэффективен при решении многомерных задач. При решении таких задач память ЭВМ, необходимая для работы метода, и сложность внутренних вычислений резко возрастают. Эти методы существенно усложняются при попытке решения многомерных задач, и требования к объему памяти также резко возрастают. Это объясняется, в основном, тем, что для построения таких алгоритмов необходимо решать сложные задачи теории покрытий. В работе [] впервые был предложен метод, где идея неравномерного покрытия была представлена в явном виде. Этот метод прост в реализации и предъявляет ограниченные требования к объему памяти при решении многомерных задач. Кроме того, схема метода такова, что позволяет использовать локальные методы и легко учитывать различную дополнительную информацию о свойствах минимизируемой функции и функций, определяющих допустимое множество. Эти свойства алгоритма открывают пути повышения его эффективности. В дальнейшем различные описания и варианты метода были приведены в ряде работ [2, ,*] . В [и] были предложены версии метода для решения задачи поиска глобального экстремума функции многих переменных. В [] метод был обобщен для решения минимаксных задач. С применением метода были успешно решены практические задачи [] . В основе этого алгоритма лежит идея послойного покрытия заданного п -мерного параллелепипеда [^ . При этом предполагается,что решение задачи принадлежит некоторому заданному параллелепипеду. Толщина слоя покрытия, образованного из объединения шаров, определяется радиусом минимального шара из шаров, составляющих слой. Эта особенность схемы покрытия такова, что при росте размерности задачи эффективность алгоритма резко снижается [п] . В диссертационной работе предложена модификация схемы метода [И, ^] и построена новая схема покрытия, основанная на принципе ветвления. На основе полученных схем разработаны алгоритмы для приближенного построения множества Парето.