close

Вход

Забыли?

вход по аккаунту

(студ.), Соколов Д.О. (студ.).

код для вставкиСкачать
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Анализ использования нескольких функций
приспособленности для построения автоматов с
помощью генетических алгоритмов на примере
задачи «Умный муравей 3»
Родиков Д.Е., Соколов Д.О.
VI Всероссийская межвузовская конференция
молодых ученых
14 – 17 апреля 2009 г., Санкт-Петербург
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
План доклада
1. Постановка задачи
2. Предлагаемый метод решения
3. Результаты
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
2
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
План доклада
1. Постановка задачи
2. Предлагаемый метод решения
3. Результаты
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
3
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ





Игровое поле
Тор – 32x32
Вероятность
существования еды в
клетке μ
200 ходов
Начальная позиция
муравья фиксирована
Цель – создать муравья,
для которого
математическое ожидание
числа съеденных яблок
максимально
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
4
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Что умеет муравей?
Муравей видит восемь клеток
 За один игровой ход совершить
одно из четырех действий:





сделать шаг вперед, съедая еду,
если она там находится
повернуть налево
повернуть направо
ничего не делать
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
5
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Как задаётся муравей?
Муравей задаётся
конечным автоматом с
действиями на переходах
(автомат Мили)
 В качестве входного
воздействия даётся
массив из 8 значений типа
boolean, каждое из
которых означает наличие
или отсутствие еды в
соответствующей клетке

!F / R
2
!F / R
F/M
1
3
F/M
F/M
F/M
!F / M
!F / R
F/M
5
!F / R
4
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
6
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
План доклада
1. Постановка задачи
2. Предлагаемый метод решения
3. Результаты
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
7
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ






Предлагаемый подход
Генетический алгоритм
Несколько функций приспособленности
(Num_Fitness)
Поколение разбито на несколько групп по числу
используемых функций приспособленности
Муравей задаётся конечным автоматом Мили =
начальное состояние + описание состояний
Состояние = 256 переходов в зависимости от
расположения еды в 8 видимых клетках
Переход = номер состояния + действие
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
8
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Создание начального
поколения
Случайно генерируется заданное
количество автоматов
 Все автоматы содержат одинаковое
количество состояний
 Автоматы разбиты на Num_Fitness равных
групп
 В каждой группе своя функция
приспособленности

Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
9
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ




Формирование следующего
поколения
В каждой группе независимо от других
реализуется генетический алгоритм
Элитизм: фиксированная доля особей переходит
напрямую в следующее поколение
Остальные особи получаются скрещиванием:
выбираются две особи из одной группы текущего
поколения и скрещиваются
С некоторой вероятностью происходит мутация
полученных скрещиванием особей
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
10
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ


Обмен и мутации поколений
Через фиксированное число шагов
происходит обмен особями между
группами. Каждая вторая особь группы
переходит в следующую группу
«Большая» мутация поколения – все
особи, кроме одной лучшей в каждой
группе, заменяются на случайно
сгенерированную особь
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
11
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Мутация автомата
Изменение начального состояния
 Изменение перехода состояния

Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
12
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Скрещивание
На входе две особи, на выходе – две
особи
 В особях для скрещивания выбирается по
одному состоянию
 В выбранных состояниях выбирается по
одному переходу
 Выбранные состояния обмениваются
выбранными переходами

Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
13
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Функции приспособленности
fitness1 = apples + (200 – steps)/200
 fitness2 = apples / 2 + 100 * usedStates / statesNumber
 apples – число съеденных яблок
 steps – номер хода, на котором съедено последнее яблоко
 statesNumber – число состояний автомата
 usedStates – число состояний автомата, использованных
при работе алгоритма

Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
14
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Функции приспособленности

fitness3 = apples * 8 + 200 * reachableStates / statesNumber
 fitness4 = forwardSteps + apples + (200 – steps)/200
 apples – число съеденных яблок
 steps – номер хода, на котором съедено последнее яблоко
 statesNumber – число состояний автомата
 reachableStates – число состояний автомата, достижимых
из начального
 forwardSteps – число шагов прямо
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
15
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ



Функции приспособленности
В процессе работы программы для получения значения
iой функции приспособленности fitness[i] рассчитывается
на 10 произвольно сгенерированных полях и берётся их
среднее значение
При обмене особями между группами значения функций
приспособленности вычисляются заново на 100
произвольных полях
Для вывода результатов пересчёт функций
приспособленности производится на 1000 произвольных
полей
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
16
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Настраиваемые параметры
Размер поколения
 Доля особей, переходящих в следующее
поколение без изменений
 Доля особей для скрещивания
 Количество состояний
 Вероятность мутации
 Время до обмена особями поколения
 Время до «большой» мутации поколения

Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
17
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
План доклада
1. Постановка задачи
2. Предлагаемый метод решения
3. Результаты
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
18
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Сравнение наборов функций
приспособленности
№ФП\μ
1,2,3,4
1,3,4
1,2
1,3
1,4
1
0,01
4,41
3,71
3,16
3,53
3,67
3,66
0,02
8,39
6,90
7,51
9,00
8,27
8,59

число особей в популяции 300

число поколений 100
0,03
12,1
14,7
13,6
13,9
14,1
13,0
0,04
17,6
19,7
19,4
16,9
19,7
15,9
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
19
Сравнение с известными
результатами
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ

μ
Работа [1]
0,01
0,02
0,03
0,04
3,74
7,95
13,8
18,6
Данная
работа
4,41
9,00
14,7
19,7
Разница, %
18
13
6,5
6,0
1. Данилов В. Р. Технология генетического программирования
для генерации автоматов управления системами со сложным
поведением http://is.ifmo.ru/download/danilov_bachelor.pdf
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
20
Динамика изменения
приспособленности
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
10
20
30
40
50
60
70
80
90
100
1,3,4 15,6 18,2 18,8 19,5 19,5 19,5 19,7 19,9 20,0 20,0
1,3
13,2 15,5 16,7 17,7 17,8 18,2 19,5 19,5 19,8 20,0
1
15,5 17,5 17,9 18,2 18,2 18,5 18,3 18,3 18,4 18,7
μ = 0,04
 число особей в популяции 1500
 число поколений 100

Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
21
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Выводы
Метод даёт улучшение: результат + более
стабильный прирост от поколения к
поколению
 Нужно правильно выбирать комбинации
функций приспособленности
 Сложно создавать содержательные функции
приспособленности
 Не эффективен при малых размерах
поколений

Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
22
ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Спасибо за внимание!
Спасибо за внимание!
Родиков Д.Е., Соколов Д.О.
Анализ использования нескольких функций приспособленности для построения автоматов с помощью генетических алгоритмов на
примере задачи «Умный муравей 3»
23
1/--страниц
Пожаловаться на содержимое документа