sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИsibsutis-447Research ArticleСтатьиЭволюционный синтез семейств оптимальных двумерных циркулянтных сетейEvolutionary synthesis of optimal two-dimensional circulant networks familiesМонаховаЭ. А.MonakhovaE. A.emilia@rav.sscc.ruМонаховО. Г.MonakhovO. G.monakhov@rav.sscc.ruИнститут вычислительной математики и математической геофизики СО РАНRussian Federation201426102022027282Copyright © Монахова Э.А., Монахов О.Г., 20222022Монахова Э.А., Монахов О.Г.Monakhova E.A., Monakhov O.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/447

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

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.

неориентированные двумерные циркулянтные сетидиаметрэволюционные алгоритмыundirected double-loop networksdiameterevolutionary algorithmsReferencesМонахова Э.А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011, №3(13). С.92-115.Монахова Э.А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011, №3(13). С.92-115.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.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.Hwang F.K. A survey on multi-loop networks // Theoretical Computer Science. 2003. No.299. P.107-121.Hwang F.K. A survey on multi-loop networks // Theoretical Computer Science. 2003. No.299. P.107-121.Монахов О.Г., Монахова Э.А. Исследование топологических свойств регулярных параметрически описываемых структур вычислительных систем// Автометрия. 2000. № 2. С. 70-82.Монахов О.Г., Монахова Э.А. Исследование топологических свойств регулярных параметрически описываемых структур вычислительных систем// Автометрия. 2000. № 2. С. 70-82.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.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.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.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.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.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.Нестеренко Б.Б., Новотарский М.А. Клеточные нейронные сети на циркулянтных графах // Искусственный интеллект. 2009. № 3. С. 132-138.Нестеренко Б.Б., Новотарский М.А. Клеточные нейронные сети на циркулянтных графах // Искусственный интеллект. 2009. № 3. С. 132-138.Монахова Э.А. Об аналитическом описании оптимальных двумерных диофантовых структур однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1981. № 90. С.81-91.Монахова Э.А. Об аналитическом описании оптимальных двумерных диофантовых структур однородных вычислительных систем // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1981. № 90. С.81-91.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.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.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.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.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).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).Монахова Э.А. Синтез оптимальных диофантовых структур // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1979. № 80. С.18-35.Монахова Э.А. Синтез оптимальных диофантовых структур // Вычислительные системы. Вопросы теории и построения ВС. Новосибирск, 1979. № 80. С.18-35.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.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.Monakhova E.A. Optimal circulant computer networks // Inter. Conf. “Parallel Computing Technologies”, Novosibirsk, USSR; World Scientific, Singapore, 1991. P.450-458.Monakhova E.A. Optimal circulant computer networks // Inter. Conf. “Parallel Computing Technologies”, Novosibirsk, USSR; World Scientific, Singapore, 1991. P.450-458.Tzvieli D. Minimal diameter double-loop networks. 1. Large infinite optimal families // Networks. 1991. No.21. P.387-415.Tzvieli D. Minimal diameter double-loop networks. 1. Large infinite optimal families // Networks. 1991. No.21. P.387-415.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.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.Jha P.K. Tight-optimal circulants vis-a-vis twisted tori // Discrete Appl. Math., (Manuscript Draft October 2013).Jha P.K. Tight-optimal circulants vis-a-vis twisted tori // Discrete Appl. Math., (Manuscript Draft October 2013).Jha P.K., Smith J.D.H. Cycle Kronecker products that are representable as optimal circulants // Discrete Appl. Math., (Manuscript Draft August 2013).Jha P.K., Smith J.D.H. Cycle Kronecker products that are representable as optimal circulants // Discrete Appl. Math., (Manuscript Draft August 2013).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.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.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.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.Монахов О.Г. Эволюционный синтез алгоритмов на основе шаблонов // Автометрия. Новосибирск, 2006. Т.42. №1. С.116-126.Монахов О.Г. Эволюционный синтез алгоритмов на основе шаблонов // Автометрия. Новосибирск, 2006. Т.42. №1. С.116-126.Монахов О.Г., Монахова Э.А. Синтез новых семейств оптимальных регулярных сетей на основе эволюционных вычислений и шаблонов функций // Автометрия. 2004. Т. 40, №4. С.106-116.Монахов О.Г., Монахова Э.А. Синтез новых семейств оптимальных регулярных сетей на основе эволюционных вычислений и шаблонов функций // Автометрия. 2004. Т. 40, №4. С.106-116.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.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.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.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.Монахов О.Г., Монахова Э.А. Свидетельство об официальной регистрации программ на ЭВМ № 2013619128 «Программа вычисления характеристик регулярных графов с параметрическим описанием» // М.:Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, 2013.Монахов О.Г., Монахова Э.А. Свидетельство об официальной регистрации программ на ЭВМ № 2013619128 «Программа вычисления характеристик регулярных графов с параметрическим описанием» // М.:Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, 2013.

The authors declare that there are no conflicts of interest present.