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

Полный текст

Введение

Генетические алгоритмы представляют собой универсальный инструмент, основанный на представлении естественного процесса эволюции. Применение генетических алгоритмов к математическим моделям было впервые рассмотрено в работах Холланда. В его работах рассматривается применение теории естественного отбора Дарвина для решения ряда прикладных математических задач поиска, распознавания образов и статистического вывода. Согласно его предположению каждой модели, может быть противопоставлено ограниченное число структур $\alpha$, представляющих собой некоторое множество хромосом (комбинация генов), изменение которых производит за счет мутации. В таком случае, общая сложность модели будет определяться общим числом генотипов (структура генов). Генетические алгоритмы с научно-практической точки зрения представляют особый интерес для оптимизации процедур обучения и логического вывода вероятностных моделей. Одним из основных алгоритмов решения данных задач является семейство алгоритмов на основе многочастичного фильтра. Решение задачи нелинейной фильтрации на основе генетических алгоритмов было рассмотрено в исследованиях Морала [1, 2]. Суть предложенного подхода заключается в случайной мутации выборок, формируемых в соответствии с переходными вероятностями марковской цепи. В случае динамических вероятностных моделей данный подход не может быть явно применен, так как выборки, подвергнутые мутации предварительно должны соответствовать вероятностному распределению по всем свидетельствам. В связи с этим возникает необходимость пошаговой фильтрации с последующем применением генетического алгоритма уже к сформированному весовому распределению, полученному в соответствии с распределениями переходов и свидетельств для момента времени $t+k$. Основная особенность предлагаемого подхода заключается в возможности скрещивания выборок, исключительно имеющих общие свидетельства, следовательно, переменные, не имеющие условные связи, будут исключены из генетического алгоритма. В таком случае можно снизить область разброса выборок и повысить степень их согласования со свидетельствами. Для динамических моделей также допустимо использовать свидетельства со всех предыдущих состояний. Следовательно, можно прийти к выводу, что генетические алгоритмы также могут быть использованы в процессе ретроспективного анализа таких моделей, при этом общее число генерируемых выборок для обеспечения требуемой точности может быть сокращено.

Результаты и обсуждение

Вероятностный вывод во временных моделях тестирования

Решение задач вероятностного вывода является одной из основных задач решаемых с помощью вероятностных моделей. Наибольший интерес представляют модели, состоящие из нескольких временных состояний. Среди таких моделей выделяют динамические байесовские (ДБС) сети и скрытые марковские модели (СММ). В исследовании рассмотрим СММ, так как в общем случае ДБС можно представить в виде СММ. СММ является графическим представлением марковского процесса, где каждому срезу соответствует модель перехода $\text{P}\left({\text{X}}_1|{\text{X}}_2\right)$ и модель восприятия $\text{P}\left(E_2|{\text{X}}_2\right)$. Каждому узлу СММ ставится в соответствие таблица условных вероятностей, характеризующая связи как в рамках одного среза, так и нескольких срезов. Типовая структура модели СММ приведена на рис. 1.

Рисунок 1 – Структура срытой марковской модели из трех временных срезов.

Матрица переходов, соответствующая рис. 1, будет иметь следующий вид:

$\begin{array}{l}T=P\left(X_{t+1}\text{|}{X}_t\right)=\left(\begin{array}{cccc}{T}_{11}& T_{12}& \cdots & T_{1k}\\ T_{21}& T_{22}& \cdots & T_{2k}\\ ⋮& ⋮& \ddots & ⋮\\ T_{n1}& T_{n2}& \cdots & T_{nk}\end{array}\right),\\ T_{ij}=P(X_{t+1}=j|X_t=i).\end{array}$ (1)

Тогда полное совместное распределение, соответствующее СММ можно записать в следующем виде [3, 4]:

$\begin{array}{l}P\left(X,Y\right)=P\left(X_0\right)\underset{t=1}{\overset{k}{}}P\left(X_{t+1}\text{|}{X}_t\right)\times \\ \times \underset{j=1}{\overset{k}{}}P\left(X_{j+1}\text{|}{X}_{j+1}\right)=\\ =P\left(X_0\right)\underset{t=1}{\overset{k}{}}{T}_{ij}\underset{j=1}{\overset{k}{}}P\left(X_{j+1}\text{|}{X}_{j+1}\right),\end{array}$ (2)

где $P\left(X_0\right)$ – начальное распределение вероятностей, соответствующее моменту $\text{t}=0$.

