Preview

Вестник СибГУТИ

Расширенный поиск

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

Аннотация

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

Просмотров: 180


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1998-6920 (Print)