РЕАЛИЗАЦИЯ МНОГОМЕТОДНЫХ ПРОЦЕДУР ОПТИМАЛЬНОГО УПРАВЛЕНИЯ
Белышев Дмитрий Владимирович 
Институт программных систем РАН
belyshev@cron.botik.ru

Бурный рост разнообразных методов в теории систем и управления — процесс противоречивый. С одной стороны, он несет новые возможности, но с другой — выдвигает чрезмерные требования к компетенции практических пользователей при выборе метода среди многих, основанных на различных математических теориях. Более того, сложные практические проблемы требуют, как правило, комбинирования различных методов. В то же время, несмотря на обилие методов, они покрывают далеко не равномерно всю область задач управления, и существует объективная необходимость развивать все новые методы. В данной статье предлагается подход к разрешению этого противоречия и представлены этапы его реализации, включающие архитектуру Интеллектуальной Системы построения процедур Оптимизации Управления (ИСОУ) [5]. Приводится пример использования описываемого подхода при решении задачи оптимально управления регионом [1].
2. Архитектура ИСОУ

Архитектура предлагаемой интеллектуальной системы в целом и наиболее существенные ее детали представлены на (Рис. 1 – 3). Как видно из Рис. 1, она ориентирована на автоматизацию естественной схемы решения прикладной проблемы от формулировки соответствующей математической задачи до практической интерпретации решения последней. В целом она отражает неформальный, творческий процесс поиска решения, хотя и включает формальные компоненты. К их числу относятся: (а) методика математической формализации исходной прикладной проблемы, включая составление паспорта задачи по классификационным признакам (рассчитана на конечных пользователей — "держателей прикладных задач"); (б) библиотека методов с паспортами; (в) библиотека методических (тестовых) задач для настройки/отладки методов; (г) процедура выбора группы методов, подходящих для данной задачи по формальным признакам; (д) процедура настройки метода (выбора его параметров). Неформальные компоненты: (а) формализация исходной прикладной задачи и интерпретация решения формализованной задачи (выполняется конечным пользователем); (б) построение процедуры оптимизации с выбором наилучших методов из отобранных (выполняется экспертной системой) (Рис. 2.).

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

