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

О

ОД

[ ' л, О Л • -

2 5 ЯУ»« РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

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

Горчаков Андрей Юрьевич

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

01.01.09 - математическая кибернетика

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

Москва - 1998

Работа выполнена в Вычислительном центре Российской Академии наук

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

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

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

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

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

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

Защита состоится "_"_ 1998г. в_часов

на заседании специализированного совета К 063.91.03 в Московском физико-техническом институте по адресу 141700, г. Долгопрудный, Институтский пер.д.9.

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

Автореферат разослан "_"_199 г.

Ученый секретарь специализированного совета

д.ф.-м.н. А.И. Самыловский

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

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

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

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

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

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

Цель работы.

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

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

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

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

1) В терминах свертывающих функций сформулированы необходимые и достаточные условия сходимости класса

' методов последовательной безусловной минимизации, СФ которых не зависит от свойств образа задачи.

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

3) Проведен сравнительный анализ "зависимых" и "независимых" методов.

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

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

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

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

Публикации.

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

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

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

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

В п.1 приводится постановка задачи многокритериальной нелинейной оптимизации, дается определение функции чувствительности, рассматриваются геометрические свойства образа задачи и свертывающих функций, формулируется проблема отыскания класса методов ПБМ, удовлетворяющих заранее заданным свойствам. Класс задач (Р) определяется следующим образом: (Р1) Субдифференциал функции Р(у) в 0 не содержит векторов с бесконечными компонентами. (Р2) Р(у) непрерывная функция. (РЗ) Выполняется условие Слейтера Класс методов (Б) определим фиксированием СФ: (51) Мк(г, у) неубывающая непрерывная функция с областью определения Ъ, имеющей цилиндрический вид (если (г,, у) е Ъ, то для любого т.г: (ъг, у) е Т), включающей часть пространства {(г, у): у < 0}.

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

(РБ1) Любая предельная точка (г+, упроизвольной последовательности {(гк, у,)} является решением: гл= Р(0), У>-

(РБ2) Выполняется ограничение на расположение стационарных точек СФ (если такие имеются): для любой (г, у) е ук))имеет место М^г, у)£0

(РБЗ) Если для некоторого метода из класса (Б) первый член м'Цг, у) последовательности СФ у)},

полученный для задачи Рхиз класса (Р) равен первому члену этого же метода М^г, у) для другой задачи Рг из (Р) (т.е. М^ = М^1), то и все остальные члены последовательностей СФ совпадают: к = 2,3,...

В п.2 приводятся необходимые и достаточные условия сходимости независимых методов определяемых (Р)-(5)-(Р§).

Теорема 2.1 дает класс последовательностей СФ решающих проблему (Р)-(8)-(Р5).

Теорема 2.2 формулирует необходимые и достаточные условия сходимости за конечное число итераций.

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

В п.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. Варьирование параметров сдвига zj-, у,,, %.

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

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

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

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

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

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

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

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

3) Проведен сравнительный анализ "зависимых" и "независимых" методов.

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

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

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

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

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

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

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

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

стр.

ВВЕДЕНИЕ 2

Глава 1. Схема гибридного алгоритма многокритериальной нелинейной оптимизации 5

§ 1. Геометрические свойства образа задачи и линий уровня свертывающих функций 5

§2. Необходимые и достаточные условия сходимости независимых методов 14

§3. Несколько схем независимых методов 25

§4. Условия сходимости зависимых методов 31

§ 5. Сравнительная характеристика зависимых и 38 независимых методов

§6. Влияние независимых методов на обусловленность задачи безусловной минимизации 46

Глава Задача обоснования региональной системы охраны лесов от пожаров 54

§ 1. Условные обозначения, символы, единицы и термины

§2. Управляемые параметры задачи, ограничения и 61 целевые функции

§3.Решение задачи оптимального планирования для сезона 1997г. по Братскому авиаотделению Иркутской территориальной авиабазы. 71

При решении практических задач разрабатываются системы, где приходится по очереди использовать различные численные методы, пока подходящее решение оптимизационной задачи не будет найдено, В связи с этим в [1, 13] предлагается автоматический вызов различных численных методов, которые включены в систему. Рассматриваемая в данной работе методика ориентируется на возможность выбора метода в результате логического анализа ситуации, сложившейся в процессе решения задачи» Метод логического вывода (типа метода резолюций) анализирует результаты вычислений данной задачи и выбирает тот либо иной численный метод и его параметры для продолжения вычислений.

Построение правил, на основе которых осуществляется логический вывод - довольно сложная задача, базирующаяся прежде всего на богатом экспериментальном материале по применению набора численных методов к некоторому классу оптимизационных задач. Такой подход был реализован для набора методов безусловной минимизации (БМ). Подход показал свою эффективность в соответствующей гибридной системе, описанной в [3]. При этом использовался принцип конечного автомата, когда задается матрица переключения состояний.

