|
61 Обзор методов дискретной оптимизации и их ПО, представ ленный в [20] показывает что, по всей видимости, единственными эффективными методами решения реальных задач псевдобулевой оптимизации являются приближенные методы, включая алгоритмы случайного поиска. Модифицированный алгоритм случайного поиска с адаптацией (МСПА) и лежит в основе предложенного автором метода, позволяющего находить эффективное решение. Соглашаясь с автором [21], где указывается на то, что выбор правильного пути исследований должен начинаться с изучения особенностей модельного описания практически реализуемых процессов управления, отметим, что рассматриваемая ниже постановка задачи оптимизации имеет ряд отличий от постановок задач выбора оптимального ряда изделий, рассматриваемых в литературе (см.[24]), основными из которых (с точки зрения трудностей оптимизации) является то, что множество, на котором определена целевая функция задачи представляет собой множество трехмерных (в общем случае четырехмерных) булевых матриц в отличии от множества двумерных булевых матриц указанных постановок задач оптимального выбора ряда изделий. Реализация схемы метода изменяющихся вероятностей для конкретных алгоритмов рассматривается автором в [25]. Таким образом, в процессе решения необходимо многократно повторять последовательные этапы оптимизации целевого функционала (при выборе оптимального времени реализации ТЦУ, согласно составу ПО), анализа реализуемости ТЦУ (корректность заданных временных ограничений) и коррекции ТЦУ. Перечислим шаги аналитико-оптимизационной процедуры этого этапа: ■ для заданного ТЦУ (либо совокупности ТЦУ) выбирается состав ПО с применением приближенных методов; ■ анализ и коррекция ТЦУ; ■ для полученной субоптималъного по времени реализации ТЦУ определяется критический путь на графовой модели; ■ оптимизируется критический путь графа ТЦУ точными методами; ■ в том случае, если значение целевого функционала улучшилось, повторяется этап анализа и коррекции ТЦУ, затем последующие шаги данной процедуры повторяются до тех пор, пока значение целевого функционала либо останется неизменным, либо ухудшится. Отметим, что в рамках интерактивной системы формирования ТЦУ между всеми этапами решения задачи организован диалоговый интерфейс, который предоставляет пользователю (специалисту по технологии управления КА) достаточную информацию для принятия решения. Библиотека средств оптимизации может быть дополнена новыми алгоритмами, что характеризует созданную систему как способную к расширению. |
ной техники. Одна из возможных трудностей заключается в написании ограничений. Она преодолима, но после этого необходимо каким-либо способом описать матрицу инциденций. Данная трудность уже серьезна, так как при задании ТЦУ такая матрица практически никогда не приводится. При этом надо учесть достаточно большие размеры матрицы инциденций. К тому же ограничения, как правило, не линейны и не выпуклы. Поэтому трудности возникнут и при реализации процесса минимизации функционала, что требует делать один из основных акцентов при решении на изучение и учет особенностей ограничений, описывающих допустимые временные развертки ТЦУ, чему и посвящен следующий раздел. Обзор методов дискретной оптимизации и их ПО, представленный в [80] показывает что, по всей видимости, единственными эффективными методами решения реальных задач псевдобулевой оптимизации являются приближенные методы, включая алгоритмы случайного поиска. Модифицированный алгоритм случайного поиска с адаптацией (МСПА) и лежит в основе предложенного автором метода, позволяющего находить эффективное решение. Соглашаясь с автором [81], где указывается на то, что выбор правильного пути исследований должен начинаться с изучения особенностей модельного описания практически реализуемых процессов управления, отметим, что рассматриваемая ниже постановка задачи оптимизации имеет ряд отличий от постановок задач выбора оптимального ряда изделий, рассматриваемых в литературе (см.[87]), основными из которых (с точки зрения трудностей оптимизации) является то, что множество, на котором определена целевая функция задачи представляет собой множество трехмерных (в общем случае четырехмерных) булевых матриц в отличии от множества двумерных булевых матриц указанных постановок задач оптимального выбора ряда изделий. Реализация схемы метода изменяющихся вероятностей для конкретных алгоритмов рассматривается автором в [106]. Таким образом, в процессе решения необходимо многократно повторять последовательные этапы оптимизации целевого функционала (при выборе оптимального времени реализации ТЦУ, согласно составу мультиверсионного ПО), анализа реализуемости ТЦУ (корректность заданных временных ограничений) и коррекции ТЦУ. Перечислим шаги аналитике оптимизационной процедуры этого этапа: 67 для заданного ТЦУ (либо совокупности ТЦУ) выбирается состав мультиверсионного ПО с применением приближенных методов; анализ и коррекция ТЦУ; для полученной су б оптимальной по времени реализации ТЦУ определяется критический путь на графовой модели; оптимизируется критический путь графа ТЦУ точными методами; в том случае, если значение целевого функционала улучшилось, повторяется этап анализа и коррекции ТЦУ, затем последующие шаги данной процедуры повторяются до тех пор, пока значение целевого функционала либо останется неизменным, либо ухудшится. Отметим, что в рамках интерактивной системы формирования ТЦУ между всеми этапами решения задачи организован диалоговый интерфейс, который предоставляет пользователю (специалисту по технологии управления КА) достаточную информацию для принятия решения. Библиотека средств оптимизации может быть дополнена новыми алгоритмами, что характеризует созданную систему как способную к расширению. Структура и схема взаимодействия компонент интерактивной системы представлены в [208]. 2.2. Моделирование технологических циклов управления КА Рассмотрим подробно модели и методы анализа и оптимизации ТЦУ КА, которые используются в рамках представленной выше аналитикооптимизационной процедуры и позволяют получать как аналитические, так и вероятностные характеристики процессов управления КА. 2.2.1. Анализ реализуемости: детерминированные модели Поскольку описание технологических циклов управления не зависит от типа комплекса управления, мы имеем начальное значение вектора временной развертки для графа ТЦУ G t = ..-Ап)', 68 При решении совокупной задачи (для всех L этапов ТЦУ) возможны три подхода. Во-первых, одновременная оптимизация по всем L этапам. С учетом очевидного требования недопустимости дублирования однотипных программных модулей на различных этапах ТЦУ, размерность задачи в этом случае становится практически нереализуемой. Поэтому возвращаться к этому подходу больше не будем как к неприемлемому. Вовторых, независимое решение задач аналогичных задаче (70),(71) для каждого из L этапов с последующей сверкой и корректировкой решений. И, наконец, поэтапное решение задачи, предполагающее последовательное дополнение недостающих программных модулей (по отношению к имеющимся к рассматриваемому этапу ТЦУ). В этом случае для ТЦУр+1) задача (70),(71) выглядит следующим образом: где ‘{ЕЕЕксь+с jeA г ев А’~1 7V7 =7V/+1 кгП /+1+ СЩ + nf+1(l+ I + лЛ))]Щ/+1) У 4-ф)+ s=l + Лг(1 + Лг)) У Д-иЛ’ 5=1 (73) maxn-’ if nj+1-maxn^ > 0, 0 в противном случае; Е /+1 У У 4ф) > С r G j G Л'+1к^1 5 = 1 (74) Мы уже отмечали ранее, что полученная постановка задачи имеет ряд существенных отличий от постановок задач выбора оптимального ряда изделий, рассматриваемых в литературе (см. например, [44,48,81,87]), основными из которых (с точки зрения трудностей оптимизации) является то, что множество, на котором определена целевая функция нашей задачи суть множество трехмерных (а в общем случае четырехмерных) булевых матриц в отличии от множества двухмерных булевых матриц указанных постановок. 132 |