3. Реализация ИСОУ
Текущая реализация ИСОУ включает в себя расширенный интеллектуальный аппарат работы с различными методами и алгоритмами, содержащимися в библиотеке алгоритмов. Библиотека представляет собой набор подпрограмм, реализованных в виде компонент с определенным интерфейсом взаимодействия. Такой подход позволяет рассматривать каждый алгоритм как некоторый базовый элемент для создания более сложных конструкций, являющихся последовательностью сменяющих друг друга базовых методов. Получающаяся конструкция также является законченным алгоритмом, обладающим рядом свойств, и может быть использована наряду с остальными методами при формировании новых составных алгоритмов. Таким образом, библиотека алгоритмов является достаточно гибкой структурой, позволяющей дополнять себя как существенно новыми алгоритмами путем написания соответствующих компонент, так и “виртуально новых” — являющихся некоторой комбинацией уже существующих. Если учесть, что каждый из алгоритмов требует своего набора параметров, то возможно составление мультиметодной процедуры, включающей в себя только один базовый алгоритм, но с меняющимися свойствами.
Через призму построения мультиметодных процедур можно рассматривать любые итерационные методы решения задач. Приведем простой пример: решение задачи конечномерной минимизации. Как правило, если задача решается численно, то она проходит несколько этапов: (1) поиск начального приближения; (2) процесс улучшения; (3) верификация результата: достигнут ли локальный минимум. В данном случае нами может быть построен одна многометодная процедура минимизации, который реализует все приведенные этапы: (1) запускается алгоритм случайного поиска и выбирается наилучшее значение, оно берется в качестве начального приближения; (2) используется алгоритм градиентного спуска до тех пор, пока не будет выполнено условие стационарности, и процесс улучшения не остановится; (3) запускается алгоритм улучшения второго порядка, основанный на достаточных условиях локального минимума [3], который сможет уйти из точки стационарности, если она не удовлетворяет условиям локального минимума, после чего можно вновь запускать более простой и эффективный градиентный алгоритм. В случае остановки алгоритма второго порядка, можно гарантировать достижение локального минимума задачи.
Для реализации такой схемы решения ИСОУ обладает рядом “интеллектуальных” процедур, позволяющих на основе описания (паспорта) алгоритма осуществить автоматический отбор наиболее подходящего для данной задачи метода (Рис. 2). Для смены метода в процессе улучшения используется так называемый “конкурс” алгоритмов, который состоит в том, что на некотором этапе минимизации процесс останавливается, и параллельно запускаются сразу несколько алгоритмов. После нескольких итераций результаты улучшения всех процессов сравниваются, и выбирается наилучший, который и продолжает работать. Таким образом, в зависимости от ситуации, может происходить динамическая смена текущего метода, что делает всю процедуру более гибкой и легко настраиваемой на конкретную задачу, позволяет алгоритмам взаимно дополнять друг друга.
4. Пример многометодной процедуры оптимизации
В качестве примера рассмотрим оптимизацию стратегии развития региона на основе его социо-эколого-экономической модели [1] с учетом инноваций. Эта задача в целом существенно нелинейна, характеризуется сложными ограничениями, в том числе — фазовыми, различными скоростями протекания процессов и вырождена благодаря наличию многих линейных управлений. Кроме того, она может иметь высокую размерность в зависимости от принятой степени агрегирования (порядка 20 как минимум) при сложной структуре данных. По этой причине ее решение каким-либо одним общим методом сильно затруднено, а практически невозможно. В то же время имеется успешный опыт исследования предшествующих моделей, в которых инновационный блок отсутствовал, с применением при некоторых идеализирующих допущениях специального высокоэффективного метода для вырожденных задач, доставляющего результат, хотя и приближенно, но почти в формульном виде. С учетом этого для ее решения была предложена и реализована многоступенчатая многометодная процедура, в которой чередуется оптимизация исходной модели при заданных во времени параметрах и их улучшение за счет управления инновациями [4].
В ходе решения этой задачи на начальном этапе применялся метод преобразования к производной задаче [2], различные вариации алгоритмов градиентного типа в функциональном пространстве для задач со свободным правым концом. Имеющиеся дополнительные ограничения учитываются опосредованно с помощью методических штрафных функционалов стандартными приемами. Для данной задачи, как и для многих других прикладных задач, важна не столько высокая точность решения, сколько возможность их быстрого получения для многочисленных сценариев с учетом высокой степени неопределенности, сопутствующей региональному анализу. В этом отношении разработанная процедура оказалась весьма эффективной. Для рассмотренной модели был рассчитан ряд сценариев развития социо-эколого-экономической системы Переславского региона [1].
5. Заключение
Представленная исследовательская работа не является законченным продуктом. Интеллектуальная система развивается, усовершенствуется механизм взаимодействия методов и логика построения их последовательностей, расширяется база алгоритмов и тестовых задач, уточняется и проводится дополнительная классификация алгоритмов. Совершенствуются механизмы подбора параметров алгоритмов и так далее. Данная работа представляет собой открытый процесс, позволяющий вовлекать в разработку других людей в качестве поставщиков алгоритмов и задач, в качестве экспертов, наполняющих базу знаний об их типизации. Ведутся исследования в области использования параллельных суперкомпьютеров для удаленного вычисления трудоемких процедур.

[1] Моделирование социо-эколого-экономической системы региона/Под ред. В.И. Гурмана, Е.В. Рюминой. — М.: Наука, 2001.
[2] Гурман В.И. Принцип расширения в задачах управления. — М.: Наука. Физматлит, 1985, 1997.
[3] Батурин В.А., Урбанович Д.Е. Приближенные методы оптимального управления, основанные на принципе расширения — Новосибирск: Наука. СО РАН, 1997.
[4] Белышев Д.В., Шевчук Е.В. Алгоритм и программный комплекс для поиска оптимального управления// Интеллектуальное управление: Новые интеллектуальные технологии в задачах управления (ICIT'99). — Труды Международной конференции, Переславль-Залесский, 6-9 декабря 1999. — М.: Наука, Физматлит, 1999. — С. 146 – 150. 
[5] Белышев Д.В. Гурман В.И. Интеллектуальные процедуры оптимального управления// Автоматика и телемеханика. ( в печати)