Применение генетического алгоритма для решения задачи распределения ресурсов в процессе выполнения административных регламентов

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

Ключевые слова: административный регламент, генетический алгоритм, распределение ресурсов.

Главное назначение административных регламентов (АР) заключается в интеграции в единое функциональное целое совокупности процессов и операций, реализуемых субъектами действия над существующими объектами в интересах, определенных нормативными регуляторами и инструкциями, для достижения заданной цели [1]. Поэтому если рассматривать АР как алгоритмический процесс, реализующий государственную услугу, то его основу будут составлять процессы и операции, закрепленные в нормативно-правовом акте АР (см. рис.1). Типовая структура АР предполагает наличие описания административных процедур c, каждая из которых достигается путем выполнения определенной последовательности задач z:

где P — предикат наличия элемента системы (P(e) — принимает значение «истина», если e существует в системе),

k >0.

При этом сам АР R будет характеризоваться последовательностью процедур:

где k >0.

Каждая задача предполагает совершение определенных операций субъектов над объектами, то есть:

Субъект-пользователь инициирует выполнение первой задачи последовательности, в результате чего запускается процесс выполнения АР. При этом субъекты и объекты выступают в качестве ресурсов, необходимых для перехода от одной задачи к другой [2].

Рис. 1. Типовая структура административного регламента

Основные проблемы, препятствующие выполнению требований АР можно разделить на две группы:

-       связанные с логической противоречивостью описания процессов АР;

-       возникающие в процессе выполнения АР.

Решение проблем логической противоречивости связано с правильным выбором методов и средств моделирования информационных процессов, подходящих для описания АР. Построение адекватной информационной модели АР позволит выявить противоречия в описании до его реализации виде совокупности информационных процессов, исключая появление в системе ряда угроз функциональной безопасности. Однако проблемы, возникающие в процессе выполнения, являются следствием отсутствия либо неправильного распределения ресурсов системы — субъектов и объектов и требуют решения оптимизационных задач. Решение одной из таких задач предлагается авторами данной статьи.

Как уже было отмечено ранее, выполнение некоторой задачи z_n связано с наличием в системе соответствующего субъекта s_m' и объекта q_k', которые можно определить как необходимые требования для z_n. Однако стоит отметить, что система государственного управления является динамичной системой и поэтому соблюдение условий P(s_m')→P(s_m) и P(q_k')→P(q_k) зависит от того, заняты ли s_m и q_k вмомент времени t_i, где t_i — время начала выполнения задачи z_n:

где t(t_i) — предикат, принимающий значение «истина»

в момент времени t_i.

При этом как показывает практика, каждый объект АР уникален и соответствует только одной задаче. Поэтому решение задачи обеспечения выполнимости АР состоит в согласовании множества необходимых объектов Q' и существующих в системе Q:

Иная ситуация обстоит с субъектами. Каждый субъект в системе государственного управления функционально может выполнять несколько задач АР. Поэтому для обеспечения выполнимости АР необходимо решение оптимизационной задачи, направленной на эффективное распределение задач между субъектами-исполнителями.

Рассмотрим процедуру решения задачи оптимального распределения субъектов-исполнителей, входящих в группу S_o(с общим количеством субъектов-исполнителей a), где каждый из субъектов-исполнителей s_nÎS_o функционально может быть задействован в выполнении задач из группы Z_l(с общим количеством задач b). Учитывая, что процесс выполнения задач непрерывный, а процесс поступления задач на выполнение случайный, то АР можно рассматривать как сеть узлов массового обслуживания, где каждый узел — это субъект-исполнитель s_n, который представляет собой систему массового обслуживания, выполняющую поток заявок l_k, соответствующий задаче z_kÎZ_l. Учитывая, что интервал между заявками и длительность выполнения задач распределены по законам A(t) и B(t), которые необходимо определять отдельно для каждого случая (отдельно для каждого исполнителя и АР в целом) и которые также могут изменяться во времени, то следует воспользоваться общим решением для одноканальных систем массового обслуживания G/G/1, которое характеризует выполнение некоторого потока задачи z_k (или задач z_k,…,z_k+p) исполнителем s_n. На основании решений для системы G/G/1 можно определить, сколько будет выполняться задача при заданных параметрах системы, которыми являются:

-          среднее фактическое время выполнения задачи t_Zk;

-          средняя интенсивность поступающих заявок l_k;

-          среднеквадратическое отклонение значения интервала между поступающими заявками s_A;

-          среднеквадратическое отклонение значения длительности выполнения задач s_B.

Рассмотрим математическую модель контроля основных параметров, влияющих на выполнимость на основе ТМО. Анализ многочисленных результатов (например результатов работ [3–5]) показывает, что наиболее удачное приближение для расчета среднего времени пребывания заявки для системы G/G/1 дает формула

,                                                                                       (1)

где , ,

Величины l_s иt_s определяются следующим образом:

l_s — суммарный поток заявок для исполнителя s, который равен

