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

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

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

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

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

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

Таблица 1.

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

Таблица 2.

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

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

Заключение

В ходе проделанной работы была создана программа на ЭВМ, реализующая описанную модель поведения муравьев. Муравьиный алгоритм показал себя адаптируемым к различным графовым задачам. «Хорошее» решение может быть найдено за короткое время. Для графов с размерностью до 500 вершин такое решение находится менее чем за 3 секунды. Экспериментальные результаты показали эффективность муравьиного алгоритма не только при решении транспортных задач, но и задачи о назначениях.

муравьиный алгоритм программа графовая задача.