Программные продукты и системы

Конечные автоматы (КА) находят самое широкое применение в различных областях науки и техники. Приведем основные определения из теории КА (подробнее см. в [1]). Пусть Σ – алфавит, а w=a1a2…an, где ∀i: ai∈Σ – слово. Множество слов L⊆Σ* называется языком. Недетерминированным конечным автоматом (НКА) называется пятерка A=(Q, Σ, ∆, I, F), где Q – конечное множество состояний; Σ – конечный алфавит; ∆⊆Q×Σ×Q – множество переходов; I ⊆Q и F⊆Q – множества начальных и конечных состояний соответственно. Переходы автомата A часто описывают с помощью функции переходов δ:Q×Σ→2Q. НКА называется детерминированным (ДКА) тогда и только тогда, когда |I|=1 и ∀q∈Q, ∀a∈Σ:|δ(q, a)|=1 (или |(q, a)|≤1). КА часто используются для описания или распознавания языков. Два автомата называются эквивалентными, если они задают один и тот же язык. Для каждого НКА с помощью процедуры детерминизации может быть построен эквивалентный ему ДКА (каждое состояние такого ДКА – это подмножество состояний исходного НКА). Для слова w=a1a2…an слово w = an an -1 ¼ a1 называется зеркальным, а для языка L зеркальным будет язык L = {w | w ∈ L} . Наконец, для автомата A=(Q, Σ, ∆, I, F) зеркальным автоматом будем называть автомат A = (Q, Σ, ∆, F , I ) , для которого ( , , )i j q a q Î D тогда и только тогда, когда (qj, a, qi)∈∆. Для данного языка L каноническим автоматом называется ДКА, распознающий этот язык и имеющий минимально возможное число состояний, а зеркальным каноническим автоматом называется ДКА, распознающий язык L и имеющий минимально возможное число состояний (данные автоматы единственны для языка L с точностью до изоморфизма). Задача вершинной минимизации НКА формулируется следующим образом: для данного НКА A найти автомат, эквивалентный данному и имеющий минимально возможное число состояний. Заметим, что решение этой задачи может быть не единственным. Как показано в [2], задача вершинной минимизации НКА является PSPACE-полной, в то время как аналогичная задача для ДКА имеет сложность в худшем случае O(Q⋅Σ⋅logQ). Следует отметить, что все известные точные методы минимизации НКА являются переборными, поэтому часто на практике их невозможно применить даже для сравнительно небольших автоматов. Это одна из причин того, что они не реализованы в таких известных пакетах для работы с НКА и родственными структурами, как AMoRE, FSM, Grail, Vaucanson, JFlap и др. [3–7]. Более того, в большинстве таких пакетов отсутствуют даже приближенные методы минимизации НКА.

В данной работе предлагается новый эвристический алгоритм минимизации НКА, основанный на сочетании классического алгоритма Камеды– Вейнера [8] и генетического алгоритма (ГА). Основная идея предлагаемого метода состоит в том, что наиболее трудоемкая переборная часть алгоритма заменяется неполным поиском с использованием ГА, что позволяет существенно сократить время вычислений.

Алгоритм Камеды–Вейнера

Приведем краткое описание алгоритма. Пусть дан НКА A. Поиск минимальных автоматов, эквивалентных A, осуществляется с помощью бинарной матрицы RAM (Reduced Automaton Matrix), которая строится следующим образом. Сначала для автомата A строятся канонический автомат B и зеркальный канонический автомат C. Каждое состояние этих автоматов является подмножеством состояний автомата A. Затем для всех непустых состояний pi автомата B (i=1, …, m) и qj автомата C (j=1, …, n) определяется элемент rij матрицы RAM:

0, ,1, .i jiji j p qr

p q  ∩ = ∅=  ∩ ≠ ∅

Пусть X – подмножество строк, а Y – подмножество столбцов матрицы RAM. Тогда декартово произведение X×Y называется гридом (блоком), если оно удовлетворяет следующим двум условиям: 1) на пересечениях всех его строк и столбцов располагаются единицы; 2) множества X и Y нельзя расширить без нарушения первого условия. Множество гридов покрывает матрицу RAM, если каждая единица в ней принадлежит по крайней мере одному из гридов данного множества. Минимальным покрытием матрицы RAM называется покрытие, содержащее наименьшее возможное количество гридов. Рассмотрим НКА A с таблицей переходов, приведенной в таблице 1 [8].

В таблицах 2 и 3 для автомата A приведены матрицы переходов канонического автомата B и зеркального канонического автомата C соответственно, а в таблице 4 – матрица RAM автомата A. Таблица 2

