Эвристические методы поиска решений в задачах оптимальной организации технологических процессов в распределенных системах запросного типа

А.Н. Колесников АВТОМАТИЗАЦИЯ ТЕХНИЧЕСКОГО ОБСЛУЖИВАНИЯ СИСТЕМ ЭНЕРГОСНАБЖЕНИЯ

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

В докладе рассматриваются вопросы использования современного программного обеспечения и вычислительных средств для решения вопросов автоматизации системы мониторинга и диагностики СЭС. Одной из наиболее сложных является задача обработки диагностической информации и дальнейшего её анализа, с целью прогнозирования технического состояния диагностируемых объектов. Автором предложен принцип построения СБД с включением в её состав вычислительных средств на базе современных персональных компьютеров. В состав такой системы входят:

- датчик (группа датчиков);

- прибор для стандартных видов анализа сигнала и специальных видов анализа, для обнаружения зарождающихся дефектов;

- программное обеспечение для прибора;

- линии связи датчиков с прибором и прибора с компьютером;

- компьютер;

- программное обеспечение для компьютера.

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

Персональный компьютер выполняет все виды измерений и анализа, что и дает возможность автоматизировать процессы диагностики и прогноза состояния СЭС.

А.М. Белевцев

ЭВРИСТИЧЕСКИЕ МЕТОДЫ ПОИСКА РЕШЕНИЙ В ЗАДАЧАХ ОПТИМАЛЬНОЙ ОРГАНИЗАЦИИ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ ЗАПРОСНОГО ТИПА

При решении задачи оптимальной организации технологических процессов в распределенных системах запросного типа РСЗТ [1] соответствующие модели формулируются в терминах линейных и квадратичных задач псевдобулевого математического программирования, а их решение обеспечивает рациональное (оптимальное) распределение нагрузки в системе.

В настоящей работе предлагаются эвристические методы поиска решений в таких моделях.

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

При построении модели распределения нагрузки в РСЗТ характерны две типовые ситуации:

а) обращения между узлами РСЗТ связаны лишь с запросами на выдачу хранимых ТО.

б) узлы обеспечивают также и обработку ТО, так что запросы связаны как с необходимостью обработки, так и выдачи ТО (т.е. являются обрабатывающими ОУ).

Обратимся вначале к рассмотрению случая (а).

Построение математической модели для случая (а) основано на методическом подходе, который впервые полно изложен в [2]. Существо этого подхода заключается в следующем.

В качестве входных параметров модели задаются величины 1 у - интенсивности

внешних запросов на использование 1-го ТО, возникающие в ^м узле (1 -1,1, j = 1, J) и

- интенсивности донесений для корректировки 1-го ТО из ]-го узла. В процессе выполнения запроса возможны обращения к другим ТО. Такие обращения задаются с помощью матрицы А = {а^ },

где а1к =

1, если при обработки 1- го ТО происходит обращение к к - му ТО;

0, в противном случае.

Причем ац полается равным 1. Тогда соответствующая математическая модель

может быть записана следующим образом.

* I * I

Найти набор значений X = |х к |, являющийся решением следующей задачи:

р1 = ХХ1 у X а1ку к(1 - хк НХХ1^

1 j

1 j

X хи 1 * j

При ограничениях

X ^хч £ ^ к

Xхк ^Пк,

j = 1,1,

к = й

[1, апёе к-е 01 Задтйааоп у а j-1 одёа; к [0, а Жоеаш пёо^аа.

Здесь V к и ук - средний объем (например, стоимость) одного взаимодействия, соответственно при обработке запросов и донесений. Величины ¥к и Wj - физический

объем, занимаемый к-м ТО, и ёмкость ]-го узла, отводимая для хранения ТО. Величина Пк определяет минимальную степень дублирования ТО, задаваемую, исходя из «важности» к-го ТО в целях обеспечения его надежной сохранности.

Рассмотрим возможный эвристический подход к решению задачи (1) - (4). Существо данного подхода основано на следующих простых физических соображениях:

- если ТО часто используются в запросах, их выгодно хранить в узлах, где такие запросы возникают;

- если ТО часто корректируется, следует хранить как можно меньше их копий.

к

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

Соответствующий эвристический алгоритм включает следующие шаги:

а) для каждого 1 и ] вычисляется значение величины а^:

ау =1 у Xа;кпк + Х1 Паппi - ;

к г г^

б) для ]=1,2,...,1 осуществляется упорядочивание а^ по убыванию их значений;

в) для ]=1,2,...,1 производится «плотная упаковка», т.е. для каждого ] назначаются 1 с наибольшими положительными значениями а^ до тех пор, пока выполняется (2).

Получаем последовательность цепочек

У j =а1ф о,/,...,

где а'д - наибольшее значение а1J, а,)2 - следующее по величине значение и т.д;

