A Versatile Genetic Algorithm System in Ada: Implementation and Applications
Max Edwards
This section explains the fundamental concepts behind optimisation, and uses these as a basis for introducing the genetic algorithm paradigm.
An optimisation problem is one which can be expressed in terms of some sort of evaluation function, which assigns a given possible solution a suitability rating depending on how well it solves the problem. This evaluation function may either be a cost function, in which case we wish to minimise its output, or a fitness function which must be maximised. For example, the problem of packing a box with objects of various sizes can be seen as an optimisation problem, where the cost function would take a particular packing configuration and calculate the amount of wasted space that the configuration would result in. For simplicity, this section mainly discusses cost functions, which are optimised when they return their minimum value, but the terms "fitness function" and "maximum" can be substituted without loss of meaning.
It is often useful to consider the cost function as representing some kind of (n+1)-dimensional surface, where n is the number of parameters which encode a possible solution. The "height" (in the "y" dimension) of each point on the surface is the cost function's value, given the parameters determined by the other n dimensions. For this purpose it is common to consider solutions as having only 1- or 2- parameters in order to be able to visualise this surface. Of course, most problems have many more than two parameters, but the principle of the model remains the same, and it can provide many insights into how to approach the task of optimisation. Essentially, we wish to find the lowest point on the cost function's "surface", which in most problems lies at the bottom of a "valley" or "hole".
The ease with which optimisation problems can be solved depends almost entirely upon two factors:
• The cardinality of the search space, i.e. the number of items in the set of all possible solutions. This is often infinite, and it is usually found necessary to discretise the search space by dividing it up into a finite number of distinct steps. The number of such steps must be sufficient to describe the "shape" of the cost function "surface" adequately. This in itself is a difficult problem, since there must be enough sample points to ensure that all important optima are present in the search space, and there is no way of guaranteeing this unless the exact locations of these optima are known - "catch 22". In all cases, the cardinality of the search space increases exponentially with each parameter added, so that even modest problems can have vast search spaces.
• the "noisiness" of the cost function; if the shape of the function is any more complicated than a simple smooth curve, which is almost certainly the case, it will contain sub-optimal local minima, which are better than all neighbouring points but not actually the global optimum (as an analogy, water running down a mountain may become trapped in a local point of minimum potential energy, between the mountain and an adjoining hill, instead of reaching the global minimum at sea-level). With a very noisy cost function, there are many local minima, with very steep "gradients" between them, and consequently the problem is extremely difficult to solve.
There are countless known optimisation problems, many of which are in disguise and are not normally expressed in terms of a cost or fitness function, and many of which are routinely solved using very ordinary techniques. However, there exists a class of problems, known as NP-Hard problems, for which no algorithm has yet been found that will guarantee an optimal solution in polynomial time, and for which such an algorithm may well not exist (see Goldschlager 1988 p90, 94; the set of NP-Complete problems is a subset of NP-Hard, for any one of which the discovery of a polynomial-time algorithm will prove the existence of polynomial algorithms for all other NP-Complete problems). Such problems include PCB and VLSI design, time tabling, scheduling, "bin-packing", and the famous Travelling Salesperson Problem (where the shortest possible circular route visiting every city on a given map must be calculated).
For NP-Hard problems, often the only guaranteed method of finding the optimal solution is to try every possible solution point in the search space, using an exhaustive search. Unfortunately, the search space of even a fairly simple problem is usually too large ever to do this in a reasonable amount of time, since as has already been mentioned, every parameter that is added to the problem causes an exponentially increasing number of search points to be created.
In such cases, we are often forced to use sub-optimal search techniques, where rather than spend a prohibitive amount of computation time to achieve absolutely the right answer, we are willing to settle for a solution that is merely good (but almost certainly not perfect), provided that it can be calculated in significantly less time. Many sub-optimal techniques have been suggested, and four are described below in order of increasing sophistication.
• Random search, where solutions are generated at random, and the best of them chosen. Whilst intuitively this approach seems very naive, its advantages are that it is computationally trivial, and more importantly that it gives equal consideration to all parts of the search space, and to all local optima.
• Hill-climbing, where the parameters to a solution are continually adjusted, each time moving the solution to a neighbouring point on the cost surface, until no further improvement is achieved. In its simplest form, this method is very prone to falling into non-global optima.
• Simulated annealing, where the inspiration comes from the physical formation of a low-energy solid lattice as a material cools. The system of problem parameters is initially very "hot", meaning that it has much "thermal energy" available to it. As the parameters are "cooled" along an exponential decay curve, they are slowly altered to minimise the system's energy (i.e. the problem cost function). By allowing the parameters to change at random provided that there is sufficient "thermal energy" remaining in the system to pay for any additional "cost" incurred, the solution is able to escape from local optima during the initial cooling phase. As the temperature drops such drastic changes become less likely, and the solution settles on a near-global optimum.
• Genetic algorithms, or simulated evolution, whereby a set of possible solutions are "mated" together, with good solutions having more chance of being selected for breeding, using a process modelled on natural evolution. This method is explained in greater detail in the next section.