Статья

Название статьи АНАЛИЗ РЕЗУЛЬТАТОВ ПРИМЕНЕНИЯ АЛГОРИТМА МУРАВЬИНОЙ КОЛОНИИ В ЗАДАЧЕ ПОИСКА ПУТИ В ГРАФЕ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ
Автор Э.И. Ватутин, В.С. Титов
Рубрика РАЗДЕЛ II. МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ СУПЕРКОМПЬЮТЕРОВ
Месяц, год 12, 2014
Индекс УДК 681.3
DOI
Аннотация Приведено описание алгоритма муравьиной колонии применительно к решению дискретных комбинаторных оптимизационных задач на примере задачи поиска кратчайшего пути в графе. Рассмотрен ряд модификаций по сравнению с классической математической моделью М. Дориго, позволяющих сократить вычислительные затраты при поиске решения и повысить его качество путем выполнения параметрической оптимизации (метаоптимизации) алгоритма. Предложена методика сравнения качества решений, базирующаяся на вычислении ряда показателей (средневыборочная оценка качества решений, средневыборочное отклонение качества решения от оптимума, вероятность нахождения решения и вероятность нахождения оптимального решения, среднее число итераций), используемых при сравнении качества решений, получаемых с использованием различных известных эвристических методов. Приведены результаты вычислительных экспериментов, выполненных с целью сравнения качества решений с известными методами для графов с различным числом вершин (различная размерность задачи) и различной плотностью, выражаемой отношением текущего числа дуг к максимально возможному.

Скачать в PDF

Ключевые слова Дискретная комбинаторная оптимизация; алгоритм муравьиной колонии; теория графов; поиск кратчайшего пути в графе; эвристические методы.
Библиографический список 1. https://ru.wikipedia.org/wiki/Равенство_классов_P_и_NP.
2. Валяев В.В., Ватутин Э.И. Метод определения изоморфизма графов общего вида за полиномиальное время // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. – 2012. – № 2. – Ч. 1. – С. 200-206.
3. Ватутин Э.И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. – Saarbrucken: Lambert Academic Publishing, 2011. – 292 с.
4. Ватутин Э.И., Зотов И.В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления
PACO’04. – М.: ИПУ РАН, 2004. – С. 884-917.
5. Dorigo M. Optimization, Learning and Natural Algorithms // PhD thesis. Politecnico di Milano, Italie, 1992.
6. Dijkstra E. W. A note on two problems in connexion with graphs // Numerische Mathematik. – 1959. – Vol. 1. – P. 269-271.
7. Зыков А.А. Основы теории графов. – М.: Наука, 1986. – 384 с.
8. Ватутин Э.И., Дремов Е.Н., Мартынов И.А., Титов В.С. Метод взвешенного случайного перебора для решения задач дискретной комбинаторной оптимизации // Известия
Волгоградского государственного технического университета. Серия: Электроника, измерительная техника, радиотехника и связь. – 2014. – № 10 (137). – Вып. 9. – С. 59-64.
9. Ватутин Э.И., Мартынов И.А., Титов В.С. Способ обхода тупиков при решении задач дискретной оптимизации с ограничениями // Перспективные информационные технологии (ПИТ-2014). – Самара: Изд-во Самарского научного центра РАН, 2014. – С. 313-317.
10. Ватутин Э.И., Колясников Д.В., Мартынов И.А., Титов В.С. Метод случайного перебора в задаче построения разбиений граф-схем параллельных алгоритмов // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов. – Барнаул, 2014. – С. 115-125.
11. Ватутин Э.И., Валяев С.Ю., Дремов Е.Н., Мартынов И.А., Титов В.С. Расчетный модуль для тестирования комбинаторных оптимизационных алгоритмов в задаче поиска кратчайшего пути в графе с использованием добровольных распределенных вычислений // Свидетельство о государственной регистрации программы для ЭВМ № 2014619797 от 22.09.14.

Comments are closed.