Please wait a minute...
Chin. Phys. B, 2016, Vol. 25(12): 128904    DOI: 10.1088/1674-1056/25/12/128904
INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY Prev  

An improved genetic algorithm with dynamic topology

Kai-Quan Cai(蔡开泉)1, Yan-Wu Tang(唐焱武)1, Xue-Jun Zhang(张学军)1, Xiang-Min Guan(管祥民)2
1. School of Electronic and Information Engineering, Beihang University, Beijing 100191, China;
2. Department of General Aviation, Civil Aviation Management Institute of China, Beijing 100102, China
Abstract  

The genetic algorithm (GA) is a nature-inspired evolutionary algorithm to find optima in search space via the interaction of individuals. Recently, researchers demonstrated that the interaction topology plays an important role in information exchange among individuals of evolutionary algorithm. In this paper, we investigate the effect of different network topologies adopted to represent the interaction structures. It is found that GA with a high-density topology ends up more likely with an unsatisfactory solution, contrarily, a low-density topology can impede convergence. Consequently, we propose an improved GA with dynamic topology, named DT-GA, in which the topology structure varies dynamically along with the fitness evolution. Several experiments executed with 15 well-known test functions have illustrated that DT-GA outperforms other test GAs for making a balance of convergence speed and optimum quality. Our work may have implications in the combination of complex networks and computational intelligence.

Keywords:  complex networks      genetic algorithm dynamic topology  
Received:  10 July 2016      Revised:  10 September 2016      Published:  05 December 2016
PACS:  89.75.Hc (Networks and genealogical trees)  
  05.45.-a (Nonlinear dynamics and chaos)  
Fund: 

Project supported by the National Natural Science Foundation for Young Scientists of China (Grant No. 61401011), the National Key Technologies R & D Program of China (Grant No. 2015BAG15B01), and the National Natural Science Foundation of China (Grant No. U1533119).

Corresponding Authors:  Xue-Jun Zhang     E-mail:  zhxjbh@163.com

Cite this article: 

Kai-Quan Cai(蔡开泉), Yan-Wu Tang(唐焱武), Xue-Jun Zhang(张学军), Xiang-Min Guan(管祥民) An improved genetic algorithm with dynamic topology 2016 Chin. Phys. B 25 128904

