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

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

Рис. 5. Рис. 6.

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

число пройденных шагов: для A0 − 20, для A1 − 10

уровень феромона (Q/пройденное расстояние): для A0 − 0.5, A1 − 1.0

ρ = 0.5

α = 0.3

β = 1.0

На рис. 6 каждый муравей выбирает свой путь (муравей A0 идет по верхнему пути, а муравей A1 - по нижнему). Муравей A0 сделал 20 шагов, а муравей A1, - только 10. По уравнению 2 мы рассчитываем количество феромонов, которое должно быть "нанесено".

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

Далее по уравнению 3 рассчитывается количество феромона, которое будет применено. Для муравья A0 результат составляет: 0,1 + (0,5 * 0,6) = 0,4. Для муравья A1 результат составляет: 0,1 + (1,0 * 0,6) = 0,7. Далее с помощью уравнения 4 определяется, какая часть феромонов испарится и, соответственно, сколько останется. Результаты (для каждого пути соответственно) составляют:

0,4 * (1,0 - 0,6) = 0,16

0,7 * (0,5 - 0,6) = 0,28

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

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

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