, где l_k,…,l_k+p — интенсивности поступления заявок на выполнение всех задач, выполняемых субъектом s;

t_s — среднее время выполнения задач субъектом s, которое определяется как

,                                                                                                 (2)

где

Для определения коэффициента вариации интервала между поступающими заявками v_As воспользуемся уравнением средней дисперсии для мультиплексированного входящего потока системы G/G/1, приведенным в работе [6]:

.                                                                (3)

Коэффициент вариации интервала между поступающими заявками в свою очередь будет равен

,                                                                                             (4)

Для определения коэффициента вариации длительности выполнения задач v_Bs необходимо учитывать, что субъект s_n выполняет задачи последовательно, поэтому нужно рассматривать множество значений длительности выполнения задач как совокупность с математическим ожиданием t_s, состоящей из групп с параметрами t_k,…,t_k+p и s_Bk,…,s_Bk+p. Воспользоваться правилом сложения дисперсий получим общую дисперсию длительности выполнения для s_n

.     (5)

Отсюда коэффициент вариации по определению равен

.

В случае если одну задачу (один поток) выполняет несколько субъектов, то необходимо воспользоваться решением для параллельных каналов с различным временем облуживания [7], то есть поступающее требование направляется на один из каналов (к одному из исполнителей) с вероятностью:

.                                                                                                      (6)

Поэтому поток заявок для каждого из исполнителей задачи z_k будет равен:

.                                                                                                                    (7)

Таким образом, выражение 2 позволяет оценить среднее время пребывания заявки у исполнителя s_n. Однако использовать данное значение для оценки выполнимости АР не возможно, так оно является общим для всех задач, выполняемых исполнителем s. Поэтому необходимо определить среднее время обслуживание для каждой задачи z_k,…,z_k+p, выполняемой s_n — T_k,...,T_k+p. Для этого рассмотрим следующую модель.

Рассмотрим узел СМО (отдельного исполнителя) как многоканальную систему (см. рисунок 2), где каждая заявка перед обслуживанием попадает в бесконечный накопитель Н, а каждый канал К_N связан с выполнением определенной задачи из множества z_k,…,z_k+p.

Рис. 2. Модель системы обслуживания потока различных задач АР

Учитывая, что накопитель Н является общим для всех потоков l_k,…,l_k+p, то среднее время ожидания в очереди будет одинаковым для всех заявок z_k,…,z_k+p. Поэтому с учетом 2 время пребывания заявки в системе для каждой из задач, выполняемых исполнителем s_n будет определяться по формуле

.                                                                                      (8)

Просчитав для каждой задачи среднее время выполнения T_i и сравнив их с максимальным временем T_imax, определенным нормативными регуляторами АР, можно сказать, что если T_i > T_imax, то задача не выполняется с заданными условиями. Результат представим в виде коэффициента:

.                                                                                                               (9)

В том случае, если задачу z_i выполняет несколько исполнителей s_n,…,s_n+l, то для сравнения выбирается максимальное значение времени пребывания заявки в системе:

.                                                                                                  (10)

Показатель a_k характеризует загруженность субъекта-исполнителя при выполнении задачи z_k и позволяет оценить запас времени, который доступен для решения других задач из группы Z_l.

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

Как уже было отмечено в первой главе, в качестве целевой функции необходимо использовать показатель, который характеризует насколько сбалансировано распределение исполнителей между задачами АР. В качестве такого показателя целесообразно использовать дисперсию величины a_k каждой из задач АР:

.                                                                                          (11)

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

Таблица 1

Матрица распределения ресурсов в системе

Z	S
	s1	s2	…	sn	…	sa
z1l1, sA1, T1max	x11	x21	…	xn1	…	xa1
z2l2, sA2, T2max	x12	x22	…	xn2	…	xa2
…	…	…	…	…	…	…
zk lk, sAk, Tkmax	x1k	x2k	…	xnk	…	xak
…	…	…	…	…	…
zblb, sAb,Tbmax	x1b	x2b	…	xnb	…	xab

Для каждой задачи также указывается поток заявок l_k и среднее время выполнения t_Znk. При этом сумма каждой строки должна быть больше 0, так как для любой из задач должен быть определен исполнитель:

(12)

Таким образом, задача распределения ресурсов схожа с классической задачей распределения ресурсов в транспортной сети (между поставщиками и потребителями, мощностей между каналами передачи данных и т. п.) и состоит в определении величин x_nk — поставка n-субъекта k-задаче, которая может принимать значение 1 либо 0. При этом для каждой из задач выполняется условие a_k≤ 1, а величина D(a) минимальна.

В работе [8] проведен подробный анализ методов оптимизации для решения задачи подбора технических средств охраны. Рассматриваемая в работе задача, также как и решаемая авторами данной статьи, имеет множество дискретных решений и сложную целевую функцию и также относится к NP-полным, в связи с чем был выбран генетический алгоритм. Поэтому целесообразно применить этот метод для решения поставленной задачи.