В матрице RAM четыре грида: {1, 3}×{2, 3}; {2, 3}×{1, 2}; {3}×{1, 2, 3}; {1, 2, 3}×{2}. Легко убедиться, что первые два грида образуют минимальное покрытие матрицы RAM. По данному покрытию матрицы RAM с помощью так называемого правила пересечений можно построить НКА, который может оказаться эквивалентным исходному НКА A (в этом случае покрытие называется легитимным). Число состояний в построенном НКА совпадает с числом гридов в покрытии. В рассматриваемом примере минимальное покрытие является легитимным, и в результате получается минимальный автомат с двумя состояниями (табл. 5).

Общая схема алгоритма Камеды–Вейнера может быть описана алгоритмом 1. Заметим, что шаги 1, 3 и 4 алгоритма теоретически имеют экспоненциальную сложность, однако на практике построение канонических автоматов обычно выполняется достаточно быстро и самыми трудоемкими являются шаги 3 и 4 (поиск гридов и минимальных легитимных покрытий).

Алгоритм 1. Вход: НКА A 1. Построить канонические автоматы B и C 2. Построить матрицу RAM 3. Найти все гриды RAM 4. Найти минимальные легитимные покрытия RAM и построить минимальные НКА с помощью правила пересечений Выход: Минимальные НКА, эквивалентные A Генетический алгоритм Популярной разновидностью эволюционных алгоритмов оптимизации, основанных на ими- тации процессов естественного отбора, происходящих в живой природе, является ГА. Эволю- ционные алгоритмы относятся к так называемым популяционным, поскольку они работают не с одним решением, а с их группой (популяцией). Такие решения в эволюционных алгоритмах часто называются особями, хромосомами и т.п. Общая схема ГА может быть описана алгоритмом 2.

Алгоритм 2. 1. Population := InitialPopulation() 2. for all i∈Population do 3. EvaluateFitness(i) 4. end for 5. while not StopCondition() do 6. Parents := Select(Population) 7. Offspring := Crossover(Parents) 8. Offspring := Mutation(Offspring) 9. for all βi∈Offspring do 10. EvaluateFitness(βi) 11. end for 12. Population:=UpdatePopulation(Population ∪ Offspring)13. end while 14. Solution := ChooseBestOf(Population) Выход: Solution На первом шаге работы алгоритма формируется начальная популяция (строка 1) и для каждой ее особи вычисляется значение функции приспособленности (строки 2–4). Функция приспособленности – это функция, позволяющая сравнивать между собой качество получаемых решений. Основная идея эволюционных алгоритмов состоит в том, что в процессе эволюции выживают решения с лучшими значениями функции приспособленности. На каждом шаге искусственной эволюции популяция решений изменяется следующим образом: сначала из популяции по некоторому алгоритму отбираются несколько особей-родителей (строка 6), затем эти особи скрещиваются между собой, давая потомство (строка 7), после чего полученное потомство подвергается мутации (строка 8) и для него вычисляются значения функции приспособленности (строки 9–11). Затем на основе старой популяции и полученных потомков формируется новая популяция (происходит естественный отбор). Процесс продолжается до наступления критерия остановки (в самом простом случае таким критерием является число итераций алгоритма). В качестве ответа обычно выдается особь с наилучшим значением функции приспособленности (или вся популяция, или ее часть). Очень часто решения в ГА кодируются двоичными векторами. В этом случае операция скрещивания (кроссовера) двух особей обычно выполняется так: сначала случайным образом определяется место скрещивания, то есть индекс в векторе, а затем особи обмениваются значениями координат (битов), начиная с данного индекса (значения координат до этого индекса остаются неизменными). В результате две особи-родителя дают двух потомков. Такой тип скрещивания называется одноточечным кроссовером. Существуют и другие варианты скрещивания. Операция мутации для двоичных векторов обычно заключается в случайном инвертировании битов [9].

Комбинирование алгоритма Камеды–Вейнера и ГА

Рассмотрим более подробно последний шаг алгоритма Камеды–Вейнера, то есть поиск минимальных легитимных покрытий (алгоритм 3). Здесь M – множество минимальных НКА; Gridsi – множество всевозможных сочетаний гридов по i элементов; IsLegitimateCover() – функция, проверяющая, является ли множество гридов легитимным покрытием; IntersectionRule() – функция построения НКА по покрытию с помощью правила пересечений. Границы imin и imax внешнего цикла могут быть вычислены следующим образом: imin= log2NB, где NB – число состояний в каноническом автомате B; max min( , 1, 1) G A Bi = N N - N - , где NG – число гридов в матрице RAM, NA – число состояний в A, NB – число состояний в B. Алгоритм 3. 1. Вычислить imin и imax 2. M := ∅

3. for i from imin to imax do 4. found := false 5. for all Comb∈Gridsi do 6. if IsLegitimateCover(Comb) then 7. M := M ∪{IntersectionRule(Comb)} 8. found := true 9. end if 10. end for 11. if found = true then 12. break 13. end if 14. end for

