A comparison of localised and global niching methods

Niching methods are a useful extension of evolutionary computation that allow evolutionary algorithms to be applied in multimodal problem domains. Current niching methods use either one of two methods to promote the formation of species within a population. Genetics-based methods, such as fitness sharing or clearing, work directly on the search space of the problem. Alternatively, spatiallystructured evolutionary algorithms are used to place individuals onto a landscape and restrict mating to within isolated demes of population members. This isolation promotes the driving of geographically distant individuals towards separate parts of the search space. This paper introduces the concept of localised niching (LC). LC takes the traditionally global operations used in genetics-based niching and applies them locally in a spatially-structured population. Testing on two well known and difficult benchmark problems indicates that LC not only has the potential to significantly outperform the traditional global niching methods, but is also more resistant to some of the known limitations of genetics-based species formation.PublishedNon Peer ReviewedBessaou, M., P´etrowski, A. & Siarry, P. (2000). “Island Model cooperating with Speciation for Multimodal Optimization” In M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J. J. Merelo & H.-P. Schwefel (eds), Parallel Problem Solving from Nature – PPSN VI. Springer Berlin pp. 437–446. Collins, R. J. & Jefferson, D. R. (1991). “Selection in Massively Parallel Genetic Algorithms” In R. K. Belew & L. B. Booker (eds), Proceedings of the Fourth International Conference on Genetic Algorithms. Morgan Kaufmann Publishers San Mateo, CA. Darwen, P. J. & Yao, X. (1995). “A Dilemma for Fitness Sharing with a Scaling Function” Proceedings of the Second IEEE International Conference on Evolutionary Computation. IEEE Press Piscataway, New Jersey. Davidor, Y. (1991). “A Naturally Occuring Niche & Species Phenomenon: The Model and First Results” In R. K. Belew & L. B. Booker (eds), Proceedings of the Fourth International Conference on Genetic Algorithms (ICGA’91). Morgan Kaufmann Publishers San Mateo, California pp. 257–263. DeJong, K. A. (1975). An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD thesis University of Michigan Ann Arbor, MI. Dissertation Abstracts International 36(10), 5140B, University Microfilms Number 76-9381. DeJong, K. & Sarma, J. (1995). “On Decentralizing Selection Algorithms” In L. J. Eshelman (ed.), Proceedings of the Sixth International Conference on Genetic Algorithms (ICGA’95). Morgan Kaufmann Publishers San Francisco, California pp. 17–23. Dick, G. & Whigham, P. (2005). “The Behaviour of Genetic Drift in a Spatially-Structured Evolutionary Algorithm” 2005 IEEE Congress on Evolutionary Computation. IEEE Press. pp. 1855–1860. Goldberg, D. E., Deb, K. & Horn, J. (1992). “Massive Multimodality, Deception, and Genetic Algorithms” In R. M¨anner & B. Manderick (eds), Parallel Problem Solving from Nature, 2. Elsevier Science Publishers, B. V. Amsterdam pp. 37–46