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

Збірник наукових праць Харківськогоуніверситету Повітряних Сил, 2014, випуск 1(38) ISSN 2073-7378В статье приводятся основные положения оперативного самодиагностирования с блуждающим диагностическим ядром. Дается краткая характеристика гибкой структуры проверочных связей вычислительных систем. Предлагается новый способ отслеживания текущих структур проверочных связей системы, основанный на характеристических числах диагностического графа системы. METHODS SELF-DIAGNOSIS COMPUTER SYSTEMS BASED ON FLEXIBLE STRUCTURES VERIFICATION RELATIONS The article describes the main provisions of operational self-diagnosis with a wandering diagnostic kernel.Недетерминированным конечным автоматом (НКА) называется пятерка вида: K = (Q, ?, ?, S, F), где Q - некоторое конечное множество состояний (вершин), ? - рассматриваемый алфавит, ? - функция переходов вида ?: Q?(??{?})?2Q (? - пустое слово, 2Q - булеан множества Q), S?Q - множество стартовых состояний (входов), F?Q - множество финальных состояний (выходов). Некоторую пару подмножеств строк и столбцов назовем блоком, если, во-первых, на всех их пересечениях стоят 1, и, во-вторых, это множество нельзя пополнить ни строкой, ни столбцом - без нарушения первого свойства. Отметим, что здесь возникает аналогия с результатами, полученными нами при самообучении игровых программ: при начале самообучения с функциями произвольного вида, т.е. функциями, не имеющими вид (2), результат работы В первую очередь отметим, что эвристические алгоритмы автором статьи понимаются как т.н. anytime-алгоритмы, т.е. алгоритмы реального времени, которые в каждый определенный момент работы имеют лучшее на данный момент решение. Специальным образом помечаем элементы, входящие в выбранный на шаге 3 блок, чтобы они не учитывались при вычислении F(Ri,Cj), но могли входить в любой вновь выбираемый блок.Приведем некоторые возможности практического применения разлtrial вариантов эвристических алгоритмов минимизации НКА больших размерностей. Такими можно назвать все задачи, связанные с практическим применением именно недетерминированных автоматов, в которых имеет значение как можно меньшее число их состояний.

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

Недетерминированным конечным автоматом (НКА) называется пятерка вида: K = (Q, ?, ?, S, F), где Q - некоторое конечное множество состояний (вершин), ? - рассматриваемый алфавит, ? - функция переходов вида ?: Q?(??{?})?2Q (? - пустое слово, 2Q - булеан множества Q), S?Q - множество стартовых состояний (входов), F?Q - множество финальных состояний (выходов).

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

154 текста и распознавания речи, при построении лексических анализаторов, описании и верификации всевозможных систем, состоящих из конечного числа состояний с заданными переходами между ними (например, коммуникационных протоколов) и т.д.

Основной материал

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

Кроме того, рассматривается еще один вариант минимизации - звездно-высотная, т.е. задача построения конечного автомата, имеющего среди всех ему эквивалентных минимальную вложенность операции «звезда Клини» [5].

Используемый подход к минимизации НКА (предложенный в [1] для более широкого класса задач дискретной оптимизации) основан на сочета-

© С.В. Пивнева

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

Важнейшей вспомогательной подзадачей при вершинной минимизации НКА является следующая. Задана прямоугольная матрица, заполненная элементами 0 или 1.

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

Рассмотрим, например, матрицу, изображенную на рис. 1.

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

