Design Of A Genetic Algorithm For A Np-hard Optimisation Problem

Design of a Genetic Algorithm for a NP-hard Optimisation Problem Matthew W. A. Sparkes School of Computing Sciences, University of East Anglia, Norwich, United Kingdom, NR4 7TJ [email protected] March 15, 2006

1

Contents 1 Question A - What is Meant by NP-Hard

3

2 Question B - Representation

4

3 Question C - Determining the Fitness of a Solution

6

4 Question D - Crossover and Mutation Operators 4.1 Crossover Operations . . . . . . . . . . . . . . . . . . . . . . . 4.2 Mutation Operations . . . . . . . . . . . . . . . . . . . . . . .

7 7 8

5 Question E - Design and Outline 10 5.1 Design Decisions . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.2 High Level Description of Algorithm . . . . . . . . . . . . . . 11 6 Question F - Testing Effectiveness

13

7 Question G - Time Dependent Variation

14

8 Question H - Complications of Delivery Implementation

15

2

1

Question A - What is Meant by NP-Hard

It is a common misconception to believe that the NP in NP-Hard or NPComplete stands for Non Polynomial. It actually refers to Non-Deterministic polynomial. [2] P is the class of problems that can be solved in polynomial time on a deterministic machine, whereas NP is the class of problems that can be verified to be solvable in polynomial time on a non deterministic machine. [5] NP-Hard is a class of problems, that is to say optimisation problems that have been converted into boolean decision problems, and are too complex to be solved polynomailly by a non-deterministic machine. In the NP class of problems, there exists one problem called the satisfiability problem, which has a useful property. Every other problem in the NP class can be transformed into this problem in a polynomial manner. [3] This led to the idea that if a polynomial time algorithm could be developed for the satisfiability problem, then all other problems in NP could also be solved in polynomial time by first being reduced to the satisfiability problem. Since then it has been found that many other problems in NP are just as difficult as the satisfiability problem to solve, and these have been grouped into the class NP-Complete. [11] NP-hard is the class of problems which all problems in NP are reducible to, with a polynomial time algorithm. [2]

3

2

Question B - Representation

The representation for the traveling salesman problem (TSP), will need to store each city, and the distances between those cities. It will be assumed for the purposes of simplicity in the model that every city is connected to every other city in the graph. If a particular model requires that some cities are not connected in this way then this can be represented with the use of a PENALTY FUNCTION?, where the associated time for a journey between those cities will be set to N, where N is a very large positive integer. This will be excluded from solutions by the GA as it will decrease the fitness of those solutions dramatically. The model is also simplified in that journeys are symmetrical, in that Cab is equal to Cba , where Cij is the travel time between cities i and j. The set of cities will be represented as: C={1,2,3,4,n} A journey solution j will be represented as a string of integers corresponding to those cities, with an implied return to city 1 at the end. The journey, j, starting at city 1 and progressing in the order 2,4,3 through the cities before returning to city 1, will be represented as thus: j{243} One possible implementation for the city journey times would be to store them in a 2D array, with a column for start city, one for end city, and one for the associated time between those cities. Duplicates can be removed as it is a symmetrical problem, so rather than 9 rows (n*(n-1)) we only need 6. Start City Destination City Associated Time 1 2 c12 1 3 c13 1 4 c14 2 3 c23 2 4 c24 3 4 c34

4

However, it would be beneficial for the sake of simplicity to store the full list in a matrix, so that looking up a journey time was simpler. It will also become important later on, when we convert the problem into a time dependent variation. The duplication is not a large problem, and will make the algorithm simpler to implement, and simpler to adapt later on. 0 1 2 3 4 0 c11 c12 c13 c14 0 c21 c22 c23 c24 0 c31 c32 c33 c34 0 c41 c42 c43 c44

5

3

Question C - Determining the Fitness of a Solution

