January 2017, 2(1): 77-85. doi: 10.3934/bdia.2017010

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

Published  September 2017

Fund Project: 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.

Citation: Jinyuan Zhang, Aimin Zhou, Guixu Zhang, Hu Zhang. A clustering based mate selection for evolutionary optimization. Big Data & Information Analytics, 2017, 2 (1) : 77-85. doi: 10.3934/bdia.2017010
References:
[1] T. BackD.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ánO.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. GohA. 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. QuirinoM. 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. TingS.-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. WangP.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. WangZ. 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.

show all references

References:
[1] T. BackD.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ánO.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. GohA. 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. QuirinoM. 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. TingS.-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. WangP.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. WangZ. 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.

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
F13.21e-08+0.00e+00≈0.00e+00≈0.00e+00
F23.14e-01+8.17e-04+2.71e-05−5.66e-05
F31.21e+05−2.13e+05−2.22e+05≈2.64e+05
F41.08e+01+3.74e+00+1.87e-01−2.72e-01
F53.90e+02−1.00e+03≈6.85e+02−8.69e+02
F62.65e+01+7.19e+01+4.55e+01≈3.80e+01
F74.70e+03+4.70e+03+4.70e+03≈4.70e+03
F82.09e+01+2.08e+01+2.02e+01−2.03e+01
F91.67e+01+5.15e-06−4.65e+00−7.31e+00
F101.63e+02+3.52e+01−4.64e+01+4.11e+01
F113.37e+01+9.85e+00−1.33e+01≈1.35e+01
F121.88e+05+1.54e+05+7.16e+04≈7.90e+04
F138.18e+00+2.65e+00−2.58e+00−2.91e+00
F141.33e+01+1.21e+01−1.24e+01≈1.23e+01
F156.40e+02+5.14e+02+4.71e+02≈4.78e+02
F164.25e+02+3.00e+02−3.10e+02≈3.15e+02
F174.66e+02+3.03e+02−3.16e+02≈3.19e+02
F189.26e+02−9.26e+02≈9.24e+02≈9.24e+02
F199.26e+02≈9.26e+02−9.25e+02≈9.26e+02
F209.26e+02≈9.24e+02−9.25e+02≈9.25e+02
+1571
3106
2313
RND NNS BCS CMS
F13.21e-08+0.00e+00≈0.00e+00≈0.00e+00
F23.14e-01+8.17e-04+2.71e-05−5.66e-05
F31.21e+05−2.13e+05−2.22e+05≈2.64e+05
F41.08e+01+3.74e+00+1.87e-01−2.72e-01
F53.90e+02−1.00e+03≈6.85e+02−8.69e+02
F62.65e+01+7.19e+01+4.55e+01≈3.80e+01
F74.70e+03+4.70e+03+4.70e+03≈4.70e+03
F82.09e+01+2.08e+01+2.02e+01−2.03e+01
F91.67e+01+5.15e-06−4.65e+00−7.31e+00
F101.63e+02+3.52e+01−4.64e+01+4.11e+01
F113.37e+01+9.85e+00−1.33e+01≈1.35e+01
F121.88e+05+1.54e+05+7.16e+04≈7.90e+04
F138.18e+00+2.65e+00−2.58e+00−2.91e+00
F141.33e+01+1.21e+01−1.24e+01≈1.23e+01
F156.40e+02+5.14e+02+4.71e+02≈4.78e+02
F164.25e+02+3.00e+02−3.10e+02≈3.15e+02
F174.66e+02+3.03e+02−3.16e+02≈3.19e+02
F189.26e+02−9.26e+02≈9.24e+02≈9.24e+02
F199.26e+02≈9.26e+02−9.25e+02≈9.26e+02
F209.26e+02≈9.24e+02−9.25e+02≈9.25e+02
+1571
3106
2313
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
F111.6812.8417.6112.99
F212.2112.7015.0212.82
F312.9312.8315.1113.09
F412.9913.2915.3913.31
F516.0715.1817.0815.09
F611.7212.76500.2812.71
F714.5415.7317.3315.58
F816.8917.6516.8914.39
F914.9814.46126.0612.82
F1015.0613.1413.9813.09
F1161.2958.7658.6457.58
F1246.4947.5944.4442.98
F1313.0613.1514.5313.00
F1417.0816.4016.3214.39
F15113.89115.58180.81115.32
F16119.73116.78171.78116.16
F17120.10117.87452.28117.31
F18123.71121.59121.74120.65
F19149.03152.96152.79147.89
F20220.64217.06218.65215.53
RND NNS BCS CMS
F111.6812.8417.6112.99
F212.2112.7015.0212.82
F312.9312.8315.1113.09
F412.9913.2915.3913.31
F516.0715.1817.0815.09
F611.7212.76500.2812.71
F714.5415.7317.3315.58
F816.8917.6516.8914.39
F914.9814.46126.0612.82
F1015.0613.1413.9813.09
F1161.2958.7658.6457.58
F1246.4947.5944.4442.98
F1313.0613.1514.5313.00
F1417.0816.4016.3214.39
F15113.89115.58180.81115.32
F16119.73116.78171.78116.16
F17120.10117.87452.28117.31
F18123.71121.59121.74120.65
F19149.03152.96152.79147.89
F20220.64217.06218.65215.53
[1]

Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial & Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565

