Интеллектуальные информационные системы

Шаг 5. Проверка на достижение оптимального результата. Проверка может выполняться для постоянного количества путей или к моменту, когда на протяжении нескольких запусков не было получены повторные изменения в выборе наилучшего пути. Если проверка дала положительный результат, то происходит окончание работы метода (переход к шагу 7), в противном случае - переход к шагу 6.

Шаг 6. Повторный запуск. После того как путь агента завершен, грани обновлены согласно длины пути и состоялось испарение феромона на всех гранях, метод выполняется повторно. Список табу очищается, и длина пути обнуляется. После этого выполняется переход к шагу 3.

Шаг 7. Конец. Определяется лучший путь, который и является решением.

Демонстрационный пример

Разберем функционирование рассмотренного выше алгоритма на простом примере, чтобы увидеть, как работают уравнения. Возьмем простой сценарий с двумя муравьями из примера который рассмотрен выше. На рис. 33 показан этот пример с двумя ребрами между двумя узлами (V₀ и V₁). Каждое ребро инициализируется и имеет одинаковые шансы на то, чтобы быть выбранным.

Рис. 33 Инициализация алгоритма

Рис. 34 Момент достижения цели

Два муравья находятся в узле V₀ помечаются как A₀ и A₁. Так как вероятность выбора любого пути одинакова, в этом цикле проигнорируем уравнение выбора пути. Данные для задачи:

число пройденных шагов: для A₀ ? 20, для A₁ ? 10

уровень феромона (Q/пройденное расстояние): для A₀ ? 0.5, A₁ ? 1.0

с = 0.6

б = 0.3

Размещено на http://www.allbest.ru/

в = 1.0

На рис. 33 кРазмещено на http://www.allbest.ru/

аждый муравей выбирает свой путь (муравей A₀ идет по верхнему пути, а муравей A₁ - по нижнему). Муравей A₀ сделал 20 шагов, а муравей A₁, - только 10. По формуле (31) рассчитывается количество феромонов, которое должно быть "нанесено".

Примечание: Работу алгоритма можно изменить, переопределив его параметры (например, б, в или p), например придав больший вес феромонам или расстоянию между узлами.

Далее по формуле (32) рассчитывается количество феромона, которое будет применено.

Для муравья A₀ результат составляет:

Для муравья A₁ результат составляет:

Далее с помощью формулы (33) определяется, какая часть феромонов испарится и, соответственно, сколько останется. Результаты (для каждого пути соответственно) составляют:

Эти значения представляют новое количество феромонов для каждого пути (верхнего и нижнего, соответственно). Затем, переместив муравьев обратно в узел V₀, используется формула выбора пути (30), чтобы определить, какой путь должны выбрать муравьи. Вероятность того, что муравей выберет верхний путь (представленный количеством феромона 0,16), составляет:

Вероятность того, что муравей выберет нижний путь (представленный количеством феромона 0,28) составляет:

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

Области применения

Алгоритм оптимизации муравьиной колонии может быть успешно применен для решения сложных комплексных задач оптимизации. Цель решения сложных комплексных задач оптимизации - поиск и определение наиболее подходящего решения для оптимизации (нахождения минимума или максимума) целевой функции (цены, точности, времени, расстояния и т.п.) из дискретного множества возможных решений. Типичный пример решения подобной задачи - квадратичная задача о назначениях, задача календарного планирования, задача маршрутизации транспорта, различных сетей (GPRS, телефонные, компьютерные и т.п.), распределение ресурсов и работ. Эти задачи возникают в бизнесе, инженерии, производстве и многих других областях. Исследования показали, что метод муравьиных колоний может давать результаты, даже лучшие чем при использовании генетических алгоритмов и нейронных сетей.

6.3 Порядок выполнения лабораторной работы

1. Разработать программное обеспечение, которое реализует метод муравьиных колоний для выбора оптимального маршрута обхода графа. Количество вершин графа должно определяться пользователем при запуске программы. Каждое ребро имеет свой вес, означающий его длину. Рекомендованные значения параметров: 1, 5, 0,5, Q1000 при условии, что длины дуг находятся в диапазоне (0; 100].

2. Для гибкости программного обеспечения все параметры метода (например, количество агентов, коэффициент испарения и т.д.) сохранять в переменных или константах.

3. Для реализации агентов, которые моделируют поведение муравьев, использовать структуру, которая имеет следующие поля:

- текущая позиция, в которой находится агент;

- следующая позиция;

- список табу, в котором хранятся те пункты, в которых уже побывал агент;

- количество пунктов, который уже посетил агент;

- массив путешествия, где хранится последовательность пунктов, в которых побывал агент;

- длина пути, который прошел агент. Рассчитывается после окончания путешествия.

4. Выделить основные этапы метода в отдельные функции:

- инициализация метода;

- моделирование перемещения агентов;

- выбор следующего пункта;

- обновление феромонов на путях;

- перезагрузка агентов.

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

5. Выполнить тестирование разработанного программного обеспечения с помощью решения конкретных примеров задачи коммивояжера. Задачи (не меньше трех) для выполнения тестирования программы сформулировать самостоятельно.

6. Оформить отчет.

7. Ответить на контрольные вопросы.

6.4 Контрольные вопросы

1. В чем состоит основная идея метода муравьиных колоний?

2. Для решения каких задач используется метод муравьиных колоний?

3. В каких условиях особенно эффективно использование муравьиных алгоритмов?

4. Сравните метод муравьиных колоний с другими оптимизационными методами.

5. Что представляет собой окружающая среда в методе муравьиных колоний?

6. С какой целью используется список табу?

7. Каким образом располагаются узлы в списке табу?

8. Что такое феромон? Которое его назначение в методе муравьиных колоний?

5.5 Оформление отчета по лабораторной работе

Текстовый файл в формате .doc

1. В отчете следует привести код программы, реализующей метод муравьиных колоний, а также скриншоты результатов работы программы.

2. Выводы по итогам работы.

Список литературы

1. Еременко, Ю.И. Введение в искусственный интеллект / Ю.И. Еременко. - Старый Оскол: ООО «ТНТ».

2. Андрейчиков, А.В. Интеллектуальные информационные системы [Текст]: учебник / А. В. Андрейчиков, О. Н. Андрейчикова. - М.: Финансы и статистика, 2004. - 424с.: ил.

3. Гаврилова, Т.А. Базы знаний интеллектуальных систем [Текст] / Т.А. Гаврилова, В. Ф. Хорошевский. - СПб: Питер, 2000. - 384 с.: ил.

Размещено на Allbest.ru