Метод динамического программирования

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 13Следующая ⇒

Еще один подход к решению задач глобальной оптимизации основан на использовании динамического программирования. Этот метод относится к классу методов декомпозиции - так называются методы, позволяющие задачи большой размерности свести к последовательному решению ряда задач меньшей размерности. Если эти вспомогательные задачи решены с достаточно хорошей точностью, то тем самым и в исходной задаче глобальный минимум будет найден с высокой точностью [8].

Впервые возможность применения метода динамического программирования в задачах синтеза антенных решеток была показана в работе [18]. В основе алгоритма, предложенного в ней, лежит итерационный процесс, на каждом шаге которого находится вектор  путем решения () - шаговой задачи динамического программирования. Так, на
k -м шаге решения для всех  и фиксированных значений  параметрического вектора  (вектора, полученного на предыдущем этапе) рассчитывается функция:

,

где ,…, - так называемые функции оптимального соответствия, построенные на () - м шаге.

Таким образом, на каждом шаге оптимизации рассматриваются все комбинации лишь двух переменных  и , поскольку считается, что оптимальные значения k -1, k -2 и так далее переменных были определены на предшествующих шагах расчета.

Соотношения ,  используются как рекуррентные для определения систем функций оптимального соответствия , . На последнем, () - м шаге решения задачи динамического программирования, с помощью построенной системы функций оптимального соответствия , , определяется вектор , такой, что .

Таким образом, в результате () - шаговой процедуры оптимизации получен вектор , для которого значения целевой функции не больше, чем для . Вектор  используется в качестве исходного для следующего этапа итерационного процесса.

Поскольку при построении семейства функций оптимального соответствия ,  для всех  необходимо решать одномерную задачу глобальной оптимизации, то практическая реализация данного алгоритма возможна лишь на дискретном множестве, то есть когда каждая из  переменных может принимать  задаваемых на сетке значений. Если итерационный процесс имеет  шагов, то необходимое число вычислений целевой функции  можно определить по следующей формуле .

Практика решения многоэкстремальных задач синтеза и многочисленных тестовых задач [19,20] показывает, что метод динамического программирования эффективно использовать на первой стадии двухэтапного алгоритма с целью выхода в область глобального экстремума. При этом надежное решение этих задач достигается при числе сеточных узлов . Это приводит к увеличению вычислительных затрат особенно с ростом размерности решаемых задач.

Поэтому в работе [20] была проведена модификация данного алгоритма с целью повышения его эффективности при малом числе сеточных узлов . Основу проведенной модификации составляет:

· применение интерполяции с использованием полинома Лагранжа при нахождении глобального экстремума функции оптимального соответствия;

· использование процедуры адаптивного сдвига сеточных узлов на каждой итерации поиска.

Результаты численного моделирования, показывают высокую эффективность проведенной модификации с точки зрения повышения точности выхода в область нелокального экстремума при малом значении числа сеточных узлов .

Поскольку с увеличением размерности решаемых задач применение регулярной сетки приводит к хорошо известному в теории сеток эффекту «затенения» [8], в работе [20] предложен и исследован вариант метода динамического программирования с использованием квазислучайной сетки. Результаты исследований показали, что предложенный метод оказался значительно эффективнее классического, практически не уступая модифицированному.

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

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология