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

• Горчаков, Андрей Юрьевич
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Горчаков, Андрей Юрьевич

стр.

ВВЕДЕНИЕ 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) для повышения надежности при получении качественного решения практической задачи.

Список литературы диссертационного исследования кандидат физико-математических наук Горчаков, Андрей Юрьевич, 2000 год

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 с.