Применение искусственного интеллекта для решения задач многокритериальной нелинейной оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РГБ ОД

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

ГОРЧАКОВ Андрей Юрьевич

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

01.01,0У - математическая кибернетика

• Автореферач диссертации на соискание ученой степени каидидага физико-математических наук

Москва - 2000

Работа выполнена в Московском физико-техническом институте (Государственном университете)

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

наук, профессор В.И. Цурков

Официальные оппоненты - доктор физико-математических

наук, профессор В.В. Дикусар

кандидат физико-математических наук В.Б. Бритков

Ведущая организация - Институт математического

моделирования Российской Академии наук

Защита состоится «2^ » 1ЛН>Н$._2000г. в /¿7

часов на заседании диссертационного совета К 063.91.03 в Московском физико-техническом институте

(Государственном университете) по адресу 141700, г. Долгопрудный, Институтский пер. д.9.

С диссертацией можно ознакомится в библиотеке Московского физико-технического института

(Государственного университета).

Автореферат разослан <Ц9 » /л(\Л 2000 г.

Ученый секретарь диссертационного совета ^у кандидат ф.-м.н. ^-то«О.С.Федько

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

Актуальность темы.

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

min f(x), х е Х(0, 0)

где Х(у, V) = {х с Q R": g(x) < у, h(x) = v}; f(x), g(x), h(x) -непрерывные вектор-функции, f: Q —> Я"1*1, g: Q —> Rp, h: Q —> Rs. Множество Q задано параллелипипедными ограничениями: Q = {x e R" \ а <x <b}, где a с R", b e R" -векторы констант, а < b.

Для решения данной задачи применяется класс методов последовательной безусловной минимизации (ПБМ), а именно методы, которые сводят исходную задачу, к последовательности задач вида:

min Mk{f(x) , gr(x) , h(x)), k= 1, 2, xeQ

где - MK : Z —> R1, Z d RmH+p+s, k = 1,2,... -последовательность так называемых свертывающих функций (СФ) (например метод внешних штрафных функций может использовать СФ вида

мк(и, У, Iii+tk£ 6V-V тк £ (¿f

t- o,m i-tp t'f.S

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

анализа ситуации, сложившейся в процессе решения задачи. Предлагаемая в данной работе методика использует свойства образа задачи и его границы - обобщенной функции чувствительности: F1 : Y1 —> Я1,

F1(z, у, V) = min f*[x) ,xeX(z, у, v),

л

где z— ,...¿"),для некоторого i е {0,...,т},

X(z, у, V) = {х е Q: < z, g(x) <у, h(x) = v};

Y1 = { {z, y, v) : X{z, y, v) ф 0}, i e {0,1 m}, а также свойства имеющихся в наборе численных методов и выбирает тот или иной метод и его параметры для продолжения вычислений.

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

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

Предлагаемые методы и система правил выбора метода и его параметров реализованы в системе оптимизации ИНТЕЛОС 1.0, которая апробирована при решении практических задач.

Цель работы.

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

Методы исследования.

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

Научная новизна.

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

2) Предложен набор «независимых» методов (методы внешних и внутренних штрафных функций с различными свертывающими функциями) и проведен анализ их свойств.

3) Проведен сравнительный анализ «зависимых» (в основном методы двойственных модифицированных функций Лагранжа) и «независимых» методов.

4) Разработана схема переключения методов и выбора их параметров.

5) На основе предложенной схемы создана диалоговая оптимизационная система ИНТЕЛОС 1.0 для решения многокритериальных задач на персональных ЭВМ.

Практическая ценность.

Разработана диалоговая система оптимизации ИНТЕЛОС 1.0 для решения многокритериальных задач на персональных ЭВМ. На ее основе совместно с Санкт-Петербургским НИИ лесного хозяйства написаны

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

Публикации.

По теме диссертации опубликовано 5 работ (см. [1-5]).

Структура и объём работы.

Диссертация состоит из введения, двух глав, списка литературы из 18 наименований и двух приложений. Объём диссертации составляет 104 страницы машинописного текста.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

Класс задач (Р) определяется следующим образом:

(Р1) Субдифференциал функции Р(у) в 0 не содержит векторов с бесконечными компонентами.

(Р2) Б(у) непрерывная функция.

(РЗ) Выполняется условие Слейтера

Класс методов (Б) определим фиксированием СФ:

(Э1)Мк(г, у) неубывающая непрерывная функция с областью определения 2 , имеющей цилиндрический вид (если (г-|, у) е 2 , то для любого, х2'.{г.2,у) е 2 ), включающей часть пространства {(г, у): у < 0}.

Условия согласования (РЭ):

(PS1) Любая предельная точка (z.,y.) произвольной последовательности {(zK, ук)} является решением: z.=F(0),y*<:0.

(PS2) Выполняется ограничение на расположение стационарных точек СФ (если такие имеются): для любой (zk, Ук) е Vk (Мк (zk, ук)) имеет место Мк (z, у) Ф 0.

(PS3) Если для некоторого метода Si из класса (S)

первый член М ^(z, у)последовательности СФ {М у)}, полученный для задачи Р^ из класса (Р) равен первому

члену этого же метода М^2 (z, у) для другой задачи Р2 из

(Р) (т.е. М^= М^2), то и все остальные члены

последовательностей СФ совпадают: Mk1 = м£2, к = 2,3,...

В §2 приводятся необходимые и достаточные условия сходимости независимых методов определяемых (P)-(S)-(PS) (Теорема 2.1) и необходимые и достаточные условия сходимости независимых методов за конечное число итераций (Теорема 2.2)

Теорема 2.1: решением проблемы (P)-(S)-(PS). является класс последовательностей СФ, которые для любых компакта К и последовательности {tk} удовлетворяют условию к, dO(Mk 0, при к

—> оо. Здесь

1) )х(А, В) := sup ¿2/11 X1-X2II хеА хеВ

-расстояние между множествами А я В по метрике Хаусдорфа;

2 )Mk(y):=sup z

