Resource Allocation Using Genetic and Neural Algorithms

Shane Murnion1, Jason E. Price2 and Alan Harget3
1 Department of geography, Portsmouth University, Buckingham Building, Lion Terrace, Portsmouth PO1 3HE, United Kingdom
2 Parallax Group Plc., StoneCourt, Siskin Drive, Coventry, United Kingdom
3 Department of Computer Science and Applied Mathematics, Aston University, Aston Triangle, Birmingham B4 7ET, United Kingdom

Many of the problems analysed using geographical information systems are in fact spatial optimisation queries, for example, maximising profit whilst minimising environmental damage. Current GIS are not capable of effectively solving one subgroup of this class of problem which are known as combinatorial optimisation problems. The most familiar combinatorial optimisation problem is perhaps the Travelling Salesman Problem and is, like many problems of this type, difficult to solve within a practical time-frame using conventional analysis. Problems of this order of difficulty are termed intractable or NP-hard and many combinatorial optimisation problems can require years of analysis to produce an algorithm capable of efficiently producing a solution. Unfortunately for spatial analysts many types of real world analysis fall into this category and the time-scale for most projects would preclude the possibility of studying the problem for years. More unusual methods such as genetic algorithms and neural networks have been recently applied to many NP-complete problems, including the Travelling Salesman Problem, and have been found to be both effective and efficient. In this work a non-standard multi-chromosomal genetic algorithm and a standard Hopfield neural network algorithm are applied to a geographical combinatorial optimisation query. The example application demonstrated here is the allocation of fishing territories within set quotas to preserve fishing stocks while maximising the number of the fleets allowed to operate. In considering the practical difficulties of checking the results obtained by the neural and genetic algorithms using a conventional analytical technique a simple synthetic dataset was generated and used which makes it possible to confirm the goodness of the results obtained by visual inspection. Since both methods rely at least in part on random processes, multiple runs of the analysis were carried out to define the statistical variation in the algorithm performance. The nature of the problem caused difficulties in implementing a genetic algorithm solution. The problem occurred because the solutions, which are coded as strings needed to be of variable lengths. Standard genetic algorithms use a fixed solution string length which does not vary. Although it would be possible to use a fixed length string of sufficient size to contain all possible solution strings of smaller length, this would not be desirable since the efficiency of the algorithm is dependent on the length of the solution strings used. As a result of this a novel, non standard genetic coding was implemented to create a genetic algorithm particularly suited to this problem. The non standard algorithm uses multiple chromosomes instead of the usual single string. Genetic operations of crossover, mutation and evaluation were applied at both a string and solution level. The non standard coding also required the development of new extended genetic operators to handle this unusual configuration, allowing dynamic addition and subtraction of the number of chromosome strings available to any candidate in the solution population pool. The effectiveness of the algorithm in this example demonstrates both the potential utility of this method for spatial combinatorial optimisation queries and also the advantages of adapting standard genetic methods to suit particular applications. The results using the Hopfield neural network show that even a relatively simple neural network structure can be effective when applied to combinatorial optimisation problems. These results suggest that unconventional and inherently parallel methods such as the Hopfield and genetic algorithms used here have a great potential for using in problems which are conventionally considered to be intractable. However further work must still be carried out to assess the scalability of these algorithms to problems of real world size and complexity.