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

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

(1.1)

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

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

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

(1.2)

где – коэффициент испарения феромона, – количество феромона оставляемое на ребре k-ым агентом:

(1.3)

– длина пути k-го агента, Q – регулируемый параметр.

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

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

(1.4)

где – параметр ослабления феромона, а – начальное значение феромона

Пример

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

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

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

Таблица 1.2

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

Ребро	1-2	1-3	1-4	2-3	2-4	3-4
Время пути (мин)d
Концентрация феромонов

 

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

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

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

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

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

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

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

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

 

 

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

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