1.3.4.Построение конечных преобразователей

Одной из областей применения автоматического построения автоматов является построение конечных преобразователей (Finite State Transducers), которые преобразуют входной поток в последовательность символов выходного алфавита. На 1.3.4 приведен пример простого преобразователя двоичной записи числа N в двоичную запись числа N + 1. При этом двоичная запись числа подается с конца. 

Более сложным примером использования автоматических преобразователей является синтез речи — отображение последовательности букв в последовательность фонем. Важным достоинством применения конечных автоматов для описания преобразователей является легкость их реализации. Как правило, в задаче построения конечного преобразователя исходными данными является «обучающее множество»: пары последовательностей символов, которые состоят из входной последовательности и соответствующей ей выходной последовательности. Задача же состоит в построении конечного преобразователя, который содержит заданное число состояний и корректно преобразует последовательности, входящие в обучающее множество.  В работе [] предлагается метод генетического программирования для построения конечных автоматов, реализующих преобразователи. Автоматы в этой работе представляются в виде графов переходов, генетические операции определяются аналогично генетическим операциям над абстрактными помеченными графами. При этом ребра помечаются входным и выходным воздействиями. Приведем описание операции рекомбинации. В используемом методе оператор рекомбинации принимает на вход две особи и возвращает две порожденных особи. Используется следующий алгоритм.

1. В двух рекомбинируемых графах выбирается по одной случайной вершине.

2. Подграфы, соответствующие вершинам меняются местами.

3. Ребра, которые ведут наружу, направляются в случайные вершины.

На 1.3.4 приведен пример рекомбинации.

Операция мутации реализуется следующим образом.

1. Выбирается случайная вершина графа.

2. Подграф, соответствующий выбранной вершине, удаляется.

3. Из вершины выращивается случайный подграф.

Определенные таким образом генетические операции часто порождают потомство, имеющее меньшее значение функции приспособленности, чем у родителей. Для того чтобы исключить это, реализуется следующая эвристика: генетические операции повторяются, пока не будет построено потомство, превосходящее родителей. Если же после фиксированного числа итераций приемлемого результата не достигается, то родители переходят в следующую популяцию. Предложенный подход был проверен на шести простых задачах построения преобразователей. Результаты экспериментов подтверждают работоспособность метода. В работе [] выполняется сравнение эволюционных алгоритмов и методов, основанных на эвристическом объединении состояний. При этом конечные преобразователи представлены в генетическом алгоритме с помощью двух таблиц: функции переходов и функции выходов.  Кроме этого, исследуются три подхода к вычислению функции приспособленности – на основе строго сравнения выходной последовательности с последовательностью из «обучающего множества», на основе вычисления расстояния Хэмминга [] и на основе вычисления редакционного расстояний (расстояния Левенштейна) []. Из этих трех методов наиболее эффективным оказался метод, основанный на редакционном расстоянии.  Результаты этой работы показывают, что наиболее эффективно (для рассмотренных в этой работе) примеров работает алгоритм ^ RMHC (random mutation hillclimber), использующий только операцию мутации. Вторым по эффективности является генетический алгоритм, а наименее эффективно работает эвристическое объединение состояний.  ^