基于聚类锦标赛与父代匹配的遗传规划算法

doi:10.12305/j.issn.1001-506X.2023.08.14

摘要/Abstract

摘要：

在遗传规划算法中, 种群多样性在避免早熟收敛方面有重要作用, 通过控制种群多样性改进算法是遗传规划算法的研究热点。从多样性角度改进算法的选择机制, 提出一种基于聚类锦标赛与父代匹配的遗传规划算法。通过聚类将种群划分为多个子种群, 从而调整算法的选择压力以维持种群多样性, 提高算法的搜索能力。此外, 提取个体的二进制特征, 利用局部匹配对父代进行针对性交叉操作, 从父代成对多样性的角度实现算法在探索和开发之间的较好平衡。对不同基准问题进行了多个对比实验, 实验结果表明所提算法在种群多样性上有较大改善, 在寻优能力和收敛速度上均取得了较好的提升。

关键词: 遗传规划, 选择压力, 父代匹配, 特征提取, 多样性

Abstract:

In the genetic programming algorithm, population diversity plays an important role in avoiding premature convergence. Improving algorithms by controlling population diversity is a hot spot in genetic programming. Therefore, this paper improves the selection mechanism of the algorithm from the perspective of diversity, and proposes a genetic programming algorithm based on clustering tournament mechanism and parent generation matching. The algorithm divides the population into multiple sub populations through clustering so as to adjust the selection pressure of the algorithm to maintain population diversity and to improve the search ability of the algorithm. In addition, the algorithm extracts individual binary features and uses local matching to cross operate the parent generation. From the perspective of parent pair diversity, the algorithm achieves a better balance between the exploration and the exploitation. Multiple comparative experiments on different benchmark problems verify that the population diversity of the proposed algorithm is greatly improved and the optimization ability and convergence speed are better improved.

Key words: genetic programming, selection pressure, parent matching, feature extraction, diversity

中图分类号:

TP18

方伟, 梁静雯, 陆恒杨. 基于聚类锦标赛与父代匹配的遗传规划算法[J]. 系统工程与电子技术, 2023, 45(8): 2405-2414.

Wei FANG, Jingwen LIANG, Hengyang LU. Genetic programming algorithm based on cluster tournament and parent matching[J]. Systems Engineering and Electronics, 2023, 45(8): 2405-2414.

图/表 15

图1

图2

图3

图4

图5

表1

表2

表3

表4

图6

图7

表5

表6

表7

表8

参考文献 33

1	KOZA J R . Genetic programming: on the programming of computers by means of natural selection[M]. Cambridge: MIT press, 1992.
2	程适, 王锐, 伍国华, 等. 群体智能优化算法[J]. 郑州大学学报(工学版), 2018, 39 (6): 1- 2.
	CHENG S , WANG R , WU G H , et al. Swarm intelligence optimization algorithms[J]. Journal of Zhengzhou University (Engineering Science), 2018, 39 (6): 1- 2.
3	LANGDON W B . Genetic programming and data structures[M]. London: Springer Science+Business Media, 1995.
4	MOYANO J M , VENTURA S . Auto-adaptive grammar-guided genetic programming algorithm to build ensembles of multi-label classifiers[J]. Information Fusion, 2021, 78, 1- 19.
5	NGUYEN T H , CAO T T , XUAN H N , et al. Genetic programming for storm surge forecasting[J]. Ocean Engineering, 2020, 215, 107812. doi: 10.1016/j.oceaneng.2020.107812
6	AL-SAHAF H , AL-SAHAF A , XUE B , et al. Automatically evolving texture image descriptors using the multi-tree representation in genetic programming using few instances[J]. Evolutionary Computation, 2021, 29 (3): 331- 366. doi: 10.1162/evco_a_00284
7	贾凌云, 李冬妮, 田云娜. 基于混合蛙跳和遗传规划的跨单元调度方法[J]. 自动化学报, 2015, 41 (5): 936- 948.
	JIA L Y , LI D N , TIAN Y N . An intercell scheduling approach using shuffled frog leaping algorithm and genetic programming[J]. Acta Automatica Sinica, 2015, 41 (5): 936- 948.
