автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Методы моделирования и решения задач глобальной оптимизации в интегрированной программной системе

РОССИЙСКАЯ АКАДЕМИЯ НАУК

РГО од

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

Кабанов Павел Николаевич

МЕТОДЫ МОДЕЛИРОВАНИЯ И РЕШЕНИЯ ЗАДАЧ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ В ИНТЕГРИРОВАННОЙ ПРОГРАММНОЙ СИСТЕМЕ.

05.13.18 - "Теоретические основы математического моделирования, численные•методы и комплексы программ"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Мосйва-1994

Работа выполнена в Вычислительном центре РАН.

Научный руководитель - кандидат физико-математических наук

H.A. Потапов.

Официальные оппоненты: доктор технических наук,

профессор Д.И. Батищеп, кандидат физико-математических наук И.С. Литвинчов.

Ведущее предприятие: Институт проблем информатики РАН

Защита диссертации состоится

.у.

1994г.

в/^часов на заседашш специализированного совета Д002.32.05 Вычислителього центра РАН по адресу: Москва, ул. Авилова, Д. 40.

С диссертацией можно ознакомиться в библиотеке МИ РАН имени В.А. Стеклова.

Автореферат разослан 1994г.

УчшшП секретарь специализированного совета ВЦ РАН

кандидат физико-математических наук

—

ОБЩАЯ ХАРАКТЕРИСТИКА. РАБОТЫ

Актуальность темы. Для современного этапа развития оптимизации характерно усиление внимания к проблемам решения много -зкстремалышх нелинейных задач большой размерности. Это вызвано тем, что нелинейные модели наиболее адекватно описывают Соль-шинство практ!гшских проблем.

Как известно, задачи поиска глобального экстремума относятся к классу особо сложных. Для решения таких задач предложены различные методы исследования и алгоритмы.

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

Цель работы. Выполняя данную работу, автор ставил перед собой следующие основные цели: . '

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

2)Разработать модификации метода неравномерных покрытий для решешш задач оптимизации.

3)Разработать алгоритмы глобальной оптимизации, основанные на построении миноранты целевой функции в окрестности точки локального минимума.

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

5/Разработать специализированные проблемно-ориентированные программные средства, позволяющие реализовать предложенную технологию.

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

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

-исследован и разработан метод решения задач глобальной оптимизация, основанный на моделировании поведения функции в окрестности локального минимума;

-разработаны модификации метода -неравномерных покрытий, использующие процедуры оценки константы Липшица в процессе работы;

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

-разработан комплекс проблемно-ориентированных программ для решения задач нелинейной оптимизащш с использованием графических средств анализа многокритериальных задач.

Практическая значимость. Разработанная программная система SOI,vex позволяет решать разнообразные практические задачи нелинейной оптимизации и исследовать математические модели. При

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

