Д. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов»




Скачать 86.31 Kb.
НазваниеД. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов»
Дата публикации08.05.2013
Размер86.31 Kb.
ТипОтчет
vbibl.ru > Информатика > Отчет

Санкт-Петербургский государственный университет

Информационных технологий, механики и оптики

Факультет «Информационные технологии и программирование»

Кафедра «Компьютерные технологии»




Д.С.Чивилихин


Отчет по курсовой работе

«Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов»




Санкт-Петербург

2011

Оглавление

1Введение………………………………………………………………………….3

2Описание алгоритма………………………………………………………………3

2.1Схема работы алгоритма………………………………………………………..3

2.2Чтение входных данных……………………………………………………….3

2.3Формирование пространства поиска………………………………………….4

2.4Инициализация муравьиного алгоритма……………………………………….4

2.5Запуск муравьев на недетерминированном конечном автомате……………..4

2.6Вычисление функции приспособленности построенного ДКА………………5

2.7Откладывание феромона построенным ДКА на ребрах НКА………………5

2.8Откладывание феромона лучшим из построенных ДКА……………………..5

2.9Испарение феромона…………………………………………………………..5

2.10 Проверка выходных условий………………………………………………..5

3Применение предложенного метода для построения управляющих автоматов на основе тестов…………………………………………………………………………….5

3.1Описание метода построения автоматов на основе тестов…………………………..5

3.2Построение автомата управления часами с будильником с помощью муравьиных алгоритмов на основе тестов ………………………………………………………….6

4Заключение……………………………………………………………………………..7

5Литература……………………………………………………………………………..7



1Введение


Целью настоящей работы является разработка метода построения управляющих автоматов с применением идей муравьиных алгоритмов.

Муравьиные алгоритмы, также известные как ^ Ant colony optimization algorithms, давно и успешно используются в решении задач оптимизации на графах, таких как, например, задача о коммивояжере. Пространством поиска в этой задаче является граф, а результатом работы муравьиного алгоритма – гамильтонов путь в этом графе.

Перейдем к формулировке задачи. Пусть задано количество состояний, множество входных воздействий (^ Events) и множество выходных воздействий (Actions) конечного автомата. Пусть на множестве всех автоматов с заданными выше параметрами (количество состояний, множество входных и выходных воздействий) задана функция, отражающая степень “приспособленности” автомата – фитнес-функция. Задача состоит в отыскании автомата, максимизирующего данную функцию.

Ясно, что любой автомат из выбранного множества автоматов является подмножеством недетерминированного конечного автомата с теми же параметрами (здесь мы рассматриваем автоматы как множества переходов и состояний). Итак, сформулируем задачу для муравьиного алгоритма оптимизации.

Задано множество входных воздействий(^ Events), множество выходных воздействий(Actions) и количество состояний numberOfStates детерминированного конечного автомата. Задана функция на множестве всех детерминированных конечных автоматов с указанными параметрами, отображающая автомат в действительное число. На полном недетерминированном конечном автомате с теми же параметрами требуется найти путь, проходящий через все вершины (возможно, не один раз), такой, что детерминированный конечный автомат, соответствующий найденному пути, имеет наибольшую функцию приспособленности.

2Описание алгоритма

2.1Схема работы алгоритма


    1. Чтение входных данных;

    2. Формирование пространства поиска – полного недетерминированного конечного автомата с заданными параметрами;

    3. Инициализация муравьиного алгоритма

    4. Запуск муравьев на недетерминированном конечном автомате – получение списка переходов, которые сделали муравьи;

    5. Формирование детерминированного конечного автомата по полученному списку переходов;

    6. Вычисление функции приспособленности построенного детерминированного конечного автомата;

    7. Откладывание феромона построенным автоматом на ребрах НКА;

    8. Откладывание феромона лучшим построенным автоматом;

    9. Испарение феромона;

    10. Проверка выходных условий.

2.2Чтение входных данных


Входные данные алгоритма подразделяются на:

  • Параметры искомого автомата;

    • Количество состояний – numberOfStates;

    • Множество входных воздействий – Events;

    • Множество выходных воздействий – Actions;

  • Параметры муравьиного алгоритма;

    • Скорость испарения феромона – evaporationRate;

    • Максимальное количество шагов алгоритма – maxNumberOfSteps;

    • Значение функции приспособленности, при котором алгоритм завершает свою работу – goalFitness;

  • Параметры задачи.


Здесь под параметрами задачи понимается информация о решаемой автоматом задаче, которая используется при вычислении функции приспособленности. Вот некоторые примеры параметров задачи:

  • Поле в задаче об умном муравье;

  • Набор тестов в задаче о построении управляющих автоматов на основе тестов.

