Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Царев Ф. Н. Научный руководитель – д.т.н., проф. А. А. Шалыто Санкт-Петербургский государственный университет информационных технологий, механики и оптики

2 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Парадигма автоматного программирования Предложено в России в 1991 году Программные системы разрабатываются как системы взаимодействующих автоматизированных объектов управления Система управления является системой взаимодействующих конечных автоматов Состояния События и входные переменные Выходные воздействия Конечный автомат Система конечных автоматов

3 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Решаемая проблема Основная сложность в автоматном программировании – построение автоматов В большинстве случаев автоматы проектируются вручную Однако эвристическое построение автоматов часто затруднено или невозможно Решение – автоматическое построение конечных автоматов с помощью генетического программирования

4 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Задача «Умный муравей» Тор – 32x32 89 клеток с едой 200 ходов Расположение еды и начальная позиция муравья фиксированы Цель – создать муравья, который съест всю еду

5 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Что умеет муравей? Определять находится ли непосредственно перед ним еда За один игровой ход совершить одно из четырех действий: сделать шаг вперед, съедая еду, если она там находится повернуть налево повернуть направо ничего не делать

6 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Задача «Умный муравей-3» Расположение еды на поле случайно – в каждой клетке еда есть с вероятностью μ Муравей видит восемь клеток Результат муравья – математическое ожидание числа единиц еды Вычисляется приближенно – моделированием поведения на случайных полей

7 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Решение задачи без применения автоматов «Жадный» алгоритм На каждом шаге муравей выбирает ближайшую клетку из области видимости, в которой есть еда, и двигается к этой клетке Может быть реализован с помощью автомата с достаточно большим числом состояний При μ=0.05 результат равен

8 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Применение генетических алгоритмов Разные методы представления автоматов: Полные таблицы переходов (простейший метод) Сокращенные таблицы переходов (Поликарпова, Точилин) Деревья решений (Данилов)

9 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Дерево решений

10 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Предлагаемый метод Функция переходов в каждом из состояний задается с помощью абстрактного конечного автомата На вход автомату подаются значения входных переменных в некотором порядке Каждое из состояний абстрактного автомата помечено новым состоянием управляющего автомата и выходным воздействием

11 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Абстрактный автомат

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

13 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Результаты экспериментов Размер поколения – 1000 В пятисотом поколении – (при μ=0.05)

14 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Выводы Предложен метод представления функции переходов структурного конечного автомата с помощью набора абстрактных автоматов Проведено экспериментальное исследование этого метода на задаче Умный муравей-3

15 Царев Ф. Н. Применение метода представления функции переходов с помощью абстрактных конечных автоматов в генетическом программировании Спасибо за внимание Спасибо за внимание!