Journal of the Operational Research Society (1996) 47, 550--561

IC> 1996 Operational Research Society Ltd. All rights reserved. 0160-5682/96 $12.00

Genetic Algorithms-a Tool for OR? KATHRYN A. DOWSLAND Statistics and OR Research Group, E.B.M.S., Swansea University Compared with other metaheuristic techniques such as simulated annealing and tabu search, research into the use of genetic algorithms for the solution of OR problems is still in its infancy. This paper provides an introduction to genetic algorithms and their use in the solution of both classical and practical operational research problems, identifies some of the reasons why they have been slow to find widespread appeal, and goes on to show that many of these reasons are gradually being eroded. Key words: genetic algorithm, heuristics, optimisation

INTRODUCTION The last decade has seen a great deal of interest in the use of metaheuristics to solve discrete optimisation problems arising in the area of operational research. Much of this work has concentrated on simulated annealing (SA), tabu search (TS) and other sequential search methods and there has been relatively little attention paid to the possibility of using genetic algorithms (GAs). There are now signs that interest in genetic algorithms is growing, and this paper can be regarded as an introduction to this technique from an operational research perspective. However, the basic introductory material is incorporated into a broader framework in an attempt to answer two questions. Firstly, why have genetic algorithms yet to find widespread appeal within the OR environment? Secondly, now that there is a growing interest, are they likely to become an established and useful tool? The investigation starts with a brief introduction to genetic algorithms using a practical example to illustrate the basis of the method. It then goes on to examine why OR practitioners and researchers may be reluctant to try genetic algorithms and to show that ongoing research means that many of these reasons are gradually being eroded. This is followed by a brief look at some practical applications of GAs in operational research, with particular reference to the fields of scheduling, timetabling and packing problems. The paper concludes with some personal views on the potential role of GAs in the OR environment. GENETIC ALGORITHMS Unlike simulated annealing and tabu search, which explore the solution space sequentially, genetic algorithms work with populations of solutions and attempt to guide the search toward improvement, using a survival of the fittest principle. The quality of each solution is measured by a fitness function (equivalent to the objective function or cost function in traditional optimisation methods), and the search proceeds through a number of generations with each individual contributing to the next generation in proportion to its fitness. This is achieved by selecting individuals randomly, using a weighted probability function, where the weights reflect actual fitness values, scaled values, or simply rank. Three standard operators are used; reproduction, crossover and mutation. Reproduction copies an individual from one generation to the next, crossover combines features from two or more parents to produce one or more children, and mutation makes small local changes. Reproduction and crossover of fit individuals provide pressure for improvement or exploitation, while mutation maintains population diversity and allows wider exploration. A classical genetic algorithm is implemented by representing individual solutions by strings, and for a number of reasons binary strings are common. Standard crossover (usually known as onepoint crossover) of two parents involves selecting a point on the string and then copying that part Correspondence: K. A. Dowsland, Statistics and OR Research Group, E.B.M.S., Swansea University, SA2 BPP, UK

Operational Research Society is collaborating with JSTOR to digitize, preserve, and extend access to Journal of the Operational Research Society. ® www.jstor.org

K. A. Dowsland-Genetic Algorithms

551

of the string before the crossover point from the first parent, and that part of the string after the crossover from the second parent. If two children are to be produced the roles of the parents are reversed for the second child. For example, given two parents: 101101110 001111001

parent 1 parent 2 and a crossover point after bit 5, we get children:

101101001 001111110 Mutation usually involves flipping a single bit. For example mutating bit 4 in child 2 will give: child 2 (mutated)

001011110

The development of a genetic algorithm in the solution of a particular problem involves two types of decision. The first concerns the way in which the problem is to be modelled to fit into the genetic algorithm framework and includes the definition of the space of feasible solutions, the form of the fitness function and the way in which individuals are to be represented as strings. The second concerns the parameters of the genetic algorithm itself and includes the proportions of the population to be produced as a result of reproduction, crossover and mutation, the selection procedure, the population size, the number of generations, and a number of other decisions concerning variants of the basic algorithm. Details can be found in any introductory text. See for example, Goldberg 1 or Reeves 2 • These concepts will be illustrated with reference to a typical operational research problem which arises in the lumber cutting industry. Example: a lumber cutting problem

