Software & Systems

Возможности практического решения задач структурного построения рассматриваются в теории сложности задач выбора, где показано, что задачи даже умеренного размера относятся к классу NP-полных и их удается решать только приближенно [1]. Поэтому большинство практических задач структурного построения решают с помощью приближенных (эвристических) методов. Эти методы не гарантируют оптимального решения, но приводят к результатам, близким к оптимальным, при приемлемых затратах вычислительных ресурсов. Рассмотрим структурное построение ПО на примере информационно-измерительной системы (ИИС) – интеллектуальный датчик влажности (ИДВ). ИДВ позволяет проводить косвенные измерения влажности материала непосредственно в процессе сушки в реальном времени [2]. В основе функционирования ИДВ лежат нейронные сети.

Важным этапом проектирования ИДВ является создание ПО, позволяющего ИИС иметь следующие свойства: слабую связанность элементов, тестируемость, диагностируемость, простоту обслуживания и эксплуатации, защищенность от несанкционированного доступа, экономичность, модифицируемость, функциональную расширяемость, возможность изменения конфигурации, максимальную длительность жизненного цикла, минимальное время на пусконаладку [3].

При проектировании ПО и информационного обеспечения в качестве основных модулей ИДВ (см. рис.) можно выделить интеллектуальный интерфейс (ИИ), супервизор (СВ), модуль опроса датчиков (МОД) и модуль реализации измерительных процедур (МРИП). Функционирование ИДВ базируется на использовании БД и БЗ.

В состав модуля ИИ входит следующее:

–      когнитивная графика, позволяющая визуально воспринимать процесс и результаты поиска благодаря установлению взаимосвязей между изображениями, возникающими на экране дисплея, с когнитивными процессами образного мышления;

–      интегрированная среда разработки, кото- рая дает возможность разработчику вносить коррективы в функциональные программные моду- ли и БЗ;

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

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

К основным типовым функциональным программным модулям информационно-измеритель­ной системы ИДВ относятся модули опроса датчиков и реализации измерительных процедур.

Для реализации работы ИДВ используются алгоритмы, которые требуется разместить по модулям таким образом, чтобы проектируемая ИИС обладала вышеприведенными свойствами.

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

Таблица 1

Варианты распределения алгоритмов по модулям

Таблица 2

Взаимодействие алгоритмов посредством информационных элементов

Решение задачи предлагается проводить по предложенной в [3] методике, состоящей их следующих этапов.

1.     Формируется вектор-строка P генов распределения алгоритмов по модулям.

2.     Описывается матрица D-связей взаимодействия алгоритмов с помощью информационных элементов.

3.     Создается матрица принадлежности i-го алгоритма j-му модулю – матрица альтернатив X. Значения матрицы X связаны с вектором P логическими функциями ограничений:

–      на однократность включения i-го алгоритма в совокупность программных модулей

;                                                               (1)

–      на дублирование занимаемой памяти k-м информационным элементом

;                                                                      (2)

–      на сложность информационного интерфейса между отдельными модулями

                                         (3)

где m – количество модулей; n – количество алгоритмов; d – количество информационных элементов; М – максимально допустимое число информационных элементов, являющихся общими для всех модулей. Данное ограничение вводится с целью минимизации информационных связей между модулями. Для формализации задачи введены следующие обозначения: xi,j – принадлежность i-го алгоритма j-му модулю; yk,l – принадлежность k-го информационного элемента l-й области памяти; zk,j – вхождение k-го информационного элемента в j-й модуль, таким образом, zk,jzk,j+1 – взаимосвязь в процессе работы алгоритмов j-го текущего модуля с последующим по k-му информационному элементу.

4.     Формируются матрицы Y=X´D и W=Y´XT. Число внутренних связей равно сумме элементов главной диагонали матрицы W. Исходя из задачи, нужно увеличить число внутренних связей, так как это означает уменьшение числа внешних связей. Эта функция целевая, она подвергается максимизации с помощью генетического алгоритма. Целевая функция является суммой элементов главной диагонали матрицы W и подлежит максимизации посредством изменения значений генов вектора P с помощью генетических алгоритмов.