8	贺晓宇. 基于遗传规划的混合社区云的调度方法研究[D]. 北京: 北京邮电大学, 2018.
	HE X Y. A genetic programming based scheduling approach for hybrid community clud[D]. Beijing: Beijing University of Posts and Telecommunications, 2018.
9	陈浩杰, 丁国富, 张剑, 等. 求解资源受限多项目调度的改进遗传规划算法[J]. 中国机械工程, 2021, 32 (10): 1213- 1221. doi: 10.3969/j.issn.1004-132X.2021.10.010
	CHEN H J , DING G F , ZHANG J , et al. Improved genetic programming algorithm for RCMPSP[J]. China Mechanical Engineering, 2021, 32 (10): 1213- 1221. doi: 10.3969/j.issn.1004-132X.2021.10.010
10	AFFENZELLER M, WINKLER S M, BURLACU B, et al. Dynamic observation of genotypic and phenotypic diversity for different symbolic regression GP variants[C]//Proc. of the Genetic and Evolutionary Computation Conference Companion, 2017: 1553-1558.
11	KELLY J, HEMBERG E, O'REILLY U M. Improving genetic programming with novel exploration-exploitation control[C]//Proc. of the European Conference on Genetic Programming, 2019: 64-80.
12	UCHII S. Darwin's principle of divergence[C]//Proc. of the 5th Quadrennial International Fellows Conference, 2004.
13	SARENI B , KRAHENBUHL L . Fitness sharing and niching methods revisited[J]. IEEE Trans.on Evolutionary Computation, 1998, 2 (3): 97- 106. doi: 10.1109/4235.735432
14	EKÁRT A, NÉMETH S Z. A metric for genetic programs and fitness sharing[C]//Proc. of the European Conference on Genetic Programming, 2000: 259-270.
15	MAHFOUD S W. Niching methods for genetic algorithms[D]. Urbana-Champaign: University of Illinois, 1995.
16	BARTOLI A , DELORENZO A , MEDVET E , et al. Multi-level diversity promotion strategies for grammar-guided genetic programming[J]. Applied Soft Computing, 2019, 83, 105599. doi: 10.1016/j.asoc.2019.105599
17	杨新武, 杨丽军. 基于交叉模型的改进遗传算法[J]. 控制与决策, 2016, 31 (10): 1837- 1844.
	YANG X W , YANG L J . An improved genetic algorithm based on crossover model[J]. Control and Decision, 2016, 31 (10): 1837- 1844.