Wooden boards, produced directly from felled timber, are to be cut into smaller sections ready for sale. The wood is classified by different quality grades and different sections of the same board may be graded differently. The value of a cut section of board will increase with length and quality, which is determined by the minimum quality within the section in question. Cooke and Wolfe 3 describe a solution based on a genetic algorithm. They deal with 20' boards which can be cut at 2' intervals. Each 2' section is graded with one of four grades (with grade 1 being the highest) and a table of values for multiples of 2' lengths from 2' to 20' for each of the 4 grades, is available. Longer lengths and higher grades tend to be more profitable. The feasible solutions are given by the set of all possible cutting patterns and the fitness of each pattern is the sum of the values of the pieces it contains. Each pattern can be represented as a binary string of length 9 (the number of cutting positions) with a value of 1 representing a cut and a value of 0 representing no cut. For example the string (0,0,1,0,1,0,0,0,0) would represent cuts at 6' and 10', as shown in Figure 1(a). If the quality of each 2' section is given by the vector (2,2,2,1,1,4,1,1,1,3) this will mean a 6' length of quality 2, a 4' length of quality 1, and a 10' length of quality 4. Now consider a second pattern given by (1,1,0,0,1,1,0,0,1). This represents two 2' lengths and a 6' length of grade 2, a 2' length of grade 4, a 6' length of grade 1 and a 2' length of grade 3 as shown in Figure 1(b). Crossing these two patterns with a crossover point after bit 2 gives (0,0,0,0,1,1,0,0,1). The resulting 10' length of grade 2, 2' length of grade 4, 6' length of grade 1 and 2' length of grade 3 is shown in Figure 1(c). (Using the value table given by Cooke and Wolfe this is the optimal solution). The two parents are moderately fit. The first contains valuable pieces in the grade 2, 6' length, and the grade 1, 4' length. It loses some value by not cutting the final length, and thereby producing a long, but very low grade section. The second parent cuts the right hand end sensibly, removing the valuable grade 1 section from the surrounding low grade regions. However, it slices through a potentially longer grade 2 section on the left hand end, thus reducing its value. The child inherits the good features from both parents and is therefore a fitter individual. Note that the second child produced by this crossover would inherit all the bad features and would be less fit. Consequentially it would have little chance of contributing to future generations and would disappear from the population. Cooke and Wolfe report good results with a population size of 30 using 20 generations with a crossover rate of 0.6 and a mutation rate of 0.033.

552

Journal of the Operational Research Society Vol. 47, No. 4

a. 0 0 10 10 0 0 0 2 1 I 4

I

6'

I

20'

10'

11 0 0 11 0 0 1

12121 2 141

b.

2' 4'

1

10' 12'

131

18'20'

0 0 0 0 11 0 0 1

2

c. FIG.

141

10' 12'

1. Lumber cutting patterns.

1

131

18'20'

This example conforms to the theory of genetic algorithms which is rooted in the building block hypothesis and uses the idea of schemata. A schema is a valid string in which some symbols are replaced by a wildcard. All strings which match the schema everywhere but at the wildcard are said to belong to that schema. For example **1*1*0* has 32 members which include 10111000 and 10101001. Two measures are commonly associated with schemata. These are the length, which is the distance between the first and last fixed elements, and the order which is the number of defined positions. Thus the schema above has length 4 (the distance between the 3rd and 7th bits), and order 3. Each individual string obviously belongs to a number of different schemata and for given rates of crossover and mutation it is possible to calculate the probability that a given schema will survive into the next generation. Not surprisingly the results indicate that fit, short, low order schemata tend to be preserved. In fact the theorem states that they will increase their representation exponentially in subsequent generations, and therefore form the building blocks for the final population. This suggests that if a genetic algorithm is to operate at its full potential then short low order schemata should be 'meaningful' in terms of the overall problem. The result holds for strings over any alphabet, but the effect is stronger for smaller alphabets and hence the bias towards binary representations. See Goldberg 1 or Reeves 2 for further detail. In the lumber cutting problem good solutions are built up from sub-solutions in which the cuts are made at profitable positions. The idea of short low order schemata is meaningful as short schemata correspond to short sections of the board. However in problems where the position of elements on the string has no physical meaning, the length of a particular schema is just an accident of coding. In such cases one-point cross-over will introduce unwanted bias, but this can be overcome by using a crossover which is independent of position such as the uniform crossover suggested by Syswerda4 • WHY IS THE OR COMMUNITY SLOW TO ADOPT GENETIC ALGORITHMS? Given that problems such as the lumber cutting problem can be modelled and solved successfully using a genetic algorithm it may appear surprising that they have not been as readily adopted as simulated annealing or tabu search. In this section we outline some of the reasons why this may be. The first problem concerns the way in which results in genetic algorithm research have traditionally been disseminated. The original work on GAs was carried out by a close-knit group based at the University of Michigan which acted as a central point for discussion of research projects

K. A. Dowsland-Genetic Algorithms

553