Определив вероятностную семантику СММ, перейдем к рассмотрению алгоритмов вероятностного вывода. Среди различных подходов к решению задачи вероятностного вывода наибольший интересе представляет многочастичный фильтры (МЧФ). Сущность МЧФ заключается в формировании множества независимых друг от друга выборок с соответствующими им весами $\text{W}\left(\text{X},\text{Y},\text{E}\right)$. Отметим, что $\text{E}\subset Y$ – свидетельства, поступающие в виде непрерывного потока плоть до текущего состояния. В данном случае вес будет определять степень согласованности выборок $S$. В таком случае, условие согласования выборок $S$ со свидетельством $\text{E}$ запишем в следующем виде [4, 6]:

$\begin{array}{l}P\left(X_{t+1}\text{|}{E}_{1:t+1}\right)=\underset{Y}{}N\left(X_{t+1},Y_{1:t},E_{1:t}\right)\times W\approx \\ \approx \underset{Y}{}{S}_{ws}\left(X_{t+1},Y_{1:t},E_{1:t}\right)W=\\ =\underset{Y}{}P\left(X_{t+1},Y_{1:t},E_{1:t}\right)=P\left(X_{t+1}\text{|}{E}_{1:t+1}\right),\\ W=W\left(X_{t+1},Y_{1:t},E_{1:t}\right) ,\end{array}$ (3)

где $N\left(X_{t+1},Y_{1:t},E_{1:t}\right)$ – число выборок, достигающих состояния t+1.

Существует несколько основных подходов к решению задач логического вывода на основе МЧФ. Наибольший интересе представляют МЧФ на основе выборки по значимости (ВЗ) и взвешивания на основе правдоподобия (ВП). В данном исследовании рассмотрим МЧФ с взвешиванием на основе правдоподобия. Данный алгоритм позволяет изначально производить генерацию только из области выборок $S\left(X_1,X_2,\dots ,X_n\right)$, которые в наибольшей степени согласуются со свидетельствами $\text{E}=\left(e_1,e_2,\dots ,e_n\right)$. Такое условие достигается за счет того, что в процессе выполнения вероятностного вывода на основе ВП происходит определение и фиксирование переменных свидетельств $\text{E}$, а формирование выборок осуществляется исключительно для всех оставшихся переменных $Z=X\cup Y$, где $X$ переменные запроса и $Y$ переменные состояния. В процессе выполнения алгоритма производится развертывания динамической модели и происходит формирования выборок $S_{ws}$, которые взвешиваются с учетом их правдоподобия на основе анализа полученных весов $W\left(X_{t+1},Y_{1:t},E_{1:t}\right)$. Веса выборок рассчитываются на основе переходных вероятностей $P\left(X_{t+1}\text{|}{X}_t\right)$ и условного распределения по всем свидетельствам $P\left(E_{t+1}\text{|}{X}_{t+1}\right)$. Типовая схема фильтра МЧФ с ВП приведена на рис. 2.

Рисунок 2 – Типовая схема МЧФ-фильтра с ВП

На рис. 2 $\text{W}\left({\text{X}}_{\text{t}+1}\right|{\text{E}}_{1:\text{t}+1})$ – веса выборок $\text{S}$, $\text{P}\left({\text{E}}_{\text{t}+1}{\text{|X}}_{\text{t}+1}\right)$ и $\text{P}\left(X_{\text{t}+1}{\text{|X}}_{\text{t}}\right)$ модели перехода и восприятия. Рассматривая метод вероятностной оценки выборок на основе ВП, отметим главное его преимущество по сравнению с ВЗ. ВП исключает формирование приближенного распределения по значимости $Q\left(X_t\right|X_{0:t-1},E_{1:t})$. Следовательно, нет необходимости на каждом этапе верификации апостериорного распределения $\text{P}\left({\text{X}}_{\text{t}+1}{\text{|E}}_{\text{t}+1}\right)$ производить вычисление дистанции Кульбака-Лейблера (КЛ) для оценки степени соответствия $Q\left(X_{t+1}\right|E_{t+1})$ и $\text{P}\left({\text{X}}_{\text{t}+1}{\text{|E}}_{\text{t}+1}\right)$. Вместо этого в ВП каждая выборка формируется в соответствии с весом $X_{t+1}^i~W\left(X_{t+1}\right|X_{1:t},E_{1:t+1})$, при этом выборки с наименьшим весом исключаются из апостериорного распределения. Следовательно, согласно алгоритму ВП степень правдоподобия выборки будет определяться в соответствии с ее весом $W\left(X_{t+1}\right|X_{1:t},E_{1:t+1})$. С учетом того, что распределение по всем выборкам прямо пропорционально общему числу выборок , запишем распределение для выборок в соответствии с распределением $\text{P}\left({\text{X}}_{\text{t}}\right|{\text{E}}_{1:\text{t}})$:

