Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» А. А. Давыдов, Д. О. Соколов, Ф. Н. Царев Научный руководитель – А. А. Шалыто 2008 год

2 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Автоматное программирование Предложено в России в 1991 году Программные системы предлагается разрабатывать так же, как выполняется автоматизация технологических (и не только) процессов Система управления является системой взаимодействующих конечных автоматов Состояния События и входные переменные Выходные воздействия Конечный автомат Система конечных автоматов

3 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Преимущества автоматного подхода Обладает наибольшей эффективностью для систем со сложным поведением Формальное и понятное описание поведения Автоматическая генерация кода по диаграммам переходов Возможность верификации программ Проектная документация

4 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Решаемая проблема Основная сложность в автоматном программировании – построение автоматов В большинстве случаев автоматы проектируются вручную Однако эвристическое построение автоматов часто затруднено или невозможно Решение – автоматическое построение конечных автоматов с помощью генетического программирования

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

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

7 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Конечный автомат – способ описания муравья Автомат с действиями на переходах (автомат Мили). Автомат с действиями в вершинах (автомат Мура). Система (пара) автоматов взаимодействующих, с помощью вложенности Придумать одиночный автомат с большим числом состояний – просто С небольшим или систему автоматов – сложно На рисунке – автомат Мили, 5 состояний, за 200 ходов – 81 единица еды

8 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Генетические алгоритмы – 1 Jefferson D., Collins R., Cooper C., Dyer M., Flowers M., Korf R., Taylor C., Wang A. The Genesys System Кодирование автоматов битовыми строками Построен автомат из 13 состояний, позволяющий съесть всю еду за 200 ходов

9 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Генетические алгоритмы – 2 Angeline P. J., Pollack J. Evolutionary Module Acquisition // Proceedings of the Second Annual Conference on Evolutionary Programming Кодирование автоматов битовыми строками + «замораживание» Построен автомат из 11 состояний, позволяющий съесть всю еду за 193 хода

10 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Генетические алгоритмы – 3 Chambers L. D. Practical Handbook of Genetic Algorithms, Volume 3, Chapter 26, 6 – Algorithms to Improve the Convergence of a Genetic Algorithm with a Finite State Machine Genome. CRC Press, Кодирование автоматов битовыми строками + приведение автоматов к каноническому виду Построен автомат из 8 состояний, позволяющий съесть всю еду за 193 хода

11 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Генетические алгоритмы – 4 Царев Ф. Н., Шалыто А. А. О построении автоматов с минимальным числом состояний для задачи об «умном муравье» /Сборник докладов X международной конференции по мягким вычислениям и измерениям. СПбГЭТУ "ЛЭТИ". Т.2, 2007, с. 88–91. Генетическое программирование

12 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Автомат из семи состояний Построены два автомата из семи состояниями после перебора 160 и 230 млн. автоматов

13 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Решаемая задача Во всех описанных работах строились автоматы Мили Цель настоящей работы – построение автоматов Мура и систем взаимодействующих автоматов Мили

14 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Предлагаемый подход – 1 Островной генетический алгоритм Автомат = начальное состояние + описание состояний + вложенный автомат Состояние = два перехода + действие в состоянии (для автомата Мура) Переход = номер состояния + действие (для автомата Мили)

15 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Предлагаемый подход – 2 class Automaton { Transition[][] transitions; int initialState; Automaton nestedAutomaton; char[] stateAction; // для Мура }

16 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Создание начального поколения Случайно генерируется заданное количество (систем) автоматов Все автоматы содержат одинаковое количество состояний

17 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Формирование следующего поколения – 1 Элитизм Фиксированная доля особей переходят напрямую Остальные – на основе турнирной стратегии выбираются две особи из текущего поколения, и они с некоторой вероятностью скрещиваются или мутируют

18 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Формирование следующего поколения – 2 На нескольких островах эволюция происходит независимо. Каждое фиксированное число поколений – обмен между случайными островами случайными элитными особями.

19 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Мутация автомата Мура Изменение начального состояния Изменение действия в состоянии Изменение состояния, в которое ведет переход Изменение условия на переходе

20 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Мутация пары автоматов Мили Изменение начального состояния Удаление (добавление) перехода Изменение состояния, в которое ведет переход Изменение действия на переходе Мутация вложенного автомата

21 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Скрещивание автоматов Мура На входе две особи, на выходе – две особи Родители – P1 и P2 Потомки – S1 и S2 Начальное состояние: S1.is = P1.is и S2.is = P2.is, либо S1.is = P2.is и S2.is = P1.is

22 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Скрещивание переходов Рассмотрим состояние номер i «Перед муравьем нет еды» P1(i, 0) «Перед муравьем есть еда» P1(i, 1) Аналогично: P2(i, 0), P2(i, 1), S1(i, 0), S1(i,1), S2(i, 0), S2(i, 1) Есть 4 варианта для S1(i, 0), S1(i,1), S2(i, 0), S2(i, 1)

23 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Четыре варианта

24 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Скрещивание пар автоматов Мили Внешние автоматы – аналогично автоматам Мура Вложенные автоматы – или также скрещиваются, или один из детей наследует вложенный автомат одного родителя, другой – другого.

25 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Функция приспособленности автомата Мура F – количество еды, которое съедает за 200 ходов муравей T – номер хода, на котором муравей съедает последнюю единицу еды

26 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Функция приспособленности пар автоматов Мили F – количество еды, которое съедает за 200 ходов муравей T – номер хода, на котором муравей съедает последнюю единицу еды Z – число посещенных состояний у внешнего автомата C – некоторый коэффициент, ключевой для генерации систем автоматов

27 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Мутации поколений Чтобы одни и те же элитные особи «путешествуя» не заполонили собой все острова, надо что-то делать. Через фиксированное число поколений – «большая» мутация нескольких островов «Большая» мутация острова – все особи либо заменяются на случайно сгенерированные, либо на мутированные

28 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Настраиваемые параметры алгоритма – 1 Число островов Размер поколения на одном острове Время до «большой» мутации Доля уничтожаемых островов во время «большой» мутации Доля особей, переходящих в следующее поколение Время между обменами особями между островами

29 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Настраиваемые параметры алгоритма – 2 Число обмениваемых особей Параметры малой мутации Параметры скрещивания Отношение «мутантов», случайных особей и детей особей из текущего поколения при формировании следующего поколения С – коэффициент влияния внешнего автомата.

30 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Автомат Мура из 10 состояний Позволяет муравью съесть всю еду за 198 ходов

31 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Система из двух вложенных автоматов Мили Позволяет муравью съесть 87 единиц еды за 185 ходов

32 Давыдов А. А., Соколов Д. О., Царев Ф. Н. Применение генетических алгоритмов для генерации автоматов Мура и систем взаимодействующих автоматов Мили в задаче об «Умном муравье» Спасибо за внимание!