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      Accepted manuscript online: 
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] Analysis of cut vertex in the control of complex networks
Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Chin. Phys. B, 2023, 32(2): 028902.
[2] Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding
Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Chin. Phys. B, 2023, 32(1): 018903.
[3] Characteristics of vapor based on complex networks in China
Ai-Xia Feng(冯爱霞), Qi-Guang Wang(王启光), Shi-Xuan Zhang(张世轩), Takeshi Enomoto(榎本刚), Zhi-Qiang Gong(龚志强), Ying-Ying Hu(胡莹莹), and Guo-Lin Feng(封国林). Chin. Phys. B, 2022, 31(4): 049201.
[4] Robust H state estimation for a class of complex networks with dynamic event-triggered scheme against hybrid attacks
Yahan Deng(邓雅瀚), Zhongkai Mo(莫中凯), and Hongqian Lu(陆宏谦). Chin. Phys. B, 2022, 31(2): 020503.
[5] Finite-time synchronization of uncertain fractional-order multi-weighted complex networks with external disturbances via adaptive quantized control
Hongwei Zhang(张红伟), Ran Cheng(程然), and Dawei Ding(丁大为). Chin. Phys. B, 2022, 31(10): 100504.
[6] LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks
Gui-Qiong Xu(徐桂琼), Lei Meng(孟蕾), Deng-Qin Tu(涂登琴), and Ping-Le Yang(杨平乐). Chin. Phys. B, 2021, 30(8): 088901.
[7] Complex network perspective on modelling chaotic systems via machine learning
Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Chin. Phys. B, 2021, 30(6): 060506.
[8] Exploring individuals' effective preventive measures against epidemics through reinforcement learning
Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni (倪顺江), and Shi-Fei Shen(申世飞). Chin. Phys. B, 2021, 30(4): 048901.
[9] 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.
[10] 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.
[11] Modeling and analysis of the ocean dynamic with Gaussian complex network
Xin Sun(孙鑫), Yongbo Yu(于勇波), Yuting Yang(杨玉婷), Junyu Dong(董军宇)†, Christian B\"ohm, and Xueen Chen(陈学恩). Chin. Phys. B, 2020, 29(10): 108901.
[12] Pyramid scheme model for consumption rebate frauds
Yong Shi(石勇), Bo Li(李博), Wen Long(龙文). Chin. Phys. B, 2019, 28(7): 078901.
[13] 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.
[14] 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.
[15] 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.
No Suggested Reading articles found!