Аппробация. Основные результаты работы прошли успешную ан-пр*~-бзцнгс на Девятой школе-сошшар по методам оптимизации и их приложениям. (Иркутск I992D, Межгосударственной научной кошфо-ринцип "экстремальнее задачи и их приложения". (Нижний Новгород. Г-ЛСг). конференции по теории исследования операций в Финляндии (г.Хельсинки 1992) п симпозиуме по математическому моделированию во Франции (г.Компьен 1993). а также на научных семинарах отдела пргасладных проблем оптимизации ВЦ РАН.

Внедрение. Система SOI.VEX используется при решении практических задач в ВЦ РАН, некоторых предприятиях и ВУЗах г. Москвы.

Структура и объем работы. Диссертация состоит из введения, четных глав, заключения, списка литературы и приложения. Объем диссертации без приложений - 106стр. Список литературы содержит 62 названия.

СОДЕРЖАНИЕ

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

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

как единого процесса, объединяющего этапы постановки, расчета и анализа результатов.

В первом параграфе даются примеры задач оптимизации в математическом моделировании.

Во втором параграфе представлены четыре возможные постановки общей задачи нелинейного программирования: .-задача безусловной оптимизации (БМ); -задача нелинейного программирования (НЛП) (шш задача условной оптимизации):

гзадача глобальной оптимизации (ГЛОБ); -задача многокритериальной оптимизации (МКО). В третьем параграфе рассматриваются особенности решения задач нелинейной оптшиэации. Задача глобальной оптимизации в первоначальной постановке может иметь такую структуру, что применение оптш.шзационных алгоритмов оказывается неэффективным. Как правило, практик не может-точно сформулировать проблему, то есть, во-первых, данные могут быть представлены с некоторой неточностью, а во-вторых, недостаточно ясны цели оптимизации. Причем, практик готов изменить условия задачи ради достижения хорошего решения.

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

В четвертом параграфе излагаются причины рассмотрения различных постановок задач нелинойной оптимизации в рамках единого

подхода п, соответственно. объединения четырех классов алгоритмов в единую алгоритмическую структуру.

Идея построения и использования быстрых методов решения, сочетания расчетов, проведенных с их помощью, с поверочными расчетами на полной модели является одной из причин рассмотрения задач БМ. НЛП, ГЛОБ, МКО в рамках единой модели.

Кроме того, задачи одного класса являются обобщением задэч другого класса. По этому признаку задачи можно расположить в следующем порядке:

МКО т

ГЛОБ г

НЛП т

БН

При этом задачи верхнего уровня оказываются обобщением задач нижнего уровня.

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

Объединение задач БМ. НЛП, ГЛОБ с задачами МКО связано с тем, что все эти три класса задач могут рассматриваться в многокритериальной форме. Задачи МКО оказываются при этом обобщешгем БМ, НЛП или ГЛОБ.

Во второй главе дано описание алгоритмов решения задач

глобальной оптимизации, включенных в систему.

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

. Во втором параграфе представлены процедуры оценки константы Липшица в методе неравномерных покрытий. Оценка константы Липшица основана на лемме:

,Лемма1: Пусть функция f(х) дифференцируема в параллелепипеде Р={хекп а < х < Ь, a€Rn. b€Rn) и имеет ограниченные частные производные, причем для любых у1,у2«Р существует константа

и такая, что выполняются условия: dt(у.) öi(y?)

|----I < Ii - Уо1. для любого 1=1.....П (1)

dxi дх1 1 *

Тогда, если оценки константы Липшица по каждому из направлений

L°= |i(x1)-l(Xg)|/JX1-X2|, (2)

ГД0 = (x^ • * - • ♦ * * * * = «X^ • • - . »ЗС-j * * • • )» TO константа Лишпцэ Ь функции Х(х) в параллелешшеде Р удовлетворяет условию:

Ь < Уз (Li+Mta1- b1))2 (3)

i 1

В двоичной схеме ветвления длина ребра параллелепипеда на уровне к принимает значение 1±/2к, длина 1-го ребра исходного парзллолепшюда Р. При этом оценка константы Липшица сверху для параллелепипеда Р^ уровня к ¡шеет вид:

LTJ - / 2 (min Ь°+МЩ/2к))^ . (4)

1 11

вычисляется в точках параллелепипеда Р^.

Радиус покрывающего шара определяется по следующей формуле:

Кр - (f(z)- f* + e)/Lp , ' (5)

К К

где z - центр шара. Радиус покрывающего шара будет зависеть от размерз того параллелепипеда, который мы собираемся покривать. Таким образом, поправка оказывает существенное влияние, если значение фушодш далеко от рекордного.

Для двоичный схемы покрытий процедура оценки константы Липшица в процессе вычислений может быть организована следующим образом. Каждому уровню к соответствует своя оценка константы Липшица L^ (минимальная из всех полученных оценок), которая вычисляется при работе на уровне к либо на более низких уровнях. При переходе с k-го уровня на к+1-ый (когда еще нет оценки константы Липшица для уровня к+1), радиус покрывающего шара определяется по формуле соответствующей уровню к. Таким образом, оценки константы Липшица для различных параллелепипедов одного и того же уровня будут разными, что и позволяет моделировать поведение функции в ходе вычислений.

В третьем параграфе дан обзор методов глобального случайного поиска.

В четвертом параграфе изложена идея широко известного ' метода мультистарт.

В пятом параграфе излагается идея моделирования поведения целевой Функции в окрестности точки локального минимума с помощью миноранты-конуса. Пусть х* - локальный минимум функции

Их). Пусть область притяжения х* ограничена. Зададим некоторое в > О. Тогда существует константа М^ > о такая, что Jx - х*| - е < (f (х) - t (х*)) для всех точек из области притяжения.

Теорема 1: Пусть х* i - 1.....k - все локальные минимумы

функции f (х) и н^ - соответствующие константы, тогда для любого £>0 И любого X € X:

f (х) > F (х). где Р(х) - mln(f (х*) + М^х - х*| - е).

На основании Теоремы 1 мы можем построить следующий алгоритм:

Пусть задано е > О. На первом шаге из случайно выбранной точки х£ осуществляем локальный спуск, получаем локальный минимум х^. Построим конус Р(х) - f (xq) + u0|x - Xq| - e, где MQ определяется по формуле:

U0 - (i (x0) - 1 (**) + e) / |x0- x*|. (6)

