[ Санкт-Петербургский национальный исследовательский университет
информационных технологий, механики и оптики
Факультет информационных технологий и программирования
Кафедра «Компьютерные Технологии»
В.С. Кононов
Отчет по лабораторной работе
«Построение управляющих автоматов с помощью генетических алгоритмов»
Вариант №10
Санкт-Петербург 2011 г.
Оглавление Введение
Постановка задачи
1.
Задача об умном муравье
1.1.
Автомат Мура
1.2.
Реализация
2.
Оператор мутации
2.1.
Оператор одноточечного скрещивания
2.2.
Оператор двухточечного скрещивания
2.3.
Оператор однородного скрещивания
2.4.
Функция приспособленности
2.5.
Результаты
3.
Заключение
4.
Приложение
5.
Автомат
5.1.
Путь муравья
5.2.
Источники
Введение В лабораторной работе исследуется эффективность работы генетического алгоритма, строящего автомат для решения задачи об умном муравье, при использовании одноточечного, двухточечного и однородного кроссоверов.
При выполнении работы применялся фреймворк Watchmaker [1] для работы с генетическими алгоритмами. Весь исходный код в данной работе написан на языке программирования Java.
1. Постановка задачи Задача данной лабораторной работы сравнить эффективность работы генетического алгоритма, строящего автомат Мура, который решает задачу об умном муравье, при использовании одноточечного, двухточечного и однородного кроссоверов.
Критерий оценки автомата заключается в том, что автомат, имея фиксированное число состояний, должен приводить к тому, что муравей, управляемые автоматом, съедает всю еду на поле за ограниченное число шагов. Из всех муравьев, съевших одинаковое количество еды, лучшим считается тот, который сделал при этом меньшее количество шагов.
1.1. Задача об умном муравье Дано поле размером 3232 клетки, расположенное на поверхности тора. На поле расположено 89 яблок, причем не более одного яблока в клетке. Муравей начинает движение из клетки, помеченной как «Start», и видит только то, что находится в клетке перед ним.
Рис. 1 Игровое поле У муравья есть три варианта действий: повернуть налево, сделать шаг вперед (и если в клетке была еда, то съесть ее), повернуть направо. Задача: съесть как можно больше яблок за 200 ходов.
1.2. Автомат Мура Автоматом Мура называется автомат, у которого выходное воздействие зависит только от состояния и не зависит от входного воздействия.
Можно записать автомат Мура в виде пятерки =,,,, µ — множество состояний;
— множество входных воздействий;
— множество выходных воздействий;
: ;
µ:.
2. Реализация Для реализации генетического алгоритма использован фреймворк Watchmaker [1], реализованы операторы мутации [2] и кроссоверов автоматов: одноточечный [2], двухточечный [3] и однородный [3]. Также реализован класс, вычисляющий функцию приспособленности.
2.1. Оператор мутации Для каждого состояния автомата выполняется следующее: с определенной вероятностью p действие и каждое состояние, в которое возможно перейти из данного, заменяются на случайные. С этой же вероятностью возможно изменение начального состояния автомата.
2.2. Оператор одноточечного скрещивания Для пары выбранных родителей происходит следующее: случайным образом выбирается номер состояния A. Родители обмениваются всеми состояниями, начиная с позиции A + 1. Потомками являются получившиеся при этом автоматы.
2.3. Оператор двухточечного скрещивания Для пары выбранных родителей происходит следующее: случайным образом выбираются номера состояний A и B (для удобства будем считать, что A B). Родители обмениваются состояниями в промежутке от A до B. Потомками являются получившиеся при этом автоматы.
2.4. Оператор однородного скрещивания Для пары выбранных родителей происходит следующее: для каждого номера состояния автоматов с определенной вероятностью p происходит обмен состояниями между родителями. Потомками являются получившиеся при этом автоматы 2.5. Функция приспособленности Функция приспособленности (ФП) определяется по следующей формуле, где count – количество яблок, съеденных муравьем; last – номер шага, на котором было съедено последнее из съеденных яблок.
3. Результаты Используем генетический алгоритм для построения автомата Мура, состоящего из 12 состояний, и сравним результаты при использовании разных методов кроссовера.
Для каждого из кроссоверов были произведены 10 и 100 запусков, генерировавших по 10 000 поколений. В каждом запуске бралась величина максимальной функции приспособленности в соответствующем поколении. После получения результатов 10 и запусков, данные значения усреднялись. Результаты 10 и 100 запусков отражены на рис. и рис. 6 соответственно.
Рис. 5. Графики функции приспособленности: 10 запусков с размером поколения Рис. 6. Графики функции приспособленности: 100 запусков с размером поколения Как видно из результата запусков, различные типы кроссоверов работают практически одинаково, разница в результатах совсем несущественна. Необходимо дополнительное исследование.
Произведем запуск генетического алгоритма для каждого типа кроссовера по 10 и 100 раз. При каждом запуске будем считать количество поколений, которые необходимо сгенерировать для получения автомата, позволяющего муравью съесть все 89 яблок в пределах 200 ходов. Результаты 10 и 100 запусков отражены на рис. 7 и рис. соответственно в отсортированном по возрастанию для числа поколений порядке.
Рис. 7. Графики числа поколений: 10 запусков c отсортированными результатами Рис. 8. Графики числа поколений: 100 запусков c отсортированными результатами Как видно из результата запусков, автомат, под управлением которого муравей съедает все 89 яблок, строится быстрее всего при использовании одноточечного кроссовера. Вторым по эффективности идет двухточечный кроссовер, наихудшие результаты показывает однородный кроссовер.
4. Заключение Результаты лабораторной работы показали, что наиболее эффективное построение автомата Мура с 12 состояниями, который решает задачу об умном муравье, достигается при использовании одноточечного кроссовера.
5. Приложение 5.1. Автомат Автомат, который съедает все 89 яблок за 196 ходов.
Рис. 9 Автомат из 12 состояний, съедающий все 89 яблок за 196 ходов 5.2. Путь муравья Путь, который проходит муравей под управлением автомата из предыдущего пункта.
Рис. 10 Путь, который проходит муравей, съедающий все 89 яблок за 196 ходов Источники 1. The Watchmaker Framework for Evolutionary Computation. http://watchmaker.uncommons.org/.
2. Методы представления конечных автоматов в генетических алгоритмах http://is.ifmo.ru/~buzdalov/lab-2011/presentations/automata-representation.pdf http://sernam.ru/book_gen.php?id=
«