$S\left(X_t\right|E_{1:t})=N\times P(X_t\left|E_{1:t}\right),N\to \infty .$ (4)

Используя переходное распределение вероятностей $\text{P}\left({\text{X}}_{\text{t}+1}\text{|}{X}_{\text{t}}\right)$ для модели СММ, приведенной на рисунке 1, можно определить условное распределение по всем выборкам, достигшим состояния $\text{t}+1$ у четом распределения (4). Тогда получим следующую сумму по всем переменных ${\text{X}}_{\text{t}}$ [5, 6]:

$S\left(X_{t+1}\right|E_{1:t})=\underset{X_t}{}P\left(X_{t+1}\text{|}{X}_t\right)S(X_t\left|E_{1:t}\right).$ (5)

Далее используем метод ВП для определения весов для каждой из выборок в соответствии со свидетельствами ${\text{E}}_{1:\text{t}}$:

$W\left(X_{t+1}\right|E_{1:t+1})=P\left(E_{t+1}\text{|}{X}_{t+1}\right)S(X_{t+1}\left|E_{1:t}\right).$ (6)

Для повышения доли согласованных выборок используется процедура повторной генерации выборок в соответствии с распределением $\text{W}\left({\text{X}}_{\text{t}+1}\right|{\text{E}}_{1:\text{t}+1})$. Каждая следующая выборка формируется случайным образом. Вероятность того, что будет выбрана конкретная выборка будет пропорциональна весу. Тогда, с учетом этого, распределение по всем выборкам можно записать в следующей окончательном виде [7, 8]:

$\begin{array}{l}S\left(X_{t+1}\text{|}{E}_{1:t+1}\right)=N\times W\left(X_{t+1}\text{|}{E}_{1:t+1}\right)=\\ =N\times P\left(X_{t+1}\text{|}{E}_{1:t+1}\right).\end{array}$ (7)

Алгоритм МЧФ с ВП является оптимальным алгоритмом вероятностного вывода, обладает высокой степенью параллелизма в связи с тем, что генерация выборок может производиться независимо. Однако на ряду с преимуществами, алгоритм обладает недостатком, связанным с тем, что на этапе повторной генерации формирования очередной выборки формируется случайно, тем самым не учитывается предыстория формирования выборок. Для решения данной проблемы в рамках алгоритма МЧФ предлагается использование генетических алгоритмов (ГА). Применительно МЧФ алгоритм ГА может быть использован на этапе повторного формирования выборок с целью снижения разброса выборок относительно истинного значения и как следствие повышения точности определения апостериорного распределения $P\left({\text{X}}_{\text{t}+1}{\text{|E}}_{\text{t}+1}\right)$. Рассмотрим детально структуру генетического алгоритма, а также возможность его адаптации для решения задач вероятностного вывода в СММ на основе фильтра МЧФ. Основными этапами генетического алгоритма являются: инициализация, отбор, размножение и мутации. На этапе инициализации выбираем множество выборок, веса которых имеют наибольшие значения. Тогда на этапе отбора доля потомков выборок с высоким значением весов будет преобладающей и будет вытеснять все другие выборки. Тогда каждая следующая популяция будет формироваться путем изменения генотипа предшествующей выборки за счет выполнения процедуры мутации. Введем обобщенную формулировку ГА, предложенную Бэком [9, 10] в соответствии с абстрактной моделью Холланда [11]:

$G\left(s\right)=<D_0,n,n_k,\delta ,\rho ,\Omega ,f,t>,$ (8)

где $D_0=\{d_1,d_2,\dots ,d_n\}\in I^n,I^n={\left\{\mathrm{0,1}\right\}}^{n_k}$ – начальная популяция частиц, полученная на этапе ВП, $I^n$ – множество допустимых значений для ${\text{X}}_{\text{t}+1}$, $n$– общее число популяция частиц, $n_k$ – размер популяции из которой производим отбор выборок, $\delta$ – селекция $I^{n_k}\to I^n$, $I^{n_k}$ – допустимые значения ${\text{X}}_{\text{t}+1}$ для популяции $n_k$, $\rho$ – скрещивание $I^{n_k}\times I^{n_{k+1}}\to I^n$, $\text{Ω}$ – мутация $I^n\to I^n$, $f$ – функция соответствия $I^n\to ℝ$, $t$ – условие останова $I^n\to \left\{\mathrm{0,1}\right\}$.

