Please wait a minute...
Chin. Phys. B, 2021, Vol. 30(10): 100505    DOI: 10.1088/1674-1056/abff40
GENERAL Prev   Next  

Application of the edge of chaos in combinatorial optimization

Yanqing Tang(唐彦卿), Nayue Zhang(张娜月), Ping Zhu(朱萍), Minghu Fang(方明虎), and Guoguang He(何国光)
Department of Physics, Zhejiang University, Hangzhou 310027, China
Abstract  Many problems in science, engineering and real life are related to the combinatorial optimization. However, many combinatorial optimization problems belong to a class of the NP-hard problems, and their globally optimal solutions are usually difficult to solve. Therefore, great attention has been attracted to the algorithms of searching the globally optimal solution or near-optimal solution for the combinatorial optimization problems. As a typical combinatorial optimization problem, the traveling salesman problem (TSP) often serves as a touchstone for novel approaches. It has been found that natural systems, particularly brain nervous systems, work at the critical region between order and disorder, namely, on the edge of chaos. In this work, an algorithm for the combinatorial optimization problems is proposed based on the neural networks on the edge of chaos (ECNN). The algorithm is then applied to TSPs of 10 cities, 21 cities, 48 cities and 70 cities. The results show that ECNN algorithm has strong ability to drive the networks away from local minimums. Compared with the transiently chaotic neural network (TCNN), the stochastic chaotic neural network (SCNN) algorithms and other optimization algorithms, much higher rates of globally optimal solutions and near-optimal solutions are obtained with ECNN algorithm. To conclude, our algorithm provides an effective way for solving the combinatorial optimization problems.
Keywords:  edge of chaos      chaotic neural networks      combinatorial optimization      travelling salesman problem  
Received:  08 January 2021      Revised:  27 April 2021      Accepted manuscript online:  10 May 2021
PACS:  05.45.Gg (Control of chaos, applications of chaos)  
  07.05.Mh (Neural networks, fuzzy logic, artificial intelligence)  
  02.60.Pn (Numerical optimization)  
Fund: Project supported by the National Natural Science Foundation of China (Grant No. 12074335) and the National Science and Technology Major Project of the Ministry of Science and Technology of China (Grant No. 2016YFA0300402).
Corresponding Authors:  Guoguang He     E-mail:  gghe@zju.edu.cn

Cite this article: 

Yanqing Tang(唐彦卿), Nayue Zhang(张娜月), Ping Zhu(朱萍), Minghu Fang(方明虎), and Guoguang He(何国光) Application of the edge of chaos in combinatorial optimization 2021 Chin. Phys. B 30 100505

