Abstract：Genetic algorithm (GA) is a natural heuristic algorithm based on biological evolutionism, which has been widely used in numerous fields. At present, studies on GA are mainly focused on theoretical research, improvement and applications of GA. In order to improve the performance of GA, this paper proposes a GA based on an improved BA network and existed research results combining complex networks with GAs, in view that complex networks are powerful model of collective behavior and individual relationships in a group composed of many individuals. The improved GA realizes further improvement of the network structure and improves the selection strategy of the traditional GA and the population size adaptive strategy adopted in response to the incremental use of nodes in the network. The specific steps and methods of the improved algorithm are given in detail and the performance of the improved algorithm is verified by numerical experiments. The results show that the improved algorithm performs better both than the basic GA and GA based on ordinary BA network. The results have a certain guiding role for the improvement of GA
李阳, 田兴华, 张纪会. 基于改进BA网络的遗传算法[J]. 复杂系统与复杂性科学, 2019, 16(2): 69-76.
LI Yang, TIAN Xinghua, ZHANG Jihui. Genetic Algorithm Based on an Improved BA Network. Complex Systems and Complexity Science, 2019, 16(2): 69-76.
吴玫, 陆金桂. 遗传算法的研究进展综述[J]. 机床与液压, 2008,36(3): 176-179.Wu Mei, Lu Jingui. Summary of research progress of the genetic algorithms[J]. Machine Tool & Hydraulics, 2008, 36(3): 176-179.
[3]
S Forrest. Genetic algorithms: principles of natural selection applied to computation[J]. Science, 1993, 261(5123), 872-878.
张晓伟, 刘三阳. 一种信赖域遗传算法[J]. 系统工程与电子技术, 2007, 29(8): 1377-1380, 1384.Zhang Xiaowei, Liu Sanyang. Genetic algorithm based on trust region method[J]. Systems Engineering and Electronics, 2007, 29(8): 1377-1380, 1384.
[6]
彭勇刚, 罗小平, 韦巍.一种新的模糊自适应模拟退火遗传算法[J]. 控制与决策, 2009, 24(6): 843-848, 853.Peng Yonggang, Luo Xiaoping, Wei Wei. New fuzzy aadaptive simulated annealing genetic algorithm[J]. Control and Decision, 2009, 24(6): 843-848, 853.
[7]
Javadi AA, Farmani R, Tan TP. A hybrid intelligent genetic algorithm[J]. Advanced Engineering Informatics, 2005, 4(4): 255-262.
[8]
Srinivas M, Patnaik LM. Adaptive probabilities of crossover and mutations in genetic algorithms[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1994, 24(4): 656-667.
[9]
黄宜军, 章卫国, 刘小雄. 一种新的自适应退火遗传算法[J]. 西北工业大学学报, 2006, 24(5): 571-575.Huang Yijun, Zhang Weiguo, Liu Xiaoxiong. An improved adaptive simulated annealing genetic algorithm (GA)[J]. Journal of Northwestern Polytechnical University, 2006, 24(5): 571-575.
王小刚, 梁仕贤, 王福利.加入局部搜索的非劣分层多目标遗传算法[J]. 东北大学学报(自然科学版), 2007, 28(7): 921-924.Wang Xiaogang, Liang Shixian, Wang Fuli. A multiobjective non-dominated sorting genetic algorithm with local searching[J]. Journal of Northeastern University(Natural Science), 2007, 28(7): 921-924.
[12]
刘淳安, 王宇平. 基于新模型的多目标遗传算法[J]. 西安电子科技大学学报(自然科学版), 2005, 32(2): 260-263, 267.Liu Chun'an, Wang Yuping. A multi-objective genetic algorithm based on a new model[J]. Journal of Xidian University(Natural Science), 2005, 32(2): 260-263, 267.
[13]
祁荣宾, 钱锋, 杜文莉, 等. 基于精英选择和个体迁移的多目标遗传算法[J]. 控制与决策, 2007, 22(2): 164-168.Qi Rongbin, Qian Feng, Du Wenli, et al. Multiobjective genetic algorithm based on elitist selection and individual migration[J]. Control and Decision, 2007, 22(2): 164-168.
[14]
祝希路, 王柏. 一种基于社团划分的小生境遗传算法[J]. 控制与决策, 2010, 25(7): 1113-1116.Zhu Xilu, Wang Bai. Niche genetic algorithm based on cluster division[J]. Control and Decision, 2010, 25(7): 1113-1116.
[15]
Wei LY, Zhao M. A niche hybrid genetic algorithm for global optimization of continuous multimodal functions[J]. Applied Mathematics and Computation, 2005, 3(3): 649-661.
[16]
陆青, 梁昌勇, 杨善林, 等. 面向多模态函数优化的自适应小生境遗传算法[J]. 模式识别与人工智能, 2009, 22(1): 91-100.Lu Qing, Liang Changyong, Yang Shanlin, et al. An adaptive niche genetic algorithm for multimodal function optimization[J]. Pattern Recognition and Artificial Intelligence, 2009, 22(1): 91-100.
Cantu-Paz E. A Summary of research on parallel genetic algorithm[R].University of Illinois: IlliGAL Report, 1995.
[19]
向丽, 顾培亮. 一种基于遗传算法的双层非线性多目标决策方法[J].系统管理学报, 1999, 8(3): 16-21.Xiang li, Gu Peiliang. A method based on genetic algorithm for bilevel nonlinear multi objective decision making[J]. Journal of Systems & Management, 1999,(3): 16-21.
[20]
Barabási A L. The Network Takeover[J].Nature Physics, 2012, 8(1), 1745-2473.
[21]
Araseki H. Genetic programming with scale-free dynamics[C].EVOLVE-A Bridge Between Probability, Set Oriented Numerics, and Evolutionary Computation IV. Leiden University, 2013: 277-291.
[22]
Araseki H. Effectiveness of scale-free properties in genetic programming[C].SCIS-ISIS.Kobe, Japan, 2012: 285-289.
[23]
Lieberman E, Hauert C, Nowak M A. Evolutionary dynamics on graphs[J].Nature 2005, 433(7023):312-316.
[24]
Giacobini M, Tomassini M, Tettamanzi A. Takeover time curves in random and small-world structured populations[J]. ACM Press the 2005 Conference. Washington DC, USA,2005,10.1145 :1333-1340.
[25]
Oner M K, Garibay I I. Wu A S. Mating networks in steady state genetic algorithms are scalefree[C]. GECCO 2006-Genetic and Evolutionary Computation Conference.Washington DC, USA, 2006: 1423-1424.
[26]
Vora M, Mirnalinee T T. Dynamic small world particle swarm optimizer for function optimization[J]. Nat Comput, 2018, 17(4): 901-917.
[27]
Kleinberg J. The small-world phenomenon: an algorithmic perspective[C]. Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing. New York, USA:ACM, 2000: 163-170.
[28]
Kennedy J. Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance[C]. CEC99. Washington DC, USA, 1999: 1931-1938.
[29]
Barabási A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439),509-512.
[30]
Du W B, Zhang M Y, Ying W. The networked evolutionary algorithm: a network science perspective[J]. Applied Mathematics and Computation, 2018, 338: 33-43.
