Evolutionary synthesis of optimal two-dimensional circulant networks families
Abstract
Solution of the optimization problem of constructing optimal diameter two-dimensional circulant networks families is investigated. Circulant networks provide a practical interest as graph- theoretical models of reliable communication networks of parallel supercomputer systems, as basis of structures in the model of the «small world networks», in neural and optical networks. The developed approach uses evolutionary algorithms for an automatic generation of analytic (described by formulas) parametric descriptions of networks families. Evolutionary synthesis algorithm combines the advantages of genetic algorithms and genetic programming and is based on evolutionary computation, template solutions and a set of experimental data. More than 70 new families of optimal two-dimensional circulant networks with unit generator, obtained by the evolutionary algorithm, are presented.
About the Authors
E. A. Monakhova
Институт вычислительной математики и математической геофизики СО РАН
Russian Federation
Russian Federation
O. G. Monakhov
Институт вычислительной математики и математической геофизики СО РАН
Russian Federation
Russian Federation
References
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 integers // 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 Networks // 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 Undirected 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 networks // 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 // Networks. 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.
Review
For citations:
Monakhova E.A., Monakhov O.G. Evolutionary synthesis of optimal two-dimensional circulant networks families. The Herald of the Siberian State University of Telecommunications and Information Science. 2014;(2):72-82. (In Russ.)
Views:
181
Email this article 