Designing Evolutionary Algorithms
The essential idea of evolutionary problem solving is quite simple. A population of candidate solutions to the task at hand is evolved over successive iterations of random variation and selection. Random variation provides the mechanism for discovering ne
- PDF / 2,853,909 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 308 Views
A thousand things advance; nine hundred and ninety-nine retreat: that is progress. Henri Frederic Amiel, Journal
The essential idea of evolutionary problem solving is quite simple. A population of candidate solutions to the task at hand is evolved over successive iterations of random variation and selection. Random variation provides the mechanism for discovering new solutions. Selection determines which solutions to maintain as a basis for further exploration. Metaphorically, the search is conducted on a landscape of hills and valleys (see figure 7.1), which is also called a "response surface" in that it indicates the response of the evaluation function to every possible trial solution. The goal of the exploration is most often to locate a solution, or set of solutions, that possesses sufficient quality as measured by the evaluation function. It's not enough to simply find these solutions, however, we need to find them quickly. After all, enumeration will find such solutions too, but for real problems we'd grow old waiting for the answers. The speed with which suitable solutions can be discovered is in part dependent on the choices we make in determining the representation of trial solutions, the evaluation function, the specific variation and selection operators, and the size and initialization of the population, among other facets. The key to designing successful evolutionary algorithms lies in making the appropriate choices for these concerns in light of the problem at hand. Wouldn't it be nice if there were one best choice for each of these parameters that would give us the optimum performance regardless of the problem we are trying to solve? Once we found this superior set up, we could just implement it directly and not have to be concerned with issues of how to represent solutions, how to construct variation operators, or how to decide which solutions to maintain as a basis for further exploration. Unfortunately, it's possible to prove (within some limited assumptions) that, in fact, such an optimum set of choices doesn't exist [499]. Essentially, all search procedures that don't resample points in the state space of possible solutions perform, on average, exactly the same across all problems. Although it might be counterintuitive at first, a hill-climbing algorithm that never resamples points will do exactly as well on average as blind random search without resampling when trying to find the maximum of all possible functions. This holds true for all evolutionary algorithms as well. If you don't know something about the problem you are facing, you have no justification for choosing any particular search algorithm. Z. Michalewicz et al., How to Solve It: Modern Heuristics © Springer-Verlag Berlin Heidelberg 2004
162
7. Designing Evolutionary Algorithms
0.8
0.6
10
Fig. 7.1. The evaluation function can present a landscape of hills and valleys (see Figure 1.2).
At first, this mathematical result might seem a bit depressing. It implies that if you don't utilize some specific knowledge in solving your pro
Data Loading...