В данной работе рассматривается другой класс оптимизационных задач и методов. Это нелинейные задачи условной оптимизации с одним или несколькими критериями. Идея переключения также основана на принципах конечного автомата, однако она учитывает специфику рассматриваемого класса задач, Здесь приходится использовать также первые производные функции чувствительности, которая выводится из исходных зависимостей задач. Для решения некоторых классов задач применяются методы последовательной безусловной минимизации (ПБМ).

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

выход выход выход

Заключение

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

Интересной особенностью методов последовательной безусловной минимизации является тот факт, что задача выбора метода или, более обще, вида СФ на очередной итерации, может быть целиком сведена к изящной геометрической задаче "на построение". Действительно, как мы видели ранее, процесс безусловной минимизации на каждом шаге метода ПБМ, может быть сведен к построению линий уровня СФ, касательной к образу задачи. Точнее, он начинается с некоторой линии уровня, которая затем смещается, видоизменясь и переходя в другие линии уровня до тех пор пока не будет построена касательная. Месторасположение точки касания и самой нижней границы образа задачи - функции чуствительности заранее не известно и постепенно определяется в результате серии подобных испытаний -построения точек касания. В то же время, мы получаем информацию о производных ФЧ, которая, в свою очередь, является "квази -выпуклой" нижней границей образа задачи (для выпуклых задач с ограничениями типа неравенств).

Интересным в связи с этой проблематикой является вопрос о нижней оценке трудоемкости методов ПБМ, при условии, что кривизна линий уровня или вторые производные приведенной СФ ограничены сверху, либо ограничена скорость их возрастания. Возвращаясь к конкретным методам, можно сказать, что методы аппроксимационного типа достаточно полно используют локальную информацию о местоположении графика ФЧ и совсем не используют глобальной информации, в результате чего могут проигрывать совсем грубым независимым методам "вдали" от решения.

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

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

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

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

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

Зависимые методы могут подключаться, в конечном итоге, после остановки независимого метода по причине плохой работоспособности метода БМ и продолжать работу с найденной независимым методом наилучшей точки графика ФЧ.

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

Следует заметить, что результат работы зависимых методов будет сильно зависеть от той точки, с которой были начаты вычисления (т.е. построена первая аппроксимация ФЧ в решении). В связи с этим, может быть рекомендован последовательный запуск зависимых методов из различных ортантов, если хорошее решение задачи не удается получить сразу.

Пршюжение I. Гибридный алгоритм безусловной минимизации

В данном приложении описываются правила выбора метода БМ, основанные на некоторых эвристических соображениях, апробированных на ряде практических задач.

Под гибридным алгоритмом БМ понимается процедура переключения "элементарных" методов БМ (табл.7) для повышения надежности при получении качественного решения практической задачи.

1. Адаменко Г.М. Субалгоритмы случайного поиска в нестационарных процедурах оптимизации. 10 Всесоюзный симпозиум. «Системы Программного обеспечения решения задач оптимального планирования». ЦЭМИ АН СССР. Москва. 1988.

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

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

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

5. Волошинов В.В., Королев А.Н., Коссых Ю.В., Коткин Г.Г. Зависимые методы векторной нелинейной оптимизации. М.: ВЦ РАН 1990.

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

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

8. Голиков А.И., Коткин Г.Г., Мазурик В.П. Диалоговый комплекс программ ДИСО/ПК. Система решения и исследования задач многокритериального нелинейного программирования (ДИСО/ПК

9. МКНЛП). Алгоритмы и программы: Информ. Бюл. ВНТИЦ, 1988, №2, с.4-5.

10. Голиков А.И., Коткин Г.Г.,Характеристика множества оптимальных оценок задачи многокритериальной оптимизации Ж.Выч. матем. и матем. физ., 1988, №10, стр. 1461-1474.

11. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

12. Fiacco А.V. and Mccormick G.P. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. Reseach Analysis Corp. New York: Willey & Sons, 1968.

13. Исскуственный интеллект. Кн. 2. Модели и методы. М.: Радио и связь, 1990.

14. Коршунов В.К., Коткин Г.Г. Применение логического программирования в численных методах оптимизации. В сб. Исследование операций (модели, системы, решения) ВЦ РАН, М. 1991, с.80-99.

15. Коткин Г.Г. Класс методов последовательной безусловной минимизации. М: ВЦ РАН СССР. 1989.

16. Ларичев О.И., Горовиц Г.Г. Методы поиска локального экстремума овражных функций. М.: Наука. 1990.

17. Мазурик В.П. 111111 Администратор полей. Программные средства. Информ. бюлл. вып. 1, М., ВЦ АН СССР, 1989, с.39-40.

18. Немировский A.C., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука 1979.

19. Нестеров Ю.Е. Эффективные методы в нелинейном программировании. М.: Радио и связь, 1989. - 304 с.