Применение генетического программирования в задаче поиска усердных бобров Д. О. Соколов, П.В. Федотов, Ф. Н. Царев Научный руководитель – А. А. Шалыто 2009 год

2 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Задача об усердных бобрах Машина Тьюринга Число состояний управляющего автомата машины Тьюринга фиксировано Изначально пустая лента Цель – создать такую машину Тьюринга, которая записывает на ленту максимальное число ненулевых символов и останавливается

3 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Пример усердного бобра ШагСостояниеЛента Начало Конец

4 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Решаемая задача Машина Тьюринга содержит автомат с шестью состояниями Работает над двоичным алфавитом {0, 1} Работает на бесконечной в обе стороны ленте На каждом шаге машина имеет два параметра: состояние автомата символ ленты, находящийся под головкой На основании этих параметров одновременно определяются: состояние, в которое переходит автомат действие, которое совершает машина Тьюринга Действие может быть одним из следующих: записать символ в ячейку под головкой передвинуть головку (влево или вправо)

5 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Трудности при поиске усердных бобров Пространство поиска очень велико существует (4n+1) 2n машин Тьюринга с n состояниями Отсутствие общего алгоритма для проверки того, останавливается ли машина Тьюринга Большое число шагов, которое может быть сделано машиной Тьюринга перед остановкой

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

7 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Представление особи public interface Individual { public byte getInitialState(); public void setInitialState(byte state); public ITransition[] getTransitions(); public int getStepsNumber(); public int getOnesNumber(); public int getTransitionUsages(ITransition transition); }

8 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Функция приспособленности В качестве функции приспособленности используется число единиц, оставленных на ленте при эмуляции работы машины Тьюринга Если машина не останавливается по преодолении заданного числа шагов, то эмуляция прекращается, и в качестве функции приспособленности такой машины используется выражение,где F max максимальное значение функции приспособленности среди всех особей предыдущего поколения c число единиц оставленных рассматриваемой машиной Тьюринга на ленте во время работы.

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

10 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Мутации Простой оператор мутации изменение случайного перехода; изменение стартового состояния на случайное. Усиленный оператор мутации изменение конечного состояния выполняется не у случайного перехода, а у перехода который использовался наибольшее число раз при подсчете функции приспособленности.

11 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Скрещивание На входе две особи, на выходе – две особи Выбор начального состояния Скрещивание переходов

12 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Формирование следующего поколения. Элитизм Фиксированная доля особей переходит напрямую Остальные – выбираются две особи из текущего поколения, и они с некоторой вероятностью скрещиваются или мутируют

13 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Формирование следующего поколения Эволюция происходит независимо на каждом из островов Через фиксированное число поколений – обмен особями между случайными островами Мутации поколения: большая; малая.

14 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Результаты Лучшая из полученных особей оставляет на ленте 74 единицы

15 Соколов Д. О., Федотов П. В., Царев Ф. Н. Применение генетического программирования в задаче поиска усердных бобров Спасибо за внимание!