In the question, the optimisation part of the problem is stated as time. ”A salesman has to visit each of n cities in turn, returning to a specified start city, in the shortest time possible, where each city can be visited once only.” However, as we hold data on the distance between those cities it would be easier to work out the fitness of a given solution using the sum distance of the journey. We are provided with no information about the traveling speed of the salesman, or the wait period in each city, so we can make some assumptions that keep the optimisation of the problem the time, but effectively convert it into a distance fitness evaluation. First we will assume that the salesman travels at a uniform speed of 1 mile per hour, and secondly we assume that he will not pause at any of the cities. Therefore we now have an evaluation metric that is equal for either a summed distance in miles, or a total time taken in hours.

6

4

Question D - Crossover and Mutation Operators

To fully equip a GA with the ability to find a solution as close as possible to optimality within a given time it is desirable to use a combination of crossover and mutation operations. With solely crossover operations there is a distinct possibility that the algorithm would work towards a local optimum and remain there, as promising solutions are crossed with others a local optimum would quickly propagate through the solutions in use, and stall the algorithm. With a mutation operation involved as well, random solutions are thrown into contention throughout the cycle of finding a solution, and this may eventually enable an algorithm to branch out from underneath a local optimum, in order to pursue other avenues.

4.1

Crossover Operations

Crossover operations on a solution that includes a string of integers present some problems. If we were to select a random subset of the cities in a solution of size n, for example the first (n/2) cities, then switch them on two solutions, it is possible and probable that we would get both city duplication and omission in each solution. It is possible that there would not be a problem, if both segments contained the same cities, but this is highly unlikely and cannot be relied upon. Using this approach almost all of our solutions would be illegal as no city can be revisited, and all must be visited once. The only progression possible would be within our segment space, in the rare occurrences when the cities matched in both parents. Therefore it is unlikely that any reasonable solution would be found. One solution would be to take a segment from each based upon some random criteria, and swap them. For example the first three positions of each solution may be exchanged. Then, to avoid the problem of repeating or absent cities, one could remove and store the second instance of any repeated city in the solutions, this would give us two solutions of equal length, but perhaps missing some number of cities smaller than our randomly generated segment size (the number cannot be larger than this, but could be zero). These cities that are removed, would then be placed at the end of the other string, in the order that they occurred in the parent string. The result would be two solutions, which have exchanged some segment with each other, and possibly also caused some 7

mutation. This mutation is not exactly desirable in a crossover operation, but unavoidable in a problem such as this where there are constraints on the forced inclusion (and limited occurrence) of elements. By keeping the order of the cities appended to the solution, we can minimise the mutation effect, and retain some of the order from the initial solution. Appendix A shows the method that parents are selected with, and their subsequent combination to form children.

4.2

Mutation Operations

With mutation the problem is far easier, as we can work on a single solution rather than a pair of parent solutions. Therefore if our mutation simply rearranges the cities order we can have no issues arising from visiting a city either more or less than one time, as long as the solution was initially legal. There are numerous ways in which mutations could take place, and to ensure a large amount of variation in our algorithm all should be used, in random amounts. This means that local optimums would be avoided, when good solutions arose, but if the solution was mutated a large amount so as to become impractical it would be quickly eliminated. This gives us a large amount of room to be radical with the mutation operator, as no bad can come from it, apart from the fact that the more illogical mutations we create the slower the algorithm becomes. This is a necessary evil if local optimums are to be avoided, and to keep the algorithm energetically exploring the whole search space. One simple answer is to take two random cities in the solution, and exchange their placement. This would be simple to implement, using a random number generator to pick two numbers, i and j, which would relate to the indexing of the cities placement in the solution S. Positions Si and Sj would then be swapped. Another method would be to vary the amount of cities that were reordered, again this number would be selected by a random number generator, and the same process would occur. Pairs of cities would be swapped, and if the amount of positions to be swapped was uneven, then the first and remaining cities would be exchanged. To implement this I would think of the first method as an instance of the second method where the number of cities to be swapped was 2. By far the simplest method of mutation would be to always mutate the entire string, this could be achieved by generating a string, M, of N random numbers, where N is the size of the solution. The solution S could be rebuilt, by placing the original value at Si at SM i , and so on throughout the solution. The best method would have to 8

be evaluated, as too radical or conservative an approach would have negative effects. Without testing I would have to assume that a varying mutation factor would be best, as it would generate both radical and conservative solutions occasionally, but on average generate mutations where (n/2) cities were repositioned.

