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

Муравьиный алгоритм определения критических связей в СБИС  

Авторы
 Запорожец Д.Ю.
 Заруба Д.В.
 Курейчик В.В.
Год публикации
 2014
УДК
 628.321.3

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

Copyright © 2009-2018 ИППМ РАН. All Rights Reserved.

Разработка сайта - ИППМ РАН