and results. As the number of researchers grew these meetings were formalised into an official conference. There have now been five of these U.S.A. based International Conferences on Genetic Algorithms and three of the European counterpart, covering the broader area of 'parallel problem solving from nature'. Not surprisingly, many researchers have chosen to present their work here rather than in applications oriented conferences, and as both the European and U.S. meetings produce refereed proceedings there is often little incentive to publish elsewhere. Those who do, frequently opt for journals in artificial intelligence as for historical reasons GAs have fallen under this heading. The result is that information about applications of genetic algorithms has been slow to filter down to others working in a given problem area, but using different techniques. This is in direct contrast to simulated annealing and tabu search which have had a lot of exposure in general OR conferences and journals. This lack of communication creates a two-way problem, and many papers on genetic algorithms fail to compare the quality of results with those obtained from other methods. This view is shared by Pirlot 5 who says: 'The GA community appears as a sociological microcosm even though about half of the applications belong to the field of OR. It is remarkable that even when dealing with classical problems of OR, the GA researchers seldom compare their results in a systematic manner with those obtained by OR researchers'. This does little to give potential GA user confidence that such methods are able to compete with other well-tried approaches. A second possible deterrent is that an initial foray into the genetic algorithm literature frequently gives the impression that getting started may not be easy. The terminology relies heavily on terms from genetics in the same way as the language of simulated annealing relies on its origins in statistical thermodynamics. However, while temperature, cooling, etc. are immediately meaningful, the same is not true in general for terms such as allele, chromosome, and phenotype. In addition, a lot of the published research is theoretical in nature, and often involves the testing of a new idea or conjecture on specially designed functions which have to be understood in order to understand the results. This is obviously a good thing, in that it is important to gain as full an understanding of the technique as possible. However, a beginner faced with this wealth of somewhat complex material finds it difficult to know what may be vital to the success of an initial experiment, and what can be left until later. Even if a would-be user is determined enough to overcome the hurdles described above, any attempt to survey the relevant literature is likely to reveal a number of statements concerning genetic algorithms which may suggest that they are not well-suited to typical discrete optimisation problems arising within an OR context. Most such problems can be regarded as problems of function optimisation subject to a series of constraints. It is therefore discouraging to find many researchers suggesting that genetic algorithms are not appropriate for highly constrained problems and that penalty function approaches frequently fail to perform well. For example Radcliffe 6 comments that 'Constraints are normally considered to be highly problematical for genetic algorithms' and Michalewicz 7 states 'There is a lot of evidence of the usefulness of GAs for a variety of unconstrained problems optimization. However, the proposed penalty function approach did not work well for heavily constrained problems'. This is in direct contrast to much of the literature on SA which advocates the use of penalties in the cost function as an effective way of dealing with constraints. Perhaps even more off-putting is the title of a recent paper by De Jong 8 -'Genetic algorithms are NOT function optimisers'. In fact De Jong argues that genetic algorithms were not originally developed from an optimisation perspective, but that with minor modifications they can be very good optimisers. However, for those who do not read any further than the title this appears to be extremely bad news. The final obstacle is the coding itself. It is not always apparent how individual solutions can be represented as strings. As operational researchers we are used to taking advantage of problem structure, and formulating our problems using matrices, trees, networks or whatever else may be appropriate. Where a string representation is obvious it may be over a large alphabet of characters, but the building block hypothesis suggests that small alphabets should be used, and this has led to a preference for binary codings. Alternatively, we are also used to defining our problems as

554

Journal of the Operational Research Society Vol. 47, No. 4

integer programs, using binary variables subject to a series of constraints. This suggests that we could allocate the variables to different positions on a binary string. But for realistically sized problems the number of variables, and hence the length of the string is likely to be very large, and we have already seen that GAs are not well suited to constrained problems. This difficulty in representation is in sharp contrast to simulated annealing which simply requires a solution space and neighbourhood structur~a model which has been familiar to those working in discrete optimisation since Kernighan and Lin's paper on graph partitioning9 • It is also likely that for large practical problems a certain amount of modification or hybridisation with other techniques may be necessary in order to reach solutions of sufficient quality in reasonable time. Such variants are often discouraged among the GA community, who believe that any modifications should be guided by nature, rather than incorporating problem specific knowledge. (See for example Davis 10 and Goldberg 11 ). It is probable that all of the above have in some way contributed to the apparent lack of interest in GAs shown by many OR workers. However, non-standard codings and operators are now being used by an increasing number of researchers, and there is a considerable amount of work underway looking at different ways of dealing with problem constraints. In the following sections some of these developments are outlined and the way in which they have been applied to some real problems is described. OVERCOMING THE PROBLEMS The travelling salesman problem was one of the first to be tackled using a non-standard coding. This was achieved by considering the problem as a permutation problem in which a tour is represented by an ordered list of cities. For example the tour shown in Figure 2 can be represented as the permutation {E,H,A,C,D,B,G,F}. Applying standard crossover methods to two such strings is unlikely to give offspring which are feasible tours as they are likely to contain repeated and missing elements. In order to overcome this a number of different crossovers have been suggested. Many of these can be found in Reeves 2 • Since the introduction of these permutation crossovers there has been much debate as to whether implementations which do not obey the conditions of the building block hypothesis can be classified as genetic algorithms. Nevertheless the evidence suggests that they do work in practice, although there is a lack of empirical evidence comparing these methods with some of the best problem specific methods. Recently there have been a number of experiments with other non-standard methods including representations using matrices 12- 14 and trees 15 •16 , thus widening the scope of GAs to include many more of the problems likely to be encountered in an OR context. There has also been a significant amount of recent research into the best way of dealing with constraints. Where feasible solutions are easy to find and to define it may be possible to incorporate the constraints into a more concise representation in conjunction with a modified crossover, such as has been done for the TSP. If feasible solutions can be constructed by applying a heuristic to an ordered list then a permutation based GA may be combined with such a heuristic as a

{E,H,A,C,D,B,G,F} FIG.

2. TSP as a permutation problem.

K. A. Dowsland-Genetic Algorithms

555

decoder. For some problems it may be relatively easy to alter infeasible solutions to gain feasibility. The mechanism for alteration is known as a repair operator. Repairs are particularly useful in cases where the level of infeasibility is likely to be low. However, depending on the way in which such operators are used they may cause a build-up of infeasible material, or result in loss of population diversity. For highly constrained problems in which finding any feasible solution may be difficult the above approaches will not provide a satisfactory solution, and the only option may be to use a penalty function to reduce the fitness of infeasible individuals. Some researchers have succeeded in finding suitable weights for penalty approaches but these are usually problem specific. A discussion of this issue can be found in Richardson et al. 17 Recently Michalewicz 7 has suggested a way of dealing with linear constraints by using linear combinations of solutions in his definition of crossover. This approach will result in fractional values for the variables which makes it unsuitable for discrete optimisation problems in its current form. GAs IN THE SOLUTION OF PRACTICAL PROBLEMS In view of the advances made in tackling classical problems such as the TSP there have been various attempts to use genetic algorithms in the solution of practical problems. Published applications of GAs cover a broad spectrum of problems in business and industry in fields such as engineering, image processing, classifier systems, finance and operational research. Surveys of many of these applications are given by Nissen 18 and by Smith 19. In this section we take a brief look at some applications in OR, in particular in the fields of scheduling and packing problems.