Пусть рассматривается клетка матрицы с координатами (i,j), пусть также R(i) - количество знаков 1 (или #) в строке i, а C(j) - количество знаков 1 в столбце j. Тогда: 1. Для каждой пары (i,j), содержащей #, по-считаем значение

F(i,j) = G(H(R(i)),H(C(j))), (1) где G(x,y) и H(x) - некоторые функции. Эти функции выбираются с помощью генетических алгоритмов (ГА), причем вид функции H(x) заранее неизвестен. А про функцию G(x,y) известно лишь то, что она является возрастающей. Таким образом, подбор параметров, необходимых для описания этих функций, есть объект самообучения.

2. При самообучении мы обычно используем следующий конкретный вид функции H(x): H(x)= e-(P1X) P2N(x-1)-1 P3 x 1, (2)

X Y Z U A 0 0 1 1 B 1 0 0 1 C 1 0 1 1 D 1 1 1 1 где N - соответствующая размерность таблицы со-ответствий состояний. Отметим, что здесь возникает аналогия с результатами, полученными нами при самообучении игровых программ: при начале самообучения с функциями произвольного вида, т.е. функциями, не имеющими вид (2), результат работы

Рис. 1. Пример матрицы с 5 блоками

В данной матрице имеются такие 5 блоков: ?={A,B,C,D}?{U}, ?={A,C,D}?{Z,U}, ?={B,C,D}? ?{X,U}, ?={C,D}?{X,Z,U}, ?={D}?{X,Y,Z,U}.

Для покрытия всех значений 1 данной матрицы достаточно использовать 3 из этих 5 блоков: ?, ? и ?.

В первую очередь отметим, что эвристические алгоритмы автором статьи понимаются как т.н. anytime-алгоритмы, т.е. алгоритмы реального времени, которые в каждый определенный момент работы имеют лучшее на данный момент решение. Для создания алгоритмов мы применяем незавершенный метод ветвей и границ (МВГ).

Эвристикой, непосредственно относящейся к задаче вершинной минимизации НКА, является выбор разделяющего элемента для МВГ. Это пример жадной эвристики (несколько упрощая ситуацию, можно сказать, что мы стремимся выбрать блок с относительно большим числом символов 1, не вошедших в уже выбранные блоки). Сами разделяющие элементы генерируются динамически, в процессе работы «основного» МВГ, а для их генерации применяется «вспомогательный» МВГ. Такой подход позволяет не строить все множество

ГА дает функции вида, близкого к указанному. Однако вид (2) все же был априори подобран эвристически.

3. Среди всех блоков выбираем такой (R,C), для которого т.н. итоговая рейтинговая сумма ?F(Ri,Cj), где Ri?R и Cj?C, будет наибольшей. Еще раз отметим, что функция F выбирается согласно (1), а функции G и H при этом получаются в результате самообучения методами ГА. Помещаем выбранный блок в итоговое множество.

4. Специальным образом помечаем элементы, входящие в выбранный на шаге 3 блок, чтобы они не учитывались при вычислении F(Ri,Cj), но могли входить в любой вновь выбираемый блок. Итак, в будущем, т.е. при повторном выполнении шагов 1-3, эти ячейки уже не считаем помеченными 1.

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

Полученное множество блоков считается искомым и используется либо для проведения очередного шага т.н. турнирного самообучения, либо для проведения очередного шага МВГ. Каждый раз при

155

Збірник наукових праць Харківськогоуніверситету Повітряних Сил, 2014, випуск 1(38) ISSN 2073-7378

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

А итоговое решение о единственном разделяющем элементе (блоке) может быть принято на основе работы любого алгоритма многокритериаль-

Теперь кратко опишем применение для незавершенного МВГ наших версий алгоритмов кластеризации ситуаций (более подробно см. в [3]). Кластеризация в первую очередь проводится на множестве подзадач - для того, чтобы после реализации одного шага МВГ для решения некоторой подзадачи применять выбор того же самого разделяющего элемента (решение подзадач «по аналогии»). Для ной оптимизации; мы же принимаем решение на применения обычных алгоритмов кластеризации основе т.н. «игровой» эвристики - с помощью т.н. функций риска (см. [2]).

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

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

Пусть X и Y - некоторые множества, n=|X?Y| - число элементов их пересечения, N=|XUY| - число элементов их объединения. Тогда будем писать ?(X,Y)=1-n/N.

Рассмотрим эвристику для определения метрики на множестве блоков подзадач.

Пусть P1 - множество клеток матрицы первой подзадачи, имеющих значение 1; P2 - то же для второй подзадачи. Тогда в качестве метрики используем значение ?(P1,P2).

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

(инициализация списка подзадач одним элементом - исходной задачей)

(«большой» шаг) loop {

1-й «малый» шаг - выбор очередной задачи из списка подзадач;

для нее - выбор разделяющего элемента; а для него - реализация одного шага метода ветвей и границ. Отметим, что сам алгоритм реализации выбора разделяющего элемента для одного шага МВГ является отдельной сложной задачей и уже был описан выше. Также отметим, что во время этого шага одновременно формируется описанная выше т.н. последовательность правых подзадач (ППЗ; см. [1]).

2-й «малый» шаг связан с предметом кластеризации ситуаций;

подробное описание реализуемого алгоритма кластеризации ситуаций приведено в наших предыдущих публикациях, а упрощенное описание может быть дано следующим образом. Ранее при формировании левой задачи мы отмечаем, какой именно правой задаче она «родственна» (т.е. отмечаем пару левая-правая); при этом если в будущем какое-то решение (о разделяющем элементе) выбирается для одной из них - то, по возможности, то же самое мы делаем и в другой. Весь этот вспомогательный алгоритм работает очень быстро (поскольку разделяющий элемент уже выбран): если этот элемент имеется в «парной» задаче -мы его и выбираем; если же его в «парной задаче» нет - то при этом мы тоже ничего не теряем. Все подобные действия также связаны со своим алгоритмом формирования ППЗ.

3-й «малый» шаг - генерация очередного потенциального разделяющего элемента (блока). В данном случае (в отличие от 1-го «малого» шага) этот разделяющий элемент пока не является конкретным разделяющим элементом ни для какой подзадачи; сам алгоритм соответствующей генерации тоже, конечно, сильно зависит от конкретной задачи. Этот шаг (в отличие от следующего, 4-го «малого» шага) выполняется с помощью «жадных» алгоритмов и случайного выбора - и обязательно дает результат; он аналогичен вышеупомянутому турнирному самообучению.

156

Кібернетика та системний аналіз

4-й «малый» шаг - один шаг метода ветвей и границ для вспомогательной ЗДО - которая использует метод ветвей и границ не для решения всей задачи, а для построения близкого к максимальному (по какой-либо естественной метрике) блока (т.е. потенциального разделяющего элемента). При этом, в отличие от «большой» ЗДО, мы здесь сохраняем все решения - даже заведомо далекие от оптимальных, поскольку нам для дальнейшей работы (для «большой» ЗДО) нужны, вообще говоря, все потенциальные разделяющие элементы. (Точнее - будут нужны на дальнейших стадиях работы алгоритма. Как уже отмечалось, наши алгоритмы хорошо работают для очень больших размерностей именно в связи с тем, что генерация всех потенциальных разделяющих элементов заранее не производится. Поэтому в данной ситуации структура задачи как объекта немного иная; однако здесь мы также формируем ППЗ, аналогичную 1-му «малому» шагу.)

}

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

Приведем некоторые возможности практического применения разлtrial вариантов эвристических алгоритмов минимизации НКА больших размерностей. Такими можно назвать все задачи, связанные с практическим применением именно недетерминированных автоматов, в которых имеет значение как можно меньшее число их состояний. Вот некоторые из этих проблем: ? недетерминированные алгоритмы моделирования работы НКА, т.е. просто решение проблемы принадлежности;

? применение НКА для моделирования дискретных объектов;

? альтернативное (отличное от входящего в иерархию Хомского) описание КС-языка с помощью т.н. интерпретирующих автоматов Оллонгрена;

и др.

1. Мельников Б.Ф. Мультиэвристический подход к задачам дискретной оптимизации / Б.Ф. Мельников // Кибернетика и системный анализ (НАН Украины). - 2006. - № 3. - С. 34-37.

2. Б.Ф. Программирование недетерминированных игр / Б.Ф. Мельников // Программирование (РАН). - 2001. - № 5. - С. 42-46.

3. Мельников Б.Ф. Кластеризация ситуаций в алгоритмах реального времени для задач дискретной оптимизации / Б.Ф. Мельников, Е.А. Мельникова // «Системы управления и информационные технологии», 2007. - № 2. - С. 54-58.

4. Мельников Б.Ф. Эвристические алгоритмы принятия решений в гуманитарных областях / Б.Ф. Мельников, С.В. Пивнева // «Известия Самарского научного центра Российской академии наук», Вып. 8. - Самара: Изд-во Самарского научного центра РАН. - 2009.

5. Баумгертнер С.В. Мультиэвристический подход к проблеме звездно-высотной минимизации недетерминированных конечных автоматов / С.В. Баумгертнер, Б.Ф. Мельников, С.В. Пивнева // Математические и компьютерные методы в технических, гуманитарных и общественных науках: моногр. - Пенза: Изд-во Приволжский Дом знаний, 2011. -С. 101-112.

Работа частично поддержана ФЦП Поступила в редколлегию 6.12.2013

"Научные и научно-педагогические кадры инновационной России" на 2009-2013 годы (соглашение № 14.В37.21.1934)

Рецензент: д-р техн. наук, проф. В.Н. Рудницкий, Черкасский государственный технологический университет, Черкассы.

ОСОБЛИВОСТІ ЗАСТОСУВАННЯ МУЛЬТИЕВРИСТИЧНОГО ПІДХОДУ

ДЛЯ ВИРІШЕННЯ ЗАВДАНЬ МІНІМІЗАЦІЇ НЕДЕТЕРМІНОВАНИХ КІНЦЕВИХ АВТОМАТІВ

С.В. Півнева

У роботі розглянуті особливості застосування мультиевристичного підходу для вирішення завдань мінімізації недетермінованого кінцевого автомата (НКА), заснованого на поєднанні комбінаторних і евристичних методів оптимізації.

Ключові слова: недетермінований кінцевий автомат (НКА), евристичні алгоритми, мінімізація НКА.

FEATURES OF APPLICATION OF MULTIHEURISTIC APPROACH FOR DECISION OF NONDETERMINISTIC EVENTUAL AUTOMATS MINIMIZATION TASKS

S.V. Pivneva

The paper discusses the features of the application multievristicheogo approach for minimization of nondeterministic finite automata (NFA), based on a combination of heuristics and combinatorial optimization.

Keywords: nondeterministic finite automaton (NFA), heuristic algorithm, minimize the NCA.

157