Article Contents
Article Contents

# A clustering based mate selection for evolutionary optimization

• * Corresponding author: A. Zhou
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.
• 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.

Mathematics Subject Classification: 78M32.

 Citation:

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

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

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

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
•  [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.

Figures(2)

Tables(2)