Разработка методов машинного обучения на основе генетических алгоритмов и эволюционной стратегии для построения управляющих конечных автоматов Второй этап ФЦП «Научные и научно-педагогические кадры инновационной России» на гг. Мероприятие Шифр – НК-385/(5) Государственный контракт П2174 от 9 ноября 2009 г.

2 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап План 1. Структура хромосомы 2. Скрещивание и мутация 3. Описание генетического алгоритма и эволюционной стратегии 4. Программная реализация 5. Экспериментальное исследование

3 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап План 1. Структура хромосомы 2. Скрещивание и мутация 3. Описание генетического алгоритма и эволюционной стратегии 4. Программная реализация 5. Экспериментальное исследование

4 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Управляющий автомат Граф переходов управляющего автомата смешанного типа Автомат Мура – частный случай

5 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Хромосома алгоритмов Храним число воздействий – «скелет» автомата Сужение пространства поиска Храним список ребер Нулевое состояние является нулевым

6 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Алгоритм расстановки пометок Вырабатываемые на переходах и в состояниях выходные воздействия расставляются на основе тестов

7 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Алгоритм расстановки пометок - 2 Подадим на вход конечному автомату последовательность событий, соответствующую каждому из тестов Будем наблюдать за тем, какие переходы выполняет автомат Каждый переход и состояние помечаются той последовательностью действий, которая чаще остальных вырабатывалась на этом переходе (состоянии)

8 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап План 1. Структура хромосомы 2. Скрещивание и мутация 3. Описание генетического алгоритма и эволюционной стратегии 4. Программная реализация 5. Экспериментальное исследование

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

10 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Изменение описания перехода Изменение состояния, в которое ведет переход Изменение числа выходных воздействий Пример:

11 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Изменение описания состояния Изменение числа выходных воздействий Пример:

12 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Удаление или добавление перехода Пример удаления перехода:

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

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

15 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Традиционный метод скрещивания. Иллюстрация скрещивания состояний

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

17 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап План 1. Структура хромосомы 2. Скрещивание и мутация 3. Описание генетического алгоритма и эволюционной стратегии 4. Программная реализация 5. Экспериментальное исследование

18 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Генетический алгоритм Начальное поколение заполняется случайным образом Использование элитизма Остальные особи генерируются мутацией или скрещиванием Малая и большая мутации

19 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Эволюционная стратегия (1+λ) эволюционная стратегия Случайная начальная особь На каждом шаге алгоритма: Генерируется λ особей путем мутации текущей Текущей выбирается лучшая из всех особей Если роста функции приспособленности долго не происходит, то перезапускаем алгоритм

20 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Функция приспособленности Для каждого теста вычисляем Значение функции особи: cnt – число переходов в автомате

21 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап План 1. Структура хромосомы 2. Скрещивание и мутация 3. Описание генетического алгоритма и эволюционной стратегии 4. Программная реализация 5. Экспериментальное исследование

22 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап Программная реализация Выполнялась на языке программирования Java Использовались интерфейсы Простота изменения программы

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

24 Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов. Первый этап План 1. Структура хромосомы 2. Скрещивание и мутация 3. Описание генетического алгоритма и эволюционной стратегии 4. Программная реализация 5. Экспериментальное исследование

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

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

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