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

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

CLC Number:

TP18

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.

Figures/Tables 15

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 1

Table 2

Table 3

Table 4

Fig.6

Fig.7

Table 5

Table 6

Table 7

Table 8

References 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

Genetic programming algorithm based on cluster tournament and parent matching

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 33

Related Articles 15

Recommended Articles

Metrics

Comments

对比类别	CMGP(1.0)	CMGP(0.99)	CMGP(0.95)
训练误差(F1)	0.107	0.093	0.098
测试误差(F1)	0.176	0.130	0.139
节点个数(F1)	28, 84	29.80	28.10
训练误差(F5)	6.97e-5	2.52e-5	4.98e-5
测试误差(F5)	6.02e-4	3.04e-4	8.32e-4
节点个数(F5)	32.40	28.52	31.16

[1]	Husheng WANG, Baixiao CHEN, Qingzhi YE. Research on anti-chaff jamming method based on measured data [J]. Systems Engineering and Electronics, 2023, 45(7): 2010-2021.
[2]	Fan YANG, Ping MA, Wei LI, Ming YANG. Intelligent ranking evaluation method of simulation models based on siamese network [J]. Systems Engineering and Electronics, 2023, 45(7): 2060-2068.
[3]	Yuqing FENG, Xiaojie FANG, Xuejun SHA, Ge SONG. High-order computation diversity for hybrid carrier system [J]. Systems Engineering and Electronics, 2023, 45(3): 859-868.
[4]	Yiqun ZHANG, Lan LAN, Guisheng LIAO, Jingwei XU. Mainlobe deceptive jammer suppression with FDA-MIMO radarbased on secondary compensation [J]. Systems Engineering and Electronics, 2022, 44(9): 2769-2775.
[5]	Zexuan MA, Jin LI, Yanli LU, Chen CHEN. Network intrusion detection method based on WaveNet and BiGRU [J]. Systems Engineering and Electronics, 2022, 44(8): 2652-2660.
[6]	Haoliang LI, Siwei CHEN, Xuesong WANG. Study on characterization of sea corner reflectors in polarimetric rotation domain [J]. Systems Engineering and Electronics, 2022, 44(7): 2065-2073.
[7]	Yuzhuo WANG, Shengqi ZHU, Ximin LI, Lan LAN. Range ambiguous clutter suppression for FDA MIMO bistatic radar with main lobe correction [J]. Systems Engineering and Electronics, 2022, 44(5): 1483-1494.
[8]	Renjie XU, Lin GONG, Mingren ZHU, Jian XIE, Jingjia YU. Combat plans recommendation method considering relativity and diversity under uncertain information [J]. Systems Engineering and Electronics, 2022, 44(10): 3115-3123.
[9]	Shanyue DOU, Fei WANG, Weiqiang YU, Jianjiang ZHOU, Jun CHEN. Design of Doppler beam sharpening altimeter based on FDA [J]. Systems Engineering and Electronics, 2021, 43(9): 2383-2391.
[10]	Feng ZHU, Qianqian JIANG, Chuan LIN, Xiao YANG. Typical wideband EMI identification based on support vector machine [J]. Systems Engineering and Electronics, 2021, 43(9): 2400-2406.
[11]	Lei LAI, Kun ZOU, Dewei WU, Baozhong LI. Multi-UAV cooperative path planning based on improved MOFA evolution of interactive strategy [J]. Systems Engineering and Electronics, 2021, 43(8): 2282-2289.
[12]	Li WANG, Ziqi LIU. Fault diagnosis of analog circuit for WPA-IGA-BP neural network [J]. Systems Engineering and Electronics, 2021, 43(4): 1133-1143.
[13]	Hao CHEN, Jun'an YANG, Hui LIU. Communication transmitter individual identification based on deep residual adaptation network [J]. Systems Engineering and Electronics, 2021, 43(3): 603-609.
[14]	Guoling ZHANG, Chongming WU, Rui LI, Jie LAI, Qian XIANG. HRRP target recognition method based on one-dimensional stacked pooling fusion convolutional autoencoder [J]. Systems Engineering and Electronics, 2021, 43(12): 3533-3541.
[15]	Ruochen ZHAO, Jingdong WANG, Siyu LIN, Dongze GU. Small building detection algorithm based on convolutional neural network [J]. Systems Engineering and Electronics, 2021, 43(11): 3098-3106.

名称	SGP	FCGP	DPS+BR	TS-S	GACM	CMGP
F1	39.90	49.24	36.36	14.60	54.60	29.80
F2	36.74	47.44	30.71	13.08	56.54	31.14
F3	54.82	63.02	43.60	12.45	44.32	39.24
F4	15.22	45.16	14.40	9.80	13.20	27.38
F5	43.64	44.20	43.60	34.60	44.60	33.60
F6	110.28	80.76	99.33	72.60	83.13	50.32
F7	131.96	128.08	139.47	126.20	122.13	61.84
F8	121.08	97.60	121.87	72.73	110.87	44.80

名称	SGP	FCGP	DPS+BR	TS-S	GACM	CMGP
F1	19.30	28.97	81.16	27.59	86.12	33.85
F2	17.05	27.62	77.80	26.03	84.03	30.16
F3	20.34	27.30	120.17	26.12	95.25	32.20
F4	10.62	23.18	320.20	133.48	250.30	208.98
F5	76.88	90.44	255.60	139.43	231.73	207.75
F6	110.28	135.46	341.60	165.93	243.11	230.16
F7	131.52	178.64	468.80	239.50	273.51	250.80
F8	98.62	102.16	376.80	113.50	234.82	103.06