Scheduling Many scheduling problems, such as flow-shop scheduling, are natural permutation problems, which can be tackled using a GA based on one of the permutation crossovers. For example, Cartwright and Mott 20 have looked at the use of a GA for scheduling in a chemical factory. Permutation based genetic algorithms have also been used in conjunction with simpler heuristics for the solution of more complex scheduling tasks. Syswerda and Palmucci 21 consider the problem of scheduling the use of equipment in a flight simulation laboratory in which a set of tasks compete for a set of finite resources over a period of 168 hours. The quality of a schedule is measured by the extent to which it fulfils a series of non-binding constraints such as preferred time windows and the use of preferred personnel. The problem is solved by using a GA to order the tasks, and then using a set of deterministic rules to find a feasible schedule from each ordering. Thus the schedule building heuristic concentrates on feasibility, while the GA searches for optimality. Hilliard et al. 22 also use a GA in conjunction with a heuristic, but instead of using the GA to determine the order in which entities are processed, they use it to tune the weights which govern preferences between various heuristic criteria. Their problem is a multi-objective routeing and scheduling problem involving the transportation of military personnel and supplies. The system has to be suitable for scheduling routine exercises and real military crises, and the weights placed on different objectives, such as speed of response and monetary cost, will differ according to the situation. The objective is therefore to produce a 'front' of undominated solutions emphasising the different optimisation criteria. Two multi-objective GAs were considered. The first allocates the individuals to pools and selection within a pool is based on a single criterion. Crossover between pools should then produce individuals strong in all criteria. The second approach is based on Pareto optimality and involves a selection procedure based on rank, which is determined by the Pareto fronts. The authors stress that the work was mainly exploratory in that their objectives were to investigate the potential of genetic algorithms for this type of problem, but the results suggest that this is a viable solution method. There has been considerable interest in the application of GAs in the solution of complex transport scheduling problems. For example Gabbert et al. 23 consider a routeing and scheduling problem for a rail freight network in which wagons of cargo must be routed from source to destination, using an appropriate combination of routes and trains. The algorithm incorporates a

556

Journal of the Operational Research Society Vol. 47, No. 4

local optimisation procedure which is used on a subset of the children in each generation, to improve the routes generated by crossover. The overall cost of a schedule depends on a series of complex interactions between the chosen routes, as one train may carry several different blocks of cargo along any portion of their journey. A genetic algorithm, in which the strings can be regarded as pointers to the actual routes used, performed successfully for problems based on a subset of the real data. However, the authors report that further refinements will be necessary for larger problems, due mainly to the rate of increase of the set of feasible routes. Wren and Wren 24 report similar findings from experiments with GAs for bus driver scheduling. The problem can be modelled as a set covering problem in which the objective is to cover all the required work by a set of shifts. This approach is non-standard in that it allows more than two parents to produce any number of children. Individuals in the population define prime covers i.e. sets of shifts which cannot be reduced without leaving some of the necessary work uncovered. The union of two or more individuals will be a cover which will usually include a degree of redundancy in that some shifts can now be removed while maintaining total cover. There will usually be a number of different ways of removing redundant shifts and each will produce a different offspring. As with the freight scheduling example, initial experiments on a small problem were very encouraging, with the GA consistently finding the known optimal solution. However, results with realistically sized problems were less promising and once again further work is required before this implementation is ready to form a part of a commercial system. Timetabling

GAs have also been applied to timetabling problems. Corne et al. 25 tackle a problem at Edinburgh University involving around 40 exams to be scheduled into 28 time periods over seven days. The objective is to find a feasible timetable which spaces out the exams taken by an individual student. Individual timetables are represented by strings in which each position represents an exam and the value in that position represents the slot when that exam will be held. Uniform crossover and standard mutation produced good results using 300 generations and a population size of 50. However, this problem is small compared to most examination scheduling problems, which may involve several thousand students and several hundred exams. Those tacking the school timetabling problem tend to use a different approach based on a two-dimensional matrix representation. For example Colorini et al. 26 use a matrix in which the rows represent the teachers and the columns the available hours. The value in each cell describes the task undertaken by the teacher at that hour, including any room or other resource allocations. The rows are always feasible in that the set of tasks for a given teacher are pre-defined and the genetic operators work with permutations of these. Columns may be infeasible in that conflicting activities could be scheduled at the same time. Such conflicts are penalised in the fitness function, but a repair operator tries to adjust solutions back to feasibility before they are evaluated. The algorithm has been tested on data from a Milan school but no details of how solution quality varies from the optimum, or that produced by other heuristic methods is given. Ling 27 uses a similar coding to solve a timetabling problem in an engineering department at Singapore Polytechnic. In this case a large portion of the timetable is produced using a PROLOG-based assignment module. The remaining 80 classes are then scheduled by the genetic algorithm, which like that of Colorini, uses a matrix structure and a repair operator to improve the feasibility of solutions. Packing problems

