ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

4
Publication date:
09 December 2024

Solution of a software structural construction problem for intelligent humidity sensor

The article was published in issue no. № 3, 2013 [ pp. 272-276 ]
Abstract:The article considers the approach to solution of softwarestructural construction problem using the intellectual humidity sensor (IHS), which is an information-measuring system (IMS).When designing software and data support, the main modules of HIS are: an intellectual interface, a supervisor, survey sensors modules and measurement procedures mod-ules. The functioning of the IHS is based on using databases and knowledge bases. The IHS implementation requires a num-ber of algorithms, which should be placed in the modules to provide the designed IMS with specified properties. Such tasks of a choice belong to the class of NP-complete that can be solved only approximately. Therefore, for practical solving of the software structural construction problem it is offered to use heuristic methods, in particular, genetic algorithms. Method to solve the tasks includes following stages: forming the vector-line of algorithms distribution genes on the modules,description of a matrix of relations, interaction of algorithms using information elements, creating the matrix of alternatives ofalgorithm belonging to module, determining the target function. This approach can be used for designing data support and software for information-measuring or information management systems, that involves a large number of modules and algorithms.
Аннотация:Рассматривается подход к решению задачи структурного построения ПО на примере интеллектуального датчика влажности(ИДВ), представляющего собой информационно-измерительную систему(ИИС). При проектировании программного и информационного обеспечения в качестве основных модулей ИДВ рассматриваются интеллектуальный интерфейс, супервизор, модули опросадатчиков и реализации измерительных процедур. Функционирование ИДВ базируется на использовании БД и БЗ. Для реализации работы ИДВ используются алгоритмы, которые требуется разместить по модулям таким образом,чтобы проектируемая ИИС обладала заданными свойствами. Подобные задачи выбора даже умеренного размера относятся к классу NP-полных, их удается решать только приближенно. Поэтому для практического решения задачи структурного построения ПО предлагается использовать эвристические методы, в частности генетические алгоритмы. Методика решения задачи включает следующие этапы: формирование вектора-строки генов распределения алгоритмов по модулям, описание матрицы связей, взаимодействие алгоритмов посредством информационных элементов, создание матрицы альтернатив принадлежности алгоритма модулю, определение целевой функции. Подобный подход можно применять при проектировании информа-ционного обеспечения и ПО как информационно-измерительных, так и информационно-управляющих систем, имеющих в своем составе большое количество модулей и алгоритмов.
Authors: (SArtemova@yandex.ru) - , Russia, Ph.D
Keywords: software, genetic algorithm, structural construction optimization
Page views: 10026
Print version
Full issue in PDF (13.63Mb)
Download the cover in PDF (1.39Мб)

Font size:       Font:

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

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

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

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

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

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

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

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

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

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

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

Таблица 1

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

Алгоритм

Наименование модуля

Номер

Наименование

1

Предварительный расчет входных значений

ИИ, СВ, МОД, МРИП

2

Нормирование входных значений

ИИ, СВ, МОД, БД, БЗ

3

Работа с когнитивной графикой

ИИ

4

Денормирование рассчитанных выходных значений

ИИ, СВ, МОД, МРИП

5

Функционирование базы данных

СВ

6

Функционирование базы знаний

ИИ

7

Опрос датчиков

МОД

8

Реализация измерительных процедур

МРИП

9

Функционирование лингвистического процессора

ИИ

10

Реализация работы технических средств

СВ, МОД

11

Реализация работы программных средств

СВ, МОД

12

Принятие решений в случае отказов датчиков

ИИ, СВ, МОД, МРИП, БЗ

13

Реализация различных моделей измерительных процедур

БЗ, МРИП

Таблица 2

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

Номер алгоритма

Номера взаимодействующих с ним алгоритмов

1

2, 3, 11, 8, 5, 7, 6

2

5, 11, 6, 8, 7

3

4, 5, 6, 12, 13, 9

4

3, 5, 6

5

1–13

6

1–13

7

1, 2, 5, 6, 8

8

5, 6, 3, 11, 12, 13

9

5, 6, 3

10

7

11

1–13

12

5, 6, 8, 7

13

5, 6, 7, 8

Решение задачи предлагается проводить по предложенной в [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:

i

1

2

3

4

5

6

7

8

9

10

11

12

13

P

2

2

1

2

2

1

3

4

1

2

2

1

4

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

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

Таблица 3

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

X

i

                         

j

1

2

3

4

5

6

7

8

9

10

11

12

13

СУММ

1

0

0

1

0

0

1

0

0

1

0

0

1

0

4

2

1

1

0

1

1

0

0

0

0

1

1

0

0

5

3

0

0

0

0

0

0

1

0

0

0

0

0

0

1

4

0

0

0

0

0

0

0

1

0

0

0

0

1

2

5

0

0

0

0

0

0

0

0

0

0

0

0

0

0

6

0

0

0

0

0

0

0

0

0

0

0

0

0

0

СУММ

1

1

1

1

1

1

1

1

1

1

1

1

1

 

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

Таблица 4

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

D

i

                       

i

1

2

3

4

5

6

7

8

9

10

11

12

13

1

0

1

1

0

1

1

1

1

0

0

1

0

0

2

0

0

0

0

1

1

1

1

0

0

1

0

0

3

0

0

0

1

1

1

0

1

1

0

1

1

1

4

0

0

0

0

1

1

0

0

0

0

1

0

0

5

0

0

0

0

0

1

1

1

1

1

1

1

1

6

0

0

0

0

0

0

1

1

1

1

1

1

1

7

0

0

0

0

0

0

0

1

0

1

1

1

1

8

0

0

0

0

0

0

0

0

0

0

1

1

1

9

0

0

0

0

0

0

0

0

0

0

1

0

0

10

0

0

0

0

0

0

0

0

0

0

1

1

1

11

0

0

0

0

0

0

0

0

0

0

0

0

0

12

0

0

0

0

0

0

0

0

0

0

0

0

0

13

0

0

0

0

0

0

0

0

0

0

0

0

0

Используем также служебные матрицы 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

Предварительный расчет входных значений

СВ

2

Нормирование входных значений

СВ

3

Работа с когнитивной графикой

ИИ

4

Денормирование рассчитанных выходных значений

СВ

5

Функционирование БД

СВ

6

Функционирование БЗ

ИИ

7

Опрос датчиков

МОД

8

Реализация измерительных процедур

МРИП

9

Функционирование лингвистического процессора

ИИ

10

Реализация работы технических средств

СВ

11

Реализация работы программных средств

СВ

12

Принятие решений в случае отказов датчиков

ИИ

13

Реализация различных моделей измерительных процедур

МРИП

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

Литература

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.


Permanent link:
http://swsys.ru/index.php?page=article&id=3602&lang=&lang=en&like=1
Print version
Full issue in PDF (13.63Mb)
Download the cover in PDF (1.39Мб)
The article was published in issue no. № 3, 2013 [ pp. 272-276 ]

Perhaps, you might be interested in the following articles of similar topics: