Genetic techniques

Nature is a robust optimiser. By analysing nature's optimisation mechanism we may find acceptable solution techniques to intractable problems. Two concepts that have most promise are simulated annealing and the genetic techniques.

Simulated annealing borrows its basic ideas from statistical mechanics. A metal cools, and the electrons align themselves in an optimal pattern for the transfer of energy. In general, a slowly cooling system, left to itself, eventually finds the arrangement of atoms which has the lowest energy. This is the behaviour which motivates the method of optimisation by simulated annealing. In simulated annealing we construct a model of a system and slowly decrease the "temperature" of this theoretical system, until the system assumes a minimal energy structure. The problem is how to map our particular problem to such an optimising scheme.

Simulated annealing as an optimisation technique was first introduced to solve problems in discrete optimisation, mainly combinatorial optimisation. Subsequently, this technique has been successfully applied to solve optimisation problems over the space of continuous decision variables. Simulated annealing is a simulation optimisation technique that allows random ascent moves in order to escape the local minima, but a price is paid in terms of a large increase in the computational time required. It can be proven that the technique will find an approximated optimum. The annealing schedule might require a long time to reach a true optimum.

Genetic techniques are optimisers that use the ideas of evolution to optimise a system that is too difficult for traditional optimisation techniques. Organisms are known to optimise themselves to adapt to their environment.

Genetic techniques differ from traditional optimisation procedures:

· work with a coding of the decision parameter set, not the parameters themselves

· search a population of points, not a single point

· use objective function information, not derivatives or other auxiliary knowledge

· use probabilistic transition rules, not deterministic rules

Genetic techniques are probabilistic search optimising techniques that do not require mathematical knowledge of the objective function of the system which they are optimising.

They borrow the paradigms of genetic evolution:

· Selection - the current points in the space are ranked in terms of their fitness by their respective response values. A probability is assigned to each point that is proportional to its fitness, and parents (a mating pair) are randomly selected.

· Crossover - the new point, or offspring, is chosen, based on some combination of the genetics of the two parents.

· Mutation - the location of offspring is also susceptible to mutation, a process which occurs with probability p, by which a offspring is replaced randomly by a new offspring location.

A generalised genetic generates new offspring at once and kills off all of the parents. This modification is important in the simulation environment. Genetic techniques well suite for qualitative or policy decision optimisation such as selecting the best queuing disciplines or network topologies. They can be used to help determine the design of the system and its operation. For applications to inventory systems, job shop, and computer time sharing problems.

Genetic techniques do not have certain shortcomings of other optimisation techniques, and they will usually result in better calculated optima than those found with the traditionally techniques. They can search a response surface with many local optima and find with a high probability the approximate global optimum.