A classification tree for speciation

The most efficient speciation methods suffer from a quite high complexity from O(n c(n)) to O(n²), 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