г) осуществляется проверка: удовлетворяют ли у j = 1^ соотношениям (3). Если все соотношения выполняются - переход к п. (е);

д) для каждого к, для которого не выполняется соотношение (3), отыскивается ],

такое, чтобы величина

тт

ау -а к)

была минимальной и выполнялось (2). Осуществляется замена 1-го ТО на к-й для ]-го узла и переход к продолжению п.(г);

е) алгоритм завершает работу.

В качестве иллюстрации рассмотрим пример решения задачи для системы из четырех ИУ и ОУ, в котором размещаются 10 ТО. Исходные данные задачи таковы: Ш-1500, j = 1,4; wk=500, к = Щ ni = 0, 1 = 1,10; У1=500; 1е {4,8,9,10}; 1е {4,8,9,10};

V; = 50, 1е {4,8,9,10}; у1=300; 1е {1,2,3,5,6,7}.

Значения элементов матрицы А приведены в табл. 1.

В табл. 2 представлены значения 1 у (числитель) и 11 (знаменатель).

Таблица 1

Элементы матрицы А________________________________________________________

Номера головных ТО Номера ТО, используемые при выполнении головных ТО

1 2 3 4 5 6 7 8 9 10

1 1 1 - 1 - - - - - 1

3 - - 1 1 - 1 - - 1 -

5 - 1 - 1 1 - - 1 1 1

7 - - - - - 1 1 1 - -

Т аблица 2

Интенсивности потоков

Номер ТО Номер узла

1 2 3 4

1 500/- 5/- 20/- 10/-

2 - - - -

3 1/- 1/- 500/- 5/-

4 - - -/100 -/1

5 1/- - 1/- 100/-

6 - - - -

7 - 500/- - 1/-

8 -/1 -/100 - -/1

9 - - -/100 -

10 -/100 - -/1 -

Осуществим поиск решения задачи изложенным выше эвристическим методом. Построим значение а у для j = 1,4;. Результаты построения сведем в табл. 3.

Таблица 3

Значения оу

Значе- ния і Значения і

1 2 3 4 5 6 7 8 9 10

1 150000 150300 300 200950 300 300 - 450 1000 250500

2 1500 1500 300 274950 - 150300 150000 252940 2500 -530

3 600 6300 150000 156250 300 150000 - -4600 250500 7600

4 3000 3300 1500 57500 30000 1800 300 25250 26500 27950

Реализация дальнейших шагов алгоритма дает следующие результаты.

Для хранения в ИУ1 назначаются следующие ТО: 4, 10, 2; в ИУ2 соответственно

- 8, 4, 7; в ИУ3 - 9, 4, 3 и в ИУ4 - 4, 9, 8.

Тем самым получаем решение, представленное в табл.4.

Таблица 4

Решение задачи

Значения і Значения 1

1 2 3 4 5 6 7 8 9 10

1 - 1 - 1 - - - - - 1

2 - - - 1 - - 1 1 - -

3 - - 1 1 - - - - 1 -

4 - - - 1 - - - - 1 1

Это решение связано с объёмом взаимодействий в системе У=644950. При этом 604300 - при выполнении запросов. Сравнивая полученную картину с ситуацией, когда все ТО хранятся в ОУ, видим, что даже на таком небольшом примере объём взаимодействия сокращается примерно в четыре раза, что обеспечивает заметную экономию затрат

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

Заметим, что в определенных ситуациях возможно получение и нулевого решения, поскольку существует обязательное дублирование ТО в ОУ. Например, нулевое решение может возникнуть, когда 1 ;;У; << 1^; для VI,j.

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

Найти набор значений X* = {х^ *}, являющийся решением задачи:

/ \

2 ^^"у

; ;

При ограничениях

Е а;кУ к(1 - хк; Ы1 - х;; V 10

xij Еа к

+ЕЕ1/;

_ ; ;

Е^хк; £ Wj, к ;=й

;-М X IV п , к = Ц

(Г VI X и" г? Е ; = й

ЕЕ1;; тй(1 - х;; )£Р8

Е хи 1* j

х

1 j

ху =

1, если 1- й ТО размещается в ^ м ИУ; 0, в противном случае.

Здесь У;0 характеризует объем взаимодействия с ИУ при реализации запроса в

ОУ, при этом полагается, что все ТО также дублируются в ОУ. Величины Ту и Т5 - это

средние времена реализации запроса, связанного с 1-м головным ТО в ^м ИУ и ОУ соответственно.

Сформулируем эвристический алгоритм для решения данной задачи. Он предусматривает реализацию следующих трех процедур:

1) решение сформулированной выше задачи (1) - (4) и (8) описанным выше эвристическим методом;

2) определение множества ТО, подлежащих обработке в ОУ;

