Genetic Algorithms and Multimodal Search

Genetic Algorithms and Multimodal Search

Marcos Gestal (University of A Coruña, Spain), José Manuel Vázquez Naya (University of A Coruña, Spain) and Norberto Ezquerra (Georgia Institute of Technology, USA)
DOI: 10.4018/978-1-59904-996-0.ch013
OnDemand PDF Download:
$37.50

Abstract

Traditionally, the Evolutionary Computation (EC) techniques, and more specifically the Genetic Algorithms (GAs), 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. Most 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 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. The present chapter tries to establish, firstly, the characterisation of the multimodal problems will be attempted. A global view of some of the several approaches proposed for adapting the classic functioning of the GAs to the search of mu ltiple solutions will be also offered. Lastly, the contributions of the authors and a brief description of several practical cases of their performance at the real world will be also showed.
Chapter Preview
Top

Multimodal Problems

The multimodal problems can be defined as those problems that have either multiple global optima or multiple local optima (Harik, 1995).

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 not explored yet. On the other hand, although being certain that the best solution has been achieved, there might be other equally fitted or slightly worse 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 is the Rastrigin function (see Figure 1) which offers an excellent graphical point of view about what multimodality means.

Figure 1.

Rastrigin function: 3D and 2D representations

Providing multiple optimal (and valid) solutions, and not only a unique global solution, is crucial in multiple environments. Usually, it is very 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.

Top

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.

Complete Chapter List

Search this Book:
Reset