Name
Abstract | ||
|---|---|---|
A general form of stochastic search is described (random heuristic search), and some of its general properties are proved. This provides a framework in which the simple genetic algorithm (SGA) is a special case. The framework is used to illuminate relationships between seemingly different probabilistic perspectives of SGA behavior. Next, the SGA is formalized as an instance of random heuristic search. The formalization then used to show expected population fitness is a Lyapunov function in the infinite population model when mutation is zero and fitness is linear. In particular, the infinite population algorithm must converge, and average population fitness increases from one generation to the next. The consequence for a finite population SGA is that the expected population fitness increases from one generation to the next. Moreover, the only stable fixed point of the expected next population operator corresponds to the population consisting entirely of the optimal string. This result is then extended by way of a perturbation argument to allow nonzero mutation. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1162/evco.1994.2.4.347 | Evolutionary Computation |
Keywords | Field | DocType |
infinite population model,finite population,sga behavior,expected population fitness increase,average population fitness increase,population fitness,infinite population algorithm,simple genetic algorithm,random heuristic search,linear fitness,expected next population operator,stochastic search,population model,fixed point,convergence,lyapunov function,heuristic search | Lyapunov function,Population,Heuristic,Mathematical optimization,Fitness approximation,Probabilistic logic,Fixed point,Population model,Mathematics,Genetic algorithm | Journal |
Volume | Issue | ISSN |
2 | 4 | 1063-6560 |
Citations | PageRank | References |
26 | 8.45 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael D. Vose | 1 | 752 | 215.67 |
| Alden H. Wright | 2 | 330 | 45.58 |