Начальная популяция $D_0$ формируется в соответствии с $\text{P}\left({\text{E}}_{\text{t}+1}{\text{|X}}_{\text{t}+1}\right)$ и $\text{P}\left(X_{\text{t}+1}{\text{|X}}_{\text{t}}\right)$, процедура оценки весов для каждой ${\text{S}}_0^i$ выполняется в соответствии с алгоритмом ВП. В соответствии с формулой (8) процедура селекции может быть выполнена за счет выборки элементов из множества $D_{t+1}=\{d_1,d_2,\dots ,d_n\}$ в соответствии с равномерным распределением $P\left(s\right):I\to \left\{\mathrm{0,1}\right\}$. Отметим, что в качестве функции соответствия будем использовать весовое распределение $\omega =\text{W}\left({\text{X}}_{\text{t}+1}{\text{|E}}_{1:\text{t}+1}\right)$ соответствующее множеству выборок $D_{t+1}$. В таком случае, наилучший генотип, соответствующей выборке $S_{t+1}$ можно переделить в виде задача поиска экстремума $\omega$:

${\widehat{D}}_{t+1}^i=argmaxW\left(X_{t+1}\text{|}{E}_{1:t+1}\right).$ (9)

Распределение $\text{P}\left(D_{\text{t}+1}^{\text{i}}\right)$ в общем виде, данное распределение можно выразить через соответствующую функцию соответствия  $f\left(D_{\text{t}+1}^{\text{i}}\right)=\omega \left(D_{\text{t}+1}^{\text{i}}\right)$. Имеем

$P\left(D_{t+1}^i\right)=\frac{\omega \left(D\right)}{{\displaystyle {\sum }_{j=1}^n\omega \left(D_{t+1}^j\right)}}.$ (10)

Селекция, представленная выражением (10), предложена Холландом и является адаптивно-пропорциональной (АП). АП также называют методом рулетки. Данный подход обладает существенным недостатком, связанным с тем, что в результате выполнения АП-селекции можно получить отдельные выборки с высоким показателем функции соответствия $\omega \left(d\right)$. В таком случае, процедура селекции может быть завершена, так и не достигнув своего оптимального состояния. В связи с этим, в работе будем рассматривать метод Бейкера, позволяющий использовать статистическое распределения для задания $P\left(d_i\right)$. Такой подход наиболее оптимальный при решении вероятностных задач на основе МЧФ. Сформулируем селекцию Бейкера (линейное ранжирование) [12] в виде следующего выражения:

$P\left(s_i\right)=\frac{1}{N}\left(a-\left(a-b\right)\frac{i-1}{N-1}\right)\mathrm{,1}\le a\le \mathrm{2,}b=2-a,$ (11)

где $\text{i}$ – порядковый номер особи в популяции частиц, $\text{N}$ – общий размер популяция выборки, задаваемый на этапе инициализации алгоритма.

Отметим, что параметр $a$ выбирается случайным образом в соответствии с равномерным распределением $\text{U}\left(\mathrm{1,2}\right)$. При отборе методом линейного ранжирования (ЛР) производим упорядочивание популяции выборок в соответствии с их функцией соответствия, в этом случае данная функция будет эквивалентна весовому распределению $\omega$, соответствующему каждой популяции из выборки $D$. В таком случае получаем, что распределение $\text{P}\left(d_{\text{i}}\right)$ будет зависеть только от порядкового номера особи в популяции. Совокупность частиц и соответствующие им веса, упорядоченным согласно весам $\omega$ запишем в виде следующего множества:

$D=\left\{\left\{D_i^1,{\omega }_i^1\right\},\dots ,\left\{D_i^N,{\omega }_i^N\right\} \right\},i=\mathrm{1,2,}\dots ,n.$ (12)

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

$\begin{array}{l}{H}_{S_{t+1}}=\left(\xi =B|{\xi }_{i_1}=h_{i_1},{\xi }_{i_2}=h_{i_2},\dots ,{\xi }_{i_n}=h_{i_n}\right),\\ i_1<i_2<\dots <i_n,\end{array}$ (13) 