{z: Mk(z,y)=tk} - результат разрешения уравнения Mk(z, у) = it-относительно z (с учетом возможной неопределенности); Ъ)А\к:=АПК;

4) dO(z0) := {(z, у): z = zft у < 0 или z<za У = О, у < О, для некоторого j} - граница отрицательного ортанта 0(z0) с началом в (za 0).

Теорема 2.2: решением проблемы (P)-(S)-(PS)/ является класс последовательностей СФ, которые для любых компакта К и последовательности {tkj удовлетворяют условиям

1) для всех к > к0 Vk(t^ n ]у(0) = dO(Mk (О)} к n iy(0)

2) для любого у > 0 (такого, что существует z:(z,y)eK,\\y+UO)

(Мк (0) - (Мк (у))/\\У+ II -> «>, при к-> со. Здесь Iy(0) ~ {(z, у): у <0};у+ := (у1* ../+), где у/+= шах {0, /).

В §3 предлагается несколько схем независимых методов (основанных на свертывающей функции смешанного штрафа - комбинация внешнего и внутреннего штрафа), отличающихся друг от друга способом пересчета коэффициентов штрафа:

1) Метод, обеспечивающий (по возможности) одинаковую скорость сходимости по невязкам -

Li = /4(УкГ'УСА- Ул-j)) -

для внешнего штрафа (и аналогичная формула для внутреннего штрафа).

2) Метод, обеспечивающий скорость сходимости не ниже скорости сходимости метода 1 с константой С2-

tk+i =шах { ik+i, С2 tk} для внешнего штрафа и шт {ik+i> С2 tк) Для внутреннего штрафа

3) Метод, обеспечивающий работоспособность метода безусловной минимизации не хуже, чем в методе 1 с константой Ci -

