Genetic Algorithms

Published: 2013-02-14
 

I got to work with genetic algorithms for some time. And I think it is just amazing how well they work in practice. But when looking at different meta-heuristic search algorithms, it becomes clear that natural evolution as a search algorithm combines various best-of-breed aspects that make it vastly superior. The following fundamentals are illustrated following Russell and Norvig—Artificial Intelligence: A Modern Approach. I think the authors did a magnificent job both in classifying and structuring the algorithms and in bringing them into a logical order. If you are interested in AI, this is definitely the book to read.

We are now talking about finding the solution to an arbitrary optimization problem (e.g. the best job schedule, the best circuit layout, ...). The search space of the problem is the solution space as defined by the set of all possible candidate solutions. If the search space is too large to be explored systematically (e.g., if it is infinite/continuous), local search algorithms were shown to produce "good enough" solutions in reasonable time. They maintain only a single current state (rather than e.g. a search path) and thus operate with a constant amount of memory, regardless of the size of the search space. In general, local search algorithms move only to neighboring states of the current state (rendering them local). The shape of the search space (called state space landscape) is defined by an objective function. Such a state space landscape has a "location" (defined by the state) and an "elevation" or objective value (defined by the value of the state according to the objective function). Depending on whether the problem is cast as an maximization or minimization problem, the aim is either to find the lowest valley (a global minimum) or the highest peak (a global maximum). Since these two problems can easily be converted from one to the other, in the following we will only consider maximization problems. Often, such landscapes also contain local maxima (a peak that is higher than each of its neighboring states, but lower than the global maximum) and plateaux (areas where the objective function is flat). An example of such a state space landscape is given below. Note that in practice, one often has multiple optimization parameters, rendering the search space as a multidimensional landscape.


Example of a one-dimensional state space landscape as defined by an objective function.

A hill-climbing search is simply a loop that moves to neighboring states in the direction of increasing value (that is, uphill) and terminates when it reaches a peak. This simple greedy algorithm often makes rapid initial progress but gets stuck on local maxima (instead of global maxima) or plateaux (where it lacks "guidance" in which direction to proceed). To circumvent this, stochastic hill climbing chooses at random from several possible uphill moves (i.e. if the landscape is multidimensional). In case of many (e.g. thousands) of neighboring states or successors, one can implement stochastic hill climbing as first-choice hill climbing by generating successors randomly until one is generated that is better than the current state. If the successor can also be worse than the current state, this is called random walk. A purely random walk is highly inefficient, but has better chances of not getting stuck at local maxima. Simulated annealing (named after the annealing process in metallurgy), also accepts a worse successor by a certain probability that decreases over time. Random-restart hill climbing conducts a series of hill-climbing searches, starting from randomly generated initial states.

Instead of a single current state, the local beam search algorithm keeps track of k states. At each step, it generates all successors of all k states, but keeps only the k best successors of the complete list. Although this may initially seem like running k random-restart hill-climbing algorithms in parallel, the difference is that it quickly abandons unfruitful searches, concentrating resources on where most progress is being made. Local beam search can suffer from a reduction of diversity among the k states (e.g. if a single state has more than k successor states which are superior to any other successor state), concentrating the states in a small region of the state space and making it little more then an expensive version of hill climbing. Stochastic beam search (analogous to stochastic hill climbing) tries to circumvent this problem by choosing k successors at random with the probability being an increasing function of the objective value.

When calling the successors "offspring" and their objective value "fitness", stochastic beam search resembles an evolutionary process of asexual reproduction and natural selection. A genetic algorithm or GA makes this a sexual reproduction by combining two parent states or individuals instead of modifying a single state. This combination is called crossover and highly dependent on the problem domain. If the individuals are sequences of anything, a crossover means that they are cut at a random crossover point and the two different halves are combined. Depending on the diversity of the parents, crossover can produce individuals that are quite different from either parent. The population is often more diverse in the beginning, so crossover (like simulated annealing) makes the algorithm take large steps in the search space early in the process and smaller steps later when individuals become more similar. Crossover also bears the advantage that it can combine different parts of individuals that evolved independently and perform useful functions, thus raising the level of granularity at which the search operates. Eventually, as in stochastic beam search, all individuals are also modified or mutated by a certain probability. The next generation of the population is then chosen from the newly generated ones, according to the objective function or fitness function. As was pointed out above, this fitness function defines the search space landscape and thus is highly important for the effectiveness of the algorithm.

Of course, genetic algorithms are a crude simplification of the complex real-world evolutionary process. From the many differences, the most important is probably that the genes themselves encode parts of the mechanisms of the biological processes (e.g., mate-selection, crossover and mutation processes and probabilities) as well as the mechanisms by which the genes are translated into an organism. So in nature, the individuals as well as the search algorithm itself are improved.

I'd love to read your response.
Mail me: moc.sthgisni-edamdnah@jrelsseor