Вывод грамматик с использованием генетических алгоритмов для описания движения робота

Иванов С.В.

Иванов Сергей Викторович / Ivanov Sergey Viktorovich – аспирант, международный факультет прикладных информационных технологий, кафедра информационных систем и технологий,
Саратовский государственный технический университет имени Ю.А. Гагарина, г. Саратов

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

Abstract: growing demands in pattern recognition methods constantly encourages new researches and enhancements of existing solutions in different areas of use. Genetic algorithms proved to give good results in different practical tasks and they were applied to a problem of context-free grammars automatic generation. Practical example of generating a grammar for describing robotic movement algorithms shows good result and the effectiveness of method.

Ключевые слова: генетические алгоритмы, функция приспособленности, контекстно-свободные грамматики, распознавание образов, синтаксический анализ.

Keywords: genetic algorithms, fitness function, context-free grammars, pattern recognition, parsing.

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

Так как процесс синтаксического анализа требует задания грамматики, служащей для классификации моделей, в ситуации, когда эта грамматика неизвестна заранее, но известен набор слов, относящихся к генерируемому ей языку (либо набор слов, не относящихся к этому языку), грамматика может быть выведена экспертом или найдена автоматически в процессе выведения грамматик. Так как часто конструирование грамматики человеком, особенно для комплексных систем, – задача трудная или почти невозможная, то в области синтаксического распознавания образов появляется большой запрос на алгоритмы, позволяющие генерировать грамматики автоматически. Результаты исследований в области автоматического генерирования грамматик на основании примеров из языка вносят существенный вклад в развитие психолингвистики, в частности, в понимание механизмов усваивания естественных языков [1].

Находится много видов практического применения автоматического генерирования грамматик как в области распознавания и классификации образов, так и в сфере понимания машинами естественных языков, например, при проектировании роботов, выполняющих сложные вербальные команды, или при создании программ агентов, общающихся с пользователем с помощью естественного языка [2].

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

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

Главная функция приспособленности  для грамматики  выразим следующей формулой:

 (1)

Где:

 - (2) - функция приспособленности для положительных примеров,

 - функция приспособленности -го положительного примера - принимает значение 1, если -ый положительный пример был принят грамматикой, и значение 0, если пример был отклонен, как отрицательный.

 - общее количество положительных примеров

 - количество некорректно классифицированных примеров

 - общее количество отрицательных примеров.

Значение расширенной функции приспособленности  для грамматики  выражается следующей формулой:

 (3)

Где:

 (4)

 (5)

 - функция приспособленности для положительных примеров;

 - функция приспособления -го положительного примера;

 - общее количество положительных примеров;

 - количество некорректно классифицированных примеров;

 - общее количество отрицательных примеров;

 - количество правильно распознанных терминальных символов в -ом положительном примере;

 - общее количество терминальных символов в -ом положительном примере.

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

Результаты

Ниже представлено сравнение результатов, касающихся вывода контекстно-свободной грамматики, описывающей движения робота, с результатами, полученными при использовании генетического алгоритма с описанной выше функцией приспособленности. Также сравниваются результаты эволюции грамматик с применением анализатора класса LALR (Bison) [3], а также анализатора CYKP [4].

Грамматика была сгенерирована на основе множества примеров языка, представленных в таблице 1.

Таблица 1.

Примеры языка, описывающего движения робота

Множество терминальных символов состоит из элементов: {c, b, e}, определенных с помощью постоянных обозначений следующим образом:

c: left | right, b: begin, e: end

Параметры, контролирующие процесс эволюции, представлены в таблице 2.

Таблица 2.

Параметры, контролирующие процесс эволюции грамматик,

описывающих движения робота

Выполнено по пять прогонов алгоритма эволюции для анализаторов Bison и CYKP. График 1 представляет среднее значение приспособленности лучшей особи из пяти процессов эволюции в отдельных поколениях, а также диапазон от наименьшего значения до наибольшего для этих процессов.

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

В то же время в случае применения анализатора Bison в шестом поколении одного из процессов эволюции была найдена корректная грамматика (с функцией приспособленности, равной 1,0), однако в одном из процессов эволюции, вплоть до пятидесятого поколения не была найдена грамматика с функцией приспособленности, равной 1.0.

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

Таблица 3 представляет номера поколений, в которых впервые была найдена корректная грамматика – темным выделены случаи, в которых нахождение грамматики наступило раньше, чем в случаях работы [5].

Таблица 3.

Поколения, в которых в первый раз была найдена корректная

грамматика в отельных процессах эволюции

Как видно, при использовании анализатора CYKP получены значительно лучшие результаты, чем в случае анализатора Bison, однако в обоих вариантах полученные результаты лучше, чем представленные в работе [5].

Литература

1.         Болл Дж., Курландер Д., Пагх Д. i inni, Моделирование компьютерных персонажей: The Persona Project в Microsoft Research. Software Agents. 1997. 191-222 с.

2.         Мерник М., Крепинсек М., Герлик Дж. Изучение контекстно-свободных грамматик с применением эволюционного подхода. Издательство университета Марибор. 2003.

3.         Синтаксический анализатор Bison [Электронный ресурс] // 2014. – Режим доступа: http://www.gnu.org/software/bison/manual/bison.html (Дата обращения: 28.09.2014).

4.         Синтаксический анализатор Elkhound [Электронный ресурс] // 2014. – Режим доступа: http://scottmcpeak.com/elkhound/sources/elkhound/manual.html (Дата обращения: 28.09.2014).

5.         Мерник М., Герлик Дж., Зумер В., Брайант Б. Может ли Парсер быть сгенерирован по примерам? Выдержки ACM симпозиума по прикладным вычислениям. 2003. 1063-1067.