Содержание к диссертации
Введение
1. Анализ существующих разработок в области исследования эволюции сообществ искусственных существ
1.1. Анализ модели «Мозг анимата» 14
1.2. Анализ модели организации поведения — «животное» 18
1.3 Анализ модели «ПолиМир» Л.Ягера 21
1.4. Анализ модели взаимодействия обучения и эволюции Д. Экли и М Литтмана 23
1.5. Анализ проекта «Кузнечик» - модели эволюционного возникновения целенаправленного поведения 26
1.6. Анализ модификаций модели «Кузнечик» - исследование развития иерархии целей 29
1.7. Обобщение результатов 31
1.8. Выводы 34
2. Разработка модели анимата на базе модели «Кузнечик» 36
2.1. Построение модели мира анимата 36
2.2, Разработка модели анимата 37
2.3. Разработка структуры блока принятия решения 45
2.3.1 Построение управляющего блока с использованием нейросетей 47
2.3.2 Построение управляющего блока на базе систем нечеткого управления 51
2.3.3. Построение управляющего блока как экспертной системы 56
2.3.4. Построение управляющего блока как конечного автомата 57
2.3.5. Вывод 61
2.4. Разработка структуры блока адаптации поведения 62
2.5. Построение схемы эволюции популяции 65
2.6. Выводы 66
3. Синтез автомата, разработка алгоритмов обучения анимата 68
3-1. Общие сведения об автомате 68
3-2. Синтез оптимального вероятностного автомата 69
3.2.1. Разработка входного и выходного алфавита 70
3.2.2. Синтез таблиц переходов и выходов 77
3-3. Модель анимата на базе доверчивых и недоверчивых автоматов 85
3.4, Разработка алгоритма адаптации поведения 88
3.5. Исследования модели 92
3.5. Выводы І 00
4. Моделирование и оценка результатов экспериментов 102
4.1. Проведение моделирования 102
4.2. Определение критериев оценки качества результатов 105
4.3. Построение плана эксперимента и определение его параметров 108
4.4. Анализ полученных результатов 111
4.5. Применение разработанной модели 127
4.5. Выводы 130
Заключение 132
Список используемой литературы 134^
Приложения 144
- Анализ модели взаимодействия обучения и эволюции Д. Экли и М Литтмана
- Построение управляющего блока на базе систем нечеткого управления
- Разработка входного и выходного алфавита
- Построение плана эксперимента и определение его параметров
Введение к работе
Исследования в области искусственного интеллекта активно и являются актуальными во многих отраслях науки и техники. В начале 80-х годов в исследованиях появляется новое направление, называемое «Искусственная Жизнь», в задачи которого входят создание и изучение «более общих форм жизни» [1-3]. Исследователи ставили своей целью понимание общих принципов организации биологической жизни. Результаты, полученные в данной области, планировалось применить в таких областях как разработка мобильных роботов, медицина, социология, биология и других [4-8]. Направление базировалось на моделях, разработанных в 60-х годах М.Л. Цетлиным и М.М. Бонгардом, которые разработали ряд моделей, способных приспосабливаться к окружающей среде [9-11]. Модели не были реализованы технологически из-за своей громоздкости и вычислительной сложности.
В 90-х годах складывается еще одно направление, тесно связанное с «Искусственной Жизнью», называемое «Адаптивное Поведение», в задачи которого входит исследование принципов совместного функционирования животных в условиях изменяющейся среды [12, 13]. Исследователи, работающие в данном направлении стремятся проанализировать эволюционное развитие познавательных способностей животных и человека и получить модель зарождения и развития человеческого интеллекта [14, 15].
Основной метод работы в данном направлении - проведение компьютерного моделирования развития сообществ искусственных существ, способных приспосабливаться к окружающей среде. Эти создания -автономные роботы, наделенные некоторыми чертами поведения животных, их назвали «аниматами», от слов «animal» и «robot» [16-18]. Для исследований в области "Адаптивное Поведение" характерен специализированный метод конструирования архитектуры, обеспечивающей "интеллектуальное" поведение аниматов - исследователь сам разрабатывает данные архитектуры, по аналогии с теми структурами, которые
обеспечивают адаптивное поведение у реальных животных, например, моделируя потребности живого организма и механизм их удовлетворения [4, 19].
Исследователь также конструирует внешний мир для эволюционной системы, задавая физические законы и параметры, исходя из конкретных задач. Существа способны поддерживать свою жизнь, размножаться, гибнуть, взаимодействовать друг с другом. Механизм размножения искусственных существ позаимствован у биологических «аналогов»: родители передают ребенку свою генную информацию, которая определяет схему поведения животного, его параметры и т.д. При передаче информации возможны случайные мутации [20-22].
Сообщества аниматов относят к классу многоагентных компьютерных систем. Ключевое отличие моделей аниматов от других многоагентных систем является наличие эволюционных изменений в популяции, ее развитие за счет появление новых аниматов (ан и матов-потомков), несущих измененную генную информацию, подверженную также случайным мутациям. В общем случае, метод компьютерного моделирования искусственной жизни является стохастическим и его можно рассматривать как подмножество методов Монте-Карло [23].
Область применения моделей искусственной жизни разнообразна:
-случаи сложного и разнообразного поведения отдельных индивидуумов, например, в зависимости от локального окружения, приводящие к трудностям в получении системы уравнений, описывающих динамику популяции;
-решение трудно формализуемых задач;
-исследование когнитивной эволюции животных;
-задачи «управления роем» [12, [24-26].
Этот круг задач и определяет основное отличие «Адаптивного Поведения» и «Искусственной Жизни» от остальных исследований в области искусственного интеллекта: «создание аниматов ориентировано в конечном
7 итоге на решение ими нечетко сформулированных задач в плохо предсказуемой среде — т.е. таких, с которыми приходится иметь дело живым организмам. Аниматы создаются не для игры в шахматы, а для таких задач, как исследование поверхности планет в условиях, когда время и ресурсы робота ограничены, а местность не изучена» [27].
Сегодня можно также наблюдать бурное развитие именно тех технологий, для которых теория аниматов может быть использована в полной мере: нанотехнологий в роботостроении и рост вычислительных мощностей компьютерной техники [28],
Развитие индустрии компьютерных технологий привело сегодня к росту развития виртуальных пространств, заселенных виртуальными существами: программные агенты помогают модераторам отслеживать контент, отвечают на вопросы пользователей, являются партнерами человека в стратегических играх, следят за обновлениями новостей, отвечают за безопасность систем, осущетвляют тематический поиск в сети. Примеры таких виртуальных агентов можно увидеть на сайтах Ananova, Microsoft, Codeprogect, CodeGuru и других. Эти системы широко используются сегодня и имеют огромные перспективы развития. Рекламируя свою новую разработку в среде IT, компания Microsoft также обратилась к аниматам - в 2003-2004 году был проведен конкурс на лучшее искусственное животное в нити проектов MicrosoftResearch.
Теория аниматов нашла свое применение и в кино - для создания массовых батальных сцен создатели одного из самых кассовых фильмов «Властелин Колец» использовали компьютерную графику в сумме с моделированием поведения аниматов. Было написано специальное программное обеспечение для моделирования сражений существ двух видов, на основе которого были отрисованы сцены массовых сражений [24, 29].
Развитие технологий роботостроения в сторону уменьшения размеров привело к созданию многих проектов, которые также используют теорию аниматов для управления. Напримерэ в 2002 году в Intelligent Autonomous
8 Systems Laboratory Британского Университета был создан робот-садовник» небольшой мобильный робот для «ручной» очистки сада от слизняков. Робот получил название SIugBot, был опробован на реальных задачах и одобрен пользователями. С точки зрения «Адаптивного Поведения» SIugBot - не анимат в чистом виде, т.к. в сообществе роботов пока не реализованы механизмы самовоспроизведения, но, тем не менее, сообщество таких роботов может быть наделено «стадностью», они адаптивны, и это одна из первых весьма удачных разработок в данной области науки [30]. Беспилотные автобусы, построенные к проведению выставки EXPO 2005 компанией Toyota, также можно отнести к категории таких удачных моделей: автобусы имеют цель движения, собираются в стаи и разъединяются для выполнения собственных локальных задач [31],
Современные проекты с использованием нанороботов также пока не включают этап самовоспроизводства» но в будущем вполне могут это сделать согласно проекту «Roboblood», предлагающему заменить кровяные тельца человека сообществом нанороботов в ближайшем будущем [32].
Согласно описаниям этих настоящих и будущих проектов можно прогнозировать стремительное развитие теории аниматов, как одного из возможных путей управления роем нанороботов, а также интеллектуализации компьютерных игр и виртуальных сред, что указывает на актуальность работ в области построение моделей в областях «Искусственная Жизнь» и «Адаптивное Поведение».
Целью данной диссертационной работы является повышение эффективности существующих моделей сообществ аниматов, за счет разработки новой модели анимата, вычислительная сложность которой не превышает оценок n!og2(n), и затраты на модернизацию и адаптацию к конкретной задаче не превышают полиномиальных оценок. Рабочей гипотезой является предположение о том, что достичь поставленной цели можно, используя математический аппарат вероятностных автоматов.
9 Для достижения поставленной цели в работе решались следующие основные задачи:
анализ разработанных на данный момент моделей аниматов, а также моделей организации сообществ аниматов, анализ затруднений, возникающих при реализации тех или иных моделей, анализ трудозатрат на реализацию и модернизацию существующих моделей;
построение общей рабочей модели анимата, а также модели сообщества аниматов, оценка качества полученной модели, сравнение с аналогами;
абстрактный синтез автомата, принимающего решение о конкретном действии в данной ситуации, разработка универсального входного алфавита, классификация ситуаций состояния внешней и внутренней среды анимата с использованием фильтров восприятия;
построение алгоритма обучения анимата в условиях активной внешней среды.
Научная новизна данной работы заключается в следующем:
-разработана модель анимата на основе математического аппарата вероятностных автоматов;
-количество состояний внешней и внутренней среды сокращено за счет включения механизма фильтров восприятия в процесс сбора информации о состоянии среды;
-разработан универсальный входной алфавит для анимата, описывающий группы состояний внешнего и внутреннего мира, на основе аппарата регулярных выражений;
-разработан метод обучения аниматов на основе успешности выполняемых действий. Практическую ценность представляют:
-предложенная модель анимата на основе разработанного вероятностного автомата;
-разработанный алгоритм фильтрации информации о ситуациях внутреннего и внешнего мира анимата;
-принцип построения входного алфавита на основе группировки схожих ситуаций;
-полученные экспериментально оптимальные схемы поведения «животных» в результате эволюционных изменений в сообществе аниматов.
Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные САПР» (пос. Дивноморское 2004 г.), на Всероссийскх научных конференциях студентов и аспирантов «Радиоэлектроника, микроэлектроника, системы связи и управления» (г. Таганрог 2002 - 2004 гг.), внутри вузовских конференциях ТРТУ (2004 г.). Результаты диссертации отражены в 8 печатных работах. Основные результаты данной работы были использованы в г/б НИР № 12353 "Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений". Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ. Использование результатов диссертационной работы подтверждено соответствующими актами.
Диссертационная работа состоит из введения, четырех глав, заключения, приложений, списка использованной литературы из 114 источников и содержит 143 страницы основного текста, 46 рисунков и 17 таблиц. Общий объем работы 150 страниц.
Во введении обоснована актуальность диссертационной работы, выдвинута цель научного исследования, сформулированы основные научные положения, выносимые на защиту, приведены сведения о практической ценности, реализации и внедрении, апробации диссертационной работы, дано краткое содержание основных разделов диссертации.
В первой главе проанализированы существующие разработки в области «Искусственная Жизнь» и «Адаптивное Поведение» в рамках анализа проблем внедрения моделей, простоты реализации^ внутреннего устройства модели, вычислительной сложности используемых алгоритмов- Проведен сравнительный анализ моделей, обнаружена тенденция к использованию механизмов нейронных сетей в организации адаптивного поведения анимата. Выяснен факт недостаточного применения многих моделей в виду их вычислительной сложности. Выявлены недостатки существующих моделей. На основе проведенного анализа построена обобщенная модель анимата, а также типичная модель сообщества аниматов. Выявлен факт малой коммуникации существ одного вида, отсутствие кооперации животных. На основе проведенной работы сделаны выводы, выработаны рекомендации и изложены новые требования к разрабатываемым моделям анимата и сообщества аниматов.
Во второй главе определена постановка задачи, а также требования к быстродействию разрабатываемой модели. Описаны модель внешнего мира анимата и вопросы взаимодействия особей различных видов Произведен анализ методов организации управляющего блока как нервной системы согласно работам А.А. Жданова [33], рассмотрены вопросы реализации данного блока в виде нейросети, экспертной системы, вероятностного автомата, а также с использованием нечетких баз знаний. Проведены оценки сложности для каждого метода реализации, рассмотрены аспекты модернизации модели в каждом случае, произведены оценки трудозатрат при модернизации моделей. На основании проведенных исследований принято решение о реализации управляющего блока на основе конечного автомата.
В третьей главе произведена разработка модели анимата, сообщества аниматов, а также мира, в котором эволюционирует сообщество. Проведен абстрактный синтез управляющего вероятностного автомата. Разработан оптимальный универсальный входной алфавит на основе комбинации двух технологий: использования фильтров восприятия для минимизации входной
12 информации, группировка сходных ситуаций с использованием механизма регулярных выражений. Рассмотрены цетлиновские автоматы: пессимист и оптимист, с различной глубиной состояний. Рассмотрены достоинства и недостатки моделей, сделаны выводы.
В четвертом разделе определены цели экспериментального исследования и составлен план проведения эксперимента. Эксперимент можно разделить на 3 главные части: сравнительное исследование эффективности полученной модели, оценка качества реализованной модели, оценка механизмов обучения аниматов (без обучения, стандартная модель на основе оценок затрат энергетического ресурса, на основе успешности выполняемого действия). Проведены запланированные эксперименты. Произведена оценка эффективности алгоритма, подтверждена ожидаемая линейная вычислительная сложность модели. Проведен анализ влияния социальных мотиваций на развитие популяции, сделаны рекомендации по применению социальных мотиваций- Произведен анализ изменения стратегий поведения животных в зависимости от применяемых алгоритмов обучения. Предложены рекомендации по методам обучения в зависимости от решаемых задач. Произведен сравнительный анализ полученных стратегий поведения в данной диссертационной работе и базовой для данного направления работы ВТ* Редько «Модель Кузнечик» [22].
В заключении изложены основные выводы и результаты диссертационной работы,
В приложении приведены копии актов внедрения, подробные результаты экспериментов.
Анализ модели взаимодействия обучения и эволюции Д. Экли и М Литтмана
Агенты образуют эволюционирующую популяцию и обновляют ее состав за счёт скрещивания- Агенты могут обучаться: их действия определяются нейронной сетью, которая может совершенствоваться в течение жизни агента. Популяция хищников не эволюционирует: все хищники одинаковы, хищники не обучаются, их действия в любой ситуации одинаковы.
Механизм управления поведением агента реализован с использованием нейронной сети, входами которой являются состояние среды в области видимости и внутреннее состояние агентов, выходы — сигнал о предпринимаемом действии. Набор действий заключатся только в движении в одном из четырех направлений, дальнейшая судьба агента определяется содержимым той клетки, в направлении которой движется агент.
Нейронная сеть (НС) имеет несколько необычную структуру - она состоит из двух блоков: блока поведения (определение направления движения) и блока оценки (обучение НС блока поведения). Блок оценки действий вырабатывает обучающий сигнал, который показывает, улучшилось или ухудшилось состояние агента в результате выполненного действия. Таким образом, нейронная сеть изменяется и в ходе эволюции, и в индивидуальном процессе обучения. Геном агента содержит веса синапсов блока оценки действий и начальные веса синапсов блока поведения.
Обучение блока поведения осуществлялось модифицированным методом обратного распространения ошибки, Основная идея метода состоит в том, что ошибка на выходе каждого нейрона блока поведения определяется по выходу данного нейрона и по сигналу обучения г, поступающего от блока оценки действий. Сигнал обучения г может быть положительным или отрицательным. В соответствии с ошибками на выходах нейронов корректируются веса синапсов нейронов, аналогично тому, как это делается в обычном методе обратного распространения ошибок,
Результатом проведенных исследований стала реализация трёх моделей: только эволюция; только обучение; эволюция и обучение.
Первоначальный состав популяции во всех трёх случаях генерировался по одинаковым принципам, затем авторы замеряли насколько «живучей» оказалась та или иная популяция [34].
Результаты экспериментов демонстрируют, что для данной модели агентов одна эволюция без обучения плохо обеспечивает адаптацию популяции агентов; обучение приводит к лучшей адаптации» но наилучший результат наблюдается в случае совместной работы эволюции и обучения, В этом последнем случае находились агенты, которые не вымирали на протяжении миллиона тактов жизни агентов. Авторы также обнаружили в такой модели и эффект успешного появления врожденных навыков [22].
Несмотря на перегруженность эксперимента деталями, что не всегда даёт достаточно чёткую картину событий — иногда трудно выделить влияние тех или иных деталей среды в общей массе факторов обучения и прогресса популяции - основной результат исследования имеет теоретический и практический интерес. Сумма эволюционных и обучающих механизмов ведет к лучшей приспособляемости организмов и более успешному развитию популяции в целом.
В данной модели также трудно говорить о взаимодействии агентов и формировании общего целенаправленного поведения, В качестве механизма принятия решения используется нейронная сеть, модифицированной структуры (с целью осуществлять обучение)- Модель управления проста в реализации, в отличие от модели мира, которая переполнена деталями, что затрудняет её использование в дальнейших экспериментах.
Авторами данной модели являются М.С. Бурцев, Р.В. Гусаров» ВТ. Редько [22]. Общая задача исследований может быть сформулирована следующим образом; изучение сущности целенаправленного поведения и путей его возникновения в процессе эволюции живых существ. Авторы утверждают, что главная задача для всех живых существ - поддержание и развитие собственной жизни. Решая эту задачу, живые существа нередко проявляют сложное адаптивное поведение, разбивая при этом процесс достижения какой-либо цели на несколько этапов. Подобное поведение можно назвать целенаправленным. При создании данной модели авторы попытались выделить и исследовать наиболее общие функциональные свойства, определяющие возможность возникновения целенаправленного поведения.
Основная концепция, использованная авторами при построении модели - концепция мотивации. Влияние мотивации на поведение животного наглядно показано в схеме функциональной системы, предложенной П-К, Анохиным [39]. В данной модели мир анимата разделяется на внутренний и внешний. Внешний мир - поле, заселенное аниматам и травой. Внутренний мир представлен набором потребностей, формируемых мотивациями [44], набор мотиваций и их формирование показаны на рисунке 1,5.
Схема управления модели на основе адаптивного поведения изображена на рис. Кб, Информация о внутреннем и внешнем мире поступает на вход нейросети, которая производит принятие решения о необходимом действии. Общая схема модели изображена на рис. 1.7. Параметры нейросети модифицируются в процессе эволюции популяции агентов. Агенты образуют популяцию, которая пополнятся за счет скрещивания, которое приводит к появлению нового агента - «потомка», которому родители передают параметры нейросети.
Построение управляющего блока на базе систем нечеткого управления
Аналогичным образом могут быть заданы и все остальные ЛП, имеющие отношения к мотивациям: «мотивация агента к скрещиванию», «мотивация к скрещиванию правого соседа» и «мотивация к скрещиванию левого соседа»,
После задания всех ЛП, характеризующих внешний и внутренний мир, входных параметров системы нечеткого управления, необходимо определить выходные параметры. Выход у системы один — рекомендуемое действие, одно из 7 возможных для «Кузнечика».
Определив все переменные входов и выходов, создадим базу знаний (БЗ) правил, сопоставляющих ситуации внешнего и внутреннего мира анимата - входные параметры для системы управления — рекомендуемым действиям в данной ситуации. В общем случае каждое правило имеет вид: «если параметр 1 соответствует терму / и параметр 2 соответствует терму/ .., и параметр п соответствует терму к , то выходной параметр 1 соответствует терму / , выходной параметр 2 соответствует терму р ,... выходной параметр m соответствует терму/ », при этом осуществляется перебор по всем термам каждого входного параметра. Общее количество правил в БЗ равно произведению количества термов каждой ЛП, в нашем случае» количество правил вычисляется исходя из того что: -ЛП описывающие наличие пищи и соседей имеют по два терма, и таких ЛП 5 (наличие соседа справа, наличие соседа слева, наличие еды справа, наличие еды слева, наличие еды в текущей клетке); -ЛП описывающие мотивации агента имеют по 5 термов, и таких ЛП 2 (по количеству мотиваций); —ЛП описывающие мотивацию к скрещиванию двоих соседей имеют по 5 термов, и таких ЛП 2 (для соседа слева и для соседа справа), что в итоге даст 20 000 правил. При этом, объем базы знаний может быть сокращен за счет объединения ситуаций и выделений доминирующих входов, но в общем плане подобное сокращение незначительно. Оценим количество операций для осуществления вывода, вывод осуществляется при помощи следующего набора действий: 1) перевод входной ситуации в термины ЛП: - цикл по всем параметрам, - цикл по всем ЛП параметра, - если значение (параметр) максимально, параметр і соответствует терму/, 2) поиск в базе необходимого правила: - в лучшем случае правила образуют массив и процесс поиска правила сводится к обращению к элементу массива, - в худшем случае производится тестовый поиск по базе знаний, для которого применяется алгоритм бинарного поиска, 3) дефазификация полученного вывода, перевод его в управляющий сигнал: - цикл по всем ЛП вывода, - расчет управляющего сигнала. Вычислительная сложность в этом случае зависит от эффективности механизма поиска ситуаций в базе (в худшем случае оценка составляет 0(tog2(tt)))7 где п - размерность базы знаний [65]. Размерность базы зависит от количества параметров, управляющих сигналов и от количества термов для соответствующих ЛП, Обозначим к - количество параметров, Р -множество соответствующее количествам термов для каждой ЛП параметров, А - количество управляющих сигналов, W - множество соответствующее количествам термов для каждой ЛП выходов, тогда количество операций (s) может быть выражено следующим образом: Размер базы знаний взят как произведение количеств термов для ЛП параметров- В рассматриваемой модели количество выходов равно 1, поэтому при получении оценок О последним слагаемым суммы можно принебречь, а среди двух элементов - суммы и произведения, быстрее растет произведение» поэтому оценка О принимает вид: где п - размер базы знаний. Рассмотрим вопросы масштабируемости такой системы управления. Здесь все возможные изменения в мире анимата (расширение кругозора и появление новых мотиваций) приводят к появлению новых ЛП, что влечет увеличение размера базы знаний в практически геометрической прогрессии-Затраты на поиск правил останутся прежними» а вот затраты на обновление самой базы и переформулировку правил огромны и требуют значительных усилий эксперта. Добавление нового действия в шаблоны поведения анимата не приводит к росту размера БЗ, но приводит к переформулированию всех существующих правил.
Стоит также дополнительно отметить, что механизмы нечеткого управления обычно не имеют механизмов саморегуляции, и все правила всегда остаются в том виде, в котором из занес в систему эксперт [33].
В целом по вопросу использования систем нечеткого управления как блока управления поведением анимата можно отметить, что затраты по использованию данной системы минимальны (не более 0(log(n))\ но каждая модификация модели приводит к вмешательству экспертов и длительной переработке правил из БЗ. Кроме того, весьма затруднительно применение механизмов адаптации в контексте подобных систем.
Разработка входного и выходного алфавита
В данной главе производится абстрактный синтез вероятностного автомата, на основании работы которого осуществляется принятие решений о действиях, оптимальных в условиях изменяющейся внешней среды. Так же необходимо разработать алгоритмы обучения анимата - правила изменения вероятностей в таблице смены состояний разработанного автомата.
Автомат, принимающий решения о необходимых действиях, получает на вход данные о внешнем и внутреннем мире, и в качестве выходного сигнала должен выдать рекомендуемое действие. Поскольку набор ситуаций мира конечен, так же как и набор действий, то сам автомат приобретает вид дискретного преобразователя ситуаций окружающей среды в сигналы действий.
Дискретный автомат имеет входы, на которые поступают буквы входного алфавита, и выходы, на которых появляются буквы выходного алфавита [74, 85, 86]. В случае использования автомата для управления аниматом логично предположить наличие двух входов - для восприятия сигналов внутреннего и внешнего мира, и одного выхода — для вывода сигнала о рекомендуемом действии. Конечный автомат задается совокупностью следующих объектов; U - конечное множество входных сигналов, называемое входным алфавитом; V — конечное множество выходных сигналов, называемое выходным алфавитом; А — произвольное множество, называемое множеством внутренних состояний; ao - элемент из множества 4, называемый начальным внутренним состоянием; 5(А,и) - функции переходов автомата; X(At U) - функции выходов автомата, [87], При подаче входного сигнздіа V(t) происходит изменение его внутреннего состояния из a(t-l) в a(t)9 причем сигнал V(t) может появиться на выходе либо раньше момента перехода автомата из состояния a(t-l) в a(t)y либо позже него. Для задачи управления аниматом рассмотрим второй случай, сигнал о состоянии внешней среды побуждает автомат к смене состояния и выдаче нового выходного сигнала. В детерминированных автоматах последовательности символов выходного алфавита однозначно определяются последовательностями символов входного алфавита. Вероятностные автоматы вырабатывают случайные последовательности символов выходного алфавита при фиксированных последовательностях входного алфавита. В вероятностных автоматах появление того или иного символа выходного алфавита имеет определенную вероятность, тогда функция выходов имеет вид %(А, U) = P(At V)t где Р- некоторый закон распределения [75]. Синтез конечных автоматов содержит два этапа: абстрактный и структурный. Абстрактный синтез включает вопросы задания автомата при помощи алфавитов и таблиц, не останавливаясь на вопросах реализации самого устройства, которые относятся к разделу структурного синтеза, В данной работе вопросы структурного синтеза автомата не рассматриваются, так как автомат будет реализован программно [88, 89]. Задача абстрактного синтеза заключается в разработке входного и выходного алфавитов, а также в создании таблиц смены состояний автомата и таблицы выходов [90]. Разрабатываемый входной алфавит, описывающий состояния внешней среды, должен удовлетворять следующим критериям: -универсальности - не зависеть ни от размерности внешнего мира, ни от количества видов живых существ в мире» -оптимальности — количество символов минимально, нет двух различных символов, описывающих одинаковые ситуации, -полноты — множество символов входного алфавита должно покрывать все возможные ситуации внешней среды. Разрабатываемый выходной алфавит также должен удовлетворять условию полноты, кроме того, необходимо обеспечить легкость адаптации алфавита к изменениям в структуре внутреннего мира анимата [90], [91]. Разработка входного алфавита Анимат может видеть мир вокруг себя на / клеток вокруг, параметр / характеризует «остроту зрения» анимата, тогда количество видимых клеток легко вычислить по формуле п = (2-/ +1)2, как показано нарис, 3-L Заметим при этом» что данная формула может быть модифицирована для применения в пространстве любой размерности Каждая клетка пространства может быть занята другим аниматом, травой или оставаться пустой. В «Кузнечике» существуют аниматы только одного вида, что дает 3 возможных состояния для каждой клетки, в новой модели сосуществуют аниматы двух видов, поэтому теперь необходимо учесть не только тот факт, что клетка занята, но еще и кем она занята — {анимат первого вида, анимат второго вида}, следовательно, количество состояний окружающего мира анимата будет вычислено следующим образом:
Построение плана эксперимента и определение его параметров
Были синтезированы управляющие автоматы трёх видов - наиболее оптимальный вероятностный автомат, в виде комбинационной схемы; довольно простой автомат с нелинейной тактикой поведения - доверчивый и недоверчивый; сложный автомат с комбинированной структурой, сочетающий элементы вероятностного и недоверчивого автомата. Из всех разработанных схем принята для реализации первая - как наиболее оптимальная.
Применение описанного алгоритма разбора ситуаций внешней среды в сумме с полученной моделью управляющего автомата позволяет сократить сложность алгоритма принятия решения об оптимальном действии на порядок по сравнению с моделью «Кузнечик», использующей для этих целей нейросеть.
Построен алгоритм работы блока адаптации поведения, позволяющий вносить значительные изменения в значение вероятностей выходов автомата, реализующего поведение анимата, при этом вероятность изменения зависит от успешности жизненной стратегии анимата. Данный алгоритм учитывает текущий запас энергетического ресурса особи, количество ресурса может служить сигналом об оптимальности поведения: чем успешнее поведение, тем больше ресурса может накопить анимат.
Дальнейшая задача заключается в проведении моделирования развития популяции и экспериментального подтверждения высказанной гипотезы о том, что применение математического аппарата вероятностных автоматов позволит реализовать модель анимата не уступающего «Кузнечику» по таким параметрам как функциональность и адаптивность, и превосходящую по таким показателям как масштабируемость модели, быстродействие и открытость к модификациям. Необходимо провести серии экспериментов и сравнить экспериментально упомянутые показатели для модели «Кузнечик» и для разрабатываемой модели.
В данной главе описывается процесс проведения моделирования с целью общей оценки разработанной модели, а также экспериментальной проверки высказанной гипотезы о том, что модель, построенная на основе математического аппарата вероятностных автоматов, будет обладать большей гибкостью и меньшей вычислительной сложностью, чем распространенные модели на основе нейронных сетей.
Проводится оценка результатов моделирования как по критериям качества модели (показатели качества жизни аниматов, оптимальность выработанных стратегий поведения), так и по показателям быстродействия.
Моделирование проводится программно, программа написана на языке С#, под Microsoft .Net Framework Л ft Язык программирования С# выбран в силу гибкого распределения памяти, оптимальности расположения объектов в памяти, надежной системы возбуждения и перехвата исключений [105, 106]. Технология программирования выбрана объектная, т.к. агенты сами по себе органично вписываются в теорию ООП [12], [107, 108].
Структура объектов представлена на рис, 4Л [109]: основным объектом моделирования является объект BaseBeing - обобщенное описание искусственного организма, задающее все базовые функциональности существа: вычисление значений мотиваций, изменение энергетического ресурса, принятие решения и т.д. Для добавления нового вида существ в мир необходимо унаследовать новый класс от BaseBeing и задать наборы мотиваций для него, на рисунке указаны три типа существ: трава, хищник и травоядное. Мотивации также являются отдельными объектами. Функция принятия решения, а также хромосомный набор определяется для организма классом-родителем, который зависит от проводимого эксперимента, либо автомат (Automation) для реализации разрабатываемой модели, либо нейронная сеть (MS) для исследования «Кузнечика».
Все аниматы содержатся в контейнере поле (класс Field), сам процесс моделирования состоит из несложного набора действий: - взять клетку поля, - вызвать для существа в клетке функцию определения действия, - вызвать функцию-делегат для выполнения выбранного действия, - проверить успешность выполненного действия и провести обучение/разобучение для данной ситуации, - произвести мутацию организма с некоторой долей вероятности. Все перечисленные функции являются пустыми для «травы», так как. трава не выполняет никаких действий, а является живым объектом лишь для однообразия интерфейса. Функциональная декомпозиция процесса моделирования представлена на рис. 4.2. Каждую итерацию каждый живой объект сохраняет данные о себе в базу данных логов [110], Лог ведется в следующем формате: - данные о координатах и такте времени моделирования, - данные о запасе энергетического ресурса и о величинах мотиваций анимата, - данные о системном времени. Процесс модернизации модели выглядит следующим образом; добавление новых мотиваций: наследуем новый класс от CommonMotivation, переопределяем функцию расчета величины мотивации в зависимости от запаса ресурса, добавляем новую мотивацию в конструктор модернизируемого существа, изменяем размерность таблицы выходов автомата; добавление новых действий, совершаемых животным - определяем новую функцию для нового действия, регистрируем ее как делегата, изменяем размер таблицы для автомата;
