A clustering based mate selection for evolutionary optimization

Jinyuan Zhang; Aimin Zhou; Guixu Zhang; Hu Zhang

doi:10.3934/bdia.2017010

Article Contents

2017, Volume 2, Issue 1: 77-85. Doi: 10.3934/bdia.2017010

This issue Previous Article Multiple-instance learning for text categorization based on semantic representation Next Article A comparative study of robustness measures for cancer signaling networks

A clustering based mate selection for evolutionary optimization

1.
Shanghai Key Laboratory of Multidimensional Information Processing, Department of Computer Science and Technology, East China Normal University, Shanghai, 200062, China
2.
Beijing Electro-Mechanical Engineering Institute, Beijing, 100074, China

* Corresponding author: A. Zhou
* Corresponding author: A. Zhou

Published: December 2016

This work is supported by the National Natural Science Foundation of China under Grant No. 61673180 and 61703382, the Shanghai Clearing House under the project of 'artificial intelligence methods for complex 0-1 financial optimization', and the Open Project of Shanghai Key Laboratory of Trustworthy Computing under Grant No. 07dz22304201507.

Abstract Full Text(HTML) Figure(2) / Table(2) Related Papers Cited by

Abstract

The mate selection plays a key role in natural evolution process. Although a variety of mating strategies have been proposed in the community of evolutionary computation, the importance of mate selection has been ignored. In this paper, we propose a clustering based mate selection (CMS) strategy for evolutionary algorithms (EAs). In CMS, the population is partitioned into clusters and only the solutions in the same cluster are chosen for offspring reproduction. Instead of doing a whole new clustering process in each EA generation, the clustering iteration process is combined with the evolution iteration process. The combination of clustering and evolving processes benefits EAs by saving the cost to discover the population structure. To demonstrate this idea, a CMS utilizing the k-means clustering method is proposed and applied to a state-of-the-art EA. The experimental results show that the CMS strategy is promising to improve the performance of the EA.

Keywords:

Mathematics Subject Classification: 78M32.

Citation:

FullText(HTML)

Figure 1. Population partition of a typical run for BCS and CMS strategies with CoDE on (a) F2 and (b) F3

Download: Full-size image PowerPoint slide

Figure 2. The error bars of the results obtained by CMS-CoDE with different combinations of control parameters (K, G) over 30 runs on some test instances

Download: Full-size image PowerPoint slide

Table 1. The mean results of the compared methods over 30 independent runs on 20 test instances of 30 variables with 3000,000 FES

	RND	NNS	BCS	CMS
F1	3.21e-08+	0.00e+00≈	0.00e+00≈	0.00e+00
F2	3.14e-01+	8.17e-04+	2.71e-05−	5.66e-05
F3	1.21e+05−	2.13e+05−	2.22e+05≈	2.64e+05
F4	1.08e+01+	3.74e+00+	1.87e-01−	2.72e-01
F5	3.90e+02−	1.00e+03≈	6.85e+02−	8.69e+02
F6	2.65e+01+	7.19e+01+	4.55e+01≈	3.80e+01
F7	4.70e+03+	4.70e+03+	4.70e+03≈	4.70e+03
F8	2.09e+01+	2.08e+01+	2.02e+01−	2.03e+01
F9	1.67e+01+	5.15e-06−	4.65e+00−	7.31e+00
F10	1.63e+02+	3.52e+01−	4.64e+01+	4.11e+01
F11	3.37e+01+	9.85e+00−	1.33e+01≈	1.35e+01
F12	1.88e+05+	1.54e+05+	7.16e+04≈	7.90e+04
F13	8.18e+00+	2.65e+00−	2.58e+00−	2.91e+00
F14	1.33e+01+	1.21e+01−	1.24e+01≈	1.23e+01
F15	6.40e+02+	5.14e+02+	4.71e+02≈	4.78e+02
F16	4.25e+02+	3.00e+02−	3.10e+02≈	3.15e+02
F17	4.66e+02+	3.03e+02−	3.16e+02≈	3.19e+02
F18	9.26e+02−	9.26e+02≈	9.24e+02≈	9.24e+02
F19	9.26e+02≈	9.26e+02−	9.25e+02≈	9.26e+02
F20	9.26e+02≈	9.24e+02−	9.25e+02≈	9.25e+02
+	15	7	1
−	3	10	6
≈	2	3	13

| Show Table

DownLoad: CSV

Table 2. The average CPU time (seconds) used by the four algorithms on F1-F20 with 300,000 function evaluations over 30 runs

	RND	NNS	BCS	CMS
