научная статья по теме Алгоритмы векторного управления производственными процессами на базе метода деформируемого многогранника Биология

Текст научной статьи на тему «Алгоритмы векторного управления производственными процессами на базе метода деформируемого многогранника»

информатика, вычислительная техника и управление

management,

computer engineering and information

science

DOI: 10.12731/wsd-2015-10.1-5 УДК 658.51

Алгоритмы векторного управления производственными процессами на базе метода деформируемого многогранника

Догадина Е.П., Холкина Н.Е.

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

Ключевые слова: критерий; оптимизация; симплекс; целевая функция; свертка.

algorithms of vector management production-mi process on base of the method of the deformed polyhedron

Dogadina E.P., Kholkina N.E.

In article is designed and offered algorithms of vector management parameter production processes. The Contributory changes to move of the realization algorithm management depending on behaviours of the targetfunction. By means of designed algorithm is spared time for optimization graphics production with provision for required production restrictions, as well as is realized possibility operative to respond to change priority and incidental circumstance in the course of performing the production process.

Keywords: criterion; the optimization; the simplex; the target function; the folding.

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

Принцип реализации метода состоит в сравнении значений функции в (п+1)-й вершинах многогранника-симплекса и перемещении симплекса в направлении оптимальной точки в n-мерном пространстве с помощью определенной итерационной процедуры (для n=2 выпуклым многогранником является треугольник).

Под вершинами симплекса в данном случае будем понимать соответствующие значения X = {Хк1,Хк2,...,Хкп)е.0.доп,к = \..п + \ вектора оптимизируемых параметров, а симплексом XJ,j = 0,1,2,.. называется упорядоченная совокупность таких вершин (XJi,XJ2,...,XJ„+i) е Qaon.

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

На рисунке 1 представлена блок-схема алгоритма управления с учетов векторных параметров производственных процессов и возможности свертки критериев на базе метода деформируемого многогранника Нел-дера-Мида.

Рис. 1. Блок-схема алгоритма векторного управления на базе метода деформируемого многогранника Нелдера-Мида

Данный алгоритм управления можно модифицировать с учетом разработанной математической модели управления [1, 3].

К = /(рф,Х)^>гт п(тах), (1)

К = {Kl,K2,...,Kr),

/ = 1,1, (2)

Х = (Х1,Х2,...,Х„)еПдоп, (3)

где р(0 - вектор-функция вероятностей состояний системы на рассматриваемом интервале времени функционирования te{0,T}, определяемых нестационарной моделью, при этом плотности вероятностей переходов зависят от вектора Х оптимизируемых параметров системы. Система ограничений (2) и выражение (3) определяют область допустимых решений задачи.

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

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

Рассмотрим предложенную модификацию алгоритма векторного управления на базе симплекс поиска подробнее [1, 2, 4].

Шаг 1 «Построение начального симплекса» и шаг 2 «Определение направления улучшения решения» остаются неизменными. Вводится переменная sovp = 0 для определения количества неизменных значений наилучшей вершины симплекса.

Производится поиск отраженной вершины по формуле

Хп+1и)=Хси)+Х*{Хси)-Хки)\ (4)

Определяем принадлежность точки области допустимых зна-

чений.

Если Хп+1принадлежит области допустимых значений, то необходимо перейти на шаг 4.

Если Хп+1(Л не принадлежит области допустимых значений, то перейти на шаг 5.

Шаг 4. Получение растяжения симплекса

Вычисляем Р'(ЛГЛ+1(Л), при этом возможно один из двух случаев:

а) Если при этом значение функции в новой вершине оказалось меньше, чем наилучшее значение симплекса, т.е. ТГ(ХИ+1(Л) < то проводят растяжение симплекса, увеличивая в р>0 (обычно Р>2) раз расстояние от отраженной вершины до центра тяжести ХС(Л:

*И+2(Л = X™ + Р * - Хси)). (5)

Если Хк+2(л не принадлежит области допустимых значений, то отбрасываем точку Хп+2и\ Х/У* = Хп+У\ Осуществляется переход на шаг 7.

Если после операции растяжения значение функции в новой точке уменьшается, т.е. /г(Хи+20)) < то эта вершина принимается за

вершину нового симплекса Х^ = Хп+2и\ и осуществляется переход на шаг 7.

Если же увеличивается, то отбрасываем точку Хп+2 Л Очевидно, что произошло перемещение слишком далеко от точки Х^ к точке Поэтому следует заменить точку Х^ на точку Хп+У\ в которой было получено улучшение: X= Хп+1и\ Осуществляется переход на шаг 7.

б) Когда значение функции в отображенной вершине больше, чем в наилучшей вершине предыдущего симплекса Р(Хп+У) > Р{Х^\ и больше, чем во всех остальных Р(Хп+1и)) > Р(Хси)), то переход на шаг 5.

