close

Вход

Забыли?

вход по аккаунту

?

Алгоритм минимизации скалярной функции многих переменных при интервальных ограничениях на переменные.

код для вставкиСкачать
Программные продукты и системы
В результате реализации тензорного подхода
к задаче оценки QoS разработанная программная
система позволяет обеспечить возможности построения любых топологий схем и выбора модели
для каждой ветви схемы. При этом результатом
работы являются длины очередей и время задержки в ветвях, а также вероятности переполнения
буферов и стационарные вероятности состояний
для каждой ветви, выбранного маршрута и всей
сети в целом. Исходя из всего сказанного можно
сделать следующие выводы: протокол IP является
наиболее распространенным и позволяет объединить практически все существующие услуги сетей
с обеспечением заданного уровня QoS; тензорный
метод дает возможность достаточно просто формализовать проектные процедуры для сетей такого типа; программная реализация тензорного
метода позволяет оценивать требуемые показате-
№ 4, 2009 г.
ли качества при приемлемых вычислительных затратах.
Литература
1. Cheng–Shang Chang. Stability, Queue Length and Delay
of deterministic and stochastic queueing networks // IEEE
Transactions on Automatic Control. 1994. Vol. 39, pp. 913–931.
2. Яновский Г.Г. Качество обслуживания в IP сетях //
Вестник связи. 2008. № 1. C. 65–74.
3. Masip-Bruin X., Yannuzzi M., Serral-Gracia R., DomingoPascual J., Enriquez-Gabeiras J., Callejo M.A., Diaz M., Racaru F.,
Stea G., Mingozzi E., Beben A., Burakowski W., Monteiro E.,
Cordeiro L. The EuQoS system: a solution for QoS routing in
heterogeneous networks // IEEE Communications Magazine. 2007.
45(2), pp. 96–103.
4. Donnet B., Friedman T. Internet topology discovery: a
survey // IEEE Communications Surveys & Tutorials. 2007. Vol. 9
(4), pp. 56–69.
5. Пономарев Д.Ю. Тензорная методология в телекоммуникациях // Системы управления и информационные технологии. 2006. 1.1(23). С. 161–165.
АЛГОРИТМ МИНИМИЗАЦИИ СКАЛЯРНОЙ ФУНКЦИИ
МНОГИХ ПЕРЕМЕННЫХ ПРИ ИНТЕРВАЛЬНЫХ ОГРАНИЧЕНИЯХ
НА ПЕРЕМЕННЫЕ
Ю.Г. Бояринов, к.т.н.; М.И. Дли, д.т.н.
(Филиал Московского энергетического института (технического университета) в г. Смоленске,
byg@yandex.ru)
Рассмотрен поисковый алгоритм минимизации скалярной функции многих переменных при неявном задании
функции и интервальных ограничениях на переменные. Суть алгоритма, в предположении, что наименьшее значение
функция принимает в одной из вершин гиперпараллелепипеда – области допустимых значений аргументов, состоит
в последовательном обходе вершин из начальной точки в сторону убывания функции. Предложена программная
реализация алгоритма в среде MATLAB.
Ключевые слова: алгоритм минимизации, скалярная функция многих переменных, интервальные ограничения на
переменные, программная реализация алгоритма.
Задача нахождения наименьшего значения
скалярной функции многих аргументов при наличии интервальных ограничений на аргументы на
практике является достаточно типовой. Для ее
решения разработано множество алгоритмов (см.,
например, [1–3]), однако, как правило, подобные
алгоритмы хорошо работают только при небольшом числе аргументов. Если же это число велико
– десятки и сотни, то многие из известных алгоритмов просто неприменимы. Для подобных ситуаций пригодными оказываются только так называемые алгоритмы большой размерности, реализованные, в частности, в системе компьютерной
математики MATLAB [4]. Однако использовать
возможности этой и других аналогичных систем
не всегда целесообразно ввиду их громоздкости,
иногда удобнее иметь автономные программы,
созданные на языке высокого уровня. В статье
рассмотрена разновидность алгоритма большой
размерности, отличающаяся простотой программной реализации.
Постановка задачи. Предполагается, что в
общем случае неявным образом задана скалярная
функция f(x) многих вещественных переменных
x1, x2,…, xn, или, иначе, векторного аргумента x
=[x1, x2, …, xn]T (здесь T – символ транспонирования). На переменные наложены интервальные ограничения в форме нестрогих неравенств:
x1 min x1 x1 max,
x2 min x2 x2 max,
. . .
xi min xi xi max,
. . .
xn min xn xn max,
xmin x xmax ,
(1)
T
где xmin =[x1min, x2min, …, xnmin] , xmax =[x1max,
или, в векторной форме,
x2max, …, xnmax]T.
Число переменных может быть значительным,
например до сотни.
69
Программные продукты и системы
№ 4, 2009 г.
Дополнительно предполагается, что функция
f(x) достаточно гладкая в области определения Sx
по соотношению (1), то есть не имеет экстремумов
внутри этой области.
Требуется найти точку x* Sx, в которой
функция f достигает наименьшего значения, то
есть, иными словами, решить оптимизационную
задачу
x* argf (x* ) argmin[f (x)] .
(2)
x Sx
Алгоритм решения. Выдвинутое предположение, что искомая функция не имеет экстремумов внутри допустимой области изменения аргументов, позволяет осуществлять поиск точки наименьшего значения функции среди граничных
(угловых) точек области Sx. Данная область, в
соответствии с ограничениями (1), представляет
собой гиперпараллелепипед в n-мерном пространстве аргументов. Суть алгоритма, как отмечалось,
в последовательном переборе вершин гиперпараллелепипеда, так, что осуществляется движение к
вершине, где значение функции наименьшее.
Приведем описание алгоритма.
Требуемая входная информация: размерность
задачи n (число аргументов функции), подпрограмма вычисления значений функции f(x1, x2,…,
xn) при заданном наборе ее аргументов, границы
изменения аргументов – векторы
x2min, …, xnmin]T и
xmin =[x1min,
xmax =[x1max, x2max, …, xnmax]T.
Начало.
1. Ввод исходных данных: числа переменных
n, предельного числа итераций N, задание подпрограммы вычисления функции f(x) , начального
приближения
(начальной
точки
расчетов)
u(0) {ui } , где i=1, 2 ,…, n; элемент ui равен 1 или
-1, при этом, если ui=1, то xi=xi max, если ui= -1, то
xi=xi min (вектор u введен для удобства обхода
вершин области определения функции, его элементы – индикаторы значений компонент x ).
Формирование вектора x0 по вектору начального приближения u0 .
2. Принятие u0 (и x(0) ) за базовую точку вычислений; расчет значения функции f (x(0) ) .
3. i=1.
4. Переход к i-й соседней с базовой вершине
гиперпараллелепипеда x(i ) путем замены значения
i-го элемента вектора u , то есть ui, на противоположный: ui= -ui. Соответствующее изменение значения xi.
5. Расчет f (x(i ) ) .
6. Сравнение
f (x(0) )
и
f (x(i) ) .
Если
f (x(0) ) f (x(i ) ) , то u(0) = u(i ) и переход к п. 3 алгоритма.
7. i=i+1.
70
8. i>n? Если нет (то есть обойдены не все n
соседних с текущей базовой точек гиперпараллелепипеда), то переход к п. 4 алгоритма.
9. Вывод информации об x* x(0) и f (x(0) )
f(x*) как о достигнутой точке наименьшего
значения функции и о значении функции в этой
точке соответственно.
Конец.
Вариант алгоритма был реализован с помощью «студенческого языка» программирования
Турбо Бейсик; без подпрограммы вычисления
значения функции основной текст программы
имел 40 строк и объем в несколько Кб; компилированный вариант программы, реализующей алгоритм, имел объем всего в 27 Кб. Программа достаточно устойчиво работала на многих модельных
примерах при числе переменных n 100. Время
счета, естественно, зависело от n и от сложности
вычисления значения функции f(x) .
Пример. Пусть задана функция f(x1, x2, …, x6)
вида (неявного)
f (x1 ,x 2 ,...,x6 )
(x1 x 2 )
x1
0
1
0 1 0 0
0
x3
0
1
x4
0
x4
1
x5
0
x6
1
1
0
0
0
1
(3)
при
ограничениях:
1.9 x1 2.1,
0.9 x2 1.1,
0.9 xу 1.1, 2.8 x4 3.2, 1.9 x5 2.1, 1.9 x6 2.1.
Требуется в условиях этой задачи найти наименьшее значение функции (и точку, в которой
она принимает это значение).
Решение. Здесь n=6, ограничение и задание
функции соответствуют принятой постановке задачи. В предположении, что точкой минимума является одна из угловых точек области определения (гиперпараллелепипеда), найдем данную точку, используя разработанный алгоритм при начальном приближении x0 =[2.1 1.1 1.1 3.2 2.1 2.1]T.
Полученный результат: x* =[1.9 1.1 1.1 2.8 1.9
1.9]T, f(x* ) 0.426.
С целью проверки этого результата минимум
рассматриваемой функции производился в среде
системы компьютерной математики MATLAB с
помощью функции fmincon [4] при начальном
приближении x0 [2 1 1 3 2 2]T . Результаты
вычислений следующие:
f=0.4262,
ans=1.9000 1.1000 1.1000 2.8000 1.9000 1.9000.
Как видно, они совпадают с полученными при помощи предложенного алгоритма, что подтверждает его работоспособность.
Разработанный алгоритм и реализующая его
программа могут эффективно применяться в составе интегрированного пакета для решения оп-
Программные продукты и системы
№ 4, 2009 г.
тимизационных задач с целью поиска минимума
скалярной функции большого числа переменных
при наличии ограничений на переменные типа нестрогих неравенств. Алгоритм эффективен, если
априори известно, что минимизируемая функция
не имеет точек экстремума внутри области ограничений и по своему виду близка к линейной.
Достоинствами алгоритма являются его простота с
вычислительной точки зрения, возможность работать с большим – до сотни и более – числом n аргументов и высокая скорость поиска точки минимума. Сходимость алгоритма 2n всегда гарантиру-
ется ввиду конечности точек поиска (вершин гиперпараллелепипеда).
Литература
1. Аоки М. Введение в методы оптимизации. М.: Наука,
1977.
2. Банди Б. Методы оптимизации: вводный курс. М.: Радио и связь, 1988.
3. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Лаборатория Базовых Знаний, 2000.
4. Дьяконов В., Круглов В. Математические пакеты расширения MATLAB: Специальный справочник. СПб: Питер,
2001.
ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ И ПРОГРАММЫ
ДЛЯ МОДЕЛИРОВАНИЯ ЭЙЛЕРОВЫХ ЭЛАСТИК
(Работа выполнена в рамках научно-технической программы Союзного государства «СКИФ-ГРИД»
«Разработка и использование программно-аппаратных средств Грид-технологий перспективных
высокопроизводительных (суперкомпьютерных) вычислительных систем семейства «СКИФ», 2007–2010»,
а также проекта РФФИ № 09-01-00246)
Ю.Л. Сачков, д.ф.-м.н.; А.А. Ардентов (Институт программных систем
им. А.К. Айламазяна РАН, г. Переславль-Залесский, sachkov@sys.botik.ru)
Описаны параллельные алгоритмы и программы для моделирования и исследования эластик Эйлера – стационарных конфигураций упругого стержня на плоскости. Продемонстрированы результаты работы программ, показатели эффективности распараллеливания.
Ключевые слова: эластики Эйлера, оптимальное управление, параллельные алгоритмы и программы.
В 1744 г. Леонард Эйлер исследовал задачу о
стационарных конфигурациях упругого стержня:
дан упругий стержень на плоскости, у которого
закреплены положения концов, а также углы наклона стержня на концах. Требуется определить
возможные профили стержня при заданных граничных условиях [1]. Эйлер получил дифференциальные уравнения для стационарных конфигураций стержня и описал их возможные качественные типы. Эти конфигурации назвали эйлеровыми
эластиками.
Задача об эластиках формализуется как следующая задача оптимального управления:
dx/dt cos , dy /dt sin , d /dt u ,
q (x,y, ) R
2
1
S , q(0)=(0,0,0),
1
u 2 (t)dt
q(1) q1 (x1 ,y1 , 1 ), u R , J
min .
0
Эластика, минимизирующая значение функционала упругой энергии J, называется оптимальной. С помощью геометрических методов теории
управления [2] в работе [3] вычисление оптимальной эластики сведено к решению систем алгебраических уравнений в эллиптических функциях
Якоби вида q( )=q1, где
– начальное значение
сопряженной переменной принципа максимума
Понтрягина, соответствующее оптимальной эластике с граничным условием q1. В работе [4] описаны разработанные на этой основе последова-
тельные алгоритмы и программы для вычисления
оптимальных эластик в системе Mathematica [5].
Цель данной статьи – описание параллельных алгоритмов и программ для вычисления индивидуальной оптимальной эластики по заданным граничным условиям q1, а также серии оптимальных
эластик по заданной деформации граничных условий q1(s), s [a,b], и для построения соответствующей анимации.
Программы разработаны и протестированы в
системе gridMathematica (параллельной версии
системы Mathematica) на кластере skif.botik.ru.
Описание алгоритмов
Вычисление индивидуальной эластики. Специфика задачи в том, что, хотя теоретически доказаны существование и единственность решения
системы уравнений q( )=q1 в определенных областях значений сопряженной переменной, для
вычисления этого решения требуется иметь хорошее начальное приближение. Такое приближение
отыскивается за счет его многократного случайного выбора на разных вычислительных узлах.
Входные параметры: q1 – граничные условия
эластики; nnodes – количество узлов суперкомпьютера, которые требуется использовать.
Выполняемые операции: На каждом узле запускается решение индивидуальной задачи с разными начальными приближениями. Схема алго71
Документ
Категория
Без категории
Просмотров
4
Размер файла
1 958 Кб
Теги
алгоритм, ограничений, многих, функции, минимизации, интервальных, скалярное, переменных
1/--страниц
Пожаловаться на содержимое документа