Many problems, for which search is the only known method of finding an answer, still cannot be solved. The search is needed because no algorithm will lead directly to a solution. It fails mainly because it must search through too large a space. Genetic Algorithms (GAs) have been used successfully for these problems. They do so by using the history of the search to explore more promising areas of the space. The history is kept in a population of trials, which are combined with each other. The combinations are designed to exploit the results of each trial as much as possible while continuing the exploration.
The search space of the problems is too large because an answer comprises many variables with a large range. Typical of these are sequencing, or ordering, problems, which are combinatorial. Their solution is a permutation, sometimes of a permutation, of variables. The search space balloons as variables are added.
Each point in the space has a value, measuring how good an answer is the values of the variables. The values of the points define a function over the variables. Failure can also occur if this function is multi-modal, discontinuous, or epistatic. (Italicised words or phrases are defined in the glossary, or refer to diagrams.) Even without these difficulties the answer may have a narrow basin of attraction, i.e. only a tiny proportion of the points around it have higher than average values. This can make finding a needle in a haystack seem simple. GAs however can still find solutions in spite of these features.
The project aimed to build an object-oriented Genetic Algorithm in C++ to test any idea that occurred to me as I read into the subject. I needed to learn the basic ideas and choose from the methods available to design and code the program. So I had to read, and another goal was to collect and summarise this material.
It became clear that there were very many choices of design for each part of the algorithm. Although the literature contained comparative studies of these competing methods, there was plenty more to be done. Any of this would have provided an experiment to justify the project. However it was even more apparent that the fiercest competition was in methods for solving sequencing problems. The conviction grew that something fundamental was wrong, and I concentrated on the representation used for these problems. Finally I decided that the program should test an idea that I had thought of for the representation.
For any problem a decision is always made between a direct solution and searching for an answer. A payroll program is an example of a direct approach: its algorithm, although possibly laborious, is prescribed. However there is no such algorithm to decide how much to pay to achieve effectiveness of staff, low turnover and other goals. One searches for an answer by trial and error, observing the success of each attempt. As variants of search techniques, Genetic Algorithms are applied to these problems.
They also operate blind; i.e. they have no knowledge of the structures through which they are searching. The algorithm is free to change any value in the structure without regard to the legality of the result. It does so to observe the change's effect, which it uses to guide its search. The representation, or coding, of the structure can be critical to the success of the search. This is especially true of sequencing problems where legal solutions are sparsely distributed throughout the search space.
For terminology I tend to use the words structure, solution and answer loosely. Roughly, solution is an abbreviation for potential solution, which the GA gives to a problem to be evaluated. I try to use answer to stand for the correct solution or one that is acceptable.
The search space may also be too large for an enumerative, and many other types of, search. GAs however can find answers, and in a reasonable time. The answers may not be the best, but they may be good enough, or at least better than those found by any other technique. The philosophy of sufficiency is important. In an uncertain and complex world any improvement is welcome.
GAs have their origin in the observed behaviour of natural adaptive systems. These operate on organisms, which respond to an environment in which they live. The organisms change to respond to and record the results of the interaction. The mechanisms of the system use this information to search for organisms that are better able to survive. The concept of decisions being made from the local level of the organism is significant. There is no suggestion that a natural adaptive system stores the history of its search elsewhere, or that it is tuned by external parameters. To build this into a computer system, GAs use random or stochastic operations based on observed behaviour. They are non-deterministic but directed.
I doubt that anyone could list all the methods that have been invented to search for an answer to a problem, let alone give a synopsis of each. I am too unfamiliar with most of the direct competitors to GAs to be able to comment on them. For instance optimisation is often used as a bench-mark against which GAs are measured. I believe that it can take years and much mathematics to use optimisation well. I have neither. This must at least be one big advantage of GAs: they are simple enough for the man on the Clapham omnibus to understand and use.
If the search space is small enough, this is sufficient to find an answer. Because of the speed of modern computers small can mean many thousands, or even millions, of possible solutions to a problem. The search merely tries each one in turn and records the best answer so far. Prolog is a good example. From the simple database of family relationships to colouring maps, it traverses a tree of possible solutions, backtracking as it reaches leaf nodes. If any answer is found, the user can accept it or continue the search. Databases too search enumeratively, although often with the advantage of linearly organised data, indexes and so on.
Random, or Monte Carlo, search works similarly but it jumps within the search space. For one trial each variable is set at random to some value in its range. Trials bear no relation to those that precede or succeed them. This may seem less efficient than a purely enumerative method because it is possible to retry the same structure. However in large spaces this is unlikely, and the search on average is more efficient. It can sample a wide range of the search space in the time that enumerative search grinds th rough the small area where it starts from. If the starting region does not contain good solutions, which is highly likely, enumerative search takes a long time to get to good areas. If their basins of attraction are wide enough, random search may at least find some good values. It is often used as a baseline for measuring GAs.
However some problems do not have to be very large for any enumerative search to take too long. And by too long I mean that the life of the Universe would not be enough time. These problems tend to be combinatorial or permutational.
Large search spaces can be reduced by finding regions that cannot contain the answer. Branch and bound techniques do this and are frequently built into Prolog programs. Strategies for games often lead to a highly combinatorial search space, where minimax and alpha-beta pruning can be used. Alternatively the search can be directed towards promising regions by A* techniques or analysing the results so far. These methods use heuristics, which help to reduce the size of the problem. A GA is a collection of heuristics, but ones that are general. Those for other searches tend to be specific to a problem.
Hill-climbing starts at the first variable of a randomly generated structure and changes it to create a child. The algorithm then finds the value associated with the child and selects the parent or the child for survival. If the child's value is better than that of the parent, it survives and the position of the perturbed variable is remembered. Otherwise the parent survives. This constitutes one trial of the structure. The search repeats this process for the second variable of the structure through to the last variable, then back to the start, and so on.
If the search returns to the last remembered position, i.e. there was no improvement to the value by changing any of the other variables, the search ends with the structure as the result. This is controlled random search with a heuristic that points it in the right direction.
The way in which a variable is changed is open to interpretation. However a best-first version of hill-climbing would examine all the possible changes and use the best of them. In this case there is no backtracking, and the technique is often called greedy.
Because this uses stochastic processes, it is often compared with GAs. Like random search and hill-climbing it changes a parent structure, which encodes a possible solution, into a child. This can be done by perturbing one or more of the variables in the structure. If the value associated with the child is better than that of the parent, the child replaces the parent, and the search continues from the new structure. In contrast to hill-climbing simulated annealing may also allow a child with a worse value to replace its parent. So motion down a gradient of the function can happen, and this helps to avoid entrapment on false peaks.
The idea comes from the process of toughening metals by heating them and allowing them to cool. So the replacement by inferior children is controlled by a temperature T. Then the probability of that replacement is usually given by a function of the form which tends towards one when the value of the child is close to the parent and zero when it is much less. The temperature is lowered during the search so that the probability is high at the start and low at the end. Often an annealing schedule is used, which has cycles of cooling, each starting at a lower temperature than the last.
GAs may find a good enough answer for a variety of problems that cannot be solved otherwise. The Sample Applications Chapter gives two: the Travelling Salesman Problem (TSP) and Job-Shop Scheduling (JSS). Even when they are quite small, there is no algorithm to solve them, and a search of the solution space is needed. The size of the space grows exponentially as the size of the problem grows. So the time to search for a solution becomes prohibitively large.
The answer to a problem is a structure of values. The Interfaces Chapter discusses a form that the GA can use, which is called a string (or chromosome). If the shape of the structure varies because of some of its values, the mapping must allow space for all the variants. The string decomposes into positions, which correspond to variables of the structure, then individual bits (or genes). The bits constituting a position encode a value for the variable. It is helpful in most cases if solutions that are next to each other in the search space are still neighbours after being mapped to strings. The representation of ordering problems is emphasised because it gives the GA great difficulty in producing legal structures.
The GA needs a critic to tell it how well it is doing. The Interfaces Chapter also shows how an application communicates with the GA through a fitness function. It looks at how the shape of various functions may affect the answer found by the GA. Finally some schemes are listed that may allow a GA to run on problems with no obvious fitness function.
How does a GA produce a new string from another one? The Exploration Chapter presents one of the operators, which is also used by random search and simulated annealing. It shows that mutation explores the search space and contrasts it with bit-climbing. Both are then combined to produce a more methodical procedure for a GA. Many search techniques fail to find an answer when the fitness function is multi-modal. To overcome this, GAs use many strings that evolve concurrently in their search. This chapter demonstrates the techniques on bit-climbing and the mutation operator. Each evolution produces a new generation. It also discusses the ideal number of strings and their values.
Because mutation by itself does not discriminate between strings, the GA must prune the search trees that have a poor fitness value, and encourage more branches from the good ones. The Selection Chapter shows how the algorithm decides which strings to reproduce. It uses the fitness value of a string to calculate an expected value, which gives the number of offspring that a string should breed. Various methods of getting an expected value are presented. Then come some sampling techniques, which use the expected value to select strings at random from a population.
As the only operator for a GA, mutation can find an answer, but slowly. Each parallel search is still running in isolation and competing against the others. The Crossover Chapter introduces co-operation by combining the searches so that the history of each can interact by exploiting the information in two strings. To do this the theory of schemata is sketched. Then I cover findings and ideas about the probabilities for crossover and mutation. The conclusion presents variants of crossover.
The Generations and Replacement Chapter discusses the consequences of, and alternatives to, complete replacement of the population at each generation. Good solutions and long fit schemata can disappear before they have a chance to establish themselves. Methods of replacement use various degrees of generation gap to prevent this: some of the strings pass through unchanged to the next generation. It is an alternative to using a rate of crossover, but it changes the emphasis to the strings that should die.
How does everything fit together, and how is an answer found and reported? The Algorithm Chapter fills in the missing details and describes how selection operates on schemata. GAs combine building blocks to work better than the brute force of simple parallel processing suggests.
The idea of a GA was inspired by evolution in nature, and much of the literature uses its terminology. The General Review Chapter summarises the natural process and matches its terms to those used so far. It then gives a brief history while extending the survey of the literature.
The Sequencing Problems Chapter reports on experiments that have investigated sequencing problems. The solutions to these impose an order on a set. The search cannot change values without keeping to constraints, which usually include uniqueness. Specialised codings and genetic operators have been invented to maintain these constraints. The problems include timetabling, bin packing, route planning and scheduling.
The Conclusion Chapter summarises the pros and cons of a Genetic Algorithm, its advantages identifying the type of problem it can solve. Finally I present the results of the project and recount the issues that seem to be worth further investigation.
The Glossary and Bibliography Chapters do pretty much what you would expect.
Names and dates in square brackets, ], refer to entries in the Bibliography. The name is omitted if it appears in the text before the reference. A letter is appended to the date if the author has several entries for that year.
In the implementation subsections bold words highlight class or member function names, or C++ reserved symbols. Sample Applications Chapter → Page modified: 28-Nov-2009
Mobile: +447739884133A.S.Gibb
© MMXI