[2]

Gurkan Ozturk, Mehmet Tahir Ciftci. Clustering based polyhedral conic functions algorithm in classification. Journal of Industrial & Management Optimization, 2015, 11 (3) : 921-932. doi: 10.3934/jimo.2015.11.921

[3]

Yuanyuan Huang, Yiping Hao, Min Wang, Wen Zhou, Zhijun Wu. Optimality and stability of symmetric evolutionary games with applications in genetic selection. Mathematical Biosciences & Engineering, 2015, 12 (3) : 503-523. doi: 10.3934/mbe.2015.12.503

[4]

Guojun Gan, Kun Chen. A soft subspace clustering algorithm with log-transformed distances. Big Data & Information Analytics, 2016, 1 (1) : 93-109. doi: 10.3934/bdia.2016.1.93

[5]

Ruiqi Yang, Dachuan Xu, Yicheng Xu, Dongmei Zhang. An adaptive probabilistic algorithm for online k-center clustering. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2018057

[6]

Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007

[7]

Mohamed A. Tawhid, Kevin B. Dsouza. Hybrid binary dragonfly enhanced particle swarm optimization algorithm for solving feature selection problems. Mathematical Foundations of Computing, 2018, 1 (2) : 181-200. doi: 10.3934/mfc.2018009

[8]

Yongbin Ou, Cun-Quan Zhang. A new multimembership clustering method. Journal of Industrial & Management Optimization, 2007, 3 (4) : 619-624. doi: 10.3934/jimo.2007.3.619

[9]

Chuang Xu. Strong Allee effect in a stochastic logistic model with mate limitation and stochastic immigration. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2321-2336. doi: 10.3934/dcdsb.2016049

[10]

Hassan Najafi Alishah, Pedro Duarte. Hamiltonian evolutionary games. Journal of Dynamics & Games, 2015, 2 (1) : 33-49. doi: 10.3934/jdg.2015.2.33

[11]

Shui-Nee Chow, Kening Lu, Yun-Qiu Shen. Normal forms for quasiperiodic evolutionary equations. Discrete & Continuous Dynamical Systems - A, 1996, 2 (1) : 65-94. doi: 10.3934/dcds.1996.2.65

[12]

Alexey Cheskidov, Landon Kavlie. Pullback attractors for generalized evolutionary systems. Discrete & Continuous Dynamical Systems - B, 2015, 20 (3) : 749-779. doi: 10.3934/dcdsb.2015.20.749

[13]

Andrzej Swierniak, Michal Krzeslak. Application of evolutionary games to modeling carcinogenesis. Mathematical Biosciences & Engineering, 2013, 10 (3) : 873-911. doi: 10.3934/mbe.2013.10.873

[14]

Elissar Nasreddine. Two-dimensional individual clustering model. Discrete & Continuous Dynamical Systems - S, 2014, 7 (2) : 307-316. doi: 10.3934/dcdss.2014.7.307

[15]

Elissar Nasreddine. Well-posedness for a model of individual clustering. Discrete & Continuous Dynamical Systems - B, 2013, 18 (10) : 2647-2668. doi: 10.3934/dcdsb.2013.18.2647

[16]

Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025

[17]

Guojun Gan, Qiujun Lan, Shiyang Sima. Scalable clustering by truncated fuzzy $c$-means. Big Data & Information Analytics, 2016, 1 (2&3) : 247-259. doi: 10.3934/bdia.2016007

[18]

Hans Weinberger. The approximate controllability of a model for mutant selection. Evolution Equations & Control Theory, 2013, 2 (4) : 741-747. doi: 10.3934/eect.2013.2.741

[19]

Jim M. Cushing. The evolutionary dynamics of a population model with a strong Allee effect. Mathematical Biosciences & Engineering, 2015, 12 (4) : 643-660. doi: 10.3934/mbe.2015.12.643

[20]

Amy Veprauskas, J. M. Cushing. Evolutionary dynamics of a multi-trait semelparous model. Discrete & Continuous Dynamical Systems - B, 2016, 21 (2) : 655-676. doi: 10.3934/dcdsb.2016.21.655

 Impact Factor: 

Metrics

  • PDF downloads (15)
  • HTML views (147)
  • Cited by (0)

Other articles
by authors

[Back to Top]