Finding Multiple Solutions with GA in Multimodal Problems

Finding Multiple Solutions with GA in Multimodal Problems

Marcos Gestal (University of A Coruña, Spain) and Mari Paz Gómez-Carracedo (University of A Coruña, Spain)
Copyright: © 2009 |Pages: 7
DOI: 10.4018/978-1-59904-849-9.ch098
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Traditionally, the Evolutionary Computation (EC) techniques, and more specifically the Genetic Algorithms (GAs) (Goldberg & Wang, 1989), have proved to be efficient when solving various problems; however, as a possible lack, the GAs tend to provide a unique solution for the problem on which they are applied. Some non global solutions discarded during the search of the best one could be acceptable under certain circumstances. The majority of the problems at the real world involve a search space with one or more global solutions and multiple local solutions; this means that they are multimodal problems (Harik, 1995) and therefore, if it is desired to obtain multiple solutions by using GAs, it would be necessary to modify their classic functioning outline for adapting them correctly to the multimodality of such problems.
Chapter Preview
Top

Background: Characterization Of Multimodal Problems

The multimodal problems can be briefly defined as those problems that have multiple global optimums or multiple local optimums.

For this type of problems, it is interesting to obtain the greatest number of solutions due to several reasons; on one hand, when there is not a total knowledge of the problem, the solution obtained might not be the best one as it can not be stated that no better solution could be found at the search space that has not been explored yet. On the other hand, although being certain that the best solution has been achieved, there might be other equally fitted or slightly worst solutions that might be preferred due to different factors (easier application, simpler interpretation, etc.) and therefore considered globally better.

One of the most characteristic multimodal functions used in lab problems are the Rastrigin function (see Fig. 1) which offers an excellent graphical point of view about multimodality means.

Figure 1.

Rastrigin function

Providing multiple optimal (and valid) solutions and not only the unique global solution is crucial in multiple environments. Usually, it is very complex to implement in the practice the best solution represents, so it can offers multiple problems: computational cost too high, complex interpretation,…

In these situations it turns out useful to have a range of valid solutions between which that one could choose that, still not being the best solution to the raised problem, offer a level of acceptable adjustment and be simpler to implement, to understand, … that the ideal global one.

Top

Classical Approaches

Nitching methods allow GAs to maintain a genetic population of diverse individuals, so it is possible to locate multiple optimal solutions within a single population.

Key Terms in this Chapter

Crossover: Genetic operation included in evolutionary techniques used to generate the offspring from current population. There are very different methods to perform crossover, but the general idea resides in merging the genetic information of the parents within the offspring with the aim of produce better solutions as generations advance.

Multimodal Problems: A special kind of problems where a unique global solution does not exist. Several global optimums or one global optimum with several local optimums (or peaks) can be found around the search space.

Mutation: The other genetic operation included in evolutionary techniques to perform the reproduction stage. Mutation operator introduces new information in the system by random changes applied within the genetic individuals.

Search Space: Set of all possible situations of the problem that we want to solve could ever be in. Combination of all the possible values for all the variables related with the problem.

Evolutionary Technique: Technique which tries to provide solutions for a problem guided by biological principles such as the survival of the fittest. This kind of techniques starts from a randomly generated population which evolves by means of crossover and mutation operations to provide the final solution.

Genetic Algorithm: A special type of evolutionary technique which represents the potential solutions of a problem within chromosomes (usually a collection of binary, natural or real values).

Species: Within the context of genetic algorithm, a subset of genetic individuals with similar genotype (genetic values) which explore the same, or a similar, area of the search space.

Complete Chapter List

Search this Book:
Reset