×

A selection process for genetic algorithm using clustering analysis. (English) Zbl 1461.90174

Summary: This article presents a newly proposed selection process for genetic algorithms on a class of unconstrained optimization problems. The \( k\)-means genetic algorithm selection process (KGA) is composed of four essential stages: clustering, membership phase, fitness scaling and selection. Inspired from the hypothesis that clustering the population helps to preserve a selection pressure throughout the evolution of the population, a membership probability index is assigned to each individual following the clustering phase. Fitness scaling converts the membership scores in a range suitable for the selection function which selects the parents of the next generation. Two versions of the KGA process are presented: using a fixed number of clusters \( K\) (KGA\( _f\)) and via an optimal partitioning \(K_{opt}\) (KGA\(_o\)) determined by two different internal validity indices. The performance of each method is tested on seven benchmark problems.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
62H30 Classification and discrimination; cluster analysis (statistical aspects)

Software:

Silhouettes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Zhang, M.-X.; Zhang, B.; Zheng, Y.-J.; Bio-Inspired Meta-Heuristics for Emergency Transportation Problems; Algorithms: 2014; Volume 7 ,15-31. · Zbl 1461.90201
[2] Fister, I.; Yang, X.-S.; Fister, I.; Brest, J.; Fister, D.; A brief review of nature-inspired algorithms for optimization; arXiv: 2013; . · Zbl 1301.65045
[3] Yang, X.-S.; ; Nature-Inspired Optimization Algorithms: Amsterdam, The Netherlands 2014; . · Zbl 1291.90005
[4] Nelder, J.A.; Mead, R.; A simplex method for function minimization; Comput. J.: 1965; Volume 7 ,308-313. · Zbl 0229.65053
[5] Hooke, R.; Jeeves, T.A.; “Direct Search” Solution of Numerical and Statistical Problems; J. ACM: 1961; Volume 8 ,212-229. · Zbl 0111.12501
[6] Li, Z.-Y.; Yi, J.-H.; Wang, G.-G.; A new swarm intelligence approach for clustering based on krill herd with elitism strategy; Algorithms: 2015; Volume 8 ,951-964. · Zbl 1461.90187
[7] Krishna, K.; Murty, M.N.; Genetic K-means algorithm; IEEE Trans. Syst. Man Cybern. B Cybern.: 1999; Volume 29 ,433-439.
[8] Wang, G.; Liu, Y.; Xiong, C.; An optimization clustering algorithm based on texture feature fusion for color image segmentation; Algorithms: 2015; Volume 8 ,234-247. · Zbl 07042248
[9] Sarkar, M.; Yegnanarayana, B.; Khemani, D.; A clustering algorithm using an evolutionary programming-based approach; Pattern Recognit. Lett.: 1997; Volume 18 ,975-986.
[10] Cura, T.; A particle swarm optimization approach to clustering; Expert Syst. Appl.: 2012; Volume 39 ,1582-1588.
[11] Das, S.; Abraham, A.; Konar, A.; Automatic kernel clustering with a multi-elitist particle swarm optimization algorithm; Pattern Recognit. Lett.: 2008; Volume 29 ,688-699.
[12] Yang, F.; Sun, T.; Zhang, C.; An efficient hybrid data clustering method based on K-harmonic means and Particle Swarm Optimization; Expert Syst. Appl.: 2009; Volume 36 ,9847-9852.
[13] Jiang, H.; Yi, S.; Li, J.; Yang, F.; Hu, X.; Ant clustering algorithm with K-harmonic means clustering; Expert Syst. Appl.: 2010; Volume 37 ,8679-8684.
[14] Shelokar, P.; Jayaraman, V.K.; Kulkarni, B.D.; An ant colony approach for clustering; Anal. Chim. Acta: 2004; Volume 509 ,187-195.
[15] Zhang, C.; Ouyang, D.; Ning, J.; An artificial bee colony approach for clustering; Expert Syst. Appl.: 2010; Volume 37 ,4761-4767.
[16] Maulik, U.; Mukhopadhyay, A.; Simulated annealing based automatic fuzzy clustering combined with ANN classification for analyzing microarray data; Comput. Oper. Res.: 2010; Volume 37 ,1369-1380. · Zbl 1183.68488
[17] Selim, S.Z.; Alsultan, K.; A simulated annealing algorithm for the clustering problem; Pattern Recognit.: 1991; Volume 24 ,1003-1008.
[18] Sung, C.S.; Jin, H.W.; A tabu-search-based heuristic for clustering; Pattern Recognit.: 2000; Volume 33 ,849-858.
[19] Hall, L.O.; Ozyurt, I.B.; Bezdek, J.C.; Clustering with a genetically optimized approach; IEEE Trans. Evolut. Comput.: 1999; Volume 3 ,103-112.
[20] Cowgill, M.C.; Harvey, R.J.; Watson, L.T.; A genetic algorithm approach to cluster analysis; Comput. Math. Appl.: 1999; Volume 37 ,99-108. · Zbl 1043.62516
[21] Maulik, U.; Bandyopadhyay, S.; Genetic algorithm-based clustering technique; Pattern Recognit.: 2000; Volume 33 ,1455-1465.
[22] Tseng, L.Y.; Yang, S.B.; A genetic approach to the automatic clustering problem; Pattern Recognit.: 2001; Volume 34 ,415-424. · Zbl 0996.68172
[23] Babu, G.P.; Murty, M.N.; A near-optimal initial seed value selection in k-means means algorithm using a genetic algorithm; Pattern Recognit. Lett.: 1993; Volume 14 ,763-769. · Zbl 0802.68116
[24] Agustı, L.; Salcedo-Sanz, S.; Jiménez-Fernández, S.; Carro-Calvo, L.; Del Ser, J.; Portilla-Figueras, J.A.; A new grouping genetic algorithm for clustering problems; Expert Syst. Appl.: 2012; Volume 39 ,9695-9703.
[25] He, H.; Tan, Y.; A two-stage genetic algorithm for automatic clustering; Neurocomputing: 2012; Volume 81 ,49-59.
[26] Maulik, U.; Bandyopadhyay, S.; Mukhopadhyay, A.; ; Multiobjective Genetic Algorithms for Clustering: Applications in Data Mining and Bioinformatics: Berlin, Germany 2011; . · Zbl 1230.68046
[27] Razavi, S.H.; Ebadati, E.O.M.; Asadi, S.; Kaur, H.; An efficient grouping genetic algorithm for data clustering and big data analysis; Computational Intelligence for Big Data Analysis: Berlin, Germany 2015; ,119-142.
[28] Krishnasamy, G.; Kulkarni, A.J.; Paramesran, R.; A hybrid approach for data clustering based on modified cohort intelligence and K-means; Expert Syst. Appl.: 2014; Volume 41 ,6009-6016.
[29] Popat, S.K.; Emmanuel, M.; Review and comparative study of clustering techniques; Int. J. Comput. Sci. Inf. Technol.: 2014; Volume 5 ,805-812.
[30] Mann, A.K.; Kaur, N.; Survey paper on clustering techniques; Int. J. Sci. Eng. Technol. Res.: 2013; Volume 2 ,803-806.
[31] Jain, A.K.; Maheswari, S.; Survey of recent clustering techniques in data mining; Int. J. Comput. Sci. Manag. Res.: 2012; Volume 3 ,72-78.
[32] Latter, B.; The island model of population differentiation: A general solution; Genetics: 1973; Volume 73 ,147-157.
[33] Qing, L.; Gang, W.; Zaiyue, Y.; Qiuping, W.; Crowding clustering genetic algorithm for multimodal function optimization; Appl. Soft Comput.: 2008; Volume 8 ,88-95.
[34] Sareni, B.; Krahenbuhl, L.; Fitness sharing and niching methods revisited; IEEE Trans. Evolut. Comput.: 1998; Volume 2 ,97-106.
[35] Goldberg, D.E.; Richardson, J.; Genetic algorithms with sharing for multimodal function optimization; Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and their Applications: Hillsdale, NJ, USA 1987; ,41-49.
[36] Pétrowski, A.; A clearing procedure as a niching method for genetic algorithms; Proceedings of the IEEE International Conference on Evolutionary Computation: ; ,798-803.
[37] Gan, J.; Warwick, K.; A genetic algorithm with dynamic niche clustering for multimodal function optimisation; Artificial Neural Nets and Genetic Algorithms: Berlin, Germany 1999; ,248-255.
[38] Yang, S.; Li, C.; A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments; IEEE Trans. Evolut. Comput.: 2010; Volume 14 ,959-974.
[39] Blackwell, T.; Branke, J.; Multi-swarm optimization in dynamic environments; Workshops on Applications of Evolutionary Computation: Berlin, Germany 2004; ,489-500.
[40] Li, C.; Yang, S.; A general framework of multipopulation methods with clustering in undetectable dynamic environments; IEEE Trans. Evolut. Comput.: 2012; Volume 16 ,556-577.
[41] Li, C.; Yang, S.; A clustering particle swarm optimizer for dynamic optimization; Proceedings of the IEEE Congress on Evolutionary Computation: ; ,439-446.
[42] Kennedy, J.; Stereotyping: Improving particle swarm performance with cluster analysis; Proceedings of the IEEE Congress on Evolutionary Computation: ; ,1507-1512.
[43] Agrawal, S.; Panigrahi, B.; Tiwari, M.K.; Multiobjective particle swarm algorithm with fuzzy clustering for electrical power dispatch; IEEE Trans.Evolut. Comput.: 2008; Volume 12 ,529-541.
[44] Zhang, J.; Chung, H.S.-H.; Lo, W.-L.; Clustering-based adaptive crossover and mutation probabilities for genetic algorithms; IEEE Trans. Evolut. Comput.: 2007; Volume 11 ,326-335.
[45] Zhang, X.; Tian, Y.; Cheng, R.; Jin, Y.; A Decision Variable Clustering-Based Evolutionary Algorithm for Large-scale Many-objective Optimization; IEEE Trans. Evolut. Comput.: 2016; .
[46] Zhang, H.; Zhou, A.; Song, S.; Zhang, Q.; Gao, X.-Z.; Zhang, J.; A self-organizing multiobjective evolutionary algorithm; IEEE Trans. Evolut. Comput.: 2016; Volume 20 ,792-806.
[47] Vattani, A.; The Hardness of K-Means Clustering in the Plane; 2009; . · Zbl 1380.68204
[48] Holland, J.H.; ; Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence: Ann Arbor, MI, USA 1975; . · Zbl 0317.68006
[49] Jain, A.K.; Data clustering: 50 years beyond K-means; Pattern Recognit. Lett.: 2010; Volume 31 ,651-666.
[50] Aggarwal, C.C.; Reddy, C.K.; ; Data Clustering: Algorithms and Applications: Boca Raton, FL, USA 2013; . · Zbl 1331.62026
[51] Jain, A.K.; Murty, M.N.; Flynn, P.J.; Data clustering: A review; ACM Comput. Surv. (CSUR): 1999; Volume 31 ,264-323.
[52] Xu, R.; Wunsch, D.; Survey of clustering algorithms; IEEE Trans. Neural Netw.: 2005; Volume 16 ,645-678.
[53] Steinhaus, H.; Sur la division des corp materiels en parties; Bull. Acad. Pol. Sci.: 1956; Volume 1 ,801.
[54] Drineas, P.; Frieze, A.; Kannan, R.; Vempala, S.; Vinay, V.; Clustering large graphs via the singular value decomposition; Mach. Learn.: 2004; Volume 56 ,9-33. · Zbl 1089.68090
[55] Halkidi, M.; Batistakis, Y.; Vazirgiannis, M.; Cluster validity methods: Part I; ACM SIGMM Rec.: 2002; Volume 31 ,40-45.
[56] Halkidi, M.; Batistakis, Y.; Vazirgiannis, M.; On clustering validation techniques; J. Intell. Inf. Syst.: 2001; Volume 17 ,107-145. · Zbl 0998.68154
[57] Vendramin, L.; Campello, R.J.; Hruschka, E.R.; Relative clustering validity criteria: A comparative overview; Stat. Anal. Data Min.: 2010; Volume 3 ,209-235. · Zbl 07260245
[58] Halkidi, M.; Batistakis, Y.; Vazirgiannis, M.; Clustering validity checking methods: Part II; ACM SIGMM Rec.: 2002; Volume 31 ,19-27. · Zbl 0998.68154
[59] Rousseeuw, P.J.; Silhouettes: A graphical aid to the interpretation and validation of cluster analysis; J. Comput. Appl. Math.: 1987; Volume 20 ,53-65. · Zbl 0636.62059
[60] Davies, D.L.; Bouldin, D.W.; A cluster separation measure; IEEE Trans. Pattern Anal. Mach. Intell.: 1979; Volume 1 ,224-227.
[61] Biswas, S.; Eita, M.A.; Das, S.; Vasilakos, A.V.; Evaluating the performance of group counseling optimizer on CEC 2014 problems for computational expensive optimization; Proceedings of the 2014 IEEE Congress on Evolutionary Computation: ; ,1076-1083.
[62] Wilcoxon, F.; Individual comparisons by ranking methods; Biom. Bull.: 1945; Volume 1 ,80-83.
[63] Chehouri, A.; Younes, R.; Perron, J.; Ilinca, A.; A Constraint-Handling Technique for Genetic Algorithms using a Violation Factor; J. Comput. Sci.: 2016; Volume 12 ,350-362.
[64] Kennedy, J.; Particle swarm optimization; Encyclopedia of Machine Learning: Berlin, Germany 2011; ,760-766.
[65] Dorigo, M.; Birattari, M.; Stutzle, T.; Ant colony optimization; IEEE Comput. Intell. Mag.: 2006; Volume 1 ,28-39.
[66] Yang, X.-S.; Firefly algorithm, stochastic test functions and design optimisation; Int. J. Bio-Inspir. Comput.: 2010; Volume 2 ,78-84.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.