На каждом шаге внешнего цикла в строках 5–10 анализируются все возможные сочетания гридов по i элементов. Следует заметить, что на практике очень часто даже для небольших автоматов число гридов в матрице RAM может достигать нескольких сотен и даже тысяч элементов, а это приводит к необходимости перебора большого числа вариантов. Идея предлагаемого алгоритма состоит в том, чтобы заменить полный перебор более быстрой процедурой поиска, то есть ГА (разумеется, алгоритм при этом перестает быть точным и получаемые автоматы могут оказаться не минимальными, а редуцированными). Эвристический поиск минимальных легитимных покрытий можно реализовать с помощью алгоритма 4. Алгоритм 4. 1. Вычислить imin и imax 2. Найти минимальные покрытия RAM с помощью ГА 3. if найдены покрытия, размером не больше imax then 4. Выбрать минимальные легитимные покрытия и построить минимальные НКА с помощью правила пересечений 5.

Таким образом, в предлагаемом методе ГА используется в алгоритме Камеды–Вейнера для нахождения минимальных покрытий матрицы RAM, после чего производится проверка их легитимности. Рассмотрим основные моменты, касающиеся ГА. Решением в ГА является покрытие, которое кодируется с помощью двоичного вектора. В этом векторе 1 в i-й позиции означает, что i-й грид включается в покрытие, а 0, что грид не включается в него. В рассматриваемом примере вектор (1, 1, 0, 0) означает, что в покрытие включаются только первые два грида из четырех. Для начала работы ГА необходимо сформировать начальную популяцию. Самым простым способом является поиск тривиальных решений, у которых все биты установлены в 1. Для получения нетривиальных решений может использоваться алгоритм 5.

Алгоритм 5. 1. Пометить все единицы RAM как непокрытые 2. repeat 3. Взять следующую непокрытую 1 в RAM 4. Случайно выбрать один из гридов, покрывающий эту 1 5. Установить соответствующий бит начального решения в 1 6. Пометить все единицы, покрываемые выбранным гридом, как покрытые 7. until нет непокрытых единиц в RAM Функция Fitness() возвращает число 1 в векторе. Оператор мутации инвертирует несколько случайно выбранных битов, а в качестве оператора кроссовера могут использоваться любые стандартные операторы для двоичных векторов (например одноточечный или двухточечный кроссовер). После применения генетических операторов решение может стать недопустимым, то есть получившийся набор гридов может не являться покрытием, поэтому потребуется его корректировка, которая выполняется с помощью алгоритма, аналогичного 5. Так, в рассматриваемом примере решение (1, 0, 0, 0) не является допустимым и должно быть скорректировано. Программно корректировка решения может осуществляться либо внутри каждого генетического оператора, либо в виде отдельного оператора. В заключение заметим: если минимальные легитимные покрытия не найдены, точный и приближенный алгоритмы возвращают канонический автомат B, когда число состояний в нем меньше, чем в автомате A.

Численные эксперименты