где $\text{B}$ – множество генотипов, характерное для популяции частиц ${\text{S}}_{\text{t}+1}^{\text{i}}$, $\xi$ – генотип.

Учитывая тот факт, что один и тот же генотип может быть характерен одновременно для нескольких особей (частиц), можно определить функция приспособленности популяции частиц $D_{\text{t}+1}$ с учетом схемы ${\text{H}}_{{\text{S}}_{\text{t}+1}}$. Получим [13, 18]:

$f\left(D_{t+1},{\Omega }_{t+1}\right)=\frac{{\displaystyle {\sum }_{{\xi }_{t+1}\in H}f\left({\xi }_{t+1}^i\right)}}{N\left(H_{S_{t+1}},{\Omega }_{t+1}\right)},$ (14)

где ${\text{Ω}}_{\text{t}+1}$– поколений частиц, соответствующих моменту t+1, $N\left(H_{D_{t+1}},{\Omega }_{t+1}\right)$ – общее число частиц с генотипом $\text{ξ}$ в поколении ${\text{Ω}}_{\text{t}+1}$.

В соответствии с выражением (14) вероятность выживания отдельной популяции частиц будет удовлетворять следующему неравенству:

$\begin{array}{l}{P}_l\left(D_{t+1},{\Omega }_{t+1}\right)\ge 1-\left(1-P_l\left(D_t,{\Omega }_t\right)\right)\times \\ \times \left(\frac{1-\delta \left(H_{D_{t+1}}\right)}{l-1}\right)\left(\frac{\delta \left(H_{D_{t+1}}\right)}{l-1}\right),\end{array}$ (15)

где $\text{δ}\left(\text{H}\right)$ – длина схемы ${\text{H}}_{D_{\text{t}+1}}$, $\text{l}$ – число элементов выборки (частиц).

Для анализа разнообразия популяции выборок можно определить вероятность изменения определенного гена в зависимости от параметров ГА $P\left(\text{N}\left({\text{H}}_{D_{\text{t}+1}},{\Omega }_{\text{t}+1}\right)\right)$ в соответствии с (8). Введем вероятность $\text{P}\left(D_{t+1}^i,{\text{H}}_{{\text{S}}_{\text{t}+1}} \right)$, определяющую принадлежность выборки $D_{t+1}^i$ схеме ${\text{H}}_{S_{\text{t}+1}}$. Запишем данную вероятность с учетом выражения (14)

$\begin{array}{l}P\left(D_{t+1}^i,H_{D_{t+1}} \right)=\frac{N\left(H_{D_{t+1}},{\Omega }_{t+1}\right)}{N}\times \\ \times \frac{f\left(H_{D_{t+1}},{\Omega }_{t+1}\right)}{N\left(B,{\Omega }_{t+1}\right)}=\\ =\frac{{\displaystyle {\sum }_{{\xi }_{t+1}\in H_{D_{t+1}}}f\left({\xi }_{t+1}^{it}\right)}}{{\displaystyle {\sum }_{j=1}^{N}f\left({\xi }_{t+1}^{jt}\right)}},\end{array}$ (16)

Тогда выражение для расчета $P\left(\text{N}\left({\text{H}}_{{\text{S}}_{\text{t}+1}},{\Omega }_{\text{t}+1}\right)\right)$ будет иметь следующий вид [15, 16]:

$\begin{array}{l}P\left(N\left(H_{D_{t+1}},{\Omega }_{t+1}\right)=N\right)=\lambda {\left(1-2\theta \right)}^N,\\ P\left(N\left(H_{D_{t+1}},{\Omega }_{t+1}\right)=0\right)={\left(1-\lambda \left(1-2\theta \right)\right)}^N,\\ \lambda =\theta +\left(\frac{1-\delta \left(H_{D_{t+1}}\right)}{l-1}\right),\end{array}$ (17).

где $\theta =P\left(D_{t+1}^i,H_{D_{t+1}} \right)$ – вероятность мутации индивида $S_{t+1}^i$ в соответствии со схемой ${\text{H}}_{{\text{S}}_{\text{t}+1}}$.

В соответствии с выражением (12) можно определить две группы, соответствующие области низких и высоких весов частиц $S_{\text{t}+1}$. Для этого введем критерий разделения. Данный критерий можно получить из нормализации весов $\omega$. Запишем данный критерий в следующем виде:

$N_{norm}=\frac{1}{{\displaystyle {\sum }_{j=1}^N{\left({\omega }_j^i\right)}^2}}$ (18)

