Математическая модель муравьиного алгоритма с модификацией муравьиной колонии
Пусть 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 минут. Возвращаясь в стартовую вершину, рассчитаем глобальное обновление феромонов на пройденных ребрах:
Таким образом, найденный путь является оптимальным за одну итерацию, однако с ростом числа итераций на данном графе, возможно, найти более короткий путь.
Выводы по первой главе
В первой главе был проведен анализ существующих алгоритмов для решения задачи построения оптимального маршрута и выбран муравьиный алгоритм с модификацией муравьиной колонии. Данный алгоритм является приближенным и его выбор для текущей задачи обусловлен, наилучшей точностью решения, среди алгоритмов этого типа и высокой скоростью решения в сравнении с точными алгоритмами, где с ростом числа значительно увеличивается время оптимизации. Затем в ходе обзора программных продуктов применяющих методы оптимизации маршрута, позволяющих уменьшить затраты за счет сокращения пути и сбора статистики по выполненной работе сотрудников, были составлены основные требования, которым должно соответствовать программное средство. Задача выпускной квалификационной работы сформулирована и заключается в разработке программного комплекса позволяющего организоватьоптимальный обход пациентов, автоматизировать обработку заявок, увеличить контроль над сотрудниками и создать доступное взаимодействие между врачами и пациентами.