[1] Zwickl D J 2006 "Genetic Algorithm Approaches for the Phylogenetic Analysis of Large Biological Sequence Datasets Under the Maximum Likelihood Criterion," Ph. D. Dissertation, Austin, University of Texas at Austin
[2] Poli R, Kennedy J and Blackwell T 2007 Swarm Intell. 1 33
[3] Dorigo M and Blum C 2005 Theor. Comput. Sci. 344 243
[4] Holland J H 1975 Adaptation in Natural and Artificial Systems (Ann Arbor:University of Michigan Press) pp. 171-198
[5] Zhang S L, Chen H S, Song Y and Yin Y H 2007 Acta Phys. Sin. 56 2553 (in Chinese)
[6] Li T J Sun Y, Zheng J W, Shao G F and Liu T D 2010 Acta Phys. Sin. 64 153601 (in Chinese)
[7] Zu Y X, Zhou J and Zeng C C 2010 Chin. Phys. B 19 119501
[8] Lu J, Wang J B and Sun G C 2009 Chin. Phys. B 18 1598
[9] Hollstein R B 1971 "Artifical Genetic Adaptation in Computer Control Systems", Ph. D. Dissertation, Ann Arbor, University of Michigan
[10] Goldberg D E 1983 "Computer-aided Gas Pipeline Operation Using Genetic Algorithms and Rule Learning", Ph. D. Dissertation, Ann Arbor, University of Michigan
[11] Goldberg D E 1991 Complex Syst. 5 139
[12] Srinivas M and Patnaik L M 1994 IEEE Trans. Syst. Man Cybern. 24 656
[13] Deb K, Pratap A, Agarwal S and Meyarivan T 2002 IEEE Trans. Evol. Comput. 6 18
[14] Zhang Q and Li H 2007 IEEE Trans. Evol. Comput. 11 712
[15] Szabó G and Fáth G 2006 Phys. Rep. 446 97
[16] Yang H X, Gao K, Han X P and Wang B H 2008 Chin. Phys. B 17 2759
[17] Strogatz S H 2001 Nature 410 268
[18] Xiong F, Liu Y, Si X M and Ding F 2010 Acta Phys. Sin. 59 6889 (in Chinese)
[19] Xing C M and Liu F A 2010 Acta Phys. Sin. 59 1608 (in Chinese)
[20] Liu C, Du W B and Wang W X 2014 PLoS One 9 e97822
[21] Du W B, Gao Y, Liu C, Zheng Z and Wang Z 2015 Appl. Math. Comput. 268 832
[22] Gao Y, Du W B and Yan G 2015 Sci. Rep. 5 9295
[23] Du W B, Ying W, Yan G, Zhu Y B and Cao X B 2016 IEEE Trans. Circuits Syst. II:Exp. Briefs
[24] Negvitsky M 2005 Artificial Intelligence, 2nd edn. (Essex:Pearson Ed. Ltd) pp. 1-415
[25] Yao X, Liu Y and Lin G 1999 IEEE Trans. Evol. Comput. 3 82
[26] Liang J J, Qu B Y and Suganthan P N 2013 Technical Report, Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou China and Technical Report, Nanyang Technological University, Singapore
[27] Schaffer J D, Caruana R A, Eshelman L J and Das R 1989 Proceedings of the 2nd International Conference on Genetic Algorithms, June, Fairfax, USA, p. 51
[28] Tan K C, Chiam S C, Mamun A A and Goh C K 2009 European Journal of Operational Research 197 701
[29] Eiben A E, Hinterding R and Michalewicz Z 1999 IEEE Trans. Evol. Comput. 3 124
[30] Karafotias G, Hoogendoorn M and Eiben A E 2015 IEEE Trans. Evol. Comput. 19 167
[1] Influential nodes identification in complex networks based on global and local information
Yuan-Zhi Yang(杨远志), Min Hu(胡敏), Tai-Yu Huang(黄泰愚). Chin. Phys. B, 2020, 29(8): 088903.
[2] Identifying influential spreaders in complex networks based on entropy weight method and gravity law
Xiao-Li Yan(闫小丽), Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni(倪顺江). Chin. Phys. B, 2020, 29(4): 048902.
[3] Modeling and analysis of the ocean dynamic with Gaussian complex network
Xin Sun(孙鑫), Yongbo Yu(于勇波), Yuting Yang(杨玉婷), Junyu Dong(董军宇), Christian Böhm(陈学恩), Xueen Chen. Chin. Phys. B, 2020, 29(10): 108901.
[4] Pyramid scheme model for consumption rebate frauds
Yong Shi(石勇), Bo Li(李博), Wen Long(龙文). Chin. Phys. B, 2019, 28(7): 078901.
[5] Theoretical analyses of stock correlations affected by subprime crisis and total assets: Network properties and corresponding physical mechanisms
Shi-Zhao Zhu(朱世钊), Yu-Qing Wang(王玉青), Bing-Hong Wang(汪秉宏). Chin. Phys. B, 2019, 28(10): 108901.
[6] Coordinated chaos control of urban expressway based on synchronization of complex networks
Ming-bao Pang(庞明宝), Yu-man Huang(黄玉满). Chin. Phys. B, 2018, 27(11): 118902.
[7] Detecting overlapping communities based on vital nodes in complex networks
Xingyuan Wang(王兴元), Yu Wang(王宇), Xiaomeng Qin(秦小蒙), Rui Li(李睿), Justine Eustace. Chin. Phys. B, 2018, 27(10): 100504.
[8] Dominant phase-advanced driving analysis of self-sustained oscillations in biological networks
Zhi-gang Zheng(郑志刚), Yu Qian(钱郁). Chin. Phys. B, 2018, 27(1): 018901.
[9] Ranking important nodes in complex networks by simulated annealing
Yu Sun(孙昱), Pei-Yang Yao(姚佩阳), Lu-Jun Wan(万路军), Jian Shen(申健), Yun Zhong(钟赟). Chin. Phys. B, 2017, 26(2): 020201.
[10] Empirical topological investigation of practical supply chains based on complex networks
Hao Liao(廖好), Jing Shen(沈婧), Xing-Tong Wu(吴兴桐), Bo-Kui Chen(陈博奎), Mingyang Zhou(周明洋). Chin. Phys. B, 2017, 26(11): 110505.
[11] Subtle role of latency for information diffusion in online social networks
Fei Xiong(熊菲), Xi-Meng Wang(王夕萌), Jun-Jun Cheng(程军军). Chin. Phys. B, 2016, 25(10): 108904.
[12] Synchronization of Markovian jumping complex networks with event-triggered control
Shao Hao-Yu, Hu Ai-Hua, Liu Dan. Chin. Phys. B, 2015, 24(9): 098902.
[13] Load-redistribution strategy based on time-varying load against cascading failure of complex network
Liu Jun, Xiong Qing-Yu, Shi Xin, Wang Kai, Shi Wei-Ren. Chin. Phys. B, 2015, 24(7): 076401.
[14] Degree distribution and robustness of cooperativecommunication network with scale-free model
Wang Jian-Rong, Wang Jian-Ping, He Zhen, Xu Hai-Tao. Chin. Phys. B, 2015, 24(6): 060101.
[15] Identifying influential nodes based on graph signal processing in complex networks
Zhao Jia, Yu Li, Li Jing-Ru, Zhou Peng. Chin. Phys. B, 2015, 24(5): 058904.
No Suggested Reading articles found!