3) перераспределение ТО для хранения в системе.

Итак, определим основные шаги алгоритма:

а) осуществляется решение задачи (1) - (4) и (8). В результате получается набор значений X* = {х^ *};

б) вычисляется множество значений величины

О; =* а

Еа1кУк (1 - хк )-уШ .к*!

в) значения О;; упорядочиваются по убыванию;

г) осуществляются последовательные назначения ТО с наибольшим значением 0^1 для обработке на ОУ. Такие назначаются осуществляются до тех пор, пока:

1) выполняются соотношения (9);

2) значения 0^ - положительны.

Невыполнение условий (1) или (2) означает завершение шага (г) алгоритма и переход к шагу д);

д) исключаются из рассмотрения ТО, которые используются лишь в ОУ. Это делается с учетом соотношения (7). В результате формируется множество М из тех ТО, которые хранятся и обрабатываются в ИУ;

е) для множества М решается задача (1) - (4) и (8);

ж) полученное в пп.(г) и (е) решение есть решение сформулированной задачи в

целом.

Проиллюстрируем примером предложенный алгоритм. Рассмотрим расширение примера, приведенного выше. Пусть значение V ;о задается в табл.5.

Пусть pj = 0,65 для j = 1,4; р5 = 0,53; п; = 1, 1 е {4,8,9,10}

Xу = 6 • 10-4, 1 е {1,3,5,7} j = 1,4; т5 = 4 • 10-4, 1 е {1,3,5,7}. Остальные значения пара-

метров такие же, как и в предыдущем примере.

Таблица 5

Значения Vю

Номера головных ТО 1 3 5 7

Значения V іо 10 1000 10 100

Решение задачи (1) - (4) и (8) в п. (а) алгоритма совпадает с представленным в табл.4. Выполнение п. (б) данного алгоритма дает значения 0^, представленные в табл.

6.

Т аблица 6

Значения 0^

Значения J Значения і

1 2 3 4 5 6 7 8 9 10

1 145000 - 100 - 1290 - - - - -

2 5450 - -120 - - - 100000 - - -

3 21800 - -450000 - 1590 - - - - -

4 5900 - -2000 - 109000 - 1000 - - -

В результате выполнения пункта (в) получаем упорядоченную последовательность значений 0І:

0'! 1 =145000; 0'54 = 109000; 0'72 =100000; 0' 3 = 21800; 0' 4 =5900; 0' 2 =5450; 0' 1 0'53 = 1590; 0'51 =1290; 0'74 =1000; 0'31 = 100; 0'32 = -120; 0'34 = -2000; 0'33 = - 450000.

Выполнение п. (г) обеспечивает следующее распределение ТО: ТО 1, 5 и 7 назначаются для обработки в ОУ, а ТО 3 обрабатывается в ИУ.

Выполнение п. (д) приводит к распределению ТО, представленному в табл. 7.

В результате выполнения п.(е) получаем некоторую корректировку табл.7. Окончательное решение задачи представлено в табл. 8.

Таблица 7

Промежуточное решение

Значе- ния J Значения і

1 2 3 4 5 6 7 8 9 10

1 - - - - - - - 1 - -

2 - - - - - - - - - 1

3 - - 1 1 - - - - 1 -

4 - - - - - - - - - -

Таблица 8

Решение задачи

Значения j Значения і

1 2 3 4 5 6 7 8 9 10

1 - - - - - - - - - 1

2 - - - - - - 1 1 - -

3 - - 1 1 - - - - 1 -

4 - - - - - - - - - -

При этом решении общий удельный объём взаимодействий в системе составляет 40600 ед. и состоит лишь из взаимодействий, связанных с реализацией запросов. Заметим, что поток, связанный с корректировкой ТО, размещенных в ОУ, не учитывается, поскольку при условии обязательности хранения ТО в ОУ он постоянен.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Белевцев А.М. Об оптимизации технологических процессов в распределенных системах запросного типа. - г. Вл-р.: Технология и проектирование электронных средств, № 1, 2003.

2. Балыбердин В.А., Белевцев А.М., Степанов О.В. Оптимизация информационных процессов в автоматизированных системах с распределенной обработкой данных. - М.: Технология, 2002. С.280

А.А. Батальщиков, А.В. Розенберг

КОЭФФИЦИЕНТ КОРРЕЛЯЦИИ ГИДРОАКУСТИЧЕСКИХ ПОЛЕЙ ДВИЖУЩЕГОСЯ И НЕПОДВИЖНОГО ВОЗДУШНОГО ИСТОЧНИКА

Здесь мы будем рассматривать модовую составляющую гидроакустического поля движущегося воздушного монохроматического источника и возможность аппроксимации этого поля полем неподвижного источника. Для сравнения полей будем использовать коэффициент корреляции в виде [1]