Genetic Algorithms and Multimodal Search - Advancing Artificial Intelligence Through Biological Process Applications - page 234

complex to implement in practice the best solution,
so it can offer multiple problems: computational
cost too high, complex interpretation, difficulty
in the acquisition of information, etc.
In these situations it is useful to have a choice
of several valid solutions and, although they are
not the best solution to the problem, they might
offer a level of acceptable adjustment, be simpler
to implement, to understand or to distribute than
the ideal global one.

among the different individuals. Other direct route
for avoiding the diversity loss involves focusing
on the elimination of duplicate partial high fitness
solutions (Landgon, 1996).
Some other of the approaches try to solve
this problem by means of the dynamic variation
of crossover and mutation rates (Ursem, 2002).
In that way, when diversity decreases, a higher
amount of mutations are done in order to increase
the exploration through the search space; when
diversity increases, the mutations decrease and
crossovers increase with the aim of improving
exploitation in optimal solution search. There
are also proposals of new genetic operators or
variations of the actual ones. For example, some
of the crossover algorithms that improve diversity
and that should be highlighted are BLX (Blend
Crossover) (Eshelman & Schaffer, 1993), SBX
(Simulated Binary Crossover) (Deb & Agrawal,
1993), PCX (Parent Centric Crossover) (Deb,
2003), CIXL2 (Confidence Interval Based Cross-
over using L2 Norm) (Ortiz, Hervás & García,
2005) or UNDX (Unimodal Normally Distributed
Crossover) (Ono & Kobayashi, 1999).
Regarding replacement algorithms, schemes
that may keep population diversity have been also
looked for. An example of this type of schemes
is crowding (DeJong, 1975) (Mengshoel & Gold-
berg, 1999). Here, a newly created individual is
compared to a randomly chosen subset of the
population and the most closely individual is
selected for replacement. Crowding techniques
are inspired by Nature where similar members in
natural populations compete for limited resources.
Likewise, dissimilar individuals tend to occupy
different niches and are unlikely to compete
for the same resource, so different solutions are
provided.
Fitness sharing was firstly implemented
by Goldberg and Richardson for being used on
multimodal functions (Goldberg & Richardson,
1987). The basic idea involves determining, from
the fitness of each solution, the maximum number
of individuals that can remain around it, awarding

EvOLUTIONARy COMPUTATION
AND MULTIMODAL PRObLEMS

As it has been mentioned, the application of
EC techniques to the resolution of multimodal
problems sets out the difficulty that this type of
techniques shows since they tend to solely provide
the best of the found solutions and to discard
possible local optima that might have been found
throughout the search. Quite many modifications
have been included in the traditional performance
of the GA in order to achieve good results with
multimodal problems.
A crucial aspect when obtaining multiple
solutions consists on keeping the diversity of
the genetic population, distributing as much as
possible the genetic individuals throughout the
search space.

Classic Approaches

Niching methods allow GAs to maintain a genetic
population of diverse individuals, so it is possible
to locate multiple optimal solutions within a single
population.
In order to minimise the impact of homogeni-
sation, or at least to restrict it to later states of
searching phase, several alternatives have been
designed, based most of them on heuristics. One
of the first alternatives for promoting the diversity
was the applications of scaling methods to the
population in order to emphasize the differences