Согласно приведенной методике сформируем вектор-строку P, число ее элементов соответствует числу распределяемых алгоритмов (n=13). Здесь неизменяемые в результате действия ограничений ячейки с i=3, 5, 6, 7, 8, 9:

Элементы P являются генами, их значения подбираются в процессе решения для достижения оптимального значения целевой функции. Диапазон изменения ограничен. Значения элементов (номер) указывают на принадлежность соответствующего алгоритма модулю с номером, который содержится в ячейке. Модули пронумерованы следующим образом: 1 – ИИ, 2 – СВ, 3 – МОД, 4 – МРИП, 5 – БЗ, 6 – БД.

Далее формируем матрицу X (см. табл. 3). Она имеет размер n´m. Если i-й алгоритм содержится в j-м модуле, то в ячейке i, j стоит единица, в противном случае ноль. Данные берутся согласно вектору-строке P. Таблица строится в Excel автоматически с помощью логических функций (функция ЕСЛИ). Служебная строка СУММ показывает, что сумма соответствующих столбцов равна единице – ограничение на принадлежность алгоритма только одному модулю. С помощью служебного столбца СУММ (сумма соответствующих строк) можно видеть и контролировать (ограничивать) наполняемость модулей.

Таблица 3

Принадлежность i-го алгоритма j-му модулю

Заполним матрицу D (n´n), которая показывает, как связаны между собой алгоритмы (связь несимметричная, направленная). Если модули связаны, то на пересечении соответствующей строки и столбца стоит единица, в противном случае ноль. Матрица формируется исходя из исходных данных задачи.

Таблица 4

Связь алгоритмов между собой

Используем также служебные матрицы PT и XT, представляющие собой транспонированные матрицы P и X. Матрица Y определяется путем произведения матриц X и D: Y=X´D.

Матрица W представляет собой произведение матриц Y и XT: W=Y´XT.

Целевая функция f является суммой элементов главной диагонали матрицы W и подлежит максимизации посредством изменения значений генов вектора P с помощью генетических алгоритмов: .

Для реализации процесса подбора подходящей комбинации используются следующие настройки: размер популяции – 50, длина хромосомы – 8 бит, тип хромосом – непрерывные, вероятность скрещивания – 0,9, вероятность мутации – 0,01, степень обновления – 0,98, стратегия элитаризма – ON, оператор разнообразия – ON.

Требуется найти максимум функции f.

Для решения поставленной задачи используются ограничения:

–      на диапазон для хромосом: 1≤Pi≤6, ;

–      на единственность алгоритмов:  ;

–      на размещение для конкретных алгоритмов (из условия): 1≤P1≤4, 1≤P4≤4, 2≤P10≤3, 2≤P11≤3, 1≤P12≤5, 4≤P13≤5.

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

Таблица 5

Результат распределения алгоритмов по модулям

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

Литература

1.     Норенков И.П Основы автоматизированного проектирования: учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.

2.     Артемова С.В., Грибков А.Н. Система мониторинга процесса сушки с интеллектуальными датчиками влажности // Датчики и системы. 2009. № 3. С. 27–30.

3.     Денисенко В.В. Компьютерное управление технологическим процессом, экспериментом, оборудованием. М.: Горячая линия–Телеком, 2009. 608 с.

References

1.     Norenkov I.P., Osnovy avtomatizirovannogo proektirova­niya [The basics of automated designing], textbook for univ., Moscow, Bauman MSTU Publ., 2002.

2.     Artemova S.V., Gribkov A.N., Datchiki & Systemi [Sensors & Systems], no. 3, 2009, pp. 27–30.

3.     Denisenko V.V., Kompyuternoe upravlenie tekhnologi­cheskim protsessom, eksperimentom, oborudovaniem [Computer control of the technological process, experiment, equipment], Moscow, Goryachaya liniya–Telekom, 2009.