Муравьиный алгоритм для решения задачи о назначениях

Определим свойства муравья.

• 1) Каждый агент обладает собственной «памятью», в котором будет храниться список работ J_k, которые необходимо распределить муравью k.
• 2) Агенты обладают «зрением», обратно пропорциональным длине стоимости работы (длина ребра):

з_ij = 1/D_ij.

• 3) Каждый агент способен улавливать след феромона, который будет определять желание агента пройти по данному ребру, т. е. выбрать соответствующее ребру назначение. Уровень феромона в момент времени t на ребре D_ij будет соответствовать ф_ij (t).
• 4) Вероятность перехода муравья из вершины i в вершину j будет определяться следующим соотношением [Bonavear et al., 1999]:

(3.1).

где б, в — параметры, задающие веса следа феромона. Они определяют «жадность» муравья. При б=0 муравей стремиться выбирать кратчайшее ребро, при в=0 — ребро с наибольшим количеством феромона. Рекомендуемые значения, полученные на основе экспериментальных исследований, варьируют от 1 до 5. Нетрудно заметить, что выражение (3.1) имеет эффект «колеса рулетки». На Рис. 1 показан пример распределения вероятностей: с вероятностью 28% 1-й исполнитель выберет 1 работу, 15% - 2-ую, 33% - 3-ю и 25% - 4-ю соответственно.

Рис. 1. Распределение вероятностей выбора работы.

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

где Q — параметр, имеющий значение порядка целевой функции оптимального назначения (задается ЛПР), L_k (t) — целевая функция T_k (t).

Испарение феромона определяется следующим выражением:

(3.3).

где m — количество муравьев, p — коэффициент испарения (0 ? p ? 1), определяющий долю оставшихся феромонов после каждой итерации.

В простом муравьином алгоритме начальное расположение колонии муравьев определяется следующим образом. Количество муравьев равно числу вершин в графе, и каждому муравью соответствует некоторая вершина. Однако в данном алгоритме все агенты изначально находятся в вершине x₁ (X — множество исполнителей). Размер колонии не ограничено в данной модели.

Приведем псевдокод муравьиного алгоритма для решения задачи о назначениях.

• 1. Ввод матрицы расстояний D.
• 2. Инициализация параметров алгоритма — б, в, Q.
• 3. Инициализация видимости з_ij и начальной концентрации феромона.
• 4. Размещение муравьев в вершину x₁.
• 5. Выбор начального назначения и определение L*.
• 6. t = 0.
• 7. t=t+1.
• 8. k = 0.
• 9. k = k+1.
• 10. Реализовать назначения T_k (t) на основе выражения (1) и ЦФ L_k (t).
• 11. Если L_k (t) < L*, то L*= L_k (t), Т* = T_k (t).
• 12. Если k < m, то перейти к п. 9.
• 13. Обновить следы феромона на всех ребрах на основе выражения (3.3).
• 14. Если t < T, то перейти к п. 7.
• 15. Вывод назначений T* и его ЦФ L*.

Временная сложность данного алгоритма зависит от времени жизни колонии, количества вершин графа и числа муравьев — O (t*n²*m) [МакКоннелл, 2004].