Packing problems in one, two and three dimensions have widespread application in business and industry and there has been a considerable amount of research into solution methods based on genetic algorithms. Several approaches to the two-dimensional problem have been suggested 16 •28 •29 , and there has also been considerable interest in the application of genetic algorithms to the more complex three dimepsional container loading problem. Traditional approaches to the problem usually pack sequentially using heuristic rules to determine which piece to place next and where to place it. Thus a permutation coding combined with a heuristic placement policy

K. A. Dowsland-Genetic Algorithms

557

as a decoder is an obvious way of tacking the problem of using a GA. This approach is taken by Lin et al. 30 who use a series of penalties to guide their placement policy and to measure the fitness of a particular individual. Bortfeldt 31 uses a layer packing approach, which has some similarities with Wren and Wren's scheduling algorithm. Individuals are represented by their layers and when two parents are selected for crossover their layers are pooled, and that with the best utilisation is chosen as the first layer of the child. These boxes are then packed and any layers containing boxes which are already included are removed. The best remaining layer is then chosen and the process is repeated until all remaining layers contain boxes surplus to requirements. All unpacked boxes are then pooled and new layers are produced using a traditional packing heuristic. Kawakami et al. 32 use a GA in a different way, in that they employ a heuristic which uses weighted priorities to decide which box to place next and where to place it. Their coding represents the different weights and these are tuned using a standard GA.

WHAT CAN GAs OFFER OR? Although there have been a number of studies into the use of GAs for classical problems, evidence of genetic algorithms performing well in the solution of practical OR problems is still scarce. The successful implementations cited above are either totally experimental, or have been applied to relatively small problems. This conclusion is in line with those of two other recent surveys. 'We have not seen the major breakthrough of EA (Evolutionary Algorithms) in practical applications, yet. Most researchers are focusing on standard problems to test the quality of their algorithms. Practical applications are often characterised by conflicting objectives and constraints that are not covered by most test-problems' (Nissen 18). 'Although there are many examples of genetic algorithms successfully applied to optimisation problems, there are as yet very few examples published of where they are applied to real-world problems' (Smith 19 ). As outlined earlier, genetic algorithms need to be modified in order to deal successfully with optimisation objectives and with highly constrained problems. The use of non-standard crossovers and repair operators is likely to weaken the relationship between parents and children, and the addition of problem specific information or other features designed to increase the pressure for improvement may be at the expense of population diversity. While such strategies can improve the results on small to moderate problems, in large problems they may not allow sufficient exploration of the solution space. In response to this there have recently been a number of attempts to introduce diversity into the population, either by increasing the mutation rate (e.g. Anderson and Ferris 33 ) or using diversification strategies borrowed from tabu search (e.g. Fox 34). With suitable modification and hybridisation, genetic algorithms may well be able to solve large practical problems, but such possibilities require further research effort. This prompts the following question. Given that we have other heuristic techniques for difficult discrete optimisation problems which have already proved themselves, are genetic algorithms worth pursuing as a useful addition to the OR tool-box? In order to comment on this we draw a further parallel with nature. As with any new species the success of genetic algorithms in the OR environment will depend on a number of factors: 1. Is there a niche where they can establish themselves without too much competition from existing species? 2. Will they be able to obtain enough sustenance in the form of problems to tackle and researchers keen to apply genetic algorithms? 3. Will they be able to adapt and evolve to match their environment? There are a few published studies which attempt to compare the performance of a genetic algorithm with other metaheuristics. For example Poon and Parks 35 compare the use of simu-

558

Journal of the Operational Research Society Vol. 47, No. 4

lated annealing and a genetic algorithm for the problem of reload core design in pressurised water reactors. Their results show that the genetic algorithm tends to converge more quickly at the start of the run, but that simulated annealing catches up and is eventually able to find better solutions, but at greater computational cost. This conclusion is in line with a widely held view that genetic algorithms 'lack the killer instinct' in that they are based on evolutionary considerations which favour producing populations of individuals with high average fitness, rather than a few super fit individuals. This is the basis of De Jong's 8 argument that the standard GA needs to be modified when used in an optimisation setting, and is supported by Grefenstette 36 who strongly advocates the use of a local search or problem specific method for final fine-tuning. Sinclair 37 compares a genetic algorithm with simulated annealing, tabu search and other local search methods for a turbine balancing problem. In this case the GA is outperformed by the other methods. Bramlette and Cusic 38 apply a number of methods, including simulated annealing and a genetic algorithm, to a problem in aircraft design. They report that SA gives a slightly better average performance and has a lower standard deviation. They suggest that the difference between the means may not be significant from a practical point of view as both methods produced high quality solutions. However, the best GA solution was still worse than any of the solutions produced by SA. Reliable comparisons are difficult as all the algorithms are sensitive to the way in which the problem is represented and to the generic parameters, and the most suitable representation for one method may not be the best coding for another. Nevertheless results such as these suggest that GAs will meet stiff competition from established approaches in many application areas. However, I believe that there are three areas where genetic algorithms may be able to gain a foothold without competition from well-established techniques, thereby generating interest over a wider spectrum of OR activity. The first is in determining parameters to guide problem specific heuristics. If we regard the order in which the problem entities are processed by a simple sequential heuristic as an example of such a parameter, then many of the applications using permutation codings will fall into this category, as well as more complex instances such as the container packing algorithm of Kawakami et al. 32 , and the scheduling algorithm of Hilliard et al. 22 • Although both simulated annealing and tabu search have been used successfully for true permutation problems such as the travelling salesman and flowshop scheduling problem (see the chapters on SA and TS in Reeves 2 for further details) there is little evidence of their use in selecting permutations of objects for use in simple single pass heuristics. This is probably due to the emphasis placed on fast efficient cost function up-dates in much of the SA and TS literature. If the cost function is the result of the application of a heuristic, subject to a given set of parameter values, then the evaluation of changes resulting from perturbations of these values will normally require at least a partial re-run. Such expensive cost function updates do not appear to be a problem for those working with genetic algorithms. Indeed the distance between an element of the solution space (the phenotype) and its coding as an individual (the genotype) is frequently stressed as one of the important features of a GA. As the crossover operator has a more disruptive effect than a neighbourhood move in SA or TS it is usual to calculate the cost of each new individual from scratch. This view is summed up by Davis and Ritter 39 who state: 'SA has been used when one can represent one's solutions so that perturbations of them are rapid and the effects of such perturbations local. Genetic algorithms are applied to problems where the overhead of population maintenance is paid for by the rapid convergence through cross-over, or where the cost of evaluating individuals is so high that more random search procedures are undesirable'. Thus an unbiased user looking for a metaheuristic method of parameter selection may well find the GA literature more encouraging. However, increasing use of GAs in this context may eventually encourage those working with SA and TS to try these methods on problems of this type. Second, there are problems for which the local changes carried out by SA and TS may not be disruptive enough to escape local optima in moderate to large problems. Sometimes this can be rectified by modifying the algorithm to encourage more diversification. For example Dowsland40 has used SA with non-monatonic cooling to avoid premature entrapment in local optima for