Когда значение функции в отображенной вершине больше, чем в наилучшей вершине предыдущего симплекса Р(Х> Р(хУ^), но мень-

Р( X ^^ < Р(X 1 X ^

ше,чемУро всех остальных Л+1 ' ~ ° ', то заменяем точку *

на "+1 . Осуществляется переход на шаг 7.

Шаг 5. Получение значения функции после сжатия, вычисленные на основе аддитивной свертки критериев.

Производят операцию сжатия с коэффициентом 0<у<1 (обычно у =0,5)

хя™ = ху)+-1*{х™-х?)). (6)

Если Хп+3(Л принадлежит области допустимых значений, то необходима замена вершины Xс максимальным значением целевой функции на Хп^]). Перейти на шаг 7.

Если ХЯ+3(Л не принадлежит области допустимых значений, то перейти на шаг 6.

Шаг 6. Уменьшение значения симплекса.

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

Выполняем операцию редукции вершин:

хи) = №0>+^/0>) к = 0пк ф ¡. (7)

Проверяем принадлежность новых вершин области допустимых значений.

Шаг 7. Проверка сходимости.

Если

^ (F(Xka)) - F(X0a) ))2 или sovp < const, (е - заданная точ-^-< е

п

ность решения), то поиск минимума заканчивается и полагается, что оптимальное решение задачи

Хопти) = х™, Р{Хопти)) = (8)

В противном случае :

1) Если Х,0) = Х;0_1),7 * 0, то = зо\р +1

2) ] = у + 1 и переход к шагу 2.

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

Список литературы

1. Догадина Е.П., Кропотов Ю.А., Суворова Г.П. Математическая модель определения вероятностей состояний системы обслуживания // Радиотехника, 2009. № 11. С. 103-105.

2. Догадина Е.П. Функциональная модель управления производственными процессами с последовательной ячеистой структурой // Методы и устройства передачи и обработки информации: Межвуз. сб. науч. тр. [Под ред. В.В. Ромашова, В.В. Булкина]. М.: Радиотехника, 2011. № 1. С. 119-120.

3. Догадина Е.П., Коноплев А.Н. Многокритериальное управление процессами мелкосерийного производства радиоэлектронной аппаратуры // Методы и устройства передачи и обработки информации: Межвуз. сб. науч. тр. [Под ред. В.В. Ромашова, В.В. Булкина]. М.: Радиотехника, 2011. № 1. С. 121-123.

4. Догадина Е.П. Программный комплекс автоматизации управления производственными процессами на базе стохастических методов локального поиска // Радиопромышленность. 2012. № 2. С. 154-159.

5. Догадина Е.П., Кропотов Ю.А. Разработка программного комплекса для выявления зависимостей характеристик систем массового обслуживания на примере распределения вероятностей состояний вычислительной системы во времени // Методы и устройства передачи и обработки информации: Межвуз. сб. науч. тр. [Под ред. В.В. Ромашова, В.В. Булкина]. М.: Радиотехника. 2009. № 11. С. 336-340.

References

1. Dogadina E.P., Kropotov U.A., Suvorova G.P. Matematicheskaya model' opredeleniya veroyatnostey sostoyaniy sistemy obsluzhivaniya [Mathe-

matical model of the determination of probability of the conditions of the system of the service]. Radiotekhnika [Radio engineering], 2009, no 11, pp. 103-105.

2. Dogadina E.P. Funktsional'naya model' upravleniya proizvodstvennymi prot-sessami s posledovatel'noy yacheistoy strukturoy [Functional model of management production process with consequent cellular structure]. Metody i us-troystvaperedachi i obrabotki informatsii [Methods and device of the issue and information handling], Moscow, Radio engineering, 2011

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком