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

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

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

Использование совокупности взаимосвязанных матричных и графовых моделей для анализа информационных потоков и технологии обработки данных в СОД РВ [1–3] в настоящее время из-за возросшего потока данных в инфокоммуникационных системах не позволяет оперативно их обрабатывать и управлять ими.

Поэтому предлагается строить алгоритм обработки информационных потоков данных в СОД РВ с использованием в начале традиционного подхода (матрицы и интегрированные информационные графы (ИИГ)), а на заключительном этапе — генетических алгоритмов (ГА).

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

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

Построение и структуризация ИИГ для решения задач обработки данных реального времени осуществляется следующим образом.

Пусть задано множество задач СОД РВ {h_n}, n = 1,—N—. Технологии решения каждой задачи соответствует направленный ИИГ Gⁿ = (Dⁿ,Rⁿ), где Dⁿ= {d_lⁿ}, l = 1,—L—ⁿ; Lⁿ — множество вершин ИИГ, отражающих информационные элементы задачи h_n; R_n = {p_r} — множество отношений между информационными элементами d_lⁿ∈Dⁿ. Каждому ИИГ Gⁿ соответствует квадратная бинарная матрица смежности Cⁿ = ||C_uⁿ|| размером LⁿxLⁿ. Элемент ||C_uⁿ|| матрицы Cⁿ равен 1, если элементы d_lⁿ и d_l′ⁿ графа Gⁿ связаны отношениями p_r, и равен 0 в противном случае.

Структурированный ИИГ взаимосвязей информационных элементов задачи, преобразованный к виду, не содержащему циклов обработки, называется скелетным ИИГ задачи и обозначается как G_cⁿ. Он состоит из ряда уровней или непересекающихся подмножеств вершин, каждая из которых является выходным результатом обработки предыдущего уровня или подмножества информационных элементов. С использованием ИИГ G_cⁿ определяется множество процедур обработки данных, необходимых для решения задач {h_n}, n = 1,—N—.

Для каждой упорядоченной пары элементов (d_lⁿ, d_l′ⁿ)∈Dⁿ определим подмножества:

D₁ⁿ = {d_lⁿ|∃d_lⁿ((d_lⁿ, d_l′ⁿ)∈Dⁿ)},

D₂ⁿ = {d_lⁿ|∃d_lⁿ((d_lⁿ, d_l′ⁿ)∈Dⁿ)},

D₁ⁿ ∪D₂ⁿ = Dⁿ.

Затем определим на множестве Dⁿ декартово произведение Dⁿ = D₁ⁿxD₂ⁿ. Пара элементов (d_lⁿ, d_l′ⁿ) связана с процедурой p_r, если она принадлежит отношению R_n. Совокупность процедур задачи образует множество {p_r} = Rⁿ. Полное множество процедур анализируемого множества {η_n} задач определяется путем объединения:

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

Под матрицей достижимости M_n понимается квадратная бинарная матрица, проиндексированная одинаковым образом по обеим осям множеством информационных элементов D_n. Элемент d_l достижим из элемента d_l′(d_lRd_l′), если на графе Gⁿ = (Dⁿ,Rⁿ) можно указать направленный путь от вершины d_l к вершине d_l′ (либо l = l′):

Матрица M_n определяется на основе матрицы C_n. При этом они связаны булевым уравнением:

M_n = C_m^m+1 = C_m^m ≠ C_m^m–1.

Анализ структур обработки данных для каждой η_n задачи СОД и определение необходимой последовательности получения информационных элементов упрощается, если элементы построенной матрицы достижимости упорядочить по уровням (этапам) их обработки. Получение матрицы M_nметодом свертки циклов позволяет уменьшить ее размерность, облегчить анализ и синтез структуры решения как отдельных задач η_n системы, так и функционирования всей СОД РВ.

Взаимосвязь между процедурами обработки данных при обслуживании каждой заявки СОД РВ, а также между наборами входных и промежуточных данных удобно представлять с помощью таблицы инциденции [3] обработки множеств запросов Y_n = ||y_rlⁿ||, которая является матрицей вида.