K. A. Dowsland-Genetic Algorithms

559

two-dimensional packing problems and Wright41 has suggested an intelligent diversification strategy which allows tabu search to jump over large peaks caused by heavily penalised constraint violations in the solution of a sports scheduling problem. However, there are problems for which local search may produce reasonable solutions, but an experienced user may feel that small local changes are not sufficiently disruptive. One solution is to redefine the neighbourhoods, but overwide neighbourhoods are unlikely to enhance the performance of either SA or TS. In such situations the ability of genetic algorithms to combine material from two or more very different parents is appealing. Indeed it has been suggested 42 that a GA should be regarded as a local search strategy where the neighbourhoods are defined on pairs of solutions, and in this context the use of GA could be regarded as a way of imposing a new neighbourhood structure on the search space. It is likely that Wren and Wren's 24 set covering example falls into this category as there is little evidence of set covering problems being tackled successfully by sequential metaheuristic searches, whereas there have been a number of different suggestions for GA approaches to the problem 17 •43 • Wren and Wren's observation that the best results were obtained when each child is produced from three parents suggests that, in this case, even a standard GA is not quite as disruptive as necessary. The third possibility lies on the boundaries between OR and AI and is concerned with subjective decision making. Humans are frequently able to rank solutions in order of desirability without being able to extract those factors which affect their decision. This ability has been exploited by a genetic algorithm in a computerised version of the photofit system for identifying criminal suspects (Caldwell and Johnston44). Witnesses are shown a population of faces made up of 35 bits representing the shape and position of the different features. These are ranked according to similarity to the suspect and the GA uses this information to form the next generation. Witnesses can lock certain features or leave all the work to the GA. Although this problem deals entirely with subjective criteria there are many problems tacked in an OR context which involve qualitative as well as quantitative objectives. For example, in his paper on the course timetabling problem, Johnson 45 states that 'The human or judgemental element is likely to be dominant in the creation of most timetables', and Tripathy46 enforces this view when he says 'The quality aspect of the timetabling has by and large remained the judgement of the decision maker.' Similar situations arise in the solution of packing problems. For example modern pallet loading software is required to produce many layouts for the same problem, so that the user can use his or her judgement to select the most suitable in terms of the storage and materials handling policy employed. A GA similar to that of Caldwell and Johnson may aid the OR worker in defining precisely those features which result in good or bad solutions from the user's point of view. These may then either be built into the solution algorithm or used to post process the results, so that solutions which most closely match the user's preferences are presented first. As for Question 2, there are certainly plenty of problems which fall into the above categories. However, interest in GA solutions will not expand unless many of the initial reasons for the slow start of GAs in OR are eliminated. There is evidence that this is now happening. Examples of GAs are being published in OR literature and there are a number of introductory texts which outline the basic idea, and the most important theoretical results. One aspect which needs to be addressed if genetic algorithms are to be widely accepted, is the comparison of the results with those obtained by other methods. As more members of the OR community become involved in GAs, and papers submitted to mainstream OR journals are refereed by those familiar with the problem area as well as the technique, this is more likely to become the norm. It is also likely that GAs will have to adapt to the OR environment. Results such as those of Wren and Wren 24 and Gabbert et a/. 25 suggest that the quality of solutions from a GA method frequently falls short of that required in large practical applications. This suggests that there is still more work to be done in developing and modifying the basic GA principles to enable them to perform well on real-life problems. Often the real successes of simulated annealing and tabu search have been achieved when these techniques are used and modified by experts in a particular application area, who have also developed the skill necessary to realise the full potential of the solution technique. Some of the most interesting GA applications surveyed here also fall into this category.

560

Journal of the Operational Research Society Vol. 47, No. 4

