Телематика'2007

XIV Всероссийская
научно-методическая
конференция


 

 

ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОБ «УМНОМ МУРАВЬЕ»

П.Г. Лобанов, А.А. Шалыто

Санкт-Петербургский государственный университет информационных технологий, механики и оптики, Санкт-Петербург

Тел.: (911) 212-55-44, e-mail: pavel.lobanov@gmail.com

(Скачать вариант для печати)


В последнее время все шире применяется автоматное программирование [1], в рамках которого поведение программ описывается с помощью конечных детерминированных автоматов (в дальнейшем, автоматов).
Для многих задач автоматы удается строить эвристически. Однако существуют задачи, для решения которых такое построение автоматов затруднительно. Известны задачи (итерированная дилемма узников [2], задача о «флибах» [3]), в которых применение генетических алгоритмов позволяет автоматизировать построение конечного автомата. Это одни из первых шагов к автоматическому построению автоматных программ.
В данной работе рассматривается одна из таких задач – задача об «Умном муравье» [4]. На тороидальном поле размером 32 на 32 находятся 89 ячеек с едой. Еда расположена вдоль ломаной линии («тропы»), некоторые ячейки которой пустые. Расположение ячеек с едой фиксировано. Муравей должен за 200 ходов съесть всю еду на линии. Требуется построить конечный автомат, моделирующий поведение такого муравья.
Вначале муравей находится в левом верхнем углу поля и смотрит направо. У муравья есть сенсор, позволяющий ему определить, есть ли еда в ячейке, находящейся непосредственно перед ним. За один ход муравей может выполнить одно из следующих действий – повернуться налево, повернуться направо, подвинуться на ячейку вперед. Для того чтобы съесть еду, муравью необходимо попасть в ячейку с ней. Ячейки с едой, в которых муравей уже побывал, неотличимы для него от исходно пустых ячеек.
Вручную построить муравья, съедающего всю еду на поле за отведенное количество ходов, очень сложно. В работе [4] предложен генетический алгоритм позволяющий построить автомат для указанной выше линии, названной в [5] «тропой Джона Мьюра» (John Muir Trail). Однако для эффективной работы алгоритма размер поколения должен быть около 70000. Поэтому построение автомата в данном случае занимает длительное время.
Для устранения указанного недостатка авторы предложили добавить в известный генетический алгоритм следующие операторы мутации:
• сортировка состояний автомата в порядке их использования – этот оператор мутации перенумеровывает состояния автомата таким образом, что меньшие номера получают те состояния, в которые автомат при моделировании муравья попадает раньше;
• всегда вперед, если впереди еда. Этот оператор изменяет значение выходной переменной на «вперед» для всех дуг переходов, помеченных входным воздействием, равным единице (в ячейке перед муравьем еда).
Помимо введения в алгоритм новых операторов мутации, авторы также изменили функцию приспособленности (количество съеденных единиц еды), добавив в нее следующее соотношение:
, где useful_state_count – число используемых состояний (состояния, в которые автомат попадает при моделировании поведения муравья).
Так как такая добавка всегда меньше единицы, то наиболее приспособленными будут те муравьи, которые съедают больше еды за 200 ходов. Если количество съеденной пищи одинаково, то предпочтение будет отдаваться автоматам с меньшим числом используемых состояний.
Благодаря предложенным в работе операторам мутации и новой целевой функции измененный алгоритм находит правильное решение при размере поколения, которое не превышает 10000. Предложенный в настоящей работе подход позволил уменьшить количество состояний у автоматов c тринадцати [4] и одиннадцати [5] до девяти.

Литература
1. Шалыто А.А., Технология автоматного программирования / Труды первой Всероссийской конференции “Методы и средства обработки информации”. М.: МГУ. 2003, с.528–535. http://is.ifmo.ru/works/tech_aut_prog.
2. Mitchell M. An Introduction to Genetic Algorithms. MIT Press. Cambridge. MA, 1996.
3. Лобанов П.Г., Шалыто А.А. Использование генетических алгоритмов для автоматического построения конечных автоматов в задаче о «флибах» / Материалы 1-й Российской мультиконференции по проблемам управления. Сборник докладов 4-й Всероссийской научной конференции "Управление и информационные технологии" (УИТ-2006). СПбГЭТУ "ЛЭТИ". 2006, с. 144–149. http://is.ifmo.ru/works/_flib.pdf.
4. Jefferson D., Collins R., Cooper C., Dyer M., Flowers M., Korf R., Taylor C., Wang A. The Genesys System: Evolution as a Theme in Artificial Life. 1992. www.cs.ucla.edu/~dyer/Papers/AlifeTracker/Alife91Jefferson.html.
5. Angeline P.J., Pollack J. Evolutionary Module Acquisition / Proceedings of the Second Annual Conference on Evolutionary Programming.1993. http://www.demo.cs.brandeis.edu/papers/ep93.pdf.

 



Санкт-Петербург, 18-21 июня 2007 г.
XIV Всероссийская научно-методическая конференция "Телематика'2007"