Multimodality in Genetic Algorithms


After working and reading a lot of literature on multimodal fitness landscapes in GAs, I found what seemed to me as a conceptual error. The following small hypothesis paper highlights this issue.

 

DO ALGORITHMS FOR TACKLING MULTIMODALITY IN GAs HAVE A FUNDAMENTAL ERROR?
-
Varun Aggarwal

Hypothesis Paper, August 2002

The fundamental question about searching multimodal search space is regarding the set of points desired at the end of the genetic search, are they solutions with high fitness values or points located on peaks? These two sets are different. A peak may have a low fitness value, its characterstic being that points adjacent to it will have lower fitness as compared to it, while points with high fitness value may not be located on peaks. My study of previous works on multimodal GAs show that the functions on which experiments were conducted, the desired motive was to find all the peaks rather than points with high fitness value.

On the other hand, techniques generally being designed for multimodal problems continue to concentrate on high fitness value to choose individuals rather than having a look at the fitness of indviduals around a point. This basic error is approach gives rise to problems such as need for value of niche radius to run the algorithm properly, algorithmic complexity, etc.

Consider the problem to search for maximas. Considering the value of the function for points around an individual to decide its fitness value looks fundamentally more impressive. The core idea is to modify the assignement of fitness from absolute function value to 'relative function value' (incremental function value from neighbouring points). It could be like turning attention from the function to its derivative!!!

I dont dare suggest a complete banishment of idea of fitness value decided by function value at the individual, because it may mean a complete change in the basic SGA and its effect, which I can't contemplate. But a decent change in the fitness function or employment of a hybrid scheme on basis of this concept looks fundamentally more strong and may render better results.


Back to Griha