Background

Introduction

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..

• CALCULUS_BASED SEARCH: the main disadvantages of calculus-based search are, firstly, a tendecy for the search to get trapped on local maxima- even though a better solution may exist. All moves from the local maxima seem to decrease the fitness of the solution. Secondly, the application of such searches depends on the existence of derivative, for example, the gradient of the graph under investigation.

• RANDOM SEARCH: This is a brute force approach to difficult functions, also known as enumerated search. Points in the search space are selected randomly. This is a very unintelligent search.

• ITERATIVE HILL-CLIMBING: This method is devised by combining hill-climbing and random search. Once one peak has been found, the hillclimbing process is repeated again at another randomly selected location. This search is performed in isolation hence, it takes no account of the overall idea of the shape of the problem domain.
  

• 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.

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

• F1 and F2 performed the same function
• F1 was expected to lead GA directly to solution with no intermediate stage
• F2 was expected to perform with less difficulty in GAs.

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.

Applications

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.