Просмотр статьи


Номер журнала: 2014.2

Заголовок статьи: Эволюционный синтез семейств оптимальных двумерных циркулянтных сетей

Резюме

Исследуется решение оптимизационной проблемы построения семейств оптимальных по диаметру циркулянтных сетей размерности два. Циркулянтные сети обеспечивают практический интерес как графо-теоретические модели надежных сетей связи параллельных супер-компьютерных систем, как основа структуры в модели малого мира, в нейронных и оптических сетях. Разрабатывается подход, использующий эволюционные алгоритмы для автоматического порождения аналитических (описываемых формулами) параметрических описаний семейств сетей. Алгоритм эволюционного синтеза комбинирует преимущества генетических алгоритмов и генетического программирования и основан на эволюционном вычислении, темплейтах решения и множестве экспериментальных данных. Представлено более 70 новых семейств оптимальных циркулянтных сетей размерности два с единичной образующей, полученных посредством эволюционного алгоритма

Авторы

Э.А. Монахова, О.Г. Монахов

Библиография

1. Монахова Э.А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011, №3(13). С.92–115.
2. Bermond J.-C., Comellas F., and Hsu D. F. Distributed loop computer networks: a survey //
J. Parallel Distributed Comput. 1995. V.24. P.2–10.
3. Hwang F.K. A survey on multi-loop networks // Theoretical Computer Science. 2003. No.299. P.107–121.
4. Монахов О.Г., Монахова Э.А. Исследование топологических свойств регулярных параметрически описываемых структур вычислительных систем// Автометрия. 2000. № 2.
С. 70–82.
5. Martinez C., Beivide R., Stafford E., et al. Modeling toroidal networks with the gaussian inte-gers // IEEE Trans. Comput. 2008. V.57. No.8. P.1046–1056.
6. Comellas F., Mitjana M., and Peters J.G. Broadcasting in Small-World Communication Net-works // 9th Inter. Coll. On Structural Information and Communication Complexity (SIROCCO 9), 2002. Proc. Informatics. 2002. No.13. P.73–85.
7. Demichev A., Ilyin V., Kryukov A., Polyakov S.A Quality and cost approach for the comparison of small-world interconnection networks // Journal of Interconnection Networks. 2013. 14:02.
8. Нестеренко Б.Б., Новотарский М.А. Клеточные нейронные сети на циркулянтных гра-фах // Искусственный интеллект. 2009. № 3. С. 132–138.
9. Монахова Э.А. Об аналитическом описании оптимальных двумерных диофантовых структур однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1981. № 90. С.81–91.
10. Chen B.-X., Meng J.-X., and Xiao W.-J. Some new optimal and suboptimal infinite families of undirected double-loop networks // DMTCS. 2006. No.8. P.299–312.
11. Chen B.-X., Meng J.-X., and Xiao W.-J. A Constant Time Optimal Routing Algorithm for Un-directed Double-Loop Networks // First Int. Conf. Mobile Ad-hoc and Sensor Networks. MSN 2005, Wuhan, China, December 2005. P.309–316.
12. Jha P.K. Dimension-order routing algorithms for a family of minimal-diameter circulants //
J. Interconnection Networks. 2013. V.14. No.1. 1350002 (24 pages).
13. Монахова Э.А. Синтез оптимальных диофантовых структур // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1979. № 80. С.18–35.
14. Du D.-Z., Hsu D.F., Li Q., and Xu J. A combinatorial problem related to distributed loop net-works // Networks. 1990. No.20. P.173–180.
15. Monakhova E.A. Optimal circulant computer networks // Inter. Conf. “Parallel Computing Technologies”, Novosibirsk, USSR; World Scientific, Singapore, 1991. P.450–458.
16. Tzvieli D. Minimal diameter double-loop networks. 1. Large infinite optimal families // Net-works. 1991. No.21. P.387–415.
17. Jha P.K. Dense bipartite circulants and their routing via rectangular twisted torus // Discrete Appl. Math., In the press. (http://web.stcloudstate.edu/pkjha/rtt6a.pdf), July 2013.
18. Jha P.K. Tight-optimal circulants vis-a-vis twisted tori // Discrete Appl. Math., (Manuscript Draft October 2013).
19. Jha P.K., Smith J.D.H. Cycle Kronecker products that are representable as optimal circulants // Discrete Appl. Math., (Manuscript Draft August 2013).
20. Chen B.-X., Xiao W.-J., and Parhami B. Diameter formulas for a class of undirected double-loop networks // J. Interconnection Networks. 2005. V.6. No.1. P.1–15.
21. Monakhova E.A. On existence of optimal double-loop computer networks // Bulletin of the Novosibirsk Computing Center, Computer Science series, issue 6, 1997, P. 29–44.
22. Монахов О.Г. Эволюционный синтез алгоритмов на основе шаблонов // Автометрия. Новосибирск, 2006. Т.42. №1. С.116–126.
23. Монахов О.Г., Монахова Э.А. Синтез новых семейств оптимальных регулярных сетей на основе эволюционных вычислений и шаблонов функций // Автометрия. 2004. Т. 40, №4. С.106–116.
24. Monakhov O.G., Monakhova E.A. Computer Discovery of Analytical Descriptions of Families of Circulant Networks // 6th Inter. Conf. on Soft Computing and Measurements, (SCM'2003), July 25-27, 2003, St.-Petersburg, Russia. V.1. P.345–348.
25. Monakhov O.G., Monakhova E.A. An Algorithm for Discovery of New Families of Optimal Regular Networks // Lecture Notes in Artificial Intelligence. 2003. V.2843. P.244–254.
26. Монахов О.Г., Монахова Э.А. Свидетельство об официальной регистрации программ на ЭВМ № 2013619128 «Программа вычисления характеристик регулярных графов с пара-метрическим описанием» // М.:Федеральная служба по интеллектуальной собственно-сти, патентам и товарным знакам, 2013.

Ключевые слова

неориентированные двумерные циркулянтные сети, диаметр, эволюционные алгоритмы

Скачать полный текст