Для проверки эффективности предложенный алгоритм и алгоритм Камеды–Вейнера были реализованы в проекте ReFaM (Rational Expressions and Finite Automata Minimization), который является частью кросс-платформенной библиотеки HeO (Heuristic Optimization) [10]. Библиотека написана на языке программирования C++ и содержит несколько параллельных эвристических (метаэвристических) методов оптимизации: ГА (GA – Genetic Algorithm), метод имитации отжига (SA – Simulated Annealing), метод стохастического восхождения на холм (SHC – Stochastic Hill Climbing), метод ветвей и границ (BnB – Branch and Bound). Данные методы реализованы в виде алгоритмических каркасов с использованием метапрограммирования, шаблонов проектирования и двух технологий параллельного программирования (OpenMP and MPI). Последнюю версию библиотеки можно скачать через SVN (домашняя страница: http://code.google.com/p/heo/). В алгоритме Камеды–Вейнера с помощью технологий OpenMP и MPI были распараллелены поиск гридов в матрице RAM и поиск минимальных легитимных покрытий. В эвристической версии алгоритма использован параллельный вариант ГА библиотеки HeO, реализующий островную модель. Каждая версия алгоритма (точная и приближенная) реализованы в виде отдельного солвера. Рассмотрим результаты работы точного и приближенного алгоритмов для случайной выборки из 100 попарно неэквивалентных НКА без недостижимых и бесполезных состояний, сгенерированных со следующими параметрами: число состояний Q=6, число начальных состояний I=1, число конечных состояний |F|=2, размер алфавита Σ=2, плотность переходов 2 0, 3 | | | |T – число переходов в автомате. Вычислительные эксперименты проводились на системе с общей памятью со следующими характеристиками: Intel Core 2 Quad Q6600 2.4Ghz, 4 Gb RAM, MS Windows XP Professionsl SP 3. Результаты работы точного алгоритма представлены в таблице 6. Здесь m и n – соответственно число строк и столбцов матрицы RAM; d – плотность единиц в RAM; NG – число гридов в RAM; NM – число минимальных автоматов NFAs; |QM| – число состояний в минимальных автоматах; min и max – минимальное и максимальное значения; µ – среднее значение; σ – среднеквадратическое отклонение. Среднее время минимизации с использованием четырех потоков составило 1,1 секунды, а общее число найденных минимальных автоматов для всей выборки – 268, при этом у 9 автоматов не оказалось эквивалентных минимальных НКА. Как видно из таблицы, у некоторых автоматов имеется несколько минимальных НКА (среднее значение – 2,95), а среднее число состояний в минимальных автоматах равно 3,52. Таблица 6 m n d NG NM QM min 1 1 0,63 1 0 1 max 16 14 1,00 92 32 5 µ 5,70 6,00 0,73 15,40 2,95 3,52 σ 2,83 2,85 0,05 17,74 5,21 0,95 Проанализируем результаты работы приближенного алгоритма, полученные с разным числом потоков (N=1, 2, 4, 8, 16, 32, 64), представленные в таблице 7. Вычисления проводились со следующими параметрами ГА: число особей в популяции – 10; вероятность кроссовера – 0,8; вероятность мутации – 0,2; число итераций – 50. Поскольку ГА используется только на последнем шаге алгоритма Камеды–Вейнера, первые 4 столбца таблицы 6 для приближенного алгоритма будут теми же, что и для точного алгоритма, поэтому в таблице 7 они заменены следующими столбцами: NT – общее число минимальных (редуцированных) автоматов для выборки; NU – число неминимизированных автоматов в выборке; T – среднее время минимизации в секундах. Для столбцов NM и QM приведены средние значения.

Из таблицы 7 видно, что с увеличением числа потоков число найденных минимальных (редуцированных) автоматов увеличивается, а число неминимизированных автоматов уменьшается. Среднее время минимизации по сравнению с точным алгоритмом мало и остается практически постоянным при числе потоков от 1 до 4, а затем увеличивается пропорционально числу потоков из-за ограничений аппаратной платформы, поддерживающей одновременное исполнение лишь четырех потоков. Проведенные численные эксперименты показали, что предложенный метод позволяет получать приемлемые результаты намного быстрее точного метода. Заметим, что полный перебор при поиске минимальных легитимных покрытий в алгоритме Камеды–Вейнера может быть заменен не только ГА, но и другими эвристическими алгоритмами, в частности алгоритмами локального поиска, что позволяет получить на основе классического алгоритма минимизации НКА новые эвристические алгоритмы вершинной минимизации.

Литература 1. Мельников Б.Ф. Недетерминированные конечные автоматы. Тольятти: Изд-во ТГУ, 2009. 160 с.

2. Jiang T., Ravikumar B. Minimal NFA problems are hard // SIAM J. Comput. 1993. December. Vol. 22, pp. 1117–1141.

3. Kell V., Maier A., Potthoff A. et al. AMORE: a system for computing automata, monoids and regular expressions // Proc. of the 6th Annual Symposium on Theoretical Aspects of Computer Science on STACS 89. NY, USA: Springer-Verlag New York, Inc., 1989, pp. 537–538.

4. Mohri M., Pereira F., Riley M. AT&T General-purpose finite-state machine software tools.

5. Raymond D., Wood D. Grail: Engineering Automata in C++: Tech. Rep. HKUST-CS96-24: Hong Kong University of Science and Technology, 1996.

6. Lombardy S., Poss R., Régis-Gianas Y., Sakarovitch J. Introducing VAUCANSON // Implementation and Application of Automata, Proc. Of the 8th Intern. Conf., CIAA 2003, Santa Barbara, California, USA, July 16–18, 2003, Vol. 2759 of Lecture Notes in Computer Science. Springer, 2003, pp. 96–107.

7. Rodger S.H. JFLAP: An Interactive Formal Languages and Automata Package. USA: Jones and Bartlett Publishers, Inc., 2006.

8. Kameda T., Weiner P. On the State Minimization of Nondeterministic Finite Automata // IEEE Transactions on Computers. 1970. Vol. 19, pp. 617–627.

9. Панченко Т.В. Генетические алгоритмы: учеб.-метод. пособ. Астрахань: Издат. дом «Астраханский университет», 2007. 87 с.

10. Цыганов А.В., Булычов О.И. HeO: библиотека метаэвристик для задач дискретной оптимизации // Программные продукты и системы. 2009. № 4. С. 148–151.