9

5 5.1

Question E - Design and Outline Design Decisions

Our GA now has a representation, and mutation/crossover operators. We also need to determine the other details of the GA, such as initial population size and the mechanics of implementing those operators. The population size is important, as it increases the runtime of the algorithm for each generation, it will also increase the likelihood of finding an acceptable solution in each generation. Extremes of each direction are unlikely to be beneficial; either extremely small or large population sizes. The population cannot be smaller than 2 at a minimum, as no evolution would be possible. It is unlikely that any meaningful improvement would be possible with a population of less than 4. Similarly a large population size would be too cumbersome, and would keep a large amount of solutions at one time, although not vary varied. Because of this the GA will have a population size of 8 solutions. We also need to decide the mechanism that will cull unwanted solutions, to remove bad genes from the pool. To do this the GA will discard the four least acceptable solutions from each generation, and using the remaining four will generate replacements for the next generation. Parent selection is an important part of any GA, and in this algorithm we will simply do this by taking a selection of the solutions (n/2) large, where n is the number of solutions. We will choose which by simply taking the best solutions, and discarding the rest. By using crossover techniques from the best four we can generate four new solutions that have properties of two of these good solutions. This will eventually lead to improved solutions by a process of natural selection, but because all solutions remain similar in certain ways it may mean that a local optimum is reached that the algorithm cannot remove itself from. To combat this problem we will also use mutation operators, though we will use them sparingly, to allow the crossover operators to continue to improve the solutions. Each generation, after the crossover operators have finished, we will determine with a random number generator if mutation is to occur in this generation. If it is decided that it will then a mutation operator will randomly select one, or in rare cases more than one, gene to mutate. It will then choose a mutation factor as described earlier to rearrange that gene. If the mutation is beneficial it will be retained by future crossovers, and if it is not then it will be quickly discarded. This discarding will not be detrimental to the solutions in a large manner, as the good solutions that made 10

the gene before mutation will remain and re-propagate throughout the solutions. Halting is another issue that will have to be addressed, as we cannot allow the program to run until an optimal solution is found. The algorithm would not be able to enumerate all possibilities due to it’s search strategy, and it would not be the most efficient way of doing so it if it could. If it did this then it would be pointless for it to be a GA; it could instead be a simple enumeration algorithm. Therefore we need some method for allowing the algorithm to stop, some way to define an acceptable solution so that our GA knows when it has reached one. There could be several methods to do this, but they fall into two main categories; those that focus on the running time of the algorithm, and those that focus on the solution fitness. The only time when the running time should be the factor is when the algorithm has to run in real time and execution speed is vital and constrained. Using this method one cannot guarantee the fitness level of the solution. This could be controlled by running a certain number of generations, or by halting after a certain amount of time. Because our solution has not been described as a real time problem we have the luxury of being able to guarantee a solution is at least of a certain level of fitness. To do this we can put a method call in our loop that takes the 8 fitness values for the solutions, and checks them against an acceptance value. If a solution exceeds this value then we can halt the program and return that solution. If more than one solution exceeds this value then we can simply return the one that is closest to optimality. Appendix B shows a sample graph, where the fitness of generations increases with generations, and it’s eventual passing through the acceptability figure, this is where the algorithm would halt.

5.2

High Level Description of Algorithm

- 8 randomly generated solutions will be used to start the algorithm. They will be generated by a function, that can only create legal solutions (each city 0><2 occurrences). - These solutions will all be tested for fitness, by a separate fitness function, and these values will be stored. - Check to see if any fitness value for the solutions exceeds the acceptance value. If it does then the algorithm can halt, and we can return that solution. If more than one exceeds the value then return the most efficient. 11