2.3Формирование пространства поиска


На этом этапе формируется полный недетерминированный конечный автомат с заданным количеством состояний и множествами входных и выходных воздействий. Под полным недетерминированным конечным автоматом понимается автомат, у которого из каждого состояния по каждому входному воздействию существует переход во все состояния с каждым из возможных выходных воздействий.

2.4Инициализация муравьиного алгоритма


Инициализация муравьиного алгоритма состоит в том, что всем ребрам (переходам) недетерминированного конечного автомата ставится в соответствие некоторый вес, равный минимальному значению феромона.

2.5Запуск муравьев на недетерминированном конечном автомате


Этот основной этап алгоритма состоит из следующих подпунктов:

  • Хранится список переходов, которые муравьи делают в НКА – visitedTransitions;

  • В каждую вершину НКА помещается муравей;

  • Каждый муравей с помощью метода “рулетки” определяет наиболее выгодный переход по каждому из входных воздействий; выбранные переходы добавляются в список visitedTransitions;

  • По полученному списку переходов visitedTransitions строится детерминированный конечный автомат.


Заметим, что автомат, полученный на этом шаге алгоритма, содержит все состояния НКА, и содержит переходы по каждому входному воздействию из каждого состояния.

Данная особенность алгоритма может стать помехой для задач, в которых требуется помимо максимизации функции приспособленности минимизировать число переходов в автомате.

В данной работе предлагается использовать предлагаемый метод в комбинации с эволюционными стратегиями. Использованная стратегия заключается в мутировании получаемых автоматов для минимизации количества переходов. Мутации заключаются в удалении некоторых переходов из автомата.

2.6Вычисление функции приспособленности построенного ДКА


На этом шаге построенному ДКА сопоставляется действительное число с помощью вычисления функции приспособленности. Здесь используются параметры задачи, о которых упоминалось в п.2.2.

2.7Откладывание феромона построенным ДКА на ребрах НКА


На данном шаге алгоритма обновляется значение феромона на ребрах, которые посетили муравьи при построении последнего ДКА. К значению феромона на этих ребрах прибавляется величина, пропорциональная функции приспособленности ДКА.

2.8Откладывание феромона лучшим из построенных ДКА


В данной работе в качестве модификации муравьиного алгоритма используется система “элитарный муравей” (Elitist ant system) Модификация заключается в том, что лучшая особь (ДКА) на каждом шаге алгоритма откладывает феромон наряду с текущей особью. Такая модификация существенно повышает устойчивость алгоритма.

2.9Испарение феромона


На этом шаге количество феромона на всех ребрах НКА уменьшается в (^ 1 – evaporationRate) раз. Значение параметра evaporationRate подбирается индивидуально для каждой задачи.

2.10 Проверка выходных условий


Если значение функции приспособленности лучшей особи не меньше, чем минимальное требуемое значение goalFitness, алгоритм прекращает свою работу, выдавая на выход лучший построенный автомат. Если значение приспособленности меньше, чем goalFitness, муравьи запускаются на НКА еще раз.

3Применение предложенного метода для построения управляющих автоматов на основе тестов

3.1Описание метода построения автоматов на основе тестов


Описанный метод построения автоматов в данной формулировке позволяет применять его к весьма широкому классу задач. Интересным примером служит использование метода для построения автоматов с заданным поведением на основе тестов.

Тест представляет собой последовательность входных воздействий Events[i] и ожидаемую последовательность выходных воздействий Actions[i], которую должен сгенерировать автомат.

Параметрами задачи в данном случае является набор тестов, а вычисление функции приспособленности автомата основано на редакционном расстоянии (расстоянии Левенштейна). Для вычисления функции приспособленности автомату подается на вход каждая из входных последовательностей Events[i]. Получив на вход данную последовательность, автомат генерирует последовательность выходных воздействия Output[i]. Далее вычисляется величина:

.

Отметим, что значения этой величины лежат между 0 и 1 и она тем больше, чем «лучше» автомат соответствует тестам. Сама функция приспособленности учитывает не только прохождение тестов, но и количество переходов в автомате, и вычисляется по формуле:



Здесь за T – «стоимость» прохождения всех тестов, а numberOfTransitionsколичество переходов в автомате.

3.2Построение автомата управления часами с будильником с помощью муравьиных алгоритмов на основе тестов


Предложенный метод построения управляющих автоматов с заданным поведением был протестирован на задаче о построении автомата управления часами с будильником, описанной в [1]. В качестве набора тестов был выбран набор из 38 тестов, которые были использованы в [2] и [3] для построения автомата управления часами с будильником различными методами.

