Title :
A classification tree for speciation
Author :
Pétrowski, Alain ; Genet, Marc Girod
Author_Institution :
Dept. Inf., Inst. Nat. des Telecommun., Evry, France
Abstract :
The most efficient speciation methods suffer from a quite high complexity from O(n c(n)) to O(n2), where c(n) is a factor that can be proportional to n, the population size. A speciation method based on a classification tree is presented, having a complexity of O(n log n). The population is considered as a set of attribute vectors to train the classification tree. The splitting method of the subsets of individuals associated to the nodes is a vector quantization algorithm. The stopping criterion of the tree induction is based on a heuristic, able to recognize whether the set of the individuals associated to a node of the tree is a subpopulation or not. Experimental results for two easy and two hard multimodal optimization problems are presented. These problems are solved with a high reliability. Moreover, experiments indicate that not only does an explicit speciation algorithm reduce the complexity of the used niching method, but it also reduces the required number of evaluations of the fitness function
Keywords :
computational complexity; evolutionary computation; tree data structures; trees (mathematics); vector quantisation; attribute vectors; classification tree; complexity; explicit speciation algorithm; fitness function; heuristic; multimodal optimization problems; niching method; population size; speciation methods; splitting method; stopping criterion; tree induction; vector quantization algorithm; Classification tree analysis; Clustering algorithms; Evolutionary computation; Genetic mutations; Performance evaluation; Testing; Vector quantization;
Conference_Titel :
Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on
Conference_Location :
Washington, DC
Print_ISBN :
0-7803-5536-9
DOI :
10.1109/CEC.1999.781927
