Введение к работе
Актуальность проблемы. Многие задачи принятия оптимальных решении (в том числе восстановление зависимостей по результатам экспериментальных наблюдений, задачи выбора оптимальных параметров проентируемых объентов и процессов и др. ) могут быть сведены и решению сложных задач глобальной многоэкстремалыюИ оптимизации. Вопросам численного решения таких задач посвящена обширная литература (работы Д. И. Батищева, В. П. Вулатова, Ф. П. Васильева, В. Ф. Демьянова, Ю. Г. Евтушенко, С. М. Ерманова, Ю. М. Ермольева, В. Г. Жадана, А. А. Жиглявского, А. Г. Жилинснаса, С. К. Завриева, В. В. Иванова, В. Г. Карманова, В. С. Михалевича, Н. Н. Моисеева, И. Б. Моцнуса, Ю. И. Неймарна; П. М. Пардалоса, Я. Пинтера, С. А. Пиягзского, Э. Полака, Б. Н. Пшеничного, Л. А. Растригина, А. С. Стреналовсно-го, Р. Г. Стронгина, А. Г. Сухарева, А. И. Тихонова, X. Туя, Д. Дж. УаИпда, В. В. Федорова, Д. Химмельбпау, П. Хансена, Р. Хорста, В. К. Чичинадэе, Д. Б. Юдина и др. ). Однако, возрастающая сложность практических задач приводит к увеличению времени, затрачиваемого на вычисление каждого значения оптимизируемой функции, и росту числа таких вычислений в целом, что накладывает ограничения на круг решаемых проблем и постоянно выдвигает на передний план задачу повышения эффективности методов глобальной оптимизации.
Появление многопроцессорных вычислительных систем открывает возможность ускорения решения указанных эалач путем создания методов оптимизации, основанных на итерациях, включающих одновременное вычисление значении оптимизируемой Функции и ее производных в нескольких точках области определения (каждый процессор проводит вычисления в одной точке).
Другим путем ускорения поиска является более полное использование всеН доступной информации о локальных свойствах решаемой задачи в различных зонах области определения во время работы процедуры глобального поиска в совокупности с экономными многомерными схемами хранения и обработки поисковой информации.
-У-
В настоящей работе рассматриваются оба этих направления. С одной стороны предлагаются нонкретные параллельные схемы решения задач глобальной многоэкстремальноИ оптимизации, а с другой стороны - конкретные схемы учета и хранения поисковой информации.
При решении задач рассматриваемого нласса на многопроцессорных системах время вычисления значения Функции даже в одноИ точке существенно превышает как времена обменов между процессорами, так и время вычисления координат очередной точки (или группы точен) для следующей параллельной итерации. Это позволяет оценивать эффективность параллельного алгоритма по двум критериям: числу точен, в которых были вычислены значения фуннции, и времени, затраченному на решение. При этом желательно, чтобы сетна в области поиска, образуемая точками параллельного алгоритма, обладала такой же (или почти такой же) плотностью, нак и в случае зффентивного последовательного метода, т. е. введение параллелизма не должно рождать избыточных вычислений значений оптимизируемой функции. С учетом этого условия желательно использовать возможно большее число процессоров с максимальной загрузкой.
Разумеется, параллельные вычисления могут быть использованы и для ускорения анализа математической модели оптимизируемого объекта, т. е. для ускорения вычислений, .соответствующих определению значения оптимизируемой функции в одной точне. Однако, организация таного ускорения имеет свою специфину для каждого конкретного класса моделей и достаточно подробно обсуждается в литературе.
Вопросы построения решающих правил для параллельного выбора точек итераций) ноторым посвящена настоящая работа, гораздо менее изучены. В настоящее время начинают появляться первые работы в этом направлении (В. Н. Белецкий, П. Ж. М. ван Лаарховен, ф. А. Лутсма, Т. А. Стратер, П. М. Пардалос, М. ФеИлмейер, Р. Флетчер, Т. Л. Фриман, Р. Шнабел и др. ), однако, большей частью они относятся н проблемам, связанным с поиском локально -от имальных решений, мало затрагивая вопросы отискания глобального оптимума. В связи с этим представляются актуальными исследования по разработке эффективных
'Л-
параллельных алгоритмов решения многоэкстремальных задач глобальной оптимизации.
Цель работы. Главной целью работы является создание технологии построения параллельных алгоритмов для решения сложных многомерных задач поиска глобального энстремума (где вычисление значения оптимизируемой функции даже в одной точке требует значительного времени). Достижение этой цели включает в себя танжеі
построение новых последовательных алгоритмов, гибко использующих локальные свойства решаемой задачи в различных зонах области определения во время глобального поиска;
создание новых многомерных методов решения проблемы, использующих эффективные схемы хранения и обработни поисновоИ информации.
Поскольку при параллельных вычислениях происходит частичная потеря поисковой информации (вычисления, выполняемые одновременно, не используют результаты друг друга), большое внимание уделяется определению условия сходимости построенных алгоритмов, а также теоретическому исследованию вопросов их эффективного применения с цепью выяснения режимов работы, при которых использование параллельных процессоров дает ускорение решения задачи во времени при минимальных дополнительных вычислениях.
Научная новизна :
для решения одномерных и многомерных безусловных задач глобальной оптимизации, в которых время вычисления значений Функции одно и то же во всех точках области определения, предложены параллельные синхронные алгоритмы, обобщающие эффективные последовательные методы, построенные в рамках информационно-статистического подхода;
разработанные методы создания параллельных алгоритмов применены для построения класса параллельных синхронных характеристических алгоритмов, где с единых позиций решен вопрос распараллеливания многих последовательных методов глобальной оптимизации;
для решения задач, в которых время вычисления значений функции может меняться в зависимости от положения точки в
обпасти определения, предложен подход н построению двух видов параллельных асинхронных алгоритмов : для безусловных задач и для задач с невыпуклыми ограничениями;
- предложен новый подход и построению быстрых алгоритмов
глобальной оптимизации эа счет введения нижних огибающих,
построенных с использованием первых производных и лучше
приближающих целевую фуннцию, чем методы, работающие тольно с
ее значениями.
^ч - построены последовательные и параллельные алгоритмы, осуществляющие' во время работы процедуры глобального поиска лональную настройку на поведение целевой фуннции и ограничении в различных зонах области определения;
предложены новые экономные схемы хранения и обработки поисковой информации, позволяющие строить многомерные методы, использующие как параллельные вычисления, так и локальную настройку для ускорения поиска;
дла всех построенных параллельных алгоритмов с единых позиции рассмотрены вопросы сходимости и теоретически установлены границы эффективного распараллеливания;
предложены подходы к решению задачи динамического управления числом процессоров, участвующих в распараллеливании, а также задачи динамического распределения нагрузки между процессорами.
Практическая ценность работы. Исследования по теме диссертации выполнялись в рамнах основного научного направления Нижегородского университета "Методы принятия решении и оптимизация", задания 06. 21А научно-технической программы ГКНТ СССР О. 80.03, а также темы 'Адаптивное управление, принятие решении и оптимизация" Ife гос. регистрации 0186. 0136674 Координационного плана НИР АН СССР на 1986-1990 гг.
Практическая значимость работы определяется возможностью использования разработанных численных методов в системах принятия решения для САПР и АСНИ на однопроцессорных и многопроцессорных вычислительных комплексах. Результаты работы использовались при проведении исследовании в рамках научно-технической темы "Раыработна теоретических основ и программная реализация систем полиержки выбора решении для
-*-
научных исследований и проектирования" (К- Гос. регистрации 01. О. 30007173).
Апробация работы. Основные результаты работы докладывались на совещаниях-семинарах "Использование вычислительных средств в экологии, экономике и медицине" (Горький, 1986, Саратов, 1988), Международной конференции "Передовые вычислительные методы, параллепьные вычисления и оптимизация " (ФРГ, Карлсруэ, 1987), VI Международной конференции "Основы теории вычислении" (Казань, 1987), IV Всесоюзной конференции "Автоматизация поискового конструирования и подготовка инженерных кадров" (Волгоград, 1987), VIII Всесоюзном конференции "Проблемы теоретической кибернетики" (Горьким, 1988), II Всесоюзном совещании "Конвейерные вычислительные системы" (Киев, 1988), VI научной конференции "Методы математического программирования и программное обеспечение" (Свердловск, 1989) , Всесоюзном научно-техническом совещании "Перспективы развития локальных информационно-вычислительных сетей на базе персональных ЭВМ" (Москва, 1989), конференции "Диалог "Человек - ЭВМ" (Свердловсн, 1989), VII Всесоюзном семинаре "Распараллеливание обработки информации" (Львов, 1909), IV Всесоюзном межвузовском научном семинаре "Диалоговые средства распределенной обработки данных в комплексах и сетях ЭВМ" (Москва, 1990), Первой Советско - Итальянской конференции по методам и приложениям математического программирования (Италия, Четраро, 1992), Международном совещании "Распределенные и параллепьные вычисления в системах логического программирования" (США, Вашингтон, 1992), Межгосударственной научной конференции "Экстремальные задачи и их приложения" (Н.Новгород, 1992), 5-И Международной конференции по параллельным вычислениям PARLE (ФРГ, Мюнхен, 1993), 18-м Международном симпозиуме "Исследование Операции" (ФРГ, Кельн, 1993), ХІІ-И Международной конференции "Математическое Программирование" (Венгрия, Матрафюред, 1994), Международном совещании "Передовые математичесние методы в электрических и электронных измерениях" (Италия, Комо, 1994), Международной конференции EURO XIII / OR 36 "Исследование Операций для разработки практических решении" (Шотландия,
-if-
Глазго, 1994), Международной конференции "Глобальная оптимизация : численные методы и приложения" (США, Принстон, 1995), II1-м Международном совещании по глобальной оптимизации (Венгрия, Сегед, 1995), а также на научных семинара* Московского, Санкт-Петербургского, Нижегородского университе тов, ВЦ РАН, в итальянских университетах городов Рим, Неаполь, Бергамо, Саперно, Коаенца, в университетах городов Поган (Юта; США), Баулдер (Колорадо, США), институтах Итальянского Наци онального Совета по Науне в городах Рим, Милан, Козенца и др.
Публикации. По теме диссертации опубликовано 53 работы. Основное содержание диссертации изложено в работах [1-30].
Структура и обьем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 358 наименования и приложения. Основной печатный текст занимает 253 страницы, кроме того, в работе содержится 32 рисунка и 16 таблиц.