- The four least optimal solutions will be discarded. - The four most optimal solutions will be retained, and used to generate the four replacements. - The four remaining solutions will be kept, and they will be used to create the four replacements by taking pairs of the remaining to become parents of the replacements. - These pairs of parents will be used with our crossover operator described earlier, and will create the four parents. - We then have 8 solutions, four of which are the best from the last generation, and four which are hopefully better still. - We then choose whether or not to apply a mutation operator on this generation, using a random number generator. - If the generator chooses to mutate a solution then one will be selected, again at random, and mutated by a mutation factor. This factor is also randomly generated and chooses how much of the solution to alter. In doing this occasionally we can hope to avoid local optimums. - All of the variables used here, initial size of population, number of best solutions to retain, and to a certain extent the random numbers used to control crossover and mutation, should be placed under user control. They can then be tweaked to provide the best algorithm for a certain problem. Running the algorithm again, with different values may prove to be more fruitful.

12

6

Question F - Testing Effectiveness

To test the effectiveness of the GA it would be wise to use standard benchmarks for the traveling salesman problem. A compendium of existing research has been compiled, which would provide many solved examples. [6] This could be used to evaluate the GA design, by inputting one of those solved problems into the algorithm and examining it’s output. Two criteria would be needed for a thorough evaluation; the optimality of the design, and the time taken to reach that optimality. The final solution would need to be checked, if the research provided information about the output of those GAs then you could compare which algorithm provided the best output, using the standard fitness test of route length. Although in our example the fitness test is time taken, if the salesman travels at a consistent speed then it is easy to convert the results of the algorithm to distance results. It may also be possible to take fully solved problems, where the optimal route is known, and to put that problem into our GA. In this instance we would be able to exactly determine how close to the optimal it had reached in a certain time. It would be hard to determine effectiveness of the algorithm in terms of run time, as it is impossible to know what hardware the past research was performed on. A certain problem may be solved faster, by a less efficient GA on a fast machine, than a very efficient and effective GA on a slow machine. To avoid this problem we could take several small TSP problems, and solve them to optimality by enumerating all possible tours and taking the shortest. These problems would have to be small, as the TSP problem is NP-hard and therefore exponential. The time taken to solve these problems could be recorded, and compared to the speed with which our GA can find an acceptable solution. From a non-academic viewpoint, the algorithm could be assessed against the demands and requirements of the user. If the package was being created for a commercial application then the results could be compared to the system requirements laid out prior to implementation, and this metric could be evaluated against user demands. If the algorithm reached an acceptable solution in an acceptable time it could be officially deemed effective in the eyes of the user.

13

7

Question G - Time Dependent Variation

The main changes to the GA for this variant are in the representation, and the evaluation of fitness, although the changes are not limited to these areas. In the representation we will have to take into account for the fact that the journey times will now vary, according to which time period we are in. The journey times, which are variable dependent on the time period in which they are undertaken is an easy problem to solve. It is feasible that in the initial problem the journey times will be stored in a matrix, J, and that you can simply look up a journey time between cities A and B by looking at element JAB . In the time dependent version we will have matrices J1 to JN , where N is the number of time periods in a day. Therefore we can now look up a journey time from A to B in time period i, by looking at the element in JiAB . The matrices will obviously have some duplication, but the simplicity of this solution makes up for it, by reducing the complexity of the algorithm. When evaluating the fitness of a solution, we can no longer simply sum the path lengths between all the cities in order on the route. Now the routes are of varied length, dependent upon which time period the journey is undertaken in. Therefore we must start with the first journey, and take that routes weighting in the first time period, by looking up the journey time in this format JiAB , where Ji is the journey time table corresponding to time period i, and A to B is the journey. We must add to this the weighting of the second journey in the solution, for the time period that we are now in, which will be the sum associated time of all journeys undertaken so far. Therefore we will need a counter, which is the current total journey time. This will have been present in the first version, as we were summing all journey times in that algorithm also.

14

8

Question H - Complications of Delivery Implementation

