Эволюционный синтез семейств оптимальных двумерных циркулянтных сетей
Аннотация
Исследуется решение оптимизационной проблемы построения семейств оптимальных по диаметру циркулянтных сетей размерности два. Циркулянтные сети обеспечивают практический интерес как графо-теоретические модели надежных сетей связи параллельных суперкомпьютерных систем, как основа структуры в модели малого мира, в нейронных и оптических сетях. Разрабатывается подход, использующий эволюционные алгоритмы для автоматического порождения аналитических (описываемых формулами) параметрических описаний семейств сетей. Алгоритм эволюционного синтеза комбинирует преимущества генетических алгоритмов и генетического программирования и основан на эволюционном вычислении, темплейтах решения и множестве экспериментальных данных. Представлено более 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 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.
Рецензия
Для цитирования:
Монахова Э.А., Монахов О.Г. Эволюционный синтез семейств оптимальных двумерных циркулянтных сетей. Вестник СибГУТИ. 2014;(2):72-82.
For citation:
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.)
Просмотров:
182
Послать статью по эл. почте 