University of Otago logo. Computer and Information Science Seminars

Seminar Homepage


Grant Dick, Department of Information Science


Spatially-Structured Evolutionary Computation for Multimodal Fitness Landscapes


Archway 2 - 1:00 pm, Friday 21 July


Unlike many optimisation methods, evolutionary algorithms (EAs) are able to escape local optima on their way towards the global optimum in a given problem. However, many problems are multimodal and have fitness landscapes with more than one desired optimal solutions. Traditional EAs have trouble searching multimodal fitness landscapes and, through a combination of selection and the stochastic process of mating, will typically converge upon a single point in the search space.

In an analogy to natural evolution, each optimum in a multimodal fitness landscape can be considered a niche, and the individuals that exploit a given niche belong to the same species. Many EAs exist that adopt the species/niche concept so as to discover and maintain multiple solutions to a multimodal fitness landscape. However, the usefulness of these niching EAs (such as fitness sharing and clearing) is hindered by several factors, the most important limitation being the requirement of a priori knowledge of the fitness landscape.

One aspect of speciation that is frequently overlooked in niching EAs is the spatial structure of a population. Population geneticists have long considered population topologies, and the resultant restrictions that they place on mating, a vital component in the divergence of a population into different species. This talk will discuss the effectiveness of spatial population structure in the context of multimodal function optimisation with EAs. It will be shown that population structures, such as a torus, can be incorporated into niching EAs and that the resulting methods are faster and more successful on many problems than the existing "panmictic" niching EAs. More importantly, the proposed technique appears to be less reliant on background knowledge of the problem.

Last modified: Thursday, 28-Jul-2005 17:23:30 NZST

This page is maintained by the seminar list administrator.