[1] Hoffman K L, Padberg M and Rinaldi G 2013 Encyclopedia of Operations Research and Management Science (Boston: Springer) pp. 1573-1578
[2] Liu J 2009 Chin. Phys. B 18 2615
[3] Shao G, Zhu M, Shangguan Y, Li W, Zhang C, Wang W and Li L 2017 Chin. Phys. B 26 063601
[4] Peng Y X, Sun K H and He S B 2020 Chin. Phys. B 29 030502
[5] Al-Ghamdi J A and Al-Masalmeh E R 2020 International Journal of Advance Research, Ideas and Innovations in Technology 6 www.IJARⅡT.com
[6] Kirkpatrick S, Gelatt C D and Vecchi M P 1983 Science 220 671
[7] Geman S and Geman D 1984 IEEE Trans. Pattern Anal. Mach. Intell. PAMI-6 721
[8] Wang D and Wang Q 2018 Chin. Phys. B 27 37801
[9] Akhand M A H, Ayon S I, Shahriyar S A and Siddique N and Adeli H 2020 Appl. Soft. Comput. 86 105887
[10] Zhang J, Hong L and Liu Q 2021 Symmetry 13 48
[11] Deng Y, Xiong J and Wang Q 2021 Math. Probl. Eng. 2021 6697598
[12] Rukhaiyar S, AlamMN and Samadhiya N K 2018 International Journal of Geotechnical Engineering 12 556
[13] Schoonover P L, Crossley W A and Heister SD 2015 J. Spacecr. Rockets 37 622
[14] Hopfield J J and Tank D W 1985 Biol. Cybern. 52 141
[15] Wilson G V and Pawley G S 1988 Biol. Cybern. 58 63
[16] Vinyals O, Fortunato M and Jaitly N 2015 Advances in Neural Information Processing Systems 28 (New York: Curran Associates) pp. 2692-2700
[17] Miki S, Yamamoto D and Ebara H 2019 2018 International Conference on Computing, Electronics & Communications Engineering (iCCECE), August 16-17, 2018, Southend, U.K. p. 65
[18] Xing Z and Tu S 2020 IEEE Access 8 108418
[19] da Costa P R O, Rhuggenaath J, Zhang Y and Akcay A 2020 Proceedings of The 12th Asian Conference on Machine Learning, November 18-20, 2020, Bangkok, Thailand p. 465
[20] Chen L and Aihara K 1995 Neural Netw. 8 915
[21] Wang L, Li S, Tian F and Fu X 2004 IEEE Trans. Syst. Man. Cybern. Part B, Cybern. 34 2119
[22] Zhao L, Sun M, Cheng J H and Xu Y Q 2009 IEEE Trans. Neural Netw. 20 735
[23] Hu Z, Li W and Qiao J 2017 Acta. Phys. Sin. 66 090502
[24] Qiao J, Hu Z and Li W 2019 Neural Comput. Appl. 31 7055
[25] He G, Chen L and Aihara K 2008 Neurocomputing 71 2794
[26] Munoz M A 2018 Rev. Mod. Phys. 90 031001
[27] Moretti P and Muñoz M A 2013 Nat. Commun. 4 2521
[28] Beggs J M 2008 Philos. Trans. R. Soc. A 366 329
[29] Fraiman D, Balenzuela P, Foss J and Chialvo D R 2009 Phys. Rev. E 79 061922
[30] Legenstein R and Maass W 2007 New directions in statistical signal processing: from systems to brain (Cambridge, MA, USA: Mit Press) pp. 127-154
[31] Feng L and Lai C H 2019 arXiv:1909.05176 [cs. LG]
[32] Haldeman C and Beggs J M 2005 Phys. Rev. Lett. 94 058101
[33] Aihara K, Takabe T and Toyoda M 1990 Phys. Lett. A 144 333
[34] Nicolis J S, Meyer-Kress G and Haubs G 1983 Z. Naturforsch. A 38 1157
[35] Reinelt G 1991 ORSA J. Comput. 3 376
[1] Adaptive synchronization of a class of fractional-order complex-valued chaotic neural network with time-delay
Mei Li(李梅), Ruo-Xun Zhang(张若洵), and Shi-Ping Yang(杨世平). Chin. Phys. B, 2021, 30(12): 120503.
[2] H synchronization of chaotic neural networks with time-varying delays
O. M. Kwon, M. J. Park, Ju H. Park, S. M. Lee, E. J. Cha. Chin. Phys. B, 2013, 22(11): 110504.
[3] Robust adaptive synchronization of chaotic neural networks by slide technique
Lou Xu-Yang(楼旭阳) and Cui Bao-Tong(崔宝同). Chin. Phys. B, 2008, 17(2): 520-528.
[4] Synchronization of stochastically hybrid coupled neural networks with coupling discrete and distributed time-varying delays
Tang Yang (唐漾), Zhong Hui-Huang(钟恢凰), Fang Jian-An(方建安). Chin. Phys. B, 2008, 17(11): 4080-4090.
[5] Linear matrix inequality approach to exponential synchronization of a class of chaotic neural networks with time-varying delays
Wu Wei(吴炜) and Cui Bao-Tong (崔宝同). Chin. Phys. B, 2007, 16(7): 1889-1896.
No Suggested Reading articles found!