|
|
|
| Genetic Algorithm Based on an Improved BA Network |
| LI Yang, TIAN Xinghua, ZHANG Jihui
|
| Institute of Complexity Science,Qingdao University,Qingdao 266071,China |
|
|
|
|
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
|
|
Received: 26 March 2019
Published: 19 August 2019
|
|
|
|
|
|
| [1] |
王小平, 曹立明. 遗传算法: 理论、应用与软件实现[M]. 西安:西安交通大学出版社, 2002:1.
|
| [2] |
吴玫, 陆金桂. 遗传算法的研究进展综述[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.
|
| [4] |
陈辉, 张家树, 张超. 实数编码混沌量子遗传算法[J]. 控制与决策, 2005, 20(11): 1300-1303.Chen Hui, Zhang Jiashu, Zhang Chao. Real-coded chaotic quantum-inspired genetic algorithm[J]. Control and Decision, 2005, 20(11): 1300-1303.
|
| [5] |
张晓伟, 刘三阳. 一种信赖域遗传算法[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.
|
| [10] |
王嵘冰, 徐红艳, 郭军. 自适应的非支配排序遗传算法[J]. 控制与决策, 2018, 33(12): 2191-2196.Wang Rongbing, Xu Hongyan, Guo Jun. Adaptive non-dominated sorting genetic algorithm[J]. Control and Decision, 2018, 33(12): 2191-2196.
|
| [11] |
王小刚, 梁仕贤, 王福利.加入局部搜索的非劣分层多目标遗传算法[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.
|
| [17] |
侯广坤, 骆江鹏. 一种理想并行遗传算法模型[J]. 软件学报, 1999, 10(5): 561-565.Hou Guangkun, Luo Jiangpeng. Modeling Idealized parallel genetic algorithms[J]. Journal of Software, 1999, 10(5): 561-565.
|
| [18] |
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.
|
| [31] |
汪小帆, 李翔, 陈关荣, 等.复杂网络理论及其应用[M]. 北京:清华大学出版社, 2005: 28.
|
|
|
|