Теперь рассмотрим каждый из этапов решения задачи с помощью классического генетического алгоритма (разработанным Холландом [9]). Вначале случайным образом выбираются N(N≥b) значений вектора x (начальная популяция изNособей), каждое из которых соответствует системе неравенств 12 и условию a_k ≤ 1. Далее генерируется промежуточная популяция — это набор особей, получивших право размножаться. Для генерации промежуточной популяции используется принцип пропорционального отбора, заключающийся в том, что каждая особь попадает в популяцию с вероятностью, пропорциональной ее приспособленности. Для данной задачи: чем меньше значение D(a), тем больше вероятность попадания в промежуточную популяцию:

(13)

Далее особи в случайном порядке разбиваются на пары, и производится скрещивание (обмен случайными отсеченными частями):

К полученному в результате отбора и скрещивания новому поколению применяется оператор мутации, который инвертирует каждый бит популяции с вероятностью 1/N. Далее из полученных особей выбираются только те, что соответствуют системе неравенств 12 и условию a_k<1, после чего цикл повторяется снова. Процесс эволюции (цикл отбор-скрещивание-мутация) может продолжаться бесконечное число шагов, поэтому критерием останова является получение сходимости целевой функции за n число шагов, либо достижения максимального количества итераций. При этом оптимальному значению вектора x будет соответствовать наиболее приспособленная особь из последнего поколения:

(14)

Блок-схема классического генетического алгоритма приведена на рисунке 3.

Рис. 3. Классический генетический алгоритм

Исследование полученного генетического алгоритма, выполненного в среде MATLAB, для распределения 26 задач между 8 исполнителями показывают, что он уступает алгоритму General Pattern Search (GPS), представляющий собой разновидность симплексного метода, входящей в пакет MATLAB (см. рисунок 4).

Рис. 4. Процесс оптимизации целевой функции при помощи алгоритма GPS (слева) и классического генетического алгоритма (справа)

Использование алгоритма GPS дает возможность получить наименьшее значение целевой функции (D(a)=0,00341268) за одно и то же время работы (2 часа), как и классический генетический алгоритм (D(a)=0,003580429). Поэтому автором данной статьи предлагается ряд модификаций, позволяющих улучшить сходимость генетического алгоритма. Блок-схема модифицированного генетического алгоритма приведена на рисунке 5.

Рис. 5. Модифицированный генетический алгоритм

В данном генетическом алгоритме улучшение сходимости достигается путем дополнительного преобразования полученной после скрещивания и мутации популяции, которое включает в себя замену неприспособленных особей на лучшую особь с применением к ней мутации и вероятностью 0,05. После этого выполняется дополнительный отбор, который исключает особей, не соответствующих условию a_k ≤ 1.

Рис. 6. Процесс оптимизации целевой функции при помощи модифицированного генетического алгоритма

Результаты вычислительного эксперимента показали, что введенные модификации позволили получить лучшее значение целевой функции (D(a)=0,003037381) при одинаковом количестве итераций (400) и времени работы алгоритма. Поэтому полученный модифицированный генетический алгоритм может быть использован в практических целях для решения задачи повышения выполнимости АР.

Литература:

1.         Региональное электронное правительство: стратегия создания, архитектура, типовые решения / Под ред. В. И. Дрожжинова, А. А. Лучина. — М.: Эко-Трендз, 2004. — 288 с.

2.         Копытов В. В., Науменко В. В., Минин В. А., Зайцев А. А. Анализ проблем обеспечения бесконфликтного выполнения электронных административных регламентов // Сборник научных статей (выпуск XII) / Ставропольский филиал ИГУТИ. — Ставрополь, 2012 — С. 72–78.

3.         Шнепс М. А. Системы распределения информации. Методы расчета.- М.:Связь, 1979.-344 с.

4.         Алиев Т. И. Основы моделирования дискретных систем. — СПб: СПбГУ ИТМО, 2009. — 363 с.

5.         Нгуен Дык Тай Методы и средства исследования распределенных сетей передачи данных с неоднородным трафиком на основе неэкспоненциальных моделей: дис. канд. техн. наук: 05.13.13 / Нгуен Дык Тай. — М., 2009. — 145 с.

6.         Бахарева, Н. Ф. Аппроксимативные методы и модели массового обслуживания для исследования компьютерных сетей: дис. д-р техн. наук: 05.13.15 / Н. Ф. Бахарева. — Пенза, 2011. — 335 с.

7.         Саати, Т. Л. Элементы теории массового обслуживания и её приложения / Т. Л. Саати. — М.: Советское радио, 1971. — 520 с.

8.    Давидюк Н. В. Разработка системы поддержки принятия решений для обеспечения физической безопасности объектов [электронный ресурс]: дис. канд. техн. наук: 05.13.01, 05.13.19 — Астрахань: РГБ, 2010.

9.    Holland J. H. Adaptation in Natural and Artificial Systems: an Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence / J. H. Holland. — Massachusetts Institute of Technology, 1992. — 328 p.