Математическая модель муравьиного алгоритма с модификацией муравьиной колонии

Пусть k-ый агент находится на i-ом пункте, а его список посещенных пунктов – еще не до конца заполненный массив Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru . Тогда переход в пункт Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru осуществляется при условии, что Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru , где Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru –случайное число, Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru – порог псевдослучайного пропорционального выбора. Иначе вероятность перехода в Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru пункт определяется следующей формулой (1.1):

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru (1.1)

где Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru и Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru – параметры управления относительной важности между феромонной информацией Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru и эвристической информацией Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Если k-ый агент посетил все пункты, то он возвращается в стартовый, по пройденному пути

При возвращении в стартовыйпункт агент оставляет на каждом пути феромоны. Концентрат феромона на ребре Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru пересчитывается по формуле (1.2):

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru (1.2)

где Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru – коэффициент испарения феромона, Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru – количество феромона оставляемое на ребре k-ым агентом:

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru (1.3)

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru – длина пути k-го агента, Q – регулируемый параметр.

Из этого следует, что чем длиннее путь k-го агента, тем меньше будет концентрат оставленных феромонов, на пройденном пути.

Помимо обновления феромонов после каждой итерации, применяется дополнительное обновление, которое выполняется после прохода по ребру Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru по формуле (1.4):

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru (1.4)

где Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru – параметр ослабления феромона, а Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru – начальное значение феромона

Пример

Для примера использования приведенной математической модели, рассмотрим решение задачи поиска оптимального маршрута на графе (рисунок 1.6):

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Рисунок 1.6. Граф для примера задачи

В таблице1.2 представлены время пути для каждого ребра и концентрация феромонов на них:

Таблица 1.2

Входные данные

Ребро 1-2 1-3 1-4 2-3 2-4 3-4
Время пути (мин)d
Концентрация феромонов Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Пусть заданы параметры: Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru ,и пусть агент стартует с вершины 1.Кидая жребий на интервале Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru пусть выпало число 0,1. Тогда вершиной для дальнейшего перехода могут быть 2, 3 или 4. Рассчитаем вероятности для каждой из возможных вершинпо формуле (1.1):

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Можно проверить, что сумма всех найденных вероятностей равна 1, следовательно, расчеты верны. Составим интервал полученных вероятностей:

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Затем кинув жребий от 0 до 1,пусть выпало число 0,87, тогда переход агента произойдет по ребру 1-4 в вершину 4. Рассчитаем локальное обновление феромонов на пройденном ребре:

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Пусть снова кидая жребий для перехода в ребро с максимальным уровнем феромона, выпадает q больше Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru . Тогдаиз вершины 4 можно перейти в вершину 2 и 3. В вершину 1 переход невозможен, так как она попала в список посещенных вершин – Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru . Найдем вероятности Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru и Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru :

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

на интервале от 0 до 1: Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru . Пусть жребий показал число 0.3, тогда переход произойдет в вершину 3, по ребру Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru :. Рассчитаем локальное обновление феромонов на ребре Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru :

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Среди оставшихся не посещённых вершин остается одна – вершина 2. Логично, что вероятность перехода в данную вершину равна 100% . Локальное обновление ребра Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru :

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Следовательно, найденный путь 1,4,3,2,время прохождения которого, составляет 49 минут. Возвращаясь в стартовую вершину, рассчитаем глобальное обновление феромонов на пройденных ребрах:

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

Математическая модель муравьиного алгоритма с модификацией муравьиной колонии - student2.ru

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

Выводы по первой главе

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


Наши рекомендации