Разработка методов совместного применения генетического и автоматного программирования

Скачать 0.78 Mb.

Название	Разработка методов совместного применения генетического и автоматного программирования
страница	9/12
Дата публикации	30.08.2013
Размер	0.78 Mb.
Тип	Задача

100-bal.ru > Информатика > Задача

1 ... 4 5 6 7 8 9 10 11 12

3.2.Описание предлагаемого метода

Исходными данными для построения конечного автомата управления системой со сложным поведением являются:

список событий;
список входных переменных;
список выходных воздействий;
набор тестов Tests, каждый из которых содержит последовательность Input[i] событий, поступающих на вход конечному автомату, и соответствующую ей эталонную последовательность Answer[i] выходных воздействий.

Отметим, что для таких тестов справедливо свойство, которое можно сформулировать следующим образом – «префиксы тестов являются тестами» – если из входной последовательности событий удалить часть событий, находящихся в ее конце, то результат обработки автоматом этой последовательности будет префиксом исходной выходной последовательности. Поэтому естественно в набор тестов включать все префиксы теста.

3.2.1.Представление конечного автомата в виде хромосомы генетического алгоритма

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

Таким образом, в особи кодируется только «скелет» управляющего конечного автомата, а конкретные выходные воздействия, вырабатываемые на переходах, определяются с помощью алгоритма расстановки пометок, который аналогичен предложенному в работе [53].

Выбор представления графа переходов автомата с помощью списков ребер (в отличие от работы [52], в которой применялись полные таблицы переходов) обоснован тем, что, как правило, в автоматах управления системами со сложным поведением не в каждом состоянии определена реакция на каждое событие.

3.2.1.1.Обработка входных переменных

Отметим, что в общем случае функция переходов и функция действий зависят не только от события, поступившего на вход автомату, но и от значений входных переменных, которые, как правило, имеют логический тип. При построении автомата вручную, например, с использованием инструментального средства UniMod [5] переходы обычно помечаются не только событиями, но и так называемыми «охранными условиями» (guard conditions) – логическими формулами, которые задают ограничения на значения входных переменных.

3.2.1.2.Алгоритм расстановки пометок

Идея алгоритма расстановки пометок состоит в том, что генетическим алгоритмом строится только «скелет» конечного автомата, а пометки на переходах – вырабатываемые на них выходные воздействия – расставляются на основе тестов. При этом расстановка пометок происходит таким образом, чтобы получившийся в результате автомат как можно лучше «соответствовал» тестам.

В работе [53] аналогичный принцип использовался при построении конечных автоматов для распознавания регулярных языков. Главное отличие состоит в том, что в этой работе расставлялись пометки на состояниях – на основе тестов определялось, будет состояние допускающим или нет.

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

Например, пусть входной последовательности событий A, T, T, M, H, T, T соответствует выходная последовательность z5, z5, z4, z3, z5, z5, и при обработке входной последовательности выполняются следующие переходы: 1 → 2 → 2 → 2 → 3 → 4 → 2 → 2. Пусть при этом на первом из переходов не должно выполняться ни одно выходное воздействие, а на каждом из остальных – должно выполняться одно (Рис. 24.).

Некоторые переходы «скелета» автомата

На Рис. 24. для каждого из переходов кроме события, при возникновении которого он выполняется, указано число выходных воздействий, которые ему соответствуют.

Тогда на основании этого теста можно сделать вывод о том, что на переходе по событию T из второго состояния в себя должно вырабатываться выходное воздействие z5, на переходе по событию M из второго состояния в третье должно вырабатываться выходное воздействие z4, на переходе по событию H из третьего состояния в четверное должно вырабатываться z5, а на переходе по событию T из четвертого состояния во второе – z3 (Рис. 25.).

Помеченные на основании теста переходы автомата

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

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

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

Этот же принцип можно распространить на случай, когда на переходе должно вырабатываться более одного выходного воздействия. Для каждого перехода T и каждой последовательности выходных воздействий zs вычисляется величина C[T][zs] – число раз, когда при обработке входной последовательности, соответствующей одному из тестов, на переходе T должны быть выработаны выходные воздействия, образующую последовательность zs. Далее, каждый переход помечается той последовательностью zs₀, для которой величина C[T][zs₀] максимальна.

3.2.1.3.Операция мутации