ik+i =min{C1 tk+i, max{tk+i, C2 tk} для внешнего штрафа и t!k+1=max{Ci tk+i, min{{k+[, C2 tk} для внутреннего штрафа

4) Группа методов, обеспечивающая (по возможности) равномерное уменьшение всех ограничений (невязок) - в основе методов лежит соотношение

Ук+г Ук+ь для iJ = 1,...,р ; сначала вычисляются по

методу 1-3, затем для/= Ащтах/У^^,

далее ¿к+1={к)(У ¡¡Ук?' -Для внешнего штрафа

Аналогичная формула выводится и для внутреннего

штрафа.

В §§4 и 5 рассматриваются условия сходимости «зависимых» методов и проводится сравнительный анализ «независимых» и «зависимых методов». Так же в §5 предлагается гибридная схема переключения методов при решении многокритериальных задач. Методы применяемые в предложенной схеме:

Независимые методы.

I. Выбор Парето-оптимальной оценки.

1. По целевой точке.

2. Линейная свертка критериев.

II. Вид штрафа.

1. Внутренний.

2. Внешний.

III. Абсолютное значение степеней в свертывающей функции.

IV. Способ пересчета коэффициентов штрафа.

1. Равномерный независимый.

2. С постоянной сходимостью на различных итерациях.

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

Зависимые методы.

I. Выбор Парето-оптимальной оценки.

1. По целевой точке.

2. Линейная свертка критериев.

II. Вид апроксимации ФЧ.

1. Линейная.

2. Квадратичная.

III. Наличие дополнительного варьирования оценок

вторых производных СФ.

1. Примерно постоянные оценки.

2. Увеличение оценок, например за счет прибавления к СФ внешнего штрафа.

3. Уменьшение оценок за счет варьирования дополнительных параметров метода.

IV. Вид СФ.

V. Варьированием каких параметров обеспечивается

работа метода в соответствии с аппроксимационной

схемой.

1. Варьирование параметров сдвига Zk, yk , v^.

2. Варьирование параметров наклона 1;к, .

3. Совместное варьирование.

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

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

В приложении 1 рассматривается гибридный алгоритм безусловной оптимизации используемый в системе ИНТЕЛОС для решения подзадач БМ на каждой итерации метода ПБМ.

В приложении 2 приводится краткая характеристика диалоговой оптимизационной системы ИНТЕЛОС 1.0. Описываются возможности по постановке и коррекции

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1)В терминах свертывающих функций сформулированы необходимые и достаточные условия сходимости класса методов последовательной безусловной минимизации, СФ которых не зависит от свойств образа задачи (так называемые «независимые» методы).

2) Предложен набор «независимых» методов и проведен анализ их свойств.

3) Проведен сравнительный анализ «зависимых» предложенных в В.В. Волошинов, А.Н. Королев, Ю.В. Коссых, Г.Г. Коткин «Зависимые методы векторной нелинейной оптимизации» и «независимых» методов с целью включения их в схему переключения методов и выбора их параметров.

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

5) На основе предложенной схемы создана диалоговая оптимизационная система ИНТЕЛОС 1.0 для решения многокритериальных задач на персональных ЭВМ, в которую вошли предложенные в работе методы. Для ускорения разработки и увеличения надежности системы за основу взяты: методы безусловной минимизации

разработанные в ВЦ РАН и система разработки пользовательского интерфейса «Администратор Полей» ("Field Manager"). Произведена компоновка данных систем с гибридной схемой алгоритма.

6) На основе диалоговой оптимизационной системы ИНТЕЛОС 1.0 совместно с Санкт-Петербургским НИИ лесного хозяйства созданы комплексы программ для поиска оптимального плана в задачах обоснования региональной системы охраны лесов от пожаров и оптимального оперативного планирования деятельности ее подразделений.

7) В процессе разработки комплексов программ был осуществлен переход с операционной системы MS-DOS к операционной системе Windows-95 путем замены модулей «Администратора Полей». Простота данного перехода показала правильность подхода к использованию модульной схемы построения системы.

СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ.

1. Базанова Ю.Н., Волошинов В.В., Горчаков А.Ю.,Гордеев Э.Н., Королев А.Н., Коршунов В.К., Коссых Ю.В., Коткин Г.Г., Лебедев A.B. Интеллектуальная оптимизационная система ИНТЕЛОС. М.: ВЦ РАН, 1993.

2. Базанова Ю.Н., Горчаков А.Ю., Коршунов В.К.,Коткин Г.Г. Гибридная схема многокритериального нелинейного программирования. М.: ВЦ РАН, 1994.

3. Горчаков А.Ю., Гордеев Э.Н., Коршунов В.К., Коткин Г.Г. Гибридная оптимизация и принятие решений. М.: ВЦ РАН, 1994.

4. Горчаков А.Ю., Коткин Г.Г. Необходимые и достаточные условия сходимости класса методов нелинейного программирования. Изв. РАН Теория и системы управления, 1995, №1 с.118-130.

5. Берман Е.С., Горчаков А.Ю., Николаева И.А., Шур Ю.З., Яшин С.К. Оптимальное планирование деятельности региональной системы охраны лесов от пожаров. Санкт-Петербург: СПбНИИЛХ 1998, с. 147-152.