Лабораторная работа №6, Цель работы, Теоретическое введение - Интеллектуальные информационные системы
Использование муравьиных алгоритмов для решения задачи поиска оптимального маршрута в графе
Цель работы
Изучить метод муравьиных колоний. Научиться решать задачи комбинаторной оптимизации с помощью метода муравьиных колоний.
Теоретическое введение
Алгоритмы муравья, или оптимизация по принципу муравьиной колонии (создатель алгоритма - Марко Дориго), основаны на применении нескольких агентов и обладают специфическими свойствами, присущими муравьям, и используют их для ориентации в физическом пространстве. Алгоритмы муравья особенно интересны потому, что их можно использовать для решения не только статических, но и динамических проблем, например, в изменяющихся сетях.
Идея алгоритма
Два муравья из муравейника должны добраться до пищи, которая находится за препятствием. Во время перемещения каждый муравей выделяет немного феромона, используя его в качестве маркера.
Рис. 29 Начальная позиция
При прочих равных каждый муравей выберет свой путь. Первый муравей выбирает верхний путь, а второй - нижний. Так как нижний путь в два раза короче верхнего, второй муравей достигнет цели за время t1. Первый муравей в этот момент пройдет только половину пути (рис. 30).
Когда один муравей достигает пищи, он берет один из объектов и возвращается к муравейнику по тому же пути. За время t2 второй муравей вернулся в муравейник с пищей, а первый муравей достиг пищи (рис. 31).
При перемещении каждого муравья на пути остается немного феромона. Для первого муравья за время t2 путь был покрыт феромонами только один раз. В то же самое время второй муравей покрыл путь феромонами дважды. За время t4 первый муравей вернулся в муравейник, а второй муравей уже успел еще раз сходить к еде и вернуться. При этом концентрация феромона на нижнем пути будет в два раза выше, чем на верхнем. Поэтому первый муравей в следующий раз выберет нижний путь, поскольку там концентрация феромона выше.
Рис. 30 Промежуточная позиция №1 Рис. 31 Промежуточная позиция №2
В этом и состоит базовая идея алгоритма муравья - оптимизация путем непрямой связи между автономными агентами.
Пошаговое описание общей схемы
Предположим, что окружающая среда для муравьев представляет собой полный неориентированный граф. Каждое ребро имеет вес, который обозначается как расстояние между двумя вершинами, соединенными им. Граф двунаправленный, поэтому муравей может путешествовать по грани в любом направлении (рис. 32).
Рис. 32 Пример двунаправленного графа
Вероятность включения ребра в маршрут отдельного муравья пропорциональна количеству феромонов на этом ребре, а количество откладываемого феромона пропорционально длине маршрута. Чем короче маршрут тем больше феромона будет отложено на его ребрах, следовательно, большее количество муравьев будет включать его в синтез собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости - большинство муравьев двигается по локально-оптимальному маршруту. Избежать этого можно моделируя отрицательно обратную связь в виде испарения феромона. Причем, если феромон испаряется быстро, то это приводит к потере памяти колонии и забыванию хороших решений, с другой стороны, большое время испарений может привести к получению устойчивого локального оптимального решения.
Муравей
Муравей - это программный агент, который является членом большой колонии и используется для решения какой-либо проблемы. Муравей снабжается набором простых правил, которые позволяют ему выбирать путь в графе. Он поддерживает список узлов, которые он уже посетил. Таким образом, муравей должен проходить через каждый узел только один раз. Путь между двумя узлами графа, по которому муравей посетил каждый узел только один раз, называется путем Гамильтона.
Узлы в списке "текущего путешествия" располагаются в том порядке, в котором муравей посещал их. Позже список используется для определения протяженности пути между узлами. Настоящий муравей во время перемещения по пути будет оставлять за собой феромоны. В алгоритме муравья агент оставляет феромоны на ребрах графа после завершения путешествия.
Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи, так как для каждой задачи способ размещения муравьев является определяющим. Либо все они помещаются в одну точку, либо в разные с повторениями, либо без повторений.
На этом же этапе задается начальный уровень феромона. Он инициализируется небольшим положительным числом для того, чтобы на начальном шаге вероятности перехода в следующую вершину не были нулевыми.
Движение муравья
Движение муравья основывается на вероятностном уравнении. Если муравей еще не закончил путь, то есть не посетил все узлы сети, для определения следующего ребра пути используется формула:
(30)
Здесь ф(r, u) - интенсивность фермента на ребре между узлами r и u, з(r, u) - функция, которая представляет измерение обратного расстояния для грани, б - вес фермента, a и в - коэффициент эвристики. Параметры б и в определяют относительную значимость двух параметров, а также их влияние на уравнение. Так как муравей путешествует только по узлам, которые еще не были посещены (как указано списком табу), вероятность рассчитывается только для ребер, которые ведут к еще не посещенным узлам. Переменная k представляет эти ребра.
Путешествие муравья
Пройденный муравьем путь отображается, когда муравей посетит все узлы графа. Циклы запрещены, поскольку в алгоритм включен список табу. После завершения длина пути может быть подсчитана - она равна сумме длин всех ребер, по которым путешествовал муравей. Формула (31) показывает количество феромона, который был оставлен на каждом ребре пути для муравья k. Переменная Q является константой.
(31)
Результат уравнения является средством измерения пути, - короткий путь характеризуется высокой концентрацией феромонов, а более длинный путь - более низкой. Затем полученный результат используется в формуле (32), чтобы увеличить количество феромона вдоль каждого ребра пройденного муравьем пути.
(32)
Важно, что данная формула применяется ко всему пути, при этом каждое ребро помечается феромоном пропорционально длине пути. Поэтому следует дождаться, пока муравей закончит путешествие и только потом обновить уровни феромона, в противном случае истинная длина пути останется неизвестной. Константа p - значение между 0 и 1.
Испарение феромонов
В начале пути у каждого ребра есть шанс быть выбранным. Чтобы постепенно удалить ребра, которые входят в худшие пути графа, ко всем ребрам применяется процедура испарения феромона:
(33)
Для испарения феромона используется обратный коэффициент обновления пути.
Повторный запуск
После того как путь муравья завершен, ребра обновлены в соответствии с длиной пути и произошло испарение феромона на всех ребрах, алгоритм запускается повторно. Список табу очищается, и длина пути обнуляется. Муравьям разрешается перемещаться по графу, основывая выбор ребра на формуле (30). Этот процесс может выполняться для постоянного количества путей или до момента, когда на протяжении нескольких запусков не было отмечено повторных изменений. Затем определяется лучший путь, который и является решением.
Последовательность выполнения метода
Метод муравьиных колоний представляет собой следующую последовательность шагов.
Шаг 1. Задать параметры метода: б - коэффициент, который определяет относительную значимость пути (количество феромона на пути); в - параметр, который означает приоритет расстояния над количеством феромона; с - коэффициент количества феромона, который агент оставляет на пути, где (1-с) показывает коэффициент испарения феромона на пути после его завершения; Q - константа, которая относится к количеству феромона, который был оставлено на пути.
Шаг 2. Инициализация метода. Создание популяции агентов. После создания популяция агентов поровну распределяется по узлам сети. Необходимо равномерное распределение агентов между узлами, чтобы все узлы имели одинаковые шансы стать отправной точкой. Если все агенты начнут движение из одной точки, это будет означать, что данная точка полагается оптимальной для старта, а на самом деле она такой может и не быть.
Шаг 3. Движение агентов. Если агент еще не закончил путь, то есть не посетил все узлы сети, для определения следующей грани пути используется формула (30).
Агент путешествует только по узлам, которые еще не были навещены им, то есть по узлам, которых не имеет в списке табу tlist. Поэтому вероятность рассчитывается только для граней, которые ведут к еще не посещенным узлам.
По завершению итерации нас будут интересовать только те агенты, которые пройдут все узлы.
Шаг 4. Пройденный агентом путь отображается, когда агент посетит все узлы сети. Циклы запрещены, поскольку в метод включенный список табу tlist. После завершения может быть рассчитана длина пути. Она равняется сумме всех граней, по которым путешествовал агент. Количество феромона, которое было оставлено на каждой грани пути i - го агента, определяется по формуле (31).
Результат является средством измерения пути: короткий путь характеризуется высокой концентрацией феромона, а более длинный путь - более низкой. Потом полученный результат используется для увеличения количества феромона вдоль каждой грани пройденного i-ым агентом пути рассчитывается по формуле (32).
Формула (33) испарения феромона применяется ко всему пути, при этом каждая дуга обозначается феромоном пропорционально длине пути. Поэтому следует дождаться, пока агент закончит путешествие и только потом обновить уровень феромона, в противном случае действительная длина пути останется неизвестной. Константа с принимает значение между 0 и 1.
Шаг 5. Проверка на достижение оптимального результата. Проверка может выполняться для постоянного количества путей или к моменту, когда на протяжении нескольких запусков не было получены повторные изменения в выборе наилучшего пути. Если проверка дала положительный результат, то происходит окончание работы метода (переход к шагу 7), в противном случае - переход к шагу 6.
Шаг 6. Повторный запуск. После того как путь агента завершен, грани обновлены согласно длины пути и состоялось испарение феромона на всех гранях, метод выполняется повторно. Список табу очищается, и длина пути обнуляется. После этого выполняется переход к шагу 3.
Шаг 7. Конец. Определяется лучший путь, который и является решением.
Демонстрационный пример
Разберем функционирование рассмотренного выше алгоритма на простом примере, чтобы увидеть, как работают уравнения. Возьмем простой сценарий с двумя муравьями из примера который рассмотрен выше. На рис. 33 показан этот пример с двумя ребрами между двумя узлами (V0 и V1). Каждое ребро инициализируется и имеет одинаковые шансы на то, чтобы быть выбранным.
Рис. 33 Инициализация алгоритма
Рис. 34 Момент достижения цели
Два муравья находятся в узле V0 помечаются как A0 и A1. Так как вероятность выбора любого пути одинакова, в этом цикле проигнорируем уравнение выбора пути. Данные для задачи:
Число пройденных шагов: для A0 ? 20, для A1 ? 10
Уровень феромона (Q/пройденное расстояние): для A0 ? 0.5, A1 ? 1.0
С = 0.6
Б = 0.3
В = 1.0
Аждый муравей выбирает свой путь (муравей A0 идет по верхнему пути, а муравей A1 - по нижнему). Муравей A0 сделал 20 шагов, а муравей A1, - только 10. По формуле (31) рассчитывается количество феромонов, которое должно быть "нанесено".
Примечание: Работу алгоритма можно изменить, переопределив его параметры (например, б, в или p), например придав больший вес феромонам или расстоянию между узлами.
Далее по формуле (32) рассчитывается количество феромона, которое будет применено.
Для муравья A0 результат составляет:
Для муравья A1 результат составляет:
Далее с помощью формулы (33) определяется, какая часть феромонов испарится и, соответственно, сколько останется. Результаты (для каждого пути соответственно) составляют:
Эти значения представляют новое количество феромонов для каждого пути (верхнего и нижнего, соответственно). Затем, переместив муравьев обратно в узел V0, используется формула выбора пути (30), чтобы определить, какой путь должны выбрать муравьи. Вероятность того, что муравей выберет верхний путь (представленный количеством феромона 0,16), составляет:
Вероятность того, что муравей выберет нижний путь (представленный количеством феромона 0,28) составляет:
При сопоставлении двух вероятностей оба муравья выберут нижний путь, который является наиболее оптимальным.
Области применения
Алгоритм оптимизации муравьиной колонии может быть успешно применен для решения сложных комплексных задач оптимизации. Цель решения сложных комплексных задач оптимизации - поиск и определение наиболее подходящего решения для оптимизации (нахождения минимума или максимума) целевой функции (цены, точности, времени, расстояния и т. п.) из дискретного множества возможных решений. Типичный пример решения подобной задачи - квадратичная задача о назначениях, задача календарного планирования, задача маршрутизации транспорта, различных сетей (GPRS, телефонные, компьютерные и т. п.), распределение ресурсов и работ. Эти задачи возникают в бизнесе, инженерии, производстве и многих других областях. Исследования показали, что метод муравьиных колоний может давать результаты, даже лучшие чем при использовании генетических алгоритмов и нейронных сетей.
Похожие статьи
-
Оптимизация функции с помощью генетических алгоритмов Цель работы Изучить на практике принцип применения генетических алгоритмов для решения задач...
-
Деревья решений - общие принципы работы Цель работы Изучить принцип построения деревьев решений и построить дерево решений на основе имеющейся выборки...
-
Изучение возможностей экспертных систем Цель работы Целью является проектирование и разработка фрагмента экспертной системы. Теоретическое введение...
-
Введение - Интеллектуальные информационные системы
Чаще всего искусственным интеллектом, или ИИ (Artificial Intelligence - AI), называют процесс создания машин, которые способны действовать таким образом,...
-
Классификация компьютерных сетей - Теоретические основы информационных процессов и систем
Для классификации компьютерных сетей используются разные признаки, выбор которых заключается в том, чтобы выделить из существующего многообразия такие,...
-
Знакомство с нейронными сетями Цель работы Ознакомление со структурой нейронных сетей. Получение навыка программирования нейронных сетей. Теоретическое...
-
Построить дерево решений. Для этого необходимо: А) запустить программу deductor studio academic. Б) провести импорт статистики в программу, вызвав...
-
Экспертные системы - Теоретические основы информационных технологий
Наибольший прогресс среди компьютерных информационных систем отмечен в области разработки экспертных систем (ЭС), основанных на использовании элементов...
-
"РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...
-
Понятие о компьютерном математическом моделировании Модель - материальный объект, система математических зависимостей или программа, имитирующая...
-
В связи с увеличением числа сотрудников, работающих в компании, а также с расширением рабочего проекта, возникла проблема, связанная с версионностью...
-
Обучение нейронной сети Цель работы Изучить принципы проектирования и обучения нейронных сетей с помощью пакета Matlab. Изучить на практике работу...
-
Написать программу на С++ моделирующую двухслойную нейронную сеть структуры согласно варианту, указанному в таблице 4. Таблица 4 Варианты заданий для...
-
Выбор средств реализации информационной системы Названные в параграфе 1.4. настоящей работы задачи могут быть решены тремя типами средств автоматизации:...
-
Сравнение алгоритмов поиска оптимальных решений в агентных системах
Аннотация Рассмотрены основные понятия теории агентов: тип агентов, основные задачи агентов, суть поиска решения агентом в пространстве состояния...
-
Информационные технологии в системах организационного управления Применение компьютерных информационных технологий позволяет в ряде случаев при...
-
Типы экспертных систем - Теоретические основы информационных технологий
Можно назвать несколько Типов современных экспертных систем . 1) Экспертные системы первого поколения. Предназначены для решения хорошо структурированных...
-
Введение - Информационные системы в управлении предприятием
Актуальность темы: главным направлением перестройки менеджмента и его радикального усовершенствования, приспособления к современным условиям стало...
-
Цель Работы - изучить приемы создания и использования шаблонов классов. - Теоретические сведения Достаточно часто встречаются классы, объекты которых...
-
Из универсальных языков программирования сегодня наиболее популярны следующие: Бейсик (Basic), Паскаль (Pascal), Си++ (C++), Ява (Java). Для каждого из...
-
Цель Работы - научиться использовать операции динамического выделения и освобождения памяти на примере работы с одномерными и двумерными массивами, а...
-
Подсистема интеллектуального анализа данных используется специальной категорией пользователей-аналитиков, которые на основе ИХ обнаруживают...
-
Моделирования случайных процессов - Теоретические основы информационных технологий
Моделирование случайных процессов - мощнейшее направление в современном математическом моделировании. Событие называется случайным, если оно достоверно...
-
Понятие системы поддержки принятия решений (СППР) - Компьютерные информационные технологии
Со временем количество информации, которую необходимо обработать для принятия нужного решения, стремительно увеличивается. Рост объемов...
-
Основные понятия СУБД Microsoft Access Microsoft Access - это система управления базами данных, предназначенная для создания и обслуживания баз данных,...
-
Цель Работы - использовать принципы архитектуры "Документ-Представление" для выборки и сохранения данных в файлах, а также взаимодействия элементов меню,...
-
Введение - Поверка и калибровка информационно измерительных систем
На сегодня метрологическая деятельность регулируется Законом Российской Федерации "Об обеспечении единства измерений". Из этого следует, что эта...
-
Объект ориентированный класс программирование Цель Работы - изучить методику создания одномерных динамических символьных массивов при помощи...
-
Сегодня положение дел в рассматриваемой области характеризуется крайней неопределенностью. Во-первых, это связано с непрерывным увеличением объема...
-
SimpleXML. В PHP версии 5.0 и выше появилось расширение для работы с xml структурой. Библитека SimpleXML содержит большое количество методов для работы с...
-
Российская система здравоохранения: текущее состояние, основные проблемы и барьеры для дальнейшего развития Российское здравоохранение на сегодняшний...
-
Технологии распределенных вычислений (РВ) Современное производство требует высоких скоростей обработки информации, удобных форм ее хранения и передачи....
-
Основная цель системы ДИСКОР - совершенствование оперативного управления работой железных дорог на основе более эффективного использования пропускной...
-
Введение - Разработка справочной информационной системы "Рецепты"
Задание курсовой работы. Разработать и отладить информационную справочную систему "Рецепты", которая будет позволять хранить, выводить на экран,...
-
Основные термины теории баз данных - БД (База данных) - совокупность специальным образом организованных данных, хранимых в памяти вычислительной системы...
-
Введение - Проектирование автоматизированной информационной системы
Информационный интерфейс программа С развитием информационных технологий компьютеры, с их расширенными функциональными возможностями, активно применяются...
-
Определить наилучшие параметры корректирующего устройства следящей системы, обеспечивающих устойчивость системы и выполнение требований технического...
-
Понятие информационной системы - Компьютерные информационные технологии
Информационной системой (ИС), либо автоматизированной ИС, АИС, будем называть программно-аппаратную систему, предназначенную для автоматизации...
-
Наименование программы Полное наименование программы - Модуль ипотечного кредитования банковской информационной системы "БИС". Краткое наименование...
-
Введение - Составление программы для решения системы уравнений
А) Постановка задач Б) Решения поставленной задачи 4. Порядок выполнения работы А) Изучение литературы Б) Составление алгоритма. В) Составление программа...
Лабораторная работа №6, Цель работы, Теоретическое введение - Интеллектуальные информационные системы