Для такого U0: P (Xq) « r (x0). P (x*) = t (x*) - e. Таким образом, мы получаем приближенное значение константы liQ.

На 1-ом шаге мы выбираем случайную точку х^. Если P(x1)>f(x1), то делаем локальный спуск, иначе переходим к следующей точке. После локального спуска возможны два исхода: I.найден новый локальный минимум, 2.мы попали в старый локальный минимум.

В первом случав находим согласно формуле:

мки -(i -* ^ + е) у »v <7>

и, увеличив-к на единицу, изменяем Р (х).

Во втором случае, если мы нашли j-й минимум, то изменяем Mj согласно формуле:

Mj = (I U±) -г (х*) + е) / Jxj- х*|. (8)

и переходим к следующей точке.

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

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

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

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

Эффективность решения прикладной задачи существенно связана с качеством организации и управления процессом решения, распадающегося на три части:

^Постановка Расчет -> Анализ и коррекция -у»

Разработаннная интегрированная система оптимизации SOLVEX включает в себя средства для организации процесса решения оптимизационной задачи во всех трех частях.

SOLVEX решает задачи в следующих постановках:

I безусловная минимизация (БМ);

2)Нолинейное программирование (Hill);

'3) Глобальна я оптимизация (ГЛОБ);

4)Многокритериальная оптимизация ШКО).

SOLVEX реализует следующие подходы к решению многокритериальных задач:

а)Линейная свертка; б Шшимаксная свертка;

в)Долевая свертка, которая предполагает наличие некоторого идеального решония (целевой точки):

д)Чбтвертым вариантом понятия решения многокритериальной задачи является е-сеть множества Парото.

SOLVEX использует два принципиально различных способа построения приближешюго решения задачи МКО. В одном из них используются свертки. Второй подход использует понятие е-сети множества Парето. Для реализации этого метода S0LVBX использует специальные модификации алгоритмов неравномерных покрытий для задач МКО.

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

Система SOLVEX состоит из 5 основных функциональных блоков: Информация, Постановка, Решение, Анализ, Настройка.

Постановка позволяет определить тип задачи, целевые функции, функции-ограничения, парзллелешшедные ограничения, точность решения задачи.

SQLVKX различает 4 типа 'задачи: функция (численный

анализ), график (графические средства), одно (задача оптимизации с одним критерием), иного (многокритериальные задачи).

Блок решение включает в себя 9 алгоритмов. Так как эффективность работы алгоритма во многом зависит от специфики конкретной задачи, то для каждого класса задач тлеется несколько ра злпчных алгоритме в.

Для решения задач БМ используются 4 алгоритма: метод Пауэлла, метод сопряженных градиентов. R-алгоритм Шора, метод прямого поиска Хука и Дживса. Для решения задач НЛП используются '3 алгоритма: метод штрафных функций, метод модифицированных функций Лагранжа и метод параметризации целевой функции. Две модификации метода неравномерных покрытий предназначены для решения задач ГЛОБ. Одни и те же условия используются для решения задач с одним критерием и задач МКО. Эти девять алгоритмов составляют ядро блока решение. Однако, комбинируя алгоритмы, меняя параметры п постановку задачи, можно создавать новыо схемы решения с учетом специфики задачи. Так, для решения задач МКО реализован специальный блок, который позволяет создавать различные свертки либо строить е-сеть множества Парето. При этом один и тот же алгоритм может приводить к различным решениям в зависимости от того, какая схема была выбрана в многокритериальном блоке.

В блоке Настройка реализован доступ к параметрам алгоритма и выбору Bepcmi алгоритма.

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

SOLVEX имеет модуль построения графиков функций одной пе-

ременной и сеченнй функций многих переменных. Примем реализованный инструмент позволяет строить не только плоские сечения, но и создавать трехмерные образы, предсталяя их с различных точек зрения.

Два инструмента реализованы для графического представления оптимального множества (множества Парето).

Гистограмма поможет проследить зависимость критериев на множестве Изрето. уточнить его структуру, отсечь заведомо неудовлетворительные точки, принять решение о направлении дальнейшего поиска. Каждая точка изображается на экране в виде гистограммы. Значение 1-го критерия в выбранной точке определяет высоту 1-го столбика гистограммы. Пользуясь клавиатурой, пользователь может перемещаться по множеству Пэрото, при этом текущая точка в каждый момент представляется на экране в виде гистограммы.

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

Блок Информация включает в себя средства для записи и чтения данных с диска. Кроме того, этот блок предоставляет возмож-

