УДК 519.8:355
МОДИФИЦИРОВАННЫЙ МЕТОД ПРЯМОГО ПОИСКА
В ОПТИМИЗАЦИОННЫХ ЗАДАЧАХ СПЕЦИАЛЬНОЙ СТРУКТУРЫ
А. А. БОРОДИН доктор технических наук, А.С. КАНИЩЕВ
ВУНЦ ВВС «Военно-воздушная академия имени профессора Н.Е. Жуковского и Ю.А.Гагарина»
И. В. ЛЮТИКОВ кандидат технических наук
Военно-инженерный институт СФУ
THE MODIFIED METHOD OF DIRECT SEARCH IN OPTIMISING TASKS
OF SPECIAL STRUCTURE
A.A. BORODIN, doctor of technical sciences, A.S. KANISHCHEV
Military Air Force Academy Professor N.E. Zhukovsky and Yuri Gagarin
I.V. Lyutikov, candidate of technical sciences
Military Engineering Institute of Siberian Federal University
В статье рассмотрен подход к решению оптимизационных задач специальной структуры: условной оптимизации вещественной нелинейной целевой функции n – мерного аргумента с неявно заданными нелинейными ограничениями. Представленный методический подход, на основе модифицированного метода Хука-Дживса, позволит определить оптимальные наборы значений характеристик систем военного назначения, функционирующих в различных условиях обстановки, по критерию минимальной стоимости при ограничении на требуемый уровень эффективности за располагаемое время.
Ключевые слова: оптимизация, вектор, варианты внешней среды, характеристики системы, метод.
In article approach to the solution of optimizing tasks of special structure is considered: conditional optimization of material nonlinear criterion function of n – measured argument with implicitly set nonlinear restrictions. The presented methodical approach, on the basis of the modified Hook-Dzhivsa's method, will allow to determine optimum sets of values of characteristics of the military systems functioning in various conditions of a situation by criterion of the minimum cost at restriction on the demanded efficiency level for the located time.
Key words: optimization, vector, external options area, system specifications, method.
В практике научных исследований процессов функционирования систем военного назначения зачастую возникает необходимость решения задачи оптимизации значений характеристик этих систем, функционирующих в различных условиях обстановки, по критерию минимальной стоимости при ограничении на требуемый уровень эффективности за располагаемое время. В общем виде математическая постановка подобных задач может быть представлена в виде:
|
|
(1) |
где функции стоимости, эффективности и времени соответственно; требуемые значения эффективности и располагаемого времени функционирования систем военного назначения; - вектор значений оптимизируемых переменных; вектор значений характеристик внешней среды; область допустимых значений оптимизируемых переменных и значений характеристик внешней среды.
Анализ подобных задач показывает, что их особенностью, как правило, является то, что функции стоимости и эффективности являются нелинейными. При этом, как правило, функция ограничений не может быть получена в явном виде, поскольку ее значения определяются на основе моделирования процессов функционирования исследуемых систем военного назначения, являющихся по своей сути сложными военно-техническими системами, при различных характеристиках внешней среды.
Механизм формирования вариантов внешней среды, принимаемых для моделирования, определяется спецификой функционирования рассматриваемых сложных военно-технических систем.
Внешняя среда характеризуется набором параметров различной природы. В военных системах военного назначения параметры могут быть сведены к основополагающим группам характеристик: характеристик противника, района военных действий и своих войск.
Группу характеристик противника составляют технические характеристики средств нападения и пространственно-временные характеристики операций противника. К характеристикам этой группы могут быть отнесены такие физические характеристики, как тактико-технические характеристики средств нападения, характеристики обеспечивающих сил и средств и т. д.
Группа характеристик района военных действий включает метеорологические характеристики, характеристики коммуникаций, характеристики объектов, имеющих повышенную опасность и т.д.
Группу характеристик своих войск составляют тактико-технических характеристик образцов оружия, характеристики боевых порядков, вариантов применения своих войск и т. д.
Учитывая вышеизложенные положения, вектор характеристик среды можно представить как:
|
, |
(2) |
где - векторы характеристик противника, района военных действий и своих войск соответственно.
В этом случае вектор значений характеристик противника будет иметь вид:
|
, |
3) |
где значения характеристик противника; N - общее количество характеристик противника.
Аналогично можно записать вектор значений характеристик района военных действий:
|
, |
(4) |
где значения характеристики района военных действий; K - общее количество характеристик района военных действий.
Аналогично вектор характеристик своих войск будет иметь вид:
|
, |
(5) |
где значения характеристик своих войск; L - общее количество характеристик своих войск.
В выражениях (3-5) каждая из характеристик может принимать значения в интервалах:
|
, |
(6) |
где минимальное и максимальное значение характеристики противника, характеристики района военных действий и характеристики своих войск.
В дальнейшем допустим, что характеристики противника, района военных действий и своих войск могут принимать счетное количество значений в интервалах (6) так, что характеристика противника принимает значений , характеристика района военных действий принимает значений , характеристика своих войск принимает значений .
В результате для всех характеристик противника имеем суммарное число значений
|
, |
(7) |
для всех характеристик района военных действий имеем суммарное число значений
|
, |
(8) |
и для всех характеристик своих войск имеем суммарное число значений
|
. |
(9) |
Кроме этого для упрощения рассуждений в дальнейшем будем полагать, что возможны любые сочетания рассматриваемых характеристик (на практике это не всегда выполняется).
На рисунке 1 показан механизм формирования вариантов среды с различными значениями параметров противника.
Из рисунка 1 видно, что число возможных вариантов среды равно числу сочетаний из общего числа возможных значений всех переменных (выражение 6) по числу временных параметров N то есть:
|
. |
(10) |
Рисунок 1 - Механизм формирования вариантов среды
с различными значениями характеристик противника
Аналогично формируются варианты среды района военных действий:
|
. |
(11) |
и параметров своих войск:
|
. |
(12) |
Каждый вариант среды с различными значениями характеристик противника является элементом множества возможных вариантов - . Аналогично, каждый вариант среды с различными значениями параметров района военных действий является элементом множества возможных вариантов - и каждый вариант среды с различными значениями пространственных параметров своих войск является элементом множества возможных вариантов .
Полагая, что значения характеристик противника, района военных действий и своих войск принимают значения независимо друг от друга, можно рассчитать число возможных вариантов внешней среды как:
|
. |
(13) |
На рисунке 2 схематично показан механизм формирования варианта внешней среды.
Рисунок 2 – Механизм формирования вариантов внешней среды
Из рисунка 2 видно, что формирование вариантов внешней среды осуществляется на основе выбора и объединения единичных элементов множеств . В качестве примера на рисунке 2 (замкнутый контур) показан вариант внешней среды , имеющий вариант характеристик противника, вариант характеристик района военных действий и вариант характеристик своих войск.
Каждый вариант внешней среды представляет собой вполне конкретную ситуацию для моделирования. Однако, даже при самом приблизительном рассмотрении, приходим в выводу о существовании большого множества таких ситуаций.
Так, например, допустим, что внешняя среда содержит по три (N=K=L=3) характеристики, каждая из которых может принимать по три значения, в этом случае число возможных физических (временных, пространственных) вариантов среды согласно (10,11,12) составит
|
. |
(14) |
В этом случае число вариантов внешней среды (ситуаций) согласно (13) будет равно
|
. |
(15) |
Естественно предположить, что в условиях такого числа ситуаций принять адекватное единственно правильное решение крайне затруднительно. При большем числе характеристик противника, района военных действий и характеристик своих войск, а также при возрастании количества значений каждой из них общее число ситуаций резко возрастает, приводя к невозможности получения, хотя бы какого-то рационального решения.
Аналогичные рассуждения можно провести для составляющих вектора оптимизируемых переменных. В этих условиях зачастую прибегают к формированию счетного числа вариантов, в наибольшей степени отражающих характеристики внешней среды для рассматриваемой задачи, что равносильно декомпозиции оптимизационной задачи (1) на ряд самостоятельных задач.
Для каждого варианта значений характеристик внешней среды в результате решения оптимизационной задачи (1) может быть получено одно единственное множество оптимальных значений оптимизируемых переменных, в рамках принятых ограничений, в точке мерного гиперкуба, ограниченного областью , вида:
|
. |
(16) |
При этом границы гиперкуба определяются в мерном пространстве минимальными и максимальными значениями вектора :
|
. |
(17) |
Отмеченные обстоятельства свидетельствуют о значительной размерности задач подобного типа, а невозможность получения целевой функции и функции ограничений в явном виде свидетельствует о том, что единственным методом получения решения для подобных задач является метод прямого поиска, предполагающий на каждом шаге моделирования вычисление значения целевой функции и проверке результатов на удовлетворение ограничениям.
Среди методов прямого поиска зачастую применяются методы симплексов (Нелдера-Мида, модифицированные методы Нелдера-Мида), методы поиска Хука-Дживса, методы сопряженных направлений Пауэлла и др.[1-4]. Уже при размерности задачи требуются значительные затраты машинного времени.
В этих условиях методы симплексов значительно уступают методу Хука-Дживса по объемам требующихся вычислительных мощностей.
Сущность метода Хука-Дживса заключается в том, что из допустимой точки по каждой характеристике исследуемой системы осуществляется последовательность шагов в сторону уменьшения и увеличения значений, составляющих вектора на величину . При этом значение характеристики снижающей значение целевой функции и удовлетворяющей функции ограничений фиксируется и с этой точки по следующей характеристике осуществляется уменьшение и увеличение ее значений на величину . Значение 2-ой характеристики снижающей значение целевой функции и удовлетворяющей функции ограничений снова фиксируется и процедура повторяется раз. В результате, через шагов, получаем точку, из которой продолжается движение к минимуму целевой функции. Окончанием процедуры поиска минимума целевой функции является отклонение функции ограничений от требуемого значения на малую наперед заданную величину такую, что:
|
. |
(18) |
Из физической сущности задачи (1) можно заметить, что возрастание значений каждой из оптимизируемых переменных приводит к возрастанию значений функций и , что указывает на их монотонный характер. Это обстоятельство позволяет снизить объемы вычислений по сравнению с классическим методом Хука-Дживса.
Поскольку функции и являются монотонными функциями оптимизируемых переменных, Парето-оптимальная область решений имеет вид, представленный на рисунке 3.
Рисунок 3 - Парето-оптимальная область решений
Парето-оптимальная область, изображенная на рисунке 3, получается за счет многократного решения задачи (1) для различных значений . Сущность модифицированного метода прямого поиска решения оптимизационной задачи (1) заключается в том, что каждая тая оптимизируемая переменная разбивается на равных частей , как показано на рисунке 4.
Рисунок 4 – Разбиение значений оптимизируемых переменных на равные части
Для целочисленных оптимизируемых переменных их значения составляют числа . Для непрерывных оптимизируемых переменных производится разбиение вида:
|
, |
(19) |
где -длительность единичного интервала разбиения.
Движение к минимуму стоимости осуществляется пошагово из точки в пространстве оптимизируемых параметров (Рисунки 3, 4), соответствующей максимальным значениям каждой из оптимизируемых переменных (для каждого интервала с номером ):
|
. |
(20) |
Изменение значений оптимизируемых переменных в сторону уменьшения приводит к снижению значений стоимости системы военного назначения (в силу монотонности функции стоимости ) (Рисунок 3), поэтому Парето-оптимальная область имеет монотонный убывающий характер. При этом, соответственно снижается и значение показателя эффективности системы.
Далее последовательно осуществляется снижение значений каждого из оптимизируемых переменных на одну дискрету и производится моделирование функционирования исследуемой системы военного назначения в течение времени Трасп с полученными значениями оптимизируемых переменных. При этом значение стоимости системы и значение ее эффективности запоминается. На каждом шаге снижения значений каждого из оптимизируемых переменных значение эффективности проверяется на удовлетворение условию
|
. |
(21) |
Если условие (21) выполняется, то из полученного ряда значений стоимости системы выбирается ее минимальное значение, а значение переменной, соответствующей минимальному значению стоимости, фиксируется, и процедура снижения значений остальных переменных повторяется. На каждом последующем шаге из полученного ряда значений стоимости системы выбирается ее минимальное значение и производится проверка на удовлетворение условию (21).
Процедуры проводятся до момента, когда начинает выполняться условие (18):
|
. |
(22) |
Модификация метода заключается в том, что в отличии от классического алгоритма метода Хука–Дживса движение в направлении минимума стоимости осуществляется путем изменения значений характеристик систем только в сторону уменьшения.
Известное направление поиска в сторону уменьшения значений характеристик системы и проверка удовлетворения ограничению по эффективности функционирования системы на каждом шаге позволяют значительно сократить область поиска значений .
Таким образом, представленный метод решения оптимизационной задачи (1) позволяет определить множество значений характеристик исследуемой системы, обеспечивающих требуемую эффективность этих систем в заданных условиях при минимуме суммарных затрат на создание и функционирование в пределах располагаемого времени.
Литература
[1] Reklаitis G.V., Revindran A., Regsdell K.M. Engineering Optimization. Methods and Applications: In 2 kN. Book 1. A Wiley-Intersciense Publication – JOHN WILEY AND SONS, 1983. – 346 pages.
[2] Reklаitis G.V., Revindran A., Regsdell K.M. Engineering Optimization. Methods and Applications: In 2 kN. Book 2. A Wiley-Intersciense Publication – JOHN WILEY AND SONS, 1983. – 320 pages.
[3] Ильичев А.В., Северцев Н.А. Эффективность сложных систем. Динамические модели/ А.В. Ильичев, Н.А. Северцев. – М.: Наука, 1989.– 168с.
[4] Бейлин И. Д., Кругляков В. М. Основы технологии моделирования сложных систем/ И. Д.Бейлин, В. М.Кругляков. – Тверь: ВУ ПВО, 2000.