Application of genetic algorithms to optimize solution of filtering and prediction problems in dynamic program testing systems

Full Text

Введение

Генетические алгоритмы представляют собой универсальный инструмент, основанный на представлении естественного процесса эволюции. Применение генетических алгоритмов к математическим моделям было впервые рассмотрено в работах Холланда. В его работах рассматривается применение теории естественного отбора Дарвина для решения ряда прикладных математических задач поиска, распознавания образов и статистического вывода. Согласно его предположению каждой модели, может быть противопоставлено ограниченное число структур $\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}$ может выполняться независимо. Процедуру распараллеливания ГА можно реализовать на этапе скрещивания и мутации, так как отбор родителей особи каждой следующей популяции выбирается в соответствии с весами потомков, которые уже заранее известны. Практические результаты анализа эффективности предложенного алгоритма позволяют прийти к выводу, что незначительно снижение производительности за счет использования в процессе выполнения ГА операций селекции, скрещивания и мутации по сравнению с классическим алгоритмом МЧФ позволяют повысить точность апостериорного распределении и степень согласования выборок в соответствии со свидетельствами, вне зависимости от общего их числа. Такой подход позволяет использовать разработанный алгоритм при решении задач логического вывода в различных динамических вероятностных моделях с неограниченным числом временных состояний. Все это доказывает обоснованность и практическую значимость проведенных исследований.

About the authors

Pavel V. Polukhin

Author for correspondence.
Email: alfa_force@bk.ru

Candidate of Technical Sciences, Lecturer of the Faculty of Applied Mathematics, Informatics and Mechanics

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Figure 1 - Structure of the torn Markov model of three time slices.

Download (98KB)

Indexing metadata

3. Figure 2 - Typical schematic diagram of the MFF-filter with EP

Download (119KB)

Indexing metadata