Solution of Travelling Salesman Problem (TSP) by Genetic Algorithm (GA)
(10 May 1999)
Introduction
The Problem
The TSP is a classical graph-theoretical problem. It can be described by the following statement :- Given a certain number of cities on a 2-dimensional grid, the TSP is to find a route, starting from and ending at the same city, of visiting each of the cities just once, which minimizes the sum of the Euclidean distances between adjacent cities.
Solution of the TSP by non-GA Approach
Obviously, there exists an optimal solution for the TSP due to the fact that a minimum for the total Euclidean distance for all the given cities exists in theory. There are many methods for the computation of such a total distance, for example, one can simply calculate the distances between any two cities and work out the total distances of each and every possible permutation of all the given cities. Though this is a possible algorithm for solving the TSP from first sight, there is no way to guarantee a solution in polynomial time. In fact, the TSP is a NPC (Non-deterministic Polynomial-time Complete) problem which in short means that it is unsolvable with a standard linear algorithm if the problem’s complexity is large enough. The method just mentioned is actually a linear algorithm and it requires that the computation time is directly proportional to the factorial of the number of the given cities. This method fails even when the number of cities is as small as 10. In order to illustrate the weakness of some conventional algorithms in solving the TSP, this project will demonstrate a ‘Low Weight Hamiltonian Cycle (LWHC)’ algorithm mentioned in standard textbooks for graphs and networks. The LWHC algorithm will also serve as a control algorithm for the assessment of the GA for program quality and effectiveness. This project had also considered the Nearest Neighbor Heuristic algorithm (NNH), which had adopted the 2-optimal techniques to obtain a better solution.
The LWHC & NNH Algorithms
This is a standard textbook algorithm for solving the TSP. The algorithm is to start from a particular city and find a second city, which is nearest in terms of distance to the first city. By the same process, another city is again located in the same manner, i.e. the city which is nearest to both of the previous two cities. This process is repeated until all the cities are handled. This LWHC algorithm does not guarantee an optimal solution though it is efficient to give a solution. Whenever the first city to start with is the same one, the algorithm will without exception return the same solution. Therefore it is ‘first-city’ dependent. This means that it may return at most the number of different solutions as the number of given cities but no more. It is obvious that these different solutions, significantly smaller than the factorial of the number of given cities, do not necessarily contain the optimal one. The study and theory of LWHC algorithm proved that the upper bound for the solution is twice the optimal value. The computation time for LWHC algorithm is directly proportional to the cubic of the number of the given cities. The NNH at first builds its distance matrix from the coordinates of the nodes concerned and searches the matrix for the shortest possible distance from a node to another. Therefore the most time-consuming part of the NNH algorithm is the building up of the distance matrix. It has the complexity of power 2 of the number of nodes concerned. The NNH is faster than the LWHC : to compute the 100-city TSP, the computation time of LWHC is in the area of minutes while NNH completes the searching within seconds. The solution of NNH with 2-optimal gives 106.30 and LWHC gives 115.02.
The Objective of the Project
This project will create a MatLab program consisting of modular M files, which is designed to find an acceptable solution for the TSP and employs the Genetic Algorithm to arrive at the solution.
The Software – MatLab for Windows
This software is matrix and vector orientated, which is suitable for handling numerical data expressing in the form of matrix and vector. In this project, the cities are labeled by natural numbers and the routes are conveniently expressed in row vector format. Graphical interface, which is easily put into codes, is another powerful features of this software. Visually, the solution can be depicted graphically, which not only gives a graph of the route itself but also gives a basis for program improvement by observing the transition of routes during the whole process of program execution. It is true that some improvement achieved in this project is in fact a result of observation and analysis of the graphs of the routes.
The Genetic Algorithm
What is a GA
The GA can be described as a stochastic search technique for an optimal solution of a problem, which can be modeled in accordance with the requirement of GA. The GA is a simulation of the process of evolution in nature. Generally, all the possible solution to a problem forms a space, a point in which is uniquely defined by the independent variables. Each point in the solution space is assigned a value, which is dictated by the problem to be solved or function to be optimized in terms of a particular set of value of the variables. The GA is implemented to search for the optimal solution point in the space. The process of evolution in nature is that the fittest biological species is propagated to the offspring in the next generation by means of sexual reproduction of parents. Mutation is also adopted by nature to achieve a sudden change to the species, which may result in a better species or, equally likely, turns into worse one. However, unlike reproduction, the mutation does not occur frequently. In any event, the ultimate objective of a process of evolution in nature is to let the fittest one survive and to extinguish the less fitted one, eventually. The GA is therefore a computer model, which extracts its “ingredients” from the evolution process. Generally, a GA consists of the following machine process, namely, crossover, mutation, propagation, and fitness evaluation. The measurement of fitness depends on the value assigned to the point as mentioned above. The GA was invented by Mr. John Holland in the early 1970's. According to Holland’s Schemata Theorem, the result of the GA applied to a problem will be a homogeneous population, which has converged on the optimum point in the space being searched.
Parallel Processing of GA
The most powerful feature of GA is its capability of being implemented by parallel processing. However, due to hardware and other constraints of resources, this is not studied and implemented in this project. It is, without diminishing the power of non-parallel GA, therefore as a matter of completeness to mention some point about parallel GA. By implementing parallel GA, the most time-consuming modules can be re-distributed to be processed by a large number of microprocessors and this will both increase the computation time and be capable of handling a population of significant size. However, any distribution of processing will involve some communication overheads, which are not present when the processing is done on one processor.
The Application of GA to TSP
Total Number of City
The coordinates of 100 points to represent all the cities will be generated. This serves as the data set for this project. The x-coordinate and y-coordinate of a particular point is each generated by a separate mathematical equation. Therefore the data set remains the same for each separate execution of program. Each point, therefore each city, is labeled by a natural number from 1 to 100. Of course, the labeling satisfies some simple rule. One hundred points are generated each along the x-axis and y-axis, which makes a total of 100 points then. The city with a label of 1 is at the left lower corner and the labeling moves upward to city 10 at the left upper corner. The city 11 starts again from the bottom and moves upwards in the same manner. Therefore the square grid formed by the xy-axis contains a total of 10 column of 10 points each.
The Solution Space of TSP
To start with a TSP, a certain number of cities, say k (k<=100), will be given and a solution will then be worked out for those cities. The solution space will then consist of all the possible permutation (k!) of the given cities. Therefore each point in the solution space is a permutation of the given city. The value of a point, a measurement of fitness as well, is defined in TSP to be the total distance between all the pair of cities in the permutation. Bearing in mind that the salesman shall return to the starting point, the first and the last city in the permutation forms a pair as well. The definition of ‘fitness’ in project is that the fittest permutation is the permutation having the shortest total distance.
Example : given cities - (4,34,67)
solution space – (4,34,67) (4,67,34) (34,4,67)
(34,67,4) (67,4,34) (67,34,4)
The Implementation of GA
(1) Select (generate) a random number of N points from the solution space and therefore this is a population of N members;
(2) evaluate the value(total distance), fitness, of each of the N members;
(3) rank the members in ascending order of value;
(4) select the first n members as parents (n<=N);
(5) perform crossover, a simulation of sexual reproduction, on the n parents;
(6) a production of 2n offspring as a result of crossover;
(7) select the last p members in the sorted population for the purpose of propagation, i.e. the first p offspring out of the 2n will replace the selected p members (p<=N);
(8) perform mutation on a member randomly selected;
(9) rank the population again;
(10) copy the first member, the fittest member;
(11) perform mutation on the copy;
(12) evaluate the value of the mutated copy;
(13) if the value is better than that of the nth member, replace the nth
member by the mutated copy otherwise perform no replacement;
(14) a new population is then formed and this is termed a new
generation;
(15) return to step(4) and repeat all the process until the pre-assigned
number of generation has reached;
(16) towards the end of the total number of generation, step(11) to
step(13) will be performed for all the cities in the permutation;
(17) the mutation method mentioned in both step(8) and step(11) will be
different for those early generation and latter generation;
(18) the offspring produced in step(6) will be ranked if (2n>p) but not
otherwise.
Implementation of Program Modules
Literature Research
Though the GA had been invented for nearly 30 years, many of the documentation only gave a very brief description of the important parts which a GA should have without going into much details. It even differed a lot among books especially when they handled the actual parameters for the execution of GA programs. It was therefore fair to mention that this project had implemented the GA without borrowing any implementation details from documentation and had managed to make improvement on some of the idea and concept. Passages on the related topic available in the internet were studied as well.
Coding of MatLab Program Modules
The implementation was divided into program modules, each performaning a specific task.
Module for Crossover
The crossover module generates two offspring from two parents. The permutation of each parent is broken into two halves. The first half of parent A is copied to form the first half of the permutation of offspring Ab. The second half of AB is formed by copying from the permutation of parent B those cities, which are not in the first half of Ab, in the same order as they are in parent B. Likewise, the second half of offspring aB is formed by copying the second half of parent B. And the first half of aB is formed by copying from the permutation of parent A those cities, which are not in the second half of aB, in the same order as they are in parent A.
Example : Parent A = (1 2 3 4 5 6 7 8) Parent B = (6 4 3 1 7 2 8 5)
Offspring Ab = (1 2 3 4 6 7 8 5) Offspring aB = (1 3 4 6 7 2 8 5)
In order that the n parents will produce 2n offspring, the crossover (XO) is performed in the following manner :
1st parent XO 2nd parent
2nd parent XO 3rd parent
………………………..
nth parent XO 1st parent
Module for Propagation
This module will replace the last p members from the population by the first p offspring. The population has been ranked before this module applies and the offspring will be ranked as well if (2n>p).
Module for Mutation
This module randomly selects a member from the population for the performance of mutation. Mutation is done by simply interchanging two cities in the permutation. The actual locations are dependent on the number of generation reached. At the earlier stage of the program execution when the number of generation is still far away from the maximum number of generation to be performed, the interchange is performed on cities across the boundary of a permutation identified at the time of crossover operation. However, when the program execution is towards the end, the interchange is performed on cities just next to each other or between cities, which have one city in between. This may be described as a mutation with variant offset. The first city in the permutation is randomly selected for the exchange. Conditional mutation is also performed on a copy of the fittest member in the population. If the mutation gives a permutation, which is better than the nth member in the population, then the nth member is replaced by the mutated copy, otherwise discard the mutated copy and the population receives no change at all. This conditional mutation is also with variant offset. The conditional mutation starts at a randomly selected city in the permutation. However, this conditional mutation is performed on each city in the permutation in turn when the program execution is towards the end.
Module for Evaluation of Fitness
This module simply calculates the total distances of every pair of city in the permutation. The first and the last member constitute a pair as well. The fitness of a member is inversely proportional to the distance. This module occupies much of the computer time during the execution of the program.
Module for Ranking and Sorting
This module simply arranges either the members in the population or the offspring in an ascending order in distance. This ranking is important for the purpose of selection of offspring and members for propagation.
Module for Generating a Population
This module simply generates a random N members and this serves as the population. This in fact is part of the solution space of the TSP for the given k cities.
Difficulties Encountered
At the initial execution of the early version of the program, the program is designed to stop execution either when the maximum number of generation has reached or all the parents are identical. Under this condition, the program usually stops execution after roughly 4 generations. At this stage, the parameters are selected in such a manner that both the number of parents and size of the population were small in magnitude, say for example, parents are between 3-8 and the population size is around 30-50. This is the figure suggested by one of the reference books. The early version of the propagation module simply duplicates the offspring to form the new population of the same size in accordance with the percentage of the fitness of individual offspring, i.e. better the fitness, more occupancy in the new population - the best offspring may appear more than once. The fact that the program accepts small number of parents and allows the best offspring to appear more than once in the new population makes the stop very soon from start or makes the program to converge quickly to an unsatisfactory solution. At the early stage of the project, it has been accepted as a fact that it is desirable to perform mutation on the worst member or at least on a bad member in order that the mutation may result in a better member. There is no conditional mutation and mutation with variant offset at the early stage of the implementation. The test run of the early version of the program does not give satisfactory results. Attempt has been made to use the LWHC module to find a better permutation to start with, which is made one of member of the initial population, with a view to giving better execution result. However, the result does not differ too much. The LWHC module has been used to act as a mutation operator to replace the worse member in the population by the permutation found by the LWHC module. However, the program converges very quickly to the value dictated by the LWHC module. The method of refinement is used a well hoping for a better result but it does not produce any significant improvement in the program execution. The method retains the result of a program execution and returns it to the initial population of a subsequent fresh execution. The idea is that this will allow the initial population to start with a better member, which may produce better offspring and propagate to next generation. It also does not produce significant improvement. A crossover module of retaining the best parent and made it one of the parents in all of the crossover process had been studied and tested, however, this would only direct the program execution to converge very quickly to a particular value. This was attributed to the fact that half of the offspring so generated by having the best parent retained in each and every crossover process contained the same first half permutation as that in the 1st parent. Therefore the variety of the permutation had decreased. This had therefore limited the scope of search of the solution space.
Improvement Made and Techniques Employed
Though the early version of the program was not satisfactory, it really gave insight and background for improvement, especially when the best permutation obtained at the end of each generation was depicted graphically. From an analysis of the graphs of route, the following conclusion was reached, which served as a further basis for improvement of the program and the implementation as a whole :-
(1) a large size of initial population was always desirable for better result;
(2) a large size of better parents would generate better offspring for propagation;
(3) the graph indicated that at the early stage of program execution, it was relatively more likely that cities farther apart were joined but the situation was reversed at the latter stage of program execution, i.e. cities nearer to each other were joined;
(4) the implementation of mutation with variant offset was devised to handle this observation : the mutation module interchanged cities farther apart at first, and after some generation later, the same module switched to swap cities nearer to each other;
(5) towards the end of program execution, it was very easy to simply adhere to a particular value of fitness and it appeared that the program execution tended to converge to this value. This value would remain the best among the members for very many generation. From the observation of the graphs, most of the cities were properly joined and only some number of cities nearer to each other remained improperly joined;
(6) observation in (5) suggested that it would be relatively likely to generate a even better permutation from this already best member when the cities nearer to each other were interchanged. This is the rationale of introducing the module for conditional mutation and it was also the reason why the module applied only to interchange cities at most at an offset of 2 away from each other in the permutation;
(7) the conditional mutation would result, if there was a mutation then, in replacing the nth parent. The reason was two-folded : the nth parent was the worst of the parents and the replacement nth parent would be acted upon by the crossover module to produce offspring with the 1st parent, i.e. the best parent, this further process might produce even better offspring;
(8) the method of crossover, which had each parent participated twice, was found to have generated relatively better offspring with a great spread of variety of permutation.
The finalized version of the program and the program modules had adopted all the above improvement and techniques.
The List of the Various Modules
MODULE FUNCTION PARAMETER
DSPP.m Display the 100 cities marked by ‘*’ Number of points
DWPTH.m Draw the route Title,Where to draw
GA.m Main module grouping other modules
GANHC.m Execute GA & LWHC for same cities Number of total execution
GENP.m Generate the label of cities for TSP
GETP.m User to enter cities for TSP City labels
GETXY.m Generation of xy-coordinates of a city
LWHC.m Low weight hamiltonian cycle module
MUTAT.m Mutation with variant offset
PL.m Evaluation – length of route City labels (row vector)
RMPTH.m Generation of random routes
RNKPTH.m Sort the routes in ascending order Vectors of city labels
RPN.m Propagation and formation of population
SCAT.m Add two strings to form a single string Two strings
SWAP.m Conditional mutation
SWAPALL.m Conditional mutation, to every city
VALIDATE.m Validation of the program Parameters in modules
XOV.m Crossover of parents and offspring
Validation of Program by Solving 19-city TSP
Control Data and Specific Pattern of City
In order to assess the validity of the program, a particular pattern of cities were selected for this purpose. The cities were selected on the basis that it was very easily to work out the optimal path and therefore the total distance simply by visual inspection. The LWHC module would act on the same set of cities to give some idea as to how good the program has been up to. 19 cities were chosen for preliminary test runs. The cities were roughly along the edges of a rectangle and the optimal total distance would then be simply the perimeter of the rectangle. The chosen 19 cities were (1,11,21,31,41,51,53,55,57,59,60,50,40,30,20,10,8,7,3). The optimal total distance for a round trip was about 28.73 and the LWHC module gave a solution of about 44.9, as expected only in a fraction of second.
Execution Result (Annexure A-Case 1 & 2)
The 19-city TSP was solved by a 800-population execution for 200 generations. The parents were 49.9% of the population. Though the execution of 200 generations on a P6-166 64M computer took about 4 hours to complete, the execution had already converged to the optimal solution of 28.73 since the 83rd generation.
The same 19-city TSP was executed again with the same parameters on a Pentium-233 96M computer. It took 2.5 hours to get the optimal solution. However, it had converged to the solution since the 152nd generation.
Conclusion in Respect of Program Validity
Therefore the validity of the program was confirmed by the solution of the 19-city TSP.
Solution of a 12-city TSP
The program was executed for a 12-city TSP, the optimal solution of which was not known beforehand. The cities were (34 36 38 40 42 44 46 48 50 52 54 56). The LWHC module gave a solution of 20.78.
The result of execution was summarized in the table below :-
Generation Population Parent Result Remark
50 150 74 20.55 21.56 appeared for 30 generations since the 13th
50 250 124 20.14 20.14 appeared for 6 generations since the 45th
150 100 49 20.14 20.14 appeared for 134 generations since the 17th
300 50 24 20.57 20.57 appeared for 117 generations since the 184th
100 300 149 20.09 20.09 appeared for 38 generations since the 62nd
20 800 399 20.09 20.09 appeared for 11 generations since the 10th
From the result of the six executions, we could confidently conclude that it was very probably that the optimal solution for the 12-city TSP was 20.09.
Further Work
Further execution of the program on 28-city, 45-city and 100-city TSPs was attempted. They were : (a) 28 cities (1 11 21 31 41 51 61 71 81 91 93 95 97 99 100 90 80 70 60 50 40 30 20 10 9 7 5 3) with a optimum distance of 38.17 and a LWHC solution of around 64.76. (b) 45 cities (from city 23 to city 67) with a LWHC solution of around 49.95, and (c) 100 cities (from city 1 to city 100) with a LWHC solution of around 113.83. The increase of the number of given cities would no doubt significantly increase the computer execution time. No optimal solutions were obtained. Mr. Goldberg had shown that for optimal results population size must increase exponentially with the number of given cities. In order to give some idea as to the inter-relation among the parameters, the following figures were quoted from [8] : (a) 50-city TSP – parallel processing by 18 computers to have the optimal result in 400 seconds with a population size of 9216 for 479232 generations, (b) 100-city TSP – parallel processing by 18 computers to have the optimal result in 47 minutes 18 seconds with a population size of 18432 for 2211840 generations, (c) 200-city TSP – parallel processing by 18 computers to have the optimal result in 3 hours 39 minutes with a population size of 18432 for 7372800 generations, and (d) 532-city TSP – parallel processing by 18 computers to have the optimal result in 27 hours 26 minutes with a population size of 18432 for 18432000 generations.
Result of Execution
Some of the execution result for further work on 28-city, 45-city and 100-city TSPs was depicted in Annexure B.
Conclusion
The LWHC module might be used as a control algorithm to give some rough idea as to the order of magnitude of the optimal solution. Small population with large generation might easily go into local minimum but could give some insight as to the solution space. Observation from this type of execution might assist in the setting of various parameters. Large population with small generation might not be sufficiently close to the optimal solution though better result would be relatively likely. Large population with large generation would be expected for the optimal result. The program was designed in such a way that the execution could be done at stages for a review of the process of the execution before a decision to continue with further execution. Though LWHC & NNH were relatively efficient algorithms to arrive at a solution with a moderate degree of good quality, it had no way to guarantee an optimal solution and in fact LWHC & NNH would rarely give such a solution. On the other hand, GA was capable of obtaining an optimal solution of course at the expenses of computer execution time. This project has already demonstrated that GA could be easily coded and it was capable of solving optimization problem. It was only a matter of computer hardware and computational time to put the GA into solving practical problem. The capability of GA in parallel processing would tremendously reduce the computer execution time and make a very practical tool. The complexity of GA was roughly the product of population size and number of generation.
Reference
1. Applications of generalized nets / editor, Krassimir T. Atanassov. Singapore :
World Scientific, c1993.
2. Advances in computational and stochastic optimization, logic programming, and heuristic search : interfaces in computer science and operations research / edited by David L. Woodruff. Boston, Mass. : Kluwer Academic Publishers, c1998.
3. Artificial neural nets and genetic algorithms : proceedings of the international conference in Innsbruck, Austria, 1993 / R.F. Albrecht, C.R. Reeves, amd N.C. Steele (eds.). Wien : Springer-Verlag, c1993.
4. Computational intelligence for optimization / Nirwan Ansari, Edwin Hou.
Boston : Kluwer Academic, c1997.
5. Genetic algorithms + data structures = evolution programs / Zbigniew Michalewicz. Berlin : Springer-Verlag, c1992.
6. The Traveling salesman problem : a guided tour of combinatorial optimization / edited by E.L. Lawler ... [et al.]. Chichester : Wiley, c1985.
7. Adaptive computing : mathematical and physical methods for complex environments : 4-5 August 1996, Denver, Colorado / H. John Caulfield, Su-Shing Chen, chairs/editors ; sponsored ... by SPIE--The International Society for Optical Engineering. Bellingham, Wa. : SPIE, c1996.
8. Parallel computation : based on the proceedings of a conference on parallel computation / organized by the Institute of Mathematics and Its Applications and held at St. Catherine's College, Oxford, in September 1991 ; edited by A.E. Fincham and B. Ford. Oxford : Clarendon Press, c1993.
9. Proceedings of the Seventh International Conference on Genetic Algorithms : Michigan State University, East Lansing, MI, July 19-23, 1997 / editor/program chair, Thomas Back ; supported by Office of Naval Research ... [et al.]. San Francisco, Calif. : M. Kaufmann, c1997.
10. Second International Conference on Genetic Algorithms in Engineering Systems : Innovations and Applications, 2-4 September 1997, venue, University of Strathclyde, Glasgow, UK. London : Institution of Electrical Engineers, c1997.
11. Applied and Algorithmic Graph Theory : edited by Gary Chartrand & O.R. Oellermann, Mcgraw-Hill International Editions.
12. http://www.acc.umu.se/~top/travel.html.
13. http://inf.cs.nthu.edu.tw/resources/matlab.html.
14. http://garage.cps.msu.edu/papers/papers-index.html.
15. http://www.aic.nrl.navy.mil/galist/.
Annexure
A. 19-City TSP-Optimal Solution
Case 1
generation=200 parent=399 population=800
replacement factor=1.00 mutation factor=1.00
71.90 67.57 66.85 62.50 61.22 60.36 52.76 52.76 52.76 52.76 50.12 50.12 50.12 50.12 50.12 50.12 50.12 50.12 50.12 48.30 44.99 44.99 44.99 44.99 44.99 41.32 41.32 39.35 37.42 37.42 35.44 35.44 35.44 35.44 35.44 35.44 35.44 30.06 30.06 30.06 30.06 30.06 30.06 30.06 30.06 30.06 30.06 30.06x38 28.73x115
Optimal Path = [11 21 31 41 51 53 55 57 59 60 50 40 30 20 1 8 7 3 1]
Case 2
generation=200 parent=399 population=800
replacement factor=1.00 mutation factor=1.00
73.00 64.05 59.80 57.75 58.50 56.45 53.28 51.05 54.43 49.95 49.95 49.95 47.52 46.63 42.84 43.90 45.44 45.66 41.82 42.65 44.31 44.31 43.67 44.31 43.67x11 42.79 43.67x6 38.51x63 37.77x7 37.76 35.95 34.62x8 33.39x15 31.42x6 30.95x5 29.53x3 28.73x49
Optimal Path = [57 59 60 50 40 30 20 10 8 7 3 1 11 21 31 41 51 53 55]
B. 28-City TSP
Parameters ===> gn=300 pnt=99 pop=200 rrp=0.99 pmt=1.00
Best distance obtained ===> 50.03 (1.5 hours)
The path returned by program ===> 61 51 41 31 21 11 1 3 5 7 9 10 20 30 90 100 40 50 60 70 80 99 97 95 93 91 71 81
Parameters ===> gn=300 pnt=399 pop=800 rrp=0.99 pmt=1.00
Best distance obtained ===> 53.93 (14.5 hours)
The path returned by program ===> 93 91 71 51 61 81 95 97 100 90 80 99 70 60 50 40 30 20 10 9 7 5 3 31 21 11 1 41
Parameters ===> gn=500 pnt=124 pop=250 rrp=0.99 pmt=1.00
Best distance obtained ===> 52.07 (5 hours)
The path returned by program ===> 50 97 91 93 95 81 71 61 51 41 31 21 11 1 3 5 7 9 10 20 30 40 60 80 99 100 90 70
Parameters ===> gn=300 pnt=249 pop=500 rrp=0.99 pmt=1.00
Best distance obtained ===> 56.73 (4.5 hours)
The path returned by program ====> 50 60 70 80 90 100 99 97 95 93 91 81 71 61 51 31 7 9 41 21 11 1 3 5 10 20 30 40
45-City TSP
Parameters ===> gn= 900 pnt=249 pop=500 rrp=0.99
Best distance obtained ===> 52.33 (24 hours)
The path obtained by program ===> 23 24 25 35 56 65 66 67 58 48 38 37 26 27 28 39 49 59 60 50 40 30 29 47 57 46 36 45 55 54 53 52 41 31 32 43 34 44 64 63 62 61 51 42 33
100-City TSP
gn=150 pnt=499 pop=1000 rrp=1.00 pmt=1.00
85 76 56 60 100 97 6 9 19 8 63 74 91 93 99 67 79 75 83 96 72 71 61 43 45 29 59 57 34 31 11 12 7 25 73 62 52 4 1 24 87 16 5 15 32 53 77 84 65 55 44 35 37 47 86 80 89 50 30 40 68 3 2 46 95 66 39 90 69 48 58 78 64 42 41 17 18 20 98 88 49 38 28 26 23 22 13 36 27 70 92 94 21 14 10 33 51 81 82 54 distance = 317.66
gn=300 pnt=49 pop=100 rrp=1.00 pmt=1.00
5 7 69 80 30 60 70 68 97 64 54 14 19 86 87 35 4 23 46 36 24 2 1 22 41 53 74 44 26 47 10 39 48 49 40 29 18 61 62 66 77 99 98 96 93 83 82 92 55 57 84 94 72 73 65 56 95 11 3 45 79 78 51 34 25 12 21 32 42 15 16 33 31 13 27 50 59 38 6 37 100 88 75 91 67 58 76 85 81 71 63 52 43 89 90 28 20 9 8 17 distance = 284.49
gn=500 pnt=99 pop=200 rrp=1.00 pmt=1.00
44 66 52 72 91 70 69 35 34 12 13 32 51 81 64 55 28 29 20 10 49 47 24 16 79 89 80 90 11 1 21 33 62 41 31 22 2 14 42 73 83 76 68 38 30 39 17 27 7 4 3 26 37 48 60 100 75 43 36 46 56 85 94 86 87 40 50 59 58 18 19 9 8 54 92 93 74 65 77 96 95 71 23 25 53 63 84 97 98 78 88 99 6 5 45 61 82 67 57 15 distance = 265.67
C. The Program Listings – Modules
function [a,l,d,rankpath,nng]=GA(generation,pnt,pth,prp,rkp,ng,dmat)
[rr,ss]=size(rkp);nng=ng;path=pth;parent=pnt;
shusernode=[1];% shusernode=[1 11 21 31 41 51 61 71 81 91 93 95 97 99 100 90 80 70 60 50 40 30 20 10 9 7 5 3];sl=PL(shusernode,dmat);
% usernode=GETP;usernode=GENP(1,100,1,1);% usernode=[1 11 21 31 41 51 61 71 81 91 93 95 97 99 100 90 80 70 60 50 40 30 20 10 9 7 5 3];
[ee,ff]=size(usernode);pm=1;N=0;
swl=floor(0.6*generation); mutate=floor(1000*rand)+1;
if ((ss==1)&(rr==1)) randompath=RMPTH(usernode,path); [randompath,dist]=RNKPTH(randompath,dmat); rankpath=randompath(1:parent,:); path=parent; parent=floor(parent*prp/2);else rankpath=rkp; dist=PL(rankpath(1,:),dmat);end
if ((parent*2) > floor(path*prp)) sort=1; fprintf(1,'Offspring - Sorting !!!!\n');else sort=0; fprintf(1,'Offspring - No Sorting !!!!!\n');end
while (N
if (N>0) zz=num2str(dist(1)); xx=num2str(N+nng); zzz=SCAT('GA => ',zz); xxx=SCAT(zzz,' of G'); xx1=SCAT(xxx,xx); yy=rankpath(1,:); if (N==1) dummy=DWPTH(xx1,yy,1,2,0); end if (N>1) dummy=DWPTH(xx1,yy,1,2,1); dummy=DWPTH(SCAT('Previous GA => ',num2str(d(N))),pmut(N-1,:),1,1,1); end pause(0.001);
fprintf(1,'G %3.0f => %6.2f\n',N+nng,dist(1)); end
[offspr,doff]=XOV(rankpath,parent,sort,dmat);newpath=RPN(offspr,rankpath,prp);
N=N+1;d(N)=dist(1,1);
check=floor(pm*1000)+1;if (check>mutate) randompath=MUTAT(newpath,N,generation);else randompath=newpath;end
[rankpath,dist]=RNKPTH(randompath,dmat);if (N
end % end-while
fprintf(1,'G %3.0f => %6.2f\n',N+nng,dist(1)); a=rankpath(1,:);l=dist(1);nng=nng+N;qq=num2str(l);qqq=SCAT('GA => ',qq);tt=num2str(ff);ttt=SCAT('Selected Points = ',tt);dummy=DWPTH(SCAT('Previous GA => ',num2str(d(N))),pmut(N,:),1,1,1);dummy=DWPTH(qqq,a,1,4,2);dummy=DWPTH(ttt,usernode,0,3,2);
********* End of Report *********
沒有留言:
張貼留言