ность доступа к результатам решения задачи - множеству Парето или "оптгадальной" точке. В системе постоянно поддерживаются два объекта : текущее "множество Парето" (для текущей задачи МКО) п текущее "оптимальное решение" (для текущей задачи с одним критерием). "Множество Парето" может быть либо решением задачи МКО, либо начальным приближением для задачи МКО, которую мы собираемся решать. Аналопгчно, "оптимальное решение" может выполнять две функции для задачи с одним критерием.

Блок Настройка организует доступ к параметрам алгоритмов и выбор типа иллюстрац1Ш работы алгоритмов. В системе реализованы 4 типа иллюстрации работы алгоритмов.

В третьем параграфе представлены, способы исследования и решения задач в интегрированной оптимизационной среде:

-средства компьютерной графики для выбора правильного масштаба переменных;

-средства для коррекции задачи и решения обратной задачи:

-средства выбора эффективного,алгоритма;

-поиск решения в подпространстве;

-принцип микроскопа;

-использование графических средств;

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

Центральной идеей предлагаемого подхода является стремло-

:шо предоставить пользователю как можно больше возможностей для •строения последовадельностий конструктивных действий при ор-анизчции пр<эцосса решения задачи. Основными группами такого ■да дойствий являются:

а)анализ состояния процесса решения задачи;

б)коррекция условий задачи:

в)выбор алгоритмов и их параметров.

Действия группы а) дают возможность проанализировать предыдущее решении и результаты, условия задачи и зависимость ре-;:;я1шя от степени ослабления или усиления условий (выявление узких мост).

Исходя из результатов анализа, операции группы б) позволяют скорректировать постановку задачи (изменяя описания функционат льных и диапазонных ограничений, описания целевых Функций, выбрать подходящую стандартную постановку задачи и подп|>остранство переменных для елодующего этапа поиска оптимального решения). На этой стадии исследователь может воспользоваться одной из четырех стандартных постановок задачи.

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

Далее описаны различные варианты сценариев для каждого из четырех классов задач:

-безу словная мшимиза ция ; -нелинейное программирование ; -глобальная оптимизация ; -многокритериальная оптимизация.

В четвертой главе представлены примеры решения задач с помощью интегрированной оптимизационной среды GOI.VKX.

В заключении сформулированы основные результаты диссертации.

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

2)Разработаны модификации метода неравномерных покрытий, использующие процедуры оценки константы Липшица в процессе работы алгоритма.

ЗШредложены системные средства анализа модели и оргзниза-Ц1Ш процесса решения с использованием специализированных графических образов.

4)Разработана технология решения задач глобальной оптимизации. позволяющая 0бъед1шить этапы постановки, решения и анализа результатов в едином процессе,.

5)Разработаны специализированные проблемно-ориентированные программные срдства, позволяющие реализовать предложенную технологию. Рззработанная программная система SOLVEX позволяет решать разнообразные практические задачи нелинейной оптимизации и исследовать математические модели. При этом использование графических средств позволяет облегчить диалог пользователя с машиной и учитывать неформальные знания пользователя.

По теме диссертации опубликованы следующие работы:

1. P.Kabanev, M.Potapov. Лп approuch for interactivo solving multlcrítería ргсЫетз. - Procoedingn of 14th Inter-

national Simposlura on Mathematical Programming, Amsterdam, Netherlands, Augu3t 5-9, 1991.

2. Кабанов П.Н., Потапов M.A. Интегр1тр0ванная система решения задач оптимизации и поддоржки принятия решений "КОМПРОМИСС" . Тезисы докладов, девятая школа-семинар. Методы оптимизации и их приложения. Иркутск 1ЭУ2г.

3. P.Kabanov, M.Potapov, Parallel algorithms ior solving multieriteria problems in decision support oy3tem "Compromioe". EURO XII/TIMS XXXI Joint International conference Operational research/management зс1епсе Juno 29- July 1, 1992, Pinland.

4. Кабанов П.Н., Потапов M.A. Решонио задач оптимизации в системе "КОМПРОМИСС". Тезисы докладов, Межгосударственная научная конфородщия "Экстремальные задачи и их приложения". Нижний Новгород, 1992г.

5. P.Kabanov, M.Potapov, The SOLVKX 3y3tera for nonlinear and multieriteria optimization. - 16th Conference on Syetom lio-delling and Optimization, July 5-9, 1993, Compiegne, Prance.

Утверждено к печати Вычислительным Центром РАН

Подписано в печать 15.04.94. Формат 60/84/I/I6. Объем In.л. Тираж 100 экз.. Заказ N 15

Участок оперативной полиграфии Института этнологии и антропологии РАН. II7304 Москва, Лешшский просп. 32.