基于改进BA网络的遗传算法

李阳; 田兴华; 张纪会; 李阳; 田兴华; 张纪会

doi:10.13306/j.1672-3813.2019.02.008

复杂系统与复杂性科学 >

2019 , Vol. 16 >Issue 2: 69 - 76

DOI: https://doi.org/10.13306/j.1672-3813.2019.02.008

基于改进BA网络的遗传算法

李阳 ,
田兴华 ,
张纪会 ,
李阳 ,
田兴华 ,
张纪会

展开

青岛大学复杂性科学研究所,山东青岛 266071

李阳(1995),男,山东聊城人,硕士研究生,主要研究方向为现代启发式算法

收稿日期: 2019-03-26

网络出版日期: 2019-08-19

基金资助

国家自然科学基金(61673228)

收起

Genetic Algorithm Based on an Improved BA Network

LI Yang ,
TIAN Xinghua ,
ZHANG Jihui ,
LI Yang ,
TIAN Xinghua ,
ZHANG Jihui

Expand

Institute of Complexity Science,Qingdao University,Qingdao 266071,China

Received date: 2019-03-26

Online published: 2019-08-19

Fold

摘要

遗传算法是基于生物进化论设计的一种自然启发式算法,在众多领域都有广泛应用。目前对于遗传算法的研究主要集中于:遗传算法的理论研究、遗传算法的改进及应用。复杂网络是研究由众多个体组成的集体行为和个体间关系的有力模型。为了改进遗传算法性能,在已有的复杂网络与遗传算法相结合的成果基础上,提出了一种基于改进BA网络的遗传算法,实现了对网络结构进一步的改进,并改进了传统遗传算法的选择策略以及为了应对网络中节点的递增采用的种群规模自适应策略,通过数值实验验证了改进算法的性能,结果表明改进算法对于不同类型的函数的寻优能力要优于基本遗传算法以及基于普通BA网络的遗传算法。研究结果对于遗传算法的改进具有一定指导作用

关键词： 改进的BA网络; 群体智能; 遗传算法; 节点度与适应度结合的选择策略; 度的继承; 种群自适应

本文引用格式

李阳 , 田兴华 , 张纪会 , 李阳 , 田兴华 , 张纪会 . 基于改进BA网络的遗传算法[J]. 复杂系统与复杂性科学, 2019 , 16(2) : 69 -76 . DOI: 10.13306/j.1672-3813.2019.02.008

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

Key words： improved BA network; swarm intelligence; genetic algorithm; selection strategy combining degree with fitness; degree inheritance; population adaptation

参考文献

[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.
[32] Bianconi G, Barabási A L. Bose-einstein condensation in complex networks[J]. Physical Review Letters, 2001, 86(24): 5632-5635.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献