После построения автомата, проходящего все тесты, для уменьшения количества переходов в автомате была применена эволюционная стратегия, описанная в п.2.5. Для вычислений использовался компьютер с процессором Intel Core i3 380M с тактовой частотой 2.53 ГГц и 3Gb RAM.

В результате работы муравьиного алгоритма был получен автомат с 21 переходом, удовлетворяющий всем тестам и имеющий функцию приспособленности, равную 100.79. Для построения этого автомата потребовалось 156412 вычислений функции приспособленности и 52 секунды. Затем была применена эволюционная стратегия, в результате работы которой был получен автомат с функцией приспособленности, равной 100.86 и имеющий 14 переходов. Для этого потребовалось менее 2000 вычислений функции приспособленности и 1 секунда.

Итак, за ^ 53 секунды и 158412 вычислений функции приспособленности был получен автомат, приведенный на рисунке, удовлетворяющий всем тестам и содержащий 3 состояния и 14 переходов.



Рисунок. Автомат управления часами с будильником, построенный с помощью муравьиного алгоритма и эволюционной стратегии
Можно заметить, что полученный автомат изоморфен автомату, полученному в [2] и [3].

4Заключение


Разработан метод построения управляющих автоматов с помощью муравьиных алгоритмов и написана программа на языке Java, реализующая этот метод. Метод протестирован на задаче о построении управляющих автоматов на основе тестов и показал результаты в производительности, сравнимые с результатами в [2] и [3]. Был получен автомат управления часами с будильником, изоморфный автоматам, построенным в [2] и [3].

Предложенный метод построения автоматов является достаточно общим и может быть применен для построения управляющих автоматов для любых задач, для которых можно ввести функцию приспособленности автомата, определенную на множестве всех автоматов с заданными параметрами.

5Литература


  1. Поликарпова, Н.И., Шалыто А.А. Автоматное программирование. СПб: Питер, 2009.

  2. Царев Ф.Н. Метод построения автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования / Материалы Международной научной конференции «Компьютерные науки и информационные технологии». Саратов: СГУ, 2009, с.216-219.

  3. К.В. Егоров, Ф.Н. Царев. Совместное применение генетического программирования и верификации моделей для построения автоматов управления системами со сложным поведением / Сборник докладов конференции молодых ученых и специалистов «Информационные технологии и системы». М.: ИППИ РАН, 2009, с.77-82.


Добавить документ в свой блог или на сайт

Похожие:

Д. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов» iconИнформационных технологий и программирования
Применение генетического программирования для построения управляющих автоматов 11

Д. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов» iconИнформационных технологий и программирования
Класс StatusEvent 10 Глава Применение генетического программирования для построения управляющих автоматов 12

Д. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов» iconПояснительная записка к курсовой работе по дисциплине «Теория автоматов»
Курсовая работа по теории автоматов выполняется с целью закрепления ранее полученных знаний, приобретения навыков и умений самостоятельного...

Д. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов» iconСодержание 2
«Умном муравье». Даже для этой относительно простой задачи полный перебор крайне трудоемок, а эвристическое построение задачу не...

Д. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов» iconОтчетов, то в этом случае по сути решается задача оценивания функции
Рассматриваются вопросы построения моделей дрейфа с использованием искусственных нейронных нейронных сетей. Предлагается новый метод...

Д. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов» iconПояснительная записка к курсовой работе по дисциплине «Теория автоматов»
Ученик может исправить полученную оценку. Завуч может добавить информацию о новом учителе или ученике, а также удалить о выбывших....

Д. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов» iconБаранов С. И. Синтез микропрограммных автоматов. 2-е изд
Баранов С. И. Синтез микропрограммных автоматов. 2-е изд., перераб и доп. Л. Энергия Ленингр отд-ние, 1979

Д. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов» iconОтчет по лабораторной работе должен содержать: постановку задачи об «Умном муравье»
Мили, решающий задачу об «Умном муравье». Используйте представление автоматов с помощью битовых строк. Способ скрещивания выберите...

Д. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов» iconА. Н. Кузнецов, Е. В. Пышкин
Применение онтологий для построения пользовательского интерфейса к системам web-поиска

Д. С. Чивилихин Отчет по курсовой работе «Применение муравьиных алгоритмов для построения управляющих автоматов на примере построения автоматов на основе тестов» iconЯвляется одной из трех важнейших незаменимых аминокислот, которые...
Он является основой для построения белков нашего тела. Лизин – первая из лимитирующих аминокислот, необходимых для усвоения пищевых...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница