Задача о назначениях - задача о наилучшем распределении некоторого числа работ между таким же числом исполнителей при условии взаимно однозначного соответствия между множествами работ и исполнителей [МакКоннелл, 2004]. При ее решении ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительности исполнителей. Производительность каждого исполнителя при выполнении каждой из имеющихся работ задается заранее. Задача сводится к задаче линейного программирования. Задача о назначениях представляет собой частный случай транспортной задачи. Данная задача имеет много интерпретаций: распределение работ между механизмами, распределение целей между огневыми средствами для максимизации математического ожидания числа пораженных целей или среднего ущерба и т.д. [МакКоннелл, 2004 [, [Каляев и др., 2009].

В математической модели задача представляется в виде двудольного графа, разбитого на два подмножества вершин X и Y одинаковой мощности n и множеством ребер U, соединяющих вершины из разных подмножеств. Информация о графе хранится в матрице чисел D_ij, где i, j 1, 2,…, n, представляющих собой стоимость выполнения j-й работы i-м исполнителем. Требуется найти перестановку ц из элементов множества X, такую, что значение ЦФ равно:

2. Общие положения муравьиного алгоритма

Как было сказано выше, основной идеей данного алгоритма является моделирование поведения муравьев, коллективной адаптации. Колония представляет собой систему с простыми правилами автономного поведения особей. Несмотря на примитивность поведения каждого отдельного муравья, поведение всей колонии оказывается достаточно разумным [МакКоннелл, 2004]. Таким образом, основой поведения муравьиной колонии служит низкоуровневое взаимодействие, благодаря которому, в целом, колония представляет собой разумную многоагентную систему. Взаимодействие осуществляется с помощью специального химического вещества - феромона, откладываемого муравьями на пройденном пути. При выборе направления движения муравей исходит не только из желания пройти кратчайший путь, но и из опыта других муравьев, информацию о котором получает непосредственно через уровень феромонов на каждом пути. Итак, концентрация феромона определяет желание особи выбрать тот или иной путь. Однако при таком подходе неизбежно попадание в локальный оптимум. Эта проблема решается благодаря испарению феромонов, которое является отрицательной обратной связью.

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

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

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. Распределение вероятностей выбора работы.

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

, (3.2)

где 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].

4. Экспериментальные исследования

Экспериментальные исследования проводились на графах, размерность которых варьировала от 10 до 500. Все рассматриваемые графы являются полными двудольными.

Для проведения исследований была создана программа на ЭВМ, производительность которого 1,6 ГГц, а объем ОЗУ равен 768 Мб. В главном окне программы отображаются: начальная ЦФ, конечная ЦФ, улучшение относительно начального назначения, график зависимости ЦФ от времени и сами назначения в виде диаграммы.

На Рис.2-3 приведены полученные решения на различных графах.

Рис.2. Тест с 20 вершинами.

На рис.2-3 показаны назначения работ для исполнителей, как показано в таблице 1. Высота i-го столбца - стоимость выполнения данной работы i-ым исполнителем, номер работы подписан под столбцами.

Таблица 1.

Оптимальные значения параметров алгоритма приведены ниже в таблице 2.

Таблица 2.

Размер колонии во всех тестах был равен 1000.

Рис.3. Тест с 80 вершинами.

Заключение