Главная         Авторы   Статьи   Год проведения   Тематика   Организации        Конференция МЭС

Муравьиный алгоритм определения критических связей в СБИС
Авторы
	Запорожец Д.Ю.
	Заруба Д.В.
	Курейчик В.В.
Год публикации
	2014
УДК
	628.321.3
Аннотация
	Статья посвящена разработке и исследованию модифицированного муравьиного алгоритма определения критических связей в СБИС на примере решения задачи о коммивояжере, а также выполнению экспериментальных исследований его характеристик. Данный алгоритм входит в состав метода роевого интеллекта, являющегося одним из биоинспирированных подходов, описывающих коллективное поведение децентрализованной самоорганизующейся системы, которая состоит из множества агентов (муравьев), локально взаимодействующих между собой и с окружающей средой. В статье приведена постановка задачи о коммивояжере. Описан модифицированный муравьиный алгоритм, позволяющий получать наборы квазиоптимальных решений. Проведен вычислительный эксперимент. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритма оптимизации и их поведение для графов различной структуры. В лучшем случае временная сложность алгоритма (ВСА) ~ O(n logn), в худшем случае – О(n3).
Ключевые слова
	оптимизация, задача коммивояжера, многоагентная система, муравьиный алгоритм
Ссылка на статью
	Запорожец Д.Ю., Заруба Д.В., Курейчик В.В. Муравьиный алгоритм определения критических связей в СБИС // Проблемы разработки перспективных микро- и наноэлектронных систем - 2014. Сборник трудов / под общ. ред. академика РАН А.Л. Стемпковского. М.: ИППМ РАН, 2014. Часть 2. С. 107-112.
Адрес статьи
	http://www.mes-conference.ru/data/year2014/pdf/D114.pdf