Studies such as these suggest that experts in specific problem areas with the necessary knowledge of genetic algorithms are now beginning to emerge, and that they are willing to bend the classical GA framework and hybridise it with both problem specific knowledge and ideas from other metaheuristic strategies in order to achieve the required solution quality. CONCLUSIONS Given the enthusiasm of those now working with GAs it seems that research into genetic algorithms for OR problems is set to continue. Whether or not they are eventually accepted as a standard and useful component of the OR toolkit, or are simply remembered as a buzzword of the nineties, will largely depend on the results of this work. REFERENCES 1. D. E. GoLDBERG (1989) Genetic Algorithms in Search, Optimisation and Machine Learning. Addison-Wesley, Reading, MA. 2. C. R. REEVES (1993) Modern Heuristic Techniques for Combinatorial Problems. Blackwell, Oxford. 3. D. F. COOKE and M. L. WOLFE (1991) Genetic algorithm approach to a lumber cutting optimisation problem. Cybernetics and Systems 22, 257-265. 4. G. SYSWERDA (1989) Uniform crossover in genetic algorithms. In Proceedings of the Third International Coriference on Genetic Algorithms (J.D. SCHAFFER, Ed.), pp. 307-316. Morgan Kaufmann, San Mateo, CA. 5. M. PIRWT (1992) General local search heuristics in combinatorial optimisation: a tutorial, JORBEL 32, 7-68. 6. N.J. RADCLIFFE (1992) Non-linear genetic representations. In Parallel Problem Solving from Nature 2 (R. MANNER and B. MANDERICK, Eds) pp. 259-268. Elsevier, Amsterdam. 7. Z. MICHALEWICZ (1994) Evolutionary computation techniques for nonlinear programming problems. Int. Trans. Opl. Res. 2, 223-240. 8. K. A. DEJoNG (1993) Genetic algorithms are NOT function optimisers. In Foundations of Genetic Algorithms 2. (L. D. WHITLEY, Ed.) pp. 5-17. Morgan Kaufmann, San Mateo, CA. 9. B. W. KERNIGHAN and S. LIN (1970) An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal49, 291-307. 10. L. DAVIS (1989) Adapting operator probabilities in genetic algorithms. In.Proceedings ofthe Third International Conference on Genetic Algorithms (J.D. ScHAFFER, Ed.) pp. 61-69. Morgan Kaufmann, San Mateo, CA. 11. D. E. GoLDBERG (1989) Zen and the art of genetic algorithms. In Proceedings of the Third International Coriference on Genetic Algorithms (J. D. SCHAFFER, Ed.) pp. 80-85. Morgan Kaufmann, San Mateo, CA. 12. B. R. Fox and M. B. McMAHON (1992) Genetic algorithms for sequencing problems. In Foundations of Genetic Algorithms (G. J. E. RAWLINS, Ed.) pp. 284-300. Morgan Kaufmann, San Mateo, CA. 13. C. A. ANDERSON, K. F. JONES and J. RYAN (1991) A two-dimensional genetic algorithm for the Ising problem. Complex Systems 5, 327-333. 14. H. M. CARTWRIGHT and S. P. HARRIS (1993) The application of the genetic algorithm to two-dimensional strings: the source apportionment problem. In Proceedings of the Fifth International Coriference on Genetic Algorithms (S. FORREST, Ed.) p 631. Morgan Kaufmann, San Mateo, CA. 15. G. A. WATERS and T. LoHBECK (1993) Optimal layout of tree networks using genetic algorithms. Eng. Optimisation 22, 27-48. 16. B. KROGER, P. SCHWENDERLING and 0. VORNBERGER (1991) Genetic packings of rectangles on transputers. In Transputing 1991 (P. WELCH, Ed.) pp. 593-608. lOS Press, Amsterdam. 17. J. T. RICHARDSON, M. R. PALMER, G. LIEPINS and M. HILLIARD (1987) Some guidelines for genetic algorithms with penalty functions. In Proceedings of the Second International Coriference on Genetic Algorithms (J. GREFENSTETTE, Ed.) pp. 191-197. Lawrence Erlbaum, Hillsdale, NJ. 18. V. NISSEN (1993) Evolutionary Algorithms in Management Science, Working Paper, Universitaet Goettingen. 19. G. D. SMITH (1994) Commercial applications of genetic algorithms. In Applications of Modern Heuristic Methods (V. J. RAYWARD-SMITH, Ed.) pp. 71-90. Alfred Waller, Henley-on-Thames. 20. H. M. CARTWRIGHT and G. F. MoTT (1991) Looking around: using clues from the data space to guide genetic algorithm searches. In Proceedings of the Fourth International Conference on Genetic Algorithms (R. K. BELEW and L. B. BooKER, Eds) pp. 108-114. Morgan Kaufmann, San Mateo, CA. 21. G. SYSWERDA and J. PALMUCCI (1991) The application of genetic algorithms to resource scheduling. In Proceedings of the Fourth International Coriference on Genetic Algorithms (R. K. BELEW and L. B. BOOKER, Eds) pp. 502-508. Morgan Kaufmann, San Mateo, CA. 22. M. R. HILLIARD, G. E. LIEPINS and M. PALMER (1989) The computer as a partner in algorithmic design: automated discovery of parameters for a multi-objective scheduling heuristic. In Impacts of Recent Computer Advances on Operations Research (B. GoLDEN, E. WASIL, 0. BALCI and W. STEWARD, Eds) pp. 321-331. North Holland, Amsterdam. 23. P. S. GABBERT, D. E. BROWN, C. L. HUNTLEY, B. P. MARKOWICZ and D. E. SAPPINGTON (1991) A system for learning routes and schedules with genetic algorithms. In Proceedings of the Fourth International Coriference on Genetic Algorithms (R. K. BELEW and L. B. BooKER, Eds) pp. 430-436. Morgan Kaufmann, San Mateo, CA. 24. A. WREN and D. 0. WREN (1995) A genetic algorithm for public transport driver scheduling. Comp. and Opns. Res. 22, 101-110. 25. D. CORNE, H.-L. FANG and C. MELLISH (1993) Solving the Modular Exam Scheduling Problem with Genetic Algorithms. University of Edinburgh, Dept. of A.l. Research Paper No. 622.