With the simple traveling salesman problem we can make several assumptions that reduce the inherent complexity of the problem. For example the salesman does not sleep, and requires no breaks. There is also no need to make any assumptions about his mode of transport, hence there are no limitations such as fuel requirements. This lack of constraints keeps the algorithm reasonably simple, however, once real world problems start to be added then the algorithm grows in complexity rapidly. With a practical implementation for delivery vehicles there are many other factors that must be taken into account. For example, the amount of time taken for any route, and the subsequent return to the start point cannot exceed the length of a shift for a delivery driver. That driver needs to return to the start point, and finish his shift within the time he is paid for a shift. There may also be legislation about the amount of time that a driver can spend at the wheel, or a maximum distance. The routes may also be asymmetrical in that they take longer one way than the other, for example if one direction is dual carriage-way and the other is not. Routes will also be variable, not only on certain time periods as in question g, but also on other factors such as day of the week, whether the local football team is playing at home, road-works on the route, accidents, etc. This means that it is impossible to predict exactly how long certain routes will take in the future, and we cannot provide the algorithm with accurate prediction data. To combat this we could keep a back log of actual data, and use data mining and KDD to predict future conditions. We could also make a slight over prediction for each route to allow a certain amount of slippage in critical path applications where a slight delay would cause problems further along the journey. In a ’loose’ solution where there is a certain amount of leeway anyway this is not so much of an issue. Another complication in a real world implementation is vehicle limitations. Certain vehicles may not be able to take optimum routes because of height or weight restrictions. There is also a requirement to refuel, which may need to be done at a company depot, and even if not requires the route to take into account that a detour may be necessary to refuel. To cope with this the graph containing routes will also need to hold such information on hazards or vehicle restrictions. If a bridge or ferry is part of a route then the 15

algorithm will constrain the set of legal solutions accordingly. Load weight may also be an issue, in that the optimum route to distribute packages will be limited by the amount of weight that the vehicle can carry, or the size of packages that can fit into the vehicle. In this instance it is feasible that two GAs would be beneficial; a binary knapsack problem for loading, and a TSP for routing. The load may impose other restrictions, in that the order that the vehicle is loaded may be important. If the packages are large, or tightly packed, then they may need to be loaded in the reverse order to their delivery plan. There may also be restrictions in the way that the packages are handled, if they are fragile or volatile. Certain packages may not be able to be stored in the vehicle for long periods of time, and might need to be delivered quickly. It is possible that a situation arose where certain packages were frozen goods, or live animals, and if that is the case they may need to be delivered first even if this detrimentally affects the efficiency of the delivery order. In this instance it would be necessary to plan the route with these packages being delivered first. The use of a penalty function that would negatively weight delivery in later time periods would achieve this.

16

References [1] Wikipedia - The Free Encyclopedia, Entry for NP-Complete, http://en.wikipedia.org/wiki/NP-complete , 14th March 2006. [2] Wikipedia - The Free Encyclopedia, Entry for http://en.wikipedia.org/wiki/NP-hard , 14th March 2006.

NP-Hard,

[3] ”The Complexity off Theorem-Proving Procedures”, Cook S. A., Proc. 3rd Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, pp. 151-158, 1971. [4] ”Computers and Intractability - A Guide to the Theory of NPCompleteness”, Michael R. Garey, David S. Johnson, Bell Laboratories, New Jersey, 1979. [5] Wikipedia - The Free Encyclopedia, Entry for Polynomial Time, http://en.wikipedia.org/wiki/Polynomial-time , 14th March 2006. [6] Jarmo T. Alander, ”An Indexed Bibliography of Genetic Algorithms and the Traveling Salesman Problem” Citeseer, 2000. [7] Jaron Lanier, One-Half of a Manifesto: Why Stupid Software Will Save the Future from Neo-Darwinian Machines. WIRED Magazine, Issue 8.12, pp. 158-179, December 2000. [8] David Pescovitz, Monsters in a Box. WIRED Magazine, Issue 8.12, pp. 340-347, December 2000. [9] Koza, John R., Jones, Lee W., Keane, Martin. A., Streeter, Matthew J., and Al-Sakran, Sameer H. Towards Automated Dewsign of Industrial Strength Analog Circuits by Means of Genetic Programming. Kluwer Academic Publishing, Genetic Programming Theory and Practice 2, Chapter 8, pp. 121-142, 2004. [10] David E. Goldberg, Department of General Engineering, University of Illionois at Urbana-Champaign, From Genetic Design and Evolutionary Optimization to the Design of Conceptual Machines. IlliGL Report No. 98008, May 1998.

17