Тогда выборку $S_{t+1}$, соответствующую моменты времени $t+1$ можно записать в виде совокупности двух групп, соответствующих области высоких и низких весов, разделяемых в соответствии с ${\text{N}}_{\text{norm}}$. Получим [17, 18]:

$\begin{array}{l}{H}_{t+1}=\left\{\begin{array}{c}{H}_{t+1}^{\text{'}}=\left\{\left\{{\xi }_{i_1},{\omega }_{i_1}\right\},\dots ,\left\{{\xi }_{i_k},{\omega }_{i_k}\right\}\right\} \\ H_{t+1}^{\text{'}\text{'}}=\left\{\left\{{\xi }_{i_{k+1}},{\omega }_{i_{k+1}}\right\},\dots ,\left\{{\xi }_{i_N},{\omega }_{i_N}\right\}\right\}\end{array}\right.,\\ k\le N_{norm}<k+\mathrm{1,}\end{array}$(19)

где ${\text{H}}_{\text{t}+1}^{\text{'}}$ и ${\text{H}}_{\text{t}+1}^{\text{''}}$ – схемы выборки, соответствующие области наибольших и наименьшим весов выборок $S_{t+1}$.

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

$\begin{array}{l}{\widehat{D}}_{t+1}^{i,j}=\left\{\begin{array}{c}{\widehat{D}}_{t+1}^i=\alpha D_t^i+\left(1-\beta \right)D_t^j\\ {\widehat{D}}_{t+1}^j=\beta D_t^i+\left(1-\alpha \right)D_t^i\end{array}\right.,\\ \alpha =\frac{W\left(D_t^i\right)}{W\left(D_t^i\right)+W\left(D_t^j\right)},\\ \beta =\frac{W\left(D_t^j\right)}{W\left(D_t^i\right)+W\left(D_t^j\right)},\end{array}$ (20)

где ${\widehat{D}}_{\text{t}+1}^{\text{i},\text{j}}$ – новая популяция частиц, образованная путем скрещивания родителей $D_{\text{t}}^{\text{i}}$ и $D_{\text{t}+1}^{\text{i}}$ из выборки ${\text{S}}_{\text{t}}$, $\text{α},\text{β}$ – весовые коэффициенты, устанавливающие соответствие между весами родителей $\text{W}\left(D_{\text{t}}^{\text{i}}\right)$ и $\text{W}\left(D_{\text{t}}^j\right)$.

Процедура мутации может быть реализована на основе распределения Гаусса. Каждая мутирующий представитель выборки $D_{t+1}=\left(d_{t+1}^1,d_{t+1}^2,\dots ,d_{t+1}^n\right)$ будет формироваться в соответствии со следующим выражением:

$\begin{array}{l}{d}_{t+1}^{\text{'}i}=M\left(d_t^i\right),\\ M\left(d_t^i\right)=d_t^i+{\rm N}\left(\mathrm{0,}{\sigma }_i\right),\end{array}$ (21)

где $\text{N}\left(\mathrm{0,}{\text{σ}}_{\text{i}}\right)$ – гауссовское распределение, $d_{t+1}^i$ – популяция выборки, полученная на шаге $t+1$, на основе которой производится мутация, $M\left(d_t^i\right)$ – процедура мутации для популяции $d_t^i$.

Приведем укрупненную схему алгоритма фильтрации частиц, используемого в исследовании:

Шаг 1. На начальном срезе из распределения $P\left(X_0\right)$ одновременно генерируется $N$ выборок.

Шаг 2. Вводится множества свидетельств для всех срезов сети $E_1,E_2\mathrm{,...,}{E}_T$.

Шаг 3. Выполняется перехода от временного среза t к временному срезу $t+1$. Через модель перехода $P\left(\left.X_{t+1}\right|X_t\right)$ осуществляется обновление множества выборок: $N\left(\left.X_{t+1}\right|E_{1:t}\right)=\sum _{X_t}P\left(\left.X_{t+1}\right|X_t\right)N\left(\left.X_t\right|E_{1:t}\right)$, $N\left(\left.X_t\right|E_{1:t}\right)$ – количество выборок для состояния $X_t$ после получения свидетельств $E_{1:t}$ выборки взвешиваются с учетом правдоподобия по отношению к новым свидетельствам ${Е}_{t+1}$, им присваивается вес $P\left(\left.{Е}_{t+1}\right|{\text{X}}_{t+1}\right)$.

Шаг 4. Вычисляется суммарный вес выборок в состоянии ${\text{X}}_{t+1}$ после получения свидетельств ${Е}_{t+1}$: $w\left(\left.X_{t+1}\right|E_{1:t+1}\right)=P\left(\left.E_{t+1}\right|X_{t+1}\right)P\left(\left.X_{t+1}\right|E_{1:t}\right)$ отбрасываются выборки с малым весом формируются новые $\text{}N$ выборок.

Шаг 5. Формируется новая популяция, состоявшая из $\text{}N$ выборок с использование генетического алгоритма, каждая выборка тиражируется пропорционально весу $w\left(\left.X_{t+1}\right|E_{1:t+1}\right)$. Каждая выборка образуется путем скрещивания родителей $D_{\text{t+1}}^{\text{i}}$ и $D_{\text{t}+1}^{\text{i+1}}$ из выборки ${\text{S}}_{\text{t+1}}$, полученной на предыдущем шаге. Процедура мутации выполняется в соответствии с выражением (21).

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

Оптимизация фильтра МЧФ на основе ГА является важным алгоритмом оптимизации стохастических процедур вероятностного вывода. Для сравнения алгоритмов МЧФ и МЧФ с ГА проведения эксперимента разработаны распределенные алгоритмы, использование которых предусмотрено в рамках параллельной платформы Spark [19], развернутой в облачной среде Yandex Cloud из 6 узлов со следующей аппаратной конфигурацией: 2 процессора Intel Xeon-Platinum 2.5 ГГц 16 ядер, 128 ГБ ОЗУ, жесткий диск 10 ТБ, оптический канал связи 25 Гб/с. По результатам исследования нами решена задача повышения качества формирования выборок на основе МЧФ фильтра. Ее решение заключается в достижении требуемой точности алгоритма за счет применения ГА, что в свою очередь позволяет повысить долю выборок, согласованных со свидетельствами. Применение генетических алгоритмов доказывает правильность выбора исследования, а также состоятельность предложенного подхода.

В рамках практической проверки предложенного метода оптимизации МЧФ на основе ГА произведено его сравнение с классическим МЧФ за счет оценки согласованности выборок на этапе повторной генерации выборок в процессе вероятностного вывода СММ процесса тестирования веб-приложений (441 узел, 195 ребер, 72079 параметров). Каждый узел СММ отвечает зав формирования определенного набора тестовых данных для поиска программных ошибок, связанных с аутентификацией пользователей за счет использования SQL-инъекции. Данная ошибка представляет собой набор SQL-команд с разделителями, позволяющая обходит фильтры безопасности веб-приложений и реализующая возможность получения пользовательские данных, используемые для аутентификации и авторизации. На сегодняшний день можно выделить следующие типы SQL-инъекций, которые могут быть использованы для получения пользовательских данных из веб-приложений, взаимодействующих с системами управления базами данных: Union (Объединенная), Boolean Blind (Логическая.), Time Blind (Временная), Error Blind (На основе ошибок), Stacked Queries (Разделенная) и Out of Band (Внешняя). В таблице 1 приведем основные показатели согласованности ${\psi }_{S_{t+1}}$ выборок $S_{t+1}$ и свидетельств $E_{t+1}$ в процессе тестирования веб-приложений на предмет наличия ошибок типа SQLинъекции в зависимости от общего числа свидетельств во всех временных срезах $N_e$ для данной сети с общим объемом выборок ${{\rm N}}_s=1000000$. Отметим, что второй и последующие срезы СММ характеризуются применением межсетевого экрана ModSecurity для блокирования типичных ошибок и оптимизацию формирования выборок для выявления аномальных ошибок.

Таблица 1 – Сравнение степени согласованности выборок

Из таблицы 1 получаем важный практический результат, заключающийся в том, что при использовании алгоритма ГА совместно с МЧФ наблюдаем фиксированную степень согласованности выборок вне зависимости от числа переменных свидетельств $N_e$. Следовательно каждая результирующая популяция, полученная по итогам выполнения алгоритма ГА, будет иметь наибольшее значение функции приспособленности $\omega$, что ведет к повышению точности апостериорного распределения вероятностей $P\left({\text{X}}_{\text{t}+1}{\text{|E}}_{\text{t}+1}\right)$. Другая особенность заключается в том, что при использовании ГА можно ограничить общее число первоначально формируемых выборок , при этом можно повысить число шагов мутаций на этапе повторного взвешивания. Такой подход позволяет настроить точность алгоритма за минимальное число шагов алгоритма МЧФ. Отметим, что применение алгоритма ГА без МЧФ к СММ не имеет смысла, так как в процессе выполнения генетического алгоритма нет необходимой информации относительно свидетельств, а также вероятностных связей между тиражируемыми между срезами переменными. С помощью ГА можно оптимизировать существующую выборку, полученную по результатам выполнения МЧФ-фильтрации. Следовательно, для повышения эффективности МЧФ можно использовать различные подходы к его распараллеливанию, в таком случае формирование выборок $S_{t+1}$будет выполняться независимо друг от друга. В таблице 2 приведем сравнительные характеристики двух программных реализаций алгоритмов МЧФ и МЧФ с ГА.

Таблица 2 – Сравнение производительности программных реализаций алгоритмов

Из анализа таблицы 2 следует, что применение ГА в незначительной степени сказывается на производительности алгоритма. Однако при использовании МЧФ с ГА количество выборок необходимых для достижения требуемого уровня согласованности ${\psi }_{S_{t+1}}$ может быть существенно сокращено за счет повышения доли популяций, согласованных со свидетельствами ${\text{E}}_{\text{t}+1}$.

Заключение и выводы

Решение задач оптимизации, существующих алгоритмов вероятностного вывода является актуальным направлением исследования. В первую очередь это связано с повышением сложности вероятностных моделей, повышением числа скрытых переменных, а также роста потока свидетельств на каждом из временных срезов. В работе рассмотрено применение предложенных подходов к скрытым марковским моделям, однако данные алгоритмы могут быть адаптированы для реализации процедуры логического вывода, как в статических, так и динамических вероятностных моделях. Использование ГА в процессе МЧФ-фильтрации позволяет решить задачу качества формирования выборок, взамен использования случайной выборки в процессе повторной генерации используется генетический алгоритмы. Такой подход позволяет повысить точность апостериорного распределения с условий роста переменных-свидетельств ${\text{E}}_{\text{t}+1}$, а также в полной мере использовать алгоритм взвешивая с учетом правдоподобия для формирования весовых распределений для первичной популяции выборок $D_0=\left(d_1,d_2,\dots ,d_n\right)$. Применение модели схем Холланда позволяет разграничить области выборок с разными генотипами в соответствии с распределением $\text{W}\left({\text{X}}_{\text{t}+1}{\text{|E}}_{1:\text{t}+1}\right)$. Это достигается за счет того, что в рамках ГА весовое распределение выбирается в качестве функции соответствия, устанавливающей соответствия весов и каждой популяции частиц, входящей в состав выборки. Отметим, что предложенный алгоритм обладает схожей с классическим МЧФ производительности, однако позволят повысить область согласования выборок в соответствии с потоком свидетельств ${\text{E}}_{1:\text{t}+\text{k}}=\left(e_1,e_2,\dots ,e_n\right)$, поступающих вплоть до момента времени $\text{t}+\text{k}$. Разработанный алгоритм является достаточно хорошо масштабируемым и его можно распараллелить. В этом случае процедура формирования выборок $S_{t+1}$ может выполняться независимо. Процедуру распараллеливания ГА можно реализовать на этапе скрещивания и мутации, так как отбор родителей особи каждой следующей популяции выбирается в соответствии с весами потомков, которые уже заранее известны. Практические результаты анализа эффективности предложенного алгоритма позволяют прийти к выводу, что незначительно снижение производительности за счет использования в процессе выполнения ГА операций селекции, скрещивания и мутации по сравнению с классическим алгоритмом МЧФ позволяют повысить точность апостериорного распределении и степень согласования выборок в соответствии со свидетельствами, вне зависимости от общего их числа. Такой подход позволяет использовать разработанный алгоритм при решении задач логического вывода в различных динамических вероятностных моделях с неограниченным числом временных состояний. Все это доказывает обоснованность и практическую значимость проведенных исследований.

Об авторах

Павел Валерьевич Полухин

Автор, ответственный за переписку.
Email: alfa_force@bk.ru

кандидат технических наук, преподаватель факультета прикладной математики, информатики и механики

Список литературы

Дополнительные файлы

Доп. файлы

Действие

1. JATS XML

Скачать

2. Рисунок 1 – Структура срытой марковской модели из трех временных срезов.

Скачать (98KB)

Метаданные

3. Рисунок 2 – Типовая схема МЧФ-фильтра с ВП

Скачать (119KB)

Метаданные