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.

GAs, Hill-climbers and Recombination

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.

Genetic Algorithm and Heuristic Search

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 :

  1. The problems addressed by heuristic search often specify a starting state and/or a a goal state, whereas the problems addressed by GAs rarely do.
  2. GAs are typically applied to problems that require only the location of a vertex that satisfies the search whereas heuristic search often require the construction of a path through the graph.
  3. GAs are often applied to problems that do not specify how an acceptable solution can be recognized.
  4. The graphs searched via heuristic algorithms often have some predined connectivity determined. Eg: the mechanical properties of a puzzle
  5. GAs navigate on several graphs, whereas state space search algorithm tend to navigate on a single graph.

Other Searchs

There are many optimization techniques, some of which are only applicable to limited domains..

GAs offer much potential and advantages over the above algorithm:
GAs deal with parameters of finite length, which are coded using a finite alphabet, rather than directly manipulating the parameters themselves. This means that the search is unconstrained neither by the continuity of the function under investigation, nor the existence of a derivative function.

Evaluation of the performance of candidate solutions is found using objective, payoff information. While this makes the search domain transparent to the algorithm and frees it from the constraint of having to use auxiliary or derivative information, it also means that there is an upper bound to its performance potential.

Search from a population, not a single point. In this way, GAs find safety in numbers. Solution would not be trapped in local maxima since search for solutions by several individuals are carried out in parrallel. If diversity in individuals is maintained, local maxima would not be mistaken as the global optima.

Search via sampling, a blind search. GAs achieve much of their breadth by ignoring information except that concerning payoff. Other methods rely heavily on such information, and in problems where the necessary information is not available or difficult to obtain, these other techniques break down.

GAs remain general by exploiting information available in any search problem. GAs process similarities in the underlying coding together with information ranking the structures according to their survival capability in the current environment. By exploiting such widely-available information, GAs may be applied to virtually any problem.

What makes a Problem Hard for GAs?

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.


In Engineering

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

In TV Commercials

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

Building Aircraft

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.