K. A. Dowsland-Genetic Algorithms

561

26. A. CoWRINI, M. DORIGO and V. MANIEzzo (1990) Genetic algorithms and highly constrained problems: the time-table case. In Parallel Problem Solving from Nature (H. P. SCHWEFEL and R. MANNER, Eds) pp. 55-59. Springer-Verlag, Berlin. 27. S.-E. LING (1992) Integrating genetic algorithms with a Prolog assignment program as a hybrid solution for a polytechnique timetable problem. In Parallel Problem Solving from Nature 2 (R. MANNER and B. MANDERICK, Eds) pp. 231-239. Elsevier, Amsterdam. 28. D. SMirn (1985) Bin packing with adaptive search. In Proceedings of an International Coriference on Genetic Algorithms and their Applications (J. J. GREFENSTETTE, Ed.) pp. 202-206. Lawrence Erlbaum, Hillsdale, NJ. 29. E. A. HERBERT and K. A. DowsLAND (1996) A family of genetic algorithms for the pallet loading problem. Annals of OR 60, to appear. 30. L.-L. LIN, B. FooTE, S. PULAT, C.-H. CHANG and J. Y. CHEUNG (1993) Hybrid genetic algorithm for container packing in three dimensions. In Proceedings of the 9th IEEE Conference on Artificial Intelligence for Applications, pp. 353-359. IEEE Computer Society Press, Washington DC. 31. A. BoRTFELDT (1994) A genetic algorithm for the container loading problem. In Proceedings of the Unicorn Seminar on Adaptive Computing and Iriformation Processing (V. J. RAYWARD-SMirn, Ed) pp. 749-757. UNICOM Brunei Science Park, U.K. 32. T. KAWAKAMI, M. MINGAWA and Y. KAKAZU (1991) Auto tuning of 3-D packing rules using genetic algorithms. IEEE/RSJ International Workshop on Intelligent Robots and Systems IROS 91, pp. 1319-1324. IEEE Computer Society Press, Washington DC. 33. E. J. ANDERSON and M. C. FERRIS (1994) Genetic algorithms for combinatorial optimisation: the assembly line balancing problem. ORSA J. Computing 6, 161-173. 34. B. L. Fox (1993) Integrating and accelerating tabu search, simulated annealing, and genetic algorithms. Annals of OR, 41,47-67. 35. P. W. PooN and G. T. PARKS (1990) Optimising PWR reload core designs. In Parallel Problem Solving from Nature (H. P. SCHWEFEL and R. MANNER, Eds) pp. 371-380. Springer-Verlag, Berlin. 36. J. J. GREFENSTETTE (1987) Incorporating problem specific knowledge into genetic algorithms. In Genetic Algorithms and Simulated Annealing (L. DAVIS, Ed.) pp. 42-60. Morgan Kaufmann, San Mateo, CA. 37. M. SINCLAIR (1993) Comparison of the performance of modern heuristics for combinatorial optimization on real data. Comps and Opns. Res. 20, 687-695. 38. M. F. BRAMLETTE and R. CUSIC (1989) A comparative evaluation of search methods applied to parametric design of aircraft. In Proceedings of the Third International Conference on Genetic Algorithms (J.D. SCHAFFER, Ed.), pp. 213-218. Morgan Kaufmann, San Mateo, CA. 39. L. DAVIS and F. RITTER (1987) Schedule optimisation with probabilistic search. In Proceedings of the 3rd IEEE Conference on Artificial Intelligence Applications. pp. 231-236. IEEE Computer Society Press, Washington DC. 40. K. A. DowsLAND (1993) Some experiments with simulated annealing techniques for packing problems. Eur. J. Opl Res. 68, 389-399. 41. M. WRIGHT (1994) Timetabling county cricket fixtures. J. Opl Res. Soc. 45,758-770. 42. V. J. RAYWARD-SMirn (1995) A unified approach to Tabu search, 'simulated annealing and genetic algorithms. In Applications of Modern Heuristic Methods (V. J. RAYWARD-SMITH, Ed.) pp. 17-38. Alfred Waller, Henley-on-Thames. 43. J. E. BEASLEY and P. C. CHu (1994) A Genetic Algorithm for the Set Covering Problem, Internal Report, The Management School, Imperial College, London. 44. C. CALDWELL and V. S. JOHNSTON (1991) Tracking a criminal suspect through 'face-space' with a genetic algorithm. In Proceedings of the Fourth International Conference on Genetic Algorithms (R. K. BELEW and L. B. BOOKER, Eds) pp. 416-421. Morgan Kaufmann, San Mateo, CA. 45. D. JOHNSON (1993) A database approach to course timetabling. J. Opl Res Soc. 44, 425-433. 46. A. TRIPATHY (1992) Computerised decision aid for timetabling-a case analysis. Dis. App. Math. 35, 313-324.

Received October 1994; accepted September 1995 after one revision