Применение искусственного интеллекта для решения задач многокритериальной нелинейной оптимизации

• Автор: Горчаков, Андрей Юрьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Москва
• Количество страниц: 104 с. : ил.

При решении практических задач разрабатываются системы, где приходится по очереди использовать различные численные методы, пока подходящее решение оптимизационной задачи не будет найдено. В связи с этим в [1, 13] предлагается автоматический вызов различных численных методов, которые включены в систему. Рассматриваемая в данной работе методика ориентируется на возможность выбора метода в результате логического анализа ситуации, сложившейся в процессе решения задачи. Метод логического вывода (типа метода резолюций) анализирует результаты вычислений данной задачи и выбирает тот либо иной численный метод и его параметры для продолжения вычислений.
Построение правил, на основе которых осуществляется логический вывод - довольно сложная задача, базирующаяся прежде всего на богатом экспериментальном материале по применению набора численных методов к некоторому классу оптимизационных задач. Такой подход был реализован для набора методов безусловной минимизации (БМ). Подход показал свою эффективность в соответствующей гибридной системе, описанной в [3]. При этом использовался принцип конечного автомата, когда задается матрица переключения состояний.
В данной работе рассматривается другой класс оптимизационных задач и методов. Это нелинейные задачи условной оптимизации с одним или несколькими критериями. Идея переключения также основана на принципах конечного автомата, однако она учитывает специфику рассматриваемого класса задач. Здесь приходится использовать также первые производные функции чувствительности, которая выводится из исходных зависимостей задач. Для решения некоторых классов задач применяются методы последовательной безусловной минимизации (ПБМ).
Диссертация состоит из двух глав, заключения, двух приложений и списка литературы.
Глава 1 организована следующим образом, В §! вводится понятие функции чувствительности (как решение параметрической задачи однокритериальной оптимизации данного класса). Определяется свертывающая функция задачи многокритериальной оптимизации, рассматриваются геометрические свойства образа задачи и свертывающих функций, формулируется проблема отыскания класса методов ПБМ, удовлетворяющих заранее заданным свойствам. В терминах свертывающих функций (СФ) оказалось возможным сформулировать необходимые и достаточные условия сходимости
довольно представительного класса методов ПБМ, СФ которых меняются независимо от свойств образа задачи (§2). Данные методы названы независимыми. Достаточно широкий набор независимых методов и анализ их эффективности производятся в §3.
Другая группа методов - зависимые методы аппрокеимационного типа, которые описываются в §4. Их детальный анализ проведен в работе [5]. Сюда относятся, в частности, методы двойственных модифицированных функций Лагранжа. Использование методики свертывающих функций (которые в некотором смысле аналогичны модифицированным функциям Лагранжа) позволяет выявить их новые свойства и рассмотреть их модификации.
В § § 4 и 5 рассматриваются условия сходимости зависимых методов и устанавливаются условия их эффективного использования. Также в §5 предлагается схема переключения методов при решении многокритериальных задач. Идея подхода заключается в том, что в процессе использования метода после некоторого количества итераций вычисляется производная функции чувствительности и в результате сравнения с некоторым фиксированным значением происходит переход к другому методу или продолжение итераций. При этом возможно изменение параметров предыдущего метода. Переключение также возможно из-за того, что метод безусловной оптимизации перестает работать внутри ПБМ.
В главе 2 рассматривается решение конкретной задачи многокритериальной нелинейной оптимизации с помощью предложенной в работе интеллектуальной оптимизационной системы -задача обоснования региональной системы охраны лесов от пожаров. Требуется минимизировать два критерия: i) ежегодные затраты на функционирование региональной системы охраны лесов (РСОЛ);
2) время распространения лесных пожаров от возникновения до начала тушения (соответственно площади сгоревшего леса) в зависимости от следующих неизвестных величин:
Г) вариантов функционирования РСОЛ;
2) количества средств обнаружения и тушения пожаров;
3) распределения их по охраняемой площади;
4) расписания осмотра охраняемой площади (куда включается число периодов - кратность - осмотра и начала осмотра);
5) протяженности патрульных маршрутов или продолжительности осмотров охраняемой территории.
В §1 и §2 представлена содержательная интерпретация переменных и параметров, а также описывается вид и содержание ограничений и функционалов. Формальная постановка представляет собой задачу многокритериальной оптимизации с выпуклыми ограничениями и невыпуклой функцией цели.

В §3 приводится решение поставленной содержательной задачи для сезона 199? года по Братскому авиаотделению Иркутской территориальной авиабазы.
В процессе счета системой в основном использовался "независимый” метод, когда выбор Парето-оптимальной оценки осуществлялся с помощью линейной свертки критериев, использовались внешние штрафные функции, абсолютное значение степеней в свертывающей функции и равномерный независимый способ пересчета коэффициентов штрафа. При меньших 1 значениях критности вызывались либо такие же независимые методы, либо независимые, отличающиеся от указанных использованием внутренних штрафных функций, и зависимый метод, основанный на выборе Парето-оптимальной оценки с помощью линейной свертки критериев, квадратичной аппроксимации функции чувствительности, наличии дополнительного варьирования оценок вторых производных свертывающих функций путем увеличения оценок за счет прибавления к СФ внешнего штрафа. При этом работа метода в соответствии с аппроксимационной схемой обеспечивалась варьированием параметров сдвига.
В заключении приводятся краткие выводы.
В приложении 1 рассматривается гибридный алгоритм безусловной оптимизации, используемый в интеллектуальной оптимизационной системе ИНТЕЛ ОС для решения подзадач БМ на каждой итерации метода ПБМ.
В приложении 2 приводится краткая характеристика диалоговой оптимизационной системы ИНТЕЛ ОС 1.0. Описываются возможности по постановке и коррекции оптимизационных задач в процессе счета, основные методы нахождения Парето-оптимальных оценок, выбор метода безусловной оптимизации и нелинейного программирования и параметры системы, доступные пользователю.
Список литературы включает 18 наименований.

дифференцируемой ФЧ такой, что Е(у)' < 0 в окрестности решения

у = О. Пусть у7 = О, > О ( й и найдена (и?,у?_). Имеем,
у; > О. Возьмем открытую е - окрестность точки у1 (О < е < <7 Г'//2рЛут + |; и покажем, что ук, к = 1,2... принадлежит этой окресности при определенном выборе t . Действительно,
достаточно рассмотреть быстро убывающую последовательность.
1* -* О, при к -» со, I = р, чтобы понять, что расстояние
|у&+;- у&1 можно сделать сколько угодно малым. Заметим, что в
предельном случае с линейной СФ это расстояние всегда остается равным нулю.
Таким образом, если рассматривать классы последовательностей СФ с точностью до оценок производных Ьк, то действительно условие (III;, а Еместе с ним и (II) близко к необходимому условию сходимости метода с линейной аппроксимацией ФЧ. Иначе говоря, существование не быстро убывающих оценок для этих методов обязательно.
Аналогичное утверждение справедливо и для методов с модифицированной аппроксимационной схемой вида
где О С А.&< I (см. (Б2) §1). Задание некоторого А,& = А. > О,
к = 7,3
у* + 7 < О, у£+? > О, которые, как показывает численный
эксперимент, зачастую имеют место для методов, удовлетворяющих условиям теоремы 1.2 из [$] и теоремы из приложения 2. Однако, в общем случав, следует ожидать снижение скорости сходимости по сравнению с традиционной схемой (32) (§1).
Иначе дело обстоит для тех зависимых методов, в основе