F1	11.68	12.84	17.61	12.99
F2	12.21	12.70	15.02	12.82
F3	12.93	12.83	15.11	13.09
F4	12.99	13.29	15.39	13.31
F5	16.07	15.18	17.08	15.09
F6	11.72	12.76	500.28	12.71
F7	14.54	15.73	17.33	15.58
F8	16.89	17.65	16.89	14.39
F9	14.98	14.46	126.06	12.82
F10	15.06	13.14	13.98	13.09
F11	61.29	58.76	58.64	57.58
F12	46.49	47.59	44.44	42.98
F13	13.06	13.15	14.53	13.00
F14	17.08	16.40	16.32	14.39
F15	113.89	115.58	180.81	115.32
F16	119.73	116.78	171.78	116.16
F17	120.10	117.87	452.28	117.31
F18	123.71	121.59	121.74	120.65
F19	149.03	152.96	152.79	147.89
F20	220.64	217.06	218.65	215.53

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	T. Back, D.B. Fogel and v Michalewicz, Handbook of Evolutionary Computation, Oxford University Press, 1997. doi: 10.1887/0750308958.
[2]	K. Deb and D. E. Goldberg, An investigation of niche and species formation in genetic function optimization, in Proceedings of the 3rd International Conference on Genetic Algorithms. Morgan Kaufmann Publishers Inc. , 1989, 42–50.
[3]	L. J. Eshelman and J. D. Schaffer, Preventing premature convergence in genetic algorithms by preventing incest, in International Conference on Genetic Algorithms, 1991,115–122.
[4]	C.M. Fernandes and A.C. Rosa, Evolutionary algorithms with dissortative mating on static and dynamic environments, Advances in Evolutionary Algorithms, (2008), 181-206.
[5]	S.F. Galán, O.J. Mengshoel and R. Pinter, A novel mating approach for genetic algorithms, Evolutionary Computation, 21 (2013), 197-229.
[6]	A. Gog, C. Chira, D. Dumitrescu and D. Zaharie, Analysis of some mating and collaboration strategies in evolutionary algorithms, in 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, IEEE, 2008,538–542. doi: 10.1109/SYNASC.2008.87.
[7]	K.S. Goh, A. Lim and B. Rodrigues, Sexual selection for genetic algorithms, Artificial Intelligence Review, 19 (2003), 123-152.
[8]	T. Hastie, R. Tibshirani and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction Second edition. Springer Series in Statistics. Springer, New York, 2009. doi: 10.1007/978-0-387-84858-7.
[9]	Y. Jin, Surrogate-assisted evolutionary computation: Recent advances and future challenges, Swarm and Evolutionary Computation, 1 (2011), 61-70. doi: 10.1016/j.swevo.2011.05.001.
[10]	P. Larranaga and J. A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation Kluwer Academic Publishers, 2002. doi: 10.1007/978-1-4615-1539-5.
[11]	J. B. MacQueen, Some methods for classification and analysis of multivariate observations, in Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, Ed. University of California Press, (1967), 281–297.
[12]	G. Ochoa, C. Mädler-Kron, R. Rodriguez and K. Jaffe, Assortative mating in genetic algorithms for dynamic problems, in Applications of Evolutionary Computing, Springer, 2005,617–622. doi: 10.1007/978-3-540-32003-6_65.
[13]	T. S. Quirino, Improving Search in Genetic Algorithms Through Instinct-Based Mating Strategies Ph. D. dissertation, The University of Miami, 2012.
[14]	T. Quirino, M. Kubat and N.J. Bryan, Instinct-based mating in genetic algorithms applied to the tuning of 1-nn classifiers, IEEE Transactions on Knowledge and Data Engineering, 22 (2010), 1724-1737. doi: 10.1109/TKDE.2009.211.
[15]	J. Sanchez-Velazco and J. A. Bullinaria, Sexual selection with competitive/co-operative operators for genetic algorithms, in Neural Networks and Computational Intelligence(NCI). ACTA Press, 2003,191–196.
[16]	R. Sivaraj and T. Ravichandran, A review of selection methods in genetic algorithm, International Journal of Engineering Science and Technology (IJEST), 3 (2011), 3792-3797.
[17]	P. N. Suganthan, N. Hansen, J. J. Liang, K. Deb, Y. P. Chen, A. Auger and S. Tiwari, Problem Definitions and Evaluation Criteria for the cec 2005 Special Session on Real-Parameter Optimization Tech. rep. , Nanyang Technological University, Singapore and Kanpur Genetic Algorithms 369 Laboratory, IIT Kanpur, 2005.
[18]	C.-K. Ting, S.-T. Li and C. Lee, On the harmonious mating strategy through tabu search, Information Sciences, 156 (2003), 189-214. doi: 10.1016/S0020-0255(03)00176-2.
[19]	S. Wagner and M. Affenzeller, Sexualga: Gender-specific selection for genetic algorithms, in Proceedings of the 9th World Multi-Conference on Systemics, Cybernetics and Informatics (WMSCI), 4 (2005), 76–81.
[20]	R. Wang, P.J. Fleming and R.C. Purshousea, General framework for localised multi-objective evolutionary algorithms, Information Sciences, 258 (2014), 29-53. doi: 10.1016/j.ins.2013.08.049.
[21]	Y. Wang, Z. Cai and Q. Zhang, Differential evolution with composite trial vector generation strategies and control parameters, IEEE Transactions on Evolutionary Computation, 15 (2011), 55-66. doi: 10.1109/TEVC.2010.2087271.