Статья

Название статьи ГЛОБАЛЬНАЯ ТРАССИРОВКА МЕТОДОМ КРИСТАЛЛИЗАЦИИ РОССЫПИ АЛЬТЕРНАТИВ
Автор Б.К. Лебедев, В.Б. Лебедев
Рубрика РАЗДЕЛ I. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫ
Месяц, год 07, 2014
Индекс УДК 681.325
DOI
Аннотация Предлагается метод и алгоритм глобальной трассировки на основе новой, предложенной авторами, парадигмы коллективного интеллекта – кристаллизации россыпи альтернатив (КРА). Решение задачи глобальной трассировки осуществляется на основе комбинаторного подхода. Наряду с метаэвристиками, на которых построены роевые алгоритмы, используется метаэвристика, имеющая тенденцию к использованию альтернатив (вариантов компонентов) из наилучших найденных решений. Сущность комбинаторного алгоритма заключается в том, что для каждой связывающей сети формируется набор вариантов ее построения. Целью задачи является нахождение на заданном наборе таких вариантов, которые обеспечивают наилучшее решение. В процессе эволюционной коллективной адаптации методами дискриминантного анализа формируются оценки приспособленности альтернатив. Приспособленность альтернатив рассматривается как вероятность ее использования в формируемом решении. Совокупность данных об альтернативах и их оценках составляет россыпь альтернатив. Дискриминантный анализ альтернатив в процессе эволюционной коллективной адаптации назван по аналогии с процессами вычленения объектов (формирования кристаллов) кристаллизацией. Другими словами, в процессе эволюционной коллективной адаптации производится вычленение из множества вариантов наиболее приспособленных альтернатив. Отсюда название метода оптимизации – метод кристаллизации россыпи альтернатив (КРА), (Crystallization of alternatives field (CAF). Проведены экспериментальные исследования, подтвердившие эффективность предложенной парадигмы. По сравнению с существующими алгоритмами достигнуто улучшение результатов на 2–3 %.

Скачать в PDF

Ключевые слова лобальная трассировка; роевой интеллект; метод кристаллизации россыпи альтернатив; адаптивное поведение; оптимизация.
Библиографический список 1. Alpert C.J., Mehta D.P. and Sapatnekar S.S. Handbook of Algorithms for Physical Design Automation. – Boston, MA: Auerbach, 2009.
2. Ozdal M.M. and Wong M.D.F. Archer: A history-driven global routing algorithm, in Proc. Int. Conf. Comput.-Aided Des, 2007. – P. 488-495.
3. Курейчик В.М. Особенности построения систем поддержки принятия решений // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 92-290.
4. Pan M. and Chu C. FastRoute 2.0: A high-quality and efficient global router, in Proc. Asia South Pacific Des. Autom. Conf., 2007. – P. 250-255.
5. Roy J.A. and Markov I.L. High performance routing at the nanometer scale, in Proc. Int. Conf. Comput.-Aided Des., 2007. – P. 496-502.
6. Лебедев Б.К., Лебедев О.Б. Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 27-34.
7. Лебедев Б.К., Лебедев О.Б. Многослойная глобальная трассировка методом коллективной адаптации // V Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем - 2012». Сборник трудов. – М.: ИППМ Р Н, 2012. – С. 251-257.
8. Курейчик В.М. Исследования шаблонных решений в муравьиных алгоритмах // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 17-22.
9. Лебедев О.Б. Трассировка в канале методом муравьиной колонии // Известия ЮФУ. Технические науки. – 2009. – № 2 (91). – С. 46-52.
10. Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования. – Таганрог: Изд-во ЮФУ, 2013. – 199 с.
11. Лебедев Б.К., Лебедев В.Б. Глобальная трассировка на основе роевого интеллекта // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 32-39.
12. Лебедев Б.К., Лебедев В.Б. Оптимизация методом кристаллизации россыпи альтернатив // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 11-17.

Comments are closed.