В матрице Y_n каждая строка отображает процедуру обработки, а каждый столбец — использование всеми процедурами при решении η_n задачи рассматриваемого информационного элемента. В строке содержится информация о множестве входных и выходных данных, связанных с анализируемой процедурой. Анализ столбцов позволяет выявить входные и выходные информационные элементы рассматриваемой задачи η_n. Элементы d_l ∈Dⁿ, l = 1,—L—ⁿ являются входными при решении η_n задачи, если d_l столбец матрицы Y_n содержит единственную, отличную от нуля запись y_rlⁿ = +1, r = 1,—R—ⁿ. Если l‑й столбец содержит запись y_rlⁿ = –1, то соответствующий ему элемент d_l ∈Dⁿ, l = 1,—L—ⁿ является выходным. Информационной матрицей смежности C_иⁿ при решении η_n задачи назовем квадратную бинарную матрицу, проиндексированную по обеим осям множествами D₁ⁿ ∪Rⁿ. Матрица C_иⁿимеет четыре подматрицы — Cⁿ, C₁ⁿ, C₂ⁿ, C₃ⁿ с размерами DⁿxDⁿ, RⁿxDⁿ, DⁿxRⁿ и RⁿxRⁿ.

Используя матрицу C_иⁿ, можно определить матрицу M_иⁿ, которая содержит подматрицы M_n, M_n⁽¹⁾, M_n⁽²⁾, M_n⁽³⁾, проиндексированные соответственно DⁿxDⁿ, RⁿxDⁿ, DⁿxRⁿ и RⁿxRⁿ.

Подматрица M_n⁽¹⁾ удовлетворяет соотношение M_n⁽¹⁾ = C₁ⁿx(Cⁿ)^k = C₁ⁿx(Cⁿ)^k+1 ≠ C₁ⁿx(Cⁿ)^k–1, где k — целое положительное число, которое не больше числа Lⁿ элементов при решении η_n задачи, то есть k < Lⁿ–1. Матрица M_n⁽¹⁾содержит единичные элементы в позиции (p_r, d_l), если процедура входит в последовательность, необходимую для получения элемента d_l при решении η_nзадачи. В противном случае при записи в позицию (p_r, d_l) подматрицы M_n⁽¹⁾ она будет равна нулю. Подматрица M_n⁽²⁾ определяется соотношением M_n⁽²⁾ = M_nxC₂ⁿ и содержит единичный элемент в позиции (d_l, p_r), если элемент d_l является входным для последовательности процедур, в состав которых входит процедура p_r. В противном случае элемент (d_l, p_r) равен нулю. Подматрица M_n⁽³⁾ является матрицей достижимости процедур обработки данных при решении η_n задачи и удовлетворяет соотношение:

(C₃ⁿ)^k–1 ≠ (C₃ⁿ)^k = (C₃ⁿ)^k+1 = M_n⁽³⁾.

Единичная запись в позиции (p_r, p_r′) подматрицы M_n⁽³⁾ соответствует наличию направленного пути в ИИГ технологии решения η_n задачи от процедуры p_rк процедуре p_r′.

Построение единого ИИГ осуществляется путем выполнения операции «наложения» графов Gⁿ и заключается в совмещении идентичных уровней каждого графа и идентичных вершин на каждом уровне. В результате формируется ИИГ G⁰, которому соответствует матрица смежности C⁰ = ||C_ll′⁰||,l = 1,—L—, l′ = 1,—L—, полученная путем логического сложения матриц C_иⁿ:

C⁰ = C_и¹ ∨C_и² ∨ … ∨C_иⁿ.

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

В качестве моделей описания и анализа задач обработки данных при создании типовых блочно-модульных СОД также используется аналогичная совокупность графовых и матричных моделей.

При формировании полного ИИГ технологии решения задачи обработки информационных потоков данных и управления ими можно учитывать всю необходимую информацию о взаимосвязях и отношениях между различными элементами отдельных задач.

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

Рис. 1. Схема генетического алгоритма

