The advent of genetic algorithms has inevitably led to the comparison with the other search algorithms, notably the heuristic search and stochastic hill climbers. In this article, thorough examinations and comparison between genetic algorithm with heuristic search and hill-climbers search would be carried out.
A lot of problems that we face in everday life fall into one particular
class of spaces. These defined spaces require genetic recombination for
successful search and are partially deceptive. A deceptive space
for a search algorithm leads the algortihm away from the global optimum and
towards a local optimum. Results comparing stochastic hill-climbers
against one with 2-point crossover support these claims.
Moreover, an attempt would be made to establish a connection
between genetic algorithm (GAs) and heuristic search.
Last of all, we would also compare the advantages and
disadvantages of other search methods, ableit trivial ones, with the
mainstream genetic algorithm.
A genetic algorithm without crossover and only mutation is a stochastic hill-climbers. Depending on the mutation rate, it can make jumps of varying sizes through the search space.
Recombination (crossover) is the key difference between genetic algorithm and hill-climbers defined above. Recombination allows large, structured jumps in the search space. In other words, it facilitates combination of lower-orderbuilding blocks to form a higher building blocks, if they exist. However, the size of jumps due to crossover in GA depends on the average hamming distance between members of the population(hamming average) or the degree of convergence. If the diversity of the population is small, the hamming average decreases and so does the size of maximium jumps. This leads to exploration of smaller neighbourhood.
From the above discussion, it is clear that GA would emerge as a winner if the distribution of the population is diverse and large. In such case, genetic algorithm would be able to make large, useful and structured jumps even after partial convergence. On the contrary, search would not gain benefit from GAs in least diverse population, in which the hill-climbers search would operate fruitfully.
GAs have genrally been regarded as having little connection with heuristic state-space search. However, an informative correspondence can be establihed, which is based on the observation that state spaces and landscape(GAs) are both labeled, directed, graphs and that algorithms move on these graphs while searching. Naturally, there are differences between these algorithms as they operate on their respective graphs.
These differences are :
There are many optimization techniques, some of which are only applicable to limited domains..
SIMULATED ANNEALING: Invented in 1982 by Kirkpatrick , it is essentially a modified version of hill-climbing. Starting from a random point in the search space, a random move is made. If the move takes us to a higher point, it is accepted, otherwise it is accepted with the probability decresaing with time. The probabilty starts from 1, decreasing towards zero as time passes. As such, any move is accepted at the begining, but as the probability continues to decrease, the probability of accepting negative moves are lowered. Negative moves are essential sometimes, if local maxima are to be escaped, but too many negative moves would lead the search away from the maxima. Again this method deals with one candidate one at a time and so does not build an overall picture of the search space, and no information from previous moves is used to guide the selection of new moves. This technique has been successful in many applications, for example VLSI circuit layout.
Suppose two functions, F1 and F2, were constructed and had the following charateristic
However, the study worked out to be the other way round. The GA actually performed better on F1 and this shows our understanding is incomplete.
In reality, it is often very difficult to define what "hard" is. We often fail to understand how hard a problem GA can solve, how quickly, and with what reliablity. The study of deceptive function has result a subsection of the GA community believing that deceptive problem is the only difficulty for the GA. However, Grefenstette showed that the existence of deception is neither neccessary nor sufficient for a problem to be hard for GA. This then prompted qualification regarding the degree of deception and the type of deception that make a problem hard.
Another attempt to capture GA hardness is centered around the notion of "rugged fitness landscape". Fitness landscape represents each individual as a point in a high-dimensional space. Each of these points is assigned a fitness, an extra dimension visualized as a height. The set of all fitness create a fitness surface. At informal level, it is held that the more rugged a fitness landscape is, the more difficult the problem is. Again it is difficult to quantify "ruggedness" and also this argument has been broken by Horn and Goldberg who managed to pose difficulties for GAs with a smooth fitness surface.
From the above disccussion, it is clear that the criteria for GA hardness
are neither clear nor easy to quantify. Hence, it is exteremely difficult
to determine if one problem is particulary hard for GA.
The Fraunhofer Institute for Manufacturing Engineering and Automation (FhG - IPA) developed a production planning system for a company in the pharmaceutical industry. This company established a production process for a new type of product to make a new market accessible. The kernel of the planning system is an order control algorithm, which builds production orders according to stochastic customer demand.
Two approaches, heuristic search and genetic algorithm,
are taken to compare and constrast the pros and cons of each prospect.
Examining closely different departments of each search, the genetic algorithm
emerge as a clear winner. The reason remains largely due to its independence
from the problem itself and therefore can adapt itself very easily to changes
in the target function or constraints, which are influenced by market survey
results and company restructuring. Also, algorithm developed by heuristic
search requires substantial user know-how in optimisation techniques
and operations research. In constrast, GAs may provide good solutions to a variety of
different problems without the user being required to have such specialised
expertise.
Heuristic vs GA
From January 1993, Channel 4 has been a statutory corporation responsible for its own financial future, dependent on advertising revenue for 96% of its revenue - and responsible for selling its own airtime (a responsibility that had previously been given to the regional ITV companies). Since it is of upmost importance to fill the commercial break with no overlap, no repeat, no gap..., they have to come up with a optimal arrangements to stretch its earning potential to the fullest.
This arrangements were previously done manually (using random search).
However, this was extremely unproductive and tedious As such, it opens an opportunity for genetic algorithms.
The use of genetic algorithm could easily overcomes the constraints posed
by the vast combination and permutation of commercial arrangements. The
solution involved the use of genetic algorithm techniques which allows
the exploration of large search spaces for optimal or near optimal solutions.
This, in contrast to random search which obtain optimal solution in infinite
time, could arrive at a near optimal solution in a short time.
GAs used in TVs
Gradient-based optimizers have been used extensively for aircraft design, but are subject to several limitations. Discrete variables and discontinuous domains are not permitted, the complexity of description cannot be increased during optimization, and the number of function evaluations required in the search increases as the square of the number of design variables. In this paper, genetic algorithms are investigated as an alternative to conventional optimization for the preliminary design of wings. Although genetic algorithms require more function evaluations than gradient-based methods, they are able to operate on discontinuous functions. A special crossover operator is introduced to allow variation of the number of design variables during optimization. This modified genetic algorithm promises to be a useful tool for the exploration of difficult design domains. Gradient-based Optimizer vs GAs in aircraft building
This article has demonstrated a correspondence between GAs and hill-climbing. Relationship has been established between GAs and heuristic state-space search. Links has also been made between GAs and other search alogrithms. All the similarities and dissimilarities between these algorithms have been compared and constrasted. In many cases, it is clear that GAs emerge as a clear winner over other algorithms. Since GAs sound so "wondeful" in many situation, why is it still not very widely ued? This "hardness" for GAs was discussed and though the arguements put forward is far from complete, it gives a rough idea what kind of problems pose difficulties for GAs. Lastly, we have looked at some applications in which GAs have turn out, as predicted, to be the better algorithms than other conventional ones.
D.E. Goldberg. Simple genetic algorithms and the minimal, deceptive problem. Pitman(Morgan Kaufmann), London, 1987.
Genetic Algorithms and Heuristic Search by Terry Jones and Stephanie Forrest Morgan Kaufmann Publisher.
Foundations of Genetic Algorithms by Gregory J.E. Rawlins.
What makes a problem hard fir a genetic algorithm? by S.Forrest and M.Mitchell .
For details of Artificial Life
, please refer to my partner, Chun's second article.