| 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.
|
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
|
| No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