Основные принципы генетических алгоритмов (ГА) были сформулированы Голландом (Holland) в 1975 году и хорошо описаны во многих работах [4–6]. В общем виде генетический алгоритм может быть представлен в виде схемы, приведенной на рис. 1 [4]. ГА работают с совокупностью особей, каждая из которых представляет возможное решение поставленной задачи СОД РВ.

На первом шаге ГА формируется исходная популяция особей, где каждая особь представляет собой решение задачи, иначе говоря, является кандидатом на решение. Если рассматривать в качестве примера инфокоммуникационную систему, то под особью понимаются информационно-управляющие потоки данных (матрицы C, D, M). Формирование исходной популяции, как правило, происходит с использованием какого-нибудь случайного закона, в ряде случаев исходная популяция может быть также результатом работы другого алгоритма.

Для применения генетических операторов значения этих параметров должны быть представлены в виде двоичной последовательности, то есть двоичной строки, состоящей из нескольких бит. Количество бит при кодировании гена (хромосомы) зависит от требуемой точности решаемой задачи. Оптимальным считается такой выбор, когда выполняется соотношение:

где n — количество бит, используемых для кодирования значения аргумента; x_max и x_min — максимальное и минимальное значения аргумента x целевой функции; Δ — погрешность решения задачи.

Количество особей M в популяции определяется, как правило, эмпирическим путем, желательно из интервала n ≤ M ≤ 2n.

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

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

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

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

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

В качестве критериев останова работы ГА приняты следующие условия:

• Сформировано заданное число поколений.
• Популяция достигла заданного уровня качества. (Например, 75% особей имеют одинаковую генетическую структуру или одинаковое значение функции пригодности.)
• Достигнут некоторый уровень сходимости, при котором улучшение популяции не происходит.

Для решения поставленной задачи можно применить ГА, представленный на рис. 2.

Рис. 2. Схема работы ГА

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

Возвращаясь к задаче работы блочно-модульной СОД РВ, поясним особенности реализации генетического алгоритма в этом случае:

• Индивидуум — вариант решения задачи: набор из 10 хромосом X_j.
• Хромосома X_j — технический или экономический параметр, влияющий на j‑ю структуру: 16‑разрядная запись этого числа.

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

Приведем полное описание работы ГА:

1. Создание структуры решения искомой задачи в виде массива a[i], i = 1, …, n, где n — максимальное число компонентов структуры.
2. Создание показателя эффективности структуры, заполненной конкретными значениями.
3. Задание некоторого массива различных структур C_k, k = 1, …, N, где размерность N больше, чем число компонентов n в структуре. Этот массив можно сгенерировать случайно, задав нули и единицы в каждой структуре.
4. Расчет показателей эффективности J_k для каждой структуры C_k.
5. Естественный отбор структур ИИГ по некоторому правилу выбора наилучших среди заданного массива структур. Пример: можно по правилу вида J₀= M(J_k) определить среднее значение J_k. Если J_k < J₀, то структура остается, иначе умирает. Если разница между J₀ предыдущим и новым меньше какого-то малого числа, то расчет заканчивается.
6. Замена выбывших структур на новые, рожденные от наиболее приспособленных структур с помощью генетических операторов:
   • Мутация — замена в структуре одного из значений случайно выбранного компонента. Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 1, 1, 0, 1, 0).
   • Инверсия — перестановка в структуре некоторой ее части наоборот. Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 0, 1, 0, 1, 0).
   • Кроссинговер — создание структуры, основанной на двух структурах, — при замене одной части первой структуры на ту же область во второй. Пример: из (A, B, C, D, E) и (a, b, c, d, e) получится (A, B, c, d, E).
7. Переход к этапу 4.

Влияние параметров генетического алгоритма на эффективность поиска оптимальной структуры СОД РВ

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

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

Аналогичный подход применяется и при реализации процесса мутации новых особей, однако в этом случае преимущество перед детерминированным подходом не так очевидно в силу традиционно малой вероятности мутации. В основном вероятность мутации составляет 0,001–0,01.