18	HELMUTH T, MCPHEE N F, SPECTOR L, et al. Lexicase selection for program synthesis: a diversity analysis. Genetic programming theory and practice XⅢ[M]. RIOLO R, WORZEL W P, KOTANCHEK M, et al. New York: Springer, 2016.
19	CHU T H , NGUYEN Q U , O'NEILL M . Semantic tournament selection for genetic programming based on statistical analysis of error vectors[J]. Information Sciences, 2018, 436, 352- 366.
20	BURLACU B, AFFENZELLER M, KRONBERGER G, et al. Online diversity control in symbolic regression via a fast hash-based tree similarity measure[C]//Proc. of the IEEE Congress on Evolutionary Computation, 2019: 2175-2182.
21	DAY P , NANDI A K . Binary string fitnesscharacterization and comparative partner selection in genetic programming[J]. IEEE Trans.on Evolutionary Computation, 2008, 12 (6): 724- 735.
22	ASLAM M W , ZHU Z , NANDI A K . Diverse partner selection with brood recombination in genetic programming[J]. Soft Computing, 2018, 67, 558- 566.
23	CHEN Q , XUE B , ZHANG M J . Preserving population diversity based on transformed semantics in genetic programming for symbolic regression[J]. IEEE Trans.on Evolutionary Computation, 2020, 25 (3): 433- 447.
24	ROSCA J P. Entropy-driven adaptive representation[C]//Proc. of the Workshop on Genetic Programming: from Theory to Real-World Applications, 1995: 23-32.
25	O'REILLY U M. Using a distance metric on genetic programs to understand genetic operators[C]//Proc. of the IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation, 1997: 4092-4097.
26	KROVI R. Genetic algorithms for clustering: a preliminary investigation[C]//Proc. of the 25th Hawaii International Confe-rence on System Sciences, 1992: 540-544.
27	YANG H Z, LI F C, WANG C M. A densityclustering based niching genetic algorithm for multimodal optimization[C]//Proc. of the International Conference on Machine Learning and Cybernetics, 2005: 1599-1604.
28	XIE H Y , ZHANG M J . Parent selection pressure auto-tuning for tournament selection in genetic programming[J]. IEEE Trans.on Evolutionary Computation, 2012, 17 (1): 1- 19.
29	DOERR B, KÖTZING T, LAGODZINSKI J A G, et al. Bounding bloat in genetic programming[C]//Proc. of the Genetic and Evolutionary Computation Conference, 2017: 921-928.
30	GLICKMAN M R, SYCARA K. Reasons for premature convergence of self-adapting mutation rates[C]//Proc. of the 2000 Congress on Evolutionary Computation, 2000: 62-69.
31	WHITE D R , MCDERMOTT J , CASTELLI M , et al. Better GP benchmarks: community survey results and proposals[J]. Genetic Programming and Evolvable Machines, 2013, 14 (1): 3- 29.
32	ASUNCION A, NEWMAN D. UCI machinelearningrepository[EB/OL]. [2021-09-07]. https://archive.ics.uci.edu/ml/datasets.php.
33	TACKETT W A. Recombination, selection, and the genetic construction of computer programs[D]. Los Angeles: University of Southern California, 1994.

参数名称	参数设置
种群大小	500
迭代次数	100
运行次数	100
交叉概率	0.85
突变概率	0.10
阈值范围	10^-3
聚类锦标赛规模	4
截断系数	0.99
最大深度	6
初始化方式	ramped half and half
精英选择	保留上一代最好的5%个体

缩写	名称	特征数	训练数	测试数
F1	Koza1	1	20	20
F2	Nguyen6	1	20	20
F3	Keijzer13	2	20	600
F4	Vladislavleva4	5	1 024	5 000
F5	Banknote	4	914	458
F6	Diabete	8	512	257
F7	Parkinson	22	504	251
F8	Sonar	60	140	70

实验	参数设置
F1, F2	{+, －, ×, /, sin, cos, eⁿ, ln(\|n\|)}
F3	$ \left\{+, \times, \frac{1}{n}, -n, \sqrt{n}\right\}$
F4	{+, －, ×, /, n²}
F5, F6, F7, F8	{+, －, ×, /, sin, abs, sqrt}

名称	SGP	FCGP	DPS+BR	TS-S	GACM	CMGP
F1	0.24	0.14	0.22	0.45	0.29	0.09
F2	0.16	0.10	0.13	0.43	0.23	0.07
F3	20.45	16.71	16.17	28.21	17.30	15.70
F4	142.41	134.38	143.11	143.67	142.23	136.67
F5	1.00	0.02	0.48	4.43	5.14	0.00
F6	26.72	26.77	26.68	26.95	26.71	26.35
F7	24.78	23.51	23.52	24.13	23.36	23.46
F8	11.92	11.96	10.09	12.85	11.86	10.54

名称	SGP	FCGP	DPS+BR	TS-S	GACM	CMGP
F1	0.39	0.24	0.35	0.70	0.36	0.13
F2	0.27	0.17	0.14	0.83	0.32	0.09
F3	891.45	854.92	728.35	918.63	760.52	771.04
F4	671.52	632.45	676.49	686.93	682.61	640.12
F5	1.65	0.25	0.46	5.31	7.78	0.30
F6	33.76	31.65	32.28	30.53	30.58	28.73
F7	37.90	37.48	37.96	37.32	33.58	36.75
F8	28.72	26.32	28.62	26.67	25.26	24.57