Niching method using clustering crowding

Abstract

This study analyzes drift phenomena of deterministic crowding and probabilistic crowding by using equivalence class model and expectation proportion equations. It is proved that the replacement errors of deterministic crowding cause the population converging to a single individual, thus resulting in premature stagnation or losing optional optima. And probabilistic crowding can maintain equilibrium multiple subpopulations as the population size is adequate large. An improved niching method using clustering crowding is proposed. By analyzing topology of fitness landscape using hill valley function and extending the search space for similarity analysis, clustering crowding determines the locality of search space more accurately, thus greatly decreasing replacement errors of crowding. The integration of deterministic and probabilistic replacement increases the capacity of both parallel local hill climbing and maintaining multiple subpopulations. The experimental results optimizing various multimodal functions show that, the performances of clustering crowding, such as the number of effective peaks maintained, average peak ratio and global optimum ratio are uniformly superior to those of the evolutionary algorithms using fitness sharing, simple deterministic crowding and probabilistic crowding.

Keywords

evolutionary computation / genetic drift / niche / clustering crowding

References

[1] Goldberg D E, Richardson J. Genetic algorithms with sharing for multimodal function optimization[A]. Proc 2nd Int Conf Genetic Algorithms[C]. 1987. 41–49.

[2] JelasityM. GAS, a concept on modeling species in genetic algorithms[J]. Artificial Intelligence, 1998, 99(1): 1-19

[3] DeJongK AAn analysis of the behavior of a class of genetic adaptive systems[D], 1975, Ann Arbor, Univ of Michigan

[4] MahfoudS WNiching Methods for genetic algorithms [D], 1995, Urbana-Champaign, Univ of Illinois

[5] Mengshoel O J, Goldberg D E. Probabilistic crowding: deterministic crowding with probabilistic replacement, Illinois Genetic Algorithms Laboratory [R]. Univ of Illinois, Urbana-Champaign, Tech. Rep. 99004, Jan. 1999.

[6] Ursem R. Multinational evolutionary algorithms[A]. Proc 1999 IEEE Int Conf Evolutionary Computation [C]. 1999. 1633–1640.

[7] Gan J, Warwick K. Dynamic niche clustering: a fuzzy variable radius niching technique for multimodal optimization in GAs[A]. Proc 2001 IEEE Int Conf Evolutionary Computation[C]. 2001. 215–222.

[8] SareniB, KrähenbühlL. Fitness sharing and niching methods revisited[J]. IEEE Trans Evolutionary Computation, 1998, 2(1): 97-106

[9] Pétrowski A. A clearing procedure as a niching method for genetic algorithms[A]. Proc 1996 IEEE Int Conf Evolutionary Computation[C]. 1996. 798–803.