При выполнении операции мутации с заданной вероятностью (по умолчанию, она равна 0.05) выполняется каждое из действий:

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

При изменении начального состояния оно заменяется на выбранное случайным образом. При изменении описания перехода с равной вероятностью выполняется одно из следующих действий:

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

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

3.2.1.4.Операция удаления дублирующихся переходов

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

3.2.1.5.Операция скрещивания

Скрещивание описаний автоматов производится следующим образом. Обозначим как P1 и P2 «родительские» особи, а как S1 и S2 – особи-«потомки». Для начальных состояний S1.is и S2.is автоматов S1 и S2 будет верно одно из двух соотношений:

S1.is = P1.is и S2.is = P2.is;
S1.is = P2.is и S2.is = P1.is.

Опишем, как устроены переходы автоматов S1 и S2. Скрещивание описаний автоматов производится отдельно для каждого состояния. Обозначим список переходов из состояния номер i автомата P1 как P1.T[i], а список переходов из состояния номер i автомата P2 как P2.T[i]. Для выполнения «скрещивания переходов» с равной вероятностью может быть выбран один из двух методов.

При использовании традиционного метода скрещивания списки переходов S1.T[i] и S2.T[i] строятся следующим образом:

Строится общий список переходов, в который помещаются переходы, входящие как в P1.T[i], так и в P2.T[i].
К полученному списку применяется случайная перестановка.
Далее возможны два равновероятных варианта:
- либо в S1.T[i] помещаются первые |P1.T[i]| переходов из полученного списка, а в S2.T[i] – оставшиеся переходы;
- либо в S1.T[i] помещаются первые |P2.T[i]| переходов из полученного списка, а в S2.T[i] – оставшиеся переходы.

При использовании метода скрещивания с учетом тестов списки переходов S1.T[i] и S2.T[i] строятся следующим образом:

В автоматах P1 и P2 помечаются те переходы, которые выполняются при обработке 10% тестов, для которых нормированное редакционное расстояние между «правильным ответом» Answer и последовательностью Output выходных воздействий, генерируемой автоматом, минимально.
Помеченные переходы копируются в S1.T[i] и S2.T[i] напрямую.
Строится общий список переходов, в который помещаются непомеченные переходы, входящие как в P1.T[i], так и в P2.T[i].
К полученному списку L применяется случайная перестановка.
Список S1.T[i] дополняется первыми переходами из списка L до размера |P1.T[i]|, а список S2.T[i] дополняется оставшимися переходами.

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

3.2.1.6.Генерация начального поколения

Начальное поколение заполняется автоматами, сгенерированными случайным образом. При этом все автоматы содержат одинаковое число состояний, из каждого их которых число переходов определяется случайным образом в диапазоне от нуля до числа событий, которые присутствуют в рассматриваемой системе со сложным поведением.

3.2.2.Генетический алгоритм

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

Программная реализация описанного алгоритма генетического программирования выполнена на языке программирования Java будет опубликована на сайте http://is.ifmo.ru в разделе «Генетические алгоритмы».

3.2.3.Вычисление функции приспособленности

Функция приспособленности основана на редакционном расстоянии. Для ее вычисления выполняются следующие действия: на вход автомату подается каждая из последовательностей Input[i]. Обозначим последовательность выходных воздействий, которую сгенерировал автомат на входе Input[i] как Output[i]. После этого вычисляется величина

, где как ED(A, B) обозначено редакционное расстояние между строками A и B. Отметим, что значения этой функции лежат в пределах от 0 до 1, при этом, чем «лучше» автомат соответствует тестам, тем больше значение функции приспособленности.

Функция приспособленности зависит не только от того, насколько «хорошо» автомат работает на тестах, но и числа переходов, которые он содержит. Она вычисляется по формуле:

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

Учет числа переходов в функции приспособленности необходим по двум причинам. Во-первых, минимизация числа переходов приводит к тому, что в результирующем автомате отсутствуют неиспользуемые в тестах переходы – так как они не используются, то могут быть удалены из автомата без ущерба для его поведения на тестах. Во-вторых, чем меньше в автомате переходов, тем более «общее» поведение он задает. Таким образом, частично решается проблема «переобучения», заключающаяся в том, что автомат демонстрирует правильное поведение только на тестовых входных последовательностях. Две указанные особенности должны учитываться при построении набора обучающих тестов.

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

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