Performance Analysis of Partial Use of Local Optimisation Operator on Genetic Algorithm for

TSP

Milan Djordjevic, Andrej Brodnik, and Marko Grgurovic

Department of Information Science and Technology University of Primorska, Koper, Slovenia

    milan.djordjevic@student.upr.si, andrej.brodnik@upr.si,
                marko.grgurovic@student.upr.si

Abstract. The paper analyzes separate, combined and partial performance of local searcher and genetic algorithm. On the well studied Euclidean Travelling Salesman Problem we examine the impact of grafting a 2-opt heuristic based local searcher into the genetic algorithm for solving the Euclidean Travelling Salesman Problem. Genetic algorithm provides a diversification, while 2-opt improves intensification. Results on examples from TSPLIB show that this method combines good qualities from both methods applied and significantly outperforms each individual method. The experiment extension demonstrate a third generation testing on hybrid genetic algorithms where an influence of partial grafting a 2-opt local searcher into genetic algorithm was tested.

1 Introduction

Genetic Algorithms (GA) use some mechanisms inspired by biological evolution [9]. They are applied on a finite set of individuals called population. Each individual in a population represents one of the feasible solutions of the search space. Mapping between genetic codes and the search space is called encoding and can be binary or over some alphabet of higher cardinality. Good choice of encoding is a basic condition for successful application of a genetic algorithm. Each individual in the population is assigned a value called fitness. Fitness represents a relative indicator of quality of an individual compared to other individuals in the population. Selection operator chooses individuals from the current population and takes the ones that are transferred to the next generation. Thereby, individuals with better fitness are more likely to survive in the population‘s next generation. The recombination operator combines parts of genetic code of the individuals (parents) into codes of new individuals (offsprings). The components of the genetic algorithm software system are: Genotype, Fitness function, Recombinator, Selector, Mater, Replacer, Terminator, and in our system a Local searcher which is new extended component. In this paper we study a well defined problem of a Traveling Salesman Problem (TSP). In the TSP a set {C_{1}, C_{2}, ...C_{N}} of cities is considered and for each pair {C_{i}, C_{j}} of distinct cities a distance d(C_{i}, C_{j}) is given. The goal is to find an ordering π of the cities that minimizes the quantity

∑_{i=1}^{N−1} d(C_{π(i)}, C_{π(i+1)}) + d(C_{π(N)}, C_{π(1)}).  (1)

This quantity is referred to as the tour length since it is the length of the tour a salesman would make when visiting the cities in the order specified by the permutation, returning at the end to the initial city. We will concentrate in this paper on the symmetric TSP in which the distances satisfy d(C_{i}, C_{j}) = d(C_{j}, C_{i}) for 1 ≤ i, j ≤ N and more specificaly to the Euclidean distance. While the TSP is known to be NP-hard [7] even under substantial restrictions, the case with Euclidean distance is well researched and there are many excellent algorithms which perform well even on very large cases [7]. The 2-opt is a simple local search algorithm for the TSP. The main idea behind it is to take a route that crosses itself and reorder it so that it does not cross itself any more. The 2-opt local search will be used to hybridize GA metaheuristic to solve TSP. Although the 2-opt algorithm [5] performs well and can be applied to Traveling Salesman Problems with many cities, it finds only a local minimum. The nearest neighbour algorithm [10] is one of the most intuitive heuristic algorithms for the TSP. It’s a greedy method for solving the TSP. The genetic algorithm considered in this paper are hybrid genetic algorithms, incorporating local search which have been referred to as Memetic Algorithms (MA) [11]. One example of hybridisation of genetic algorithms is shown in [12]

2 Grafted GA for the TSP

Grafting in botanic is when the tissues of one plant are affixed to the tissues of another. Grafting can reduce the time to flowering and shorten the breeding program. Local Searcher is an extension of the conventional genetic algorithm as it does not need to make use of genetic components. It facilitates the optimization of individual genomes outside the evolution process. There are many implementations of local searchers [6], some even in hardware [10]. In our algorithm, the pseudocode can be seen in Algorithm 1, after the recombination has been applied (line 7 in the pseudocode), a Local Searcher is used to optimize every single offspring genome (line 8 in the pseudocode). Because of the usage of such external optimizer the genetic algorithm is no longer pure and therefore we speak of a grafted genetic algorithm [2, 3]. This form of optimization is of a local kind. It alters the genome by heuristically changing the solution. Edge map crossover [6] is an implementation of the recombination operator (line 7 in the Algorithm 1). It makes use of a so called edge map. Distance preserving crossover [8] is another implementation of the recombination operator (line 7 in the Algorithm 1). It attempts to create a new tour with the same distance to both parents. The local learcher is an extension to the conventional genetic algorithm as it needs not make use of genetic operators. It facilitates the optimization of individual genomes outside the evolution process. The Local Searcher has no further knowledge on the execution of the genetic algorithm in the larger setting. The system will provide it with the genome it needs to locally optimize when needed.

Algorithm 1 Pseudocode

1: t = 0 2: initialize (P (t)) 3: evaluate (P (t)) 4: while not terminate (P (t)) do 5: sel = select (P (t)) 6: mat = mate (sel) 7: rec = for each mated collection m ∈ mat do recombination(r) 8: loc = for each genome g in each recombined collection r ∈ rec do local search 9: rep = replace(loc, P (t)) 10: P (t + 1) = select(rep) 11: evaluate (P (t + 1)) 12: t = t + 1 13: end while

The 2-opt local searcher is a local optimizer for the TSP that has been grafted into the standard genetic algorithm (line 8 in the Algorithm 1). This local optimizer performs the 2-opt heuristic that exchanges edges to reduce the length of a tour. An exchange step consists of removing two edges from the current tour and reconnecting the resulting two paths in the best possible way Fig. 1. Following experiments demonstrate a third generation testing on hybrid genetic algorithms. In the extension of an experiment an influence of partial grafting a 2-opt local searcher into genetic algorithm was tested. In the conducted experiments we will present an influence of grafting GA with local search and we will perform a performance analysis of partial use of local optimisation operator on GA for TSP. Furthermore, we will answer the questions of how often to graft a GA and when.

Fig. 1. Exchange step of 2-opt algorithm

3 Experiment

Table 1. Five techniques for solving Euclidean TSP

For testing our strategy and comparing it to other solutions we used the instances of symmetric traveling salesman problem which can be found on TSPLIB. We deliberately used well known problem (TSP) and relatively small instances for which best solutions are known since the goal of this research is not to find a better algorithm for the symmetric TSP, but rather to compare on a controlled environment the impact of grafting a genetic algorithm. Altogether 20 instances have been tried out, with different complexity and range from 14 to 150 cities per instance, look in Table 1. We compared our method (grafted genetic algorithm (GGA)), separately in one case with edge map crossover (GGAemc) and in another case with a distance preserving crossover (GGAdpc) with four other methods. As the upper bound for the quality of solution we used the above mentioned Greedy Heuristic. For the lower bound for the quality of solution we used exact solutions, global minima, obtained by Concorde [1]. Then we compared our grafted method with a pure 2-opt algorithm and pure genetic algorithm. For Greedy Heuristic and the pure 2-opt Heuristic the running time is in a range from 0.5 to 1.5 seconds. In experiment extension a local searcher is periodically implemented with 10, 20, 30, 40, 50, 60, 70, 80 and 90% frequency. In all cases three different independent distributions of generations with local searcher were used: random, beginning sequence and ending sequence. Random variations means that use of local searcher is with adequate probability distributed in iterations of the algorithm. Begin sequence means that a sequence of iterations with local searcher is used in the first generations of an algorithm. While in the ending it is used on the last generations of the algorithm. The total number of iterations are limited to the number of iterations reached in grafted genetic algorithm with edge map recombination (GGAemc). The extension of an experiment include testing on a 10 largest instances from the Table 1 plus instance pr439. The results presents average values of 5 runs for each tested method. All experiments were conducted on a computer with Pentium(R) 2.8 GHz CPU, with Windows 7. Furthemore, a development environment the EA Visualizer [4], an application written in Java programming language, was used. The Concorde’s code is written in the AnsiC programming language. Therefore, in this research absolute times were not of crucial importance, we were only interested in relative performance of tested algorithms.

4 Results

The results of an experiment are summarized in Table 1. Twenty cases from the well known TSPLIB were used for testing. The names of these cases are in the first column and the name always contains the size of the problem, i.e. the number of cities (which are between 14 and 150). The last two columns are exact solutions (global minima) obtained by Concorde [1], together with execution times. A well known problem with moderate sized examples and tools to get optimal solutions were selected, recall that a goal of this research is not to improve solutions for difficult problems but to compare and quantitatively examine the effects of grafting local searches (in this case 2-opt based) to standard genetic algorithm. Such knowledge can be used to fine tune and calibrate a hybrid system which can then be used on large cases. These last two columns are used as a reference for all other tests. The second column in Table 1 represents lower bound for the quality of solution. It is a simple nearest neighbour heuristic. It is fast, but very unsophisticated and any reasonable algorithm should do better than that. This greedy heuristic gives results that are about 15 % (except for some very small cases) worse than the optimal solution. The column titled quality shows by how many percent is the solution produced by this algorithm worse than the optimal solution. 0 % in this column means algorithm found the best solution. The running times of the algorithm are from 0.2 to 2.3 in seconds. The third column in the Table 1 corresponds to the pure 2-opt algorithm. As expected, it also gives quick but far from optimal solutions. It quickly finds a local minimum, but it is unable to broaden the search to find another local minimum. However, 2-opt algorithm is superior to greedy algorithm, the quality of the solution, with the similar running times from 0.2 to 2.5 seconds, is on average about 8 % worse than optimal. The fourth column in the Table 1 corresponds to the pure Genetic Algorithm. The running time, as expected, is significantly increased. While our GGA algorithm reached optimal solution below one second or few seconds (0.6 to 15.3 seconds), the running time for pure genetic algorithm was from 3.4 seconds to 100 seconds which was time-limit. In 12 out of 20 cases no optimal solution was found within that time limit, but in 8 cases an optimal solution was found and the middle column indicates in which generation that happened. For 12 cases where optimal solution was not found, the quality of found solution is expressed as for previous cases in percents above the optimal solution. The sixth column in Table 1 describes results obtained by our grafted algorithm, which is programmed with edge map crossover as recombination operator (GGAemc). In 17 out of 20 considered cases an optimal solution was found. Remaining three instances differ from optimal solution in 0.01, 0.10 and 0.22 percent. The solutions were found in relatively few generations and very fast. Execution times were 0.6 to 15.2 seconds. The seventh column in Table 1 corresponds to our grafted genetic algorithm which contains a distance preserving crossover as recombination operator (GGAdpc). In 11 out of 20 considered cases an optimal solution was found. In remained 9 cases, delivered solutions differ from optimal in range from 0.13 to 0.32 percent. The running time and number of generations of GGAdpc, in comparison with GGAemc, are slightly lesser, particularly in the lowermost part of the table which represents more complex instances. Quantitative results on test cases from TSPLIB show that grafted algorithms, GGAemc and GGAdpc, have advantages. Even when their’s components have serious drawbacks, their grafted combinations exhibits a very good behaviour. Results on examples from TSPLIB show that this grafted method combines good qualities from both methods applied and significantly outperforms each individual method. The results of experiment extension are summarized in Table 2 and in Figures 2, 3 and 4. The first column in Table 2 corresponds to the names of instances and the size of the problem (which are between 76 and 439) which are duplicated for better visualization of the table. The second column in the Table 2 presents the result of the pure Genetic Algorithm and grafted Genetic Algorithm, both with edge map crossover as recombination operator (GAemc and GGAemc). This algorithms contain 0% and 100% frequency of local search, respectively. The q in Table 2 stands for quality differ from optimal solution. The t stands for running time. The third column in Table 2 represents results for 10% and 90% frequency. The subcolumn titles rnd, begin, end stands for three variations of partial hybridization, random, begin sequence and end sequence, respectively. The result for 10% frequency shows that this kind of algorithm settings is fast (the time vary from 0.9 seconds to 11.0 seconds), but the quality of solution (which vary from 0.34% to 4.92%), are weak. The best performance of all tested cases was achieved in the configuration with 90% frequency, especially in variation with end sequence, with results coloured in red. In 9 out of 11 tested instances the results was the same as for GGAemc. For instance (kroB100) result was better in 0.01%, and for instance pr439 a result is worse in 0.04%. Furthermore, the solutions provided by, 90% end sequnce variations, were found faster then by GGAemc. The running time vary from 3.3 to 78.9 seconds, compared to the time achieved by GGAemc, which vary from 3.6 to 91.8 seconds. This mean, that the same quality of result was achieved in shorter time. The results for instance pr439 can be seen in Figure 2. In 95% of all tested cases, (look in columns from 3 to 7 in Table 2) the best performance was achieved in variation with end sequence. Additionally, the results of end sequence for all instances can be seen in Figure 4. In all three variations

7

Table 2. Partial Grafting of a Genetic Algorithm of hybridization (random, begin and end) the running time is the same for particular frequency. For all tested instances the running time grows almost linerly with regard to percent of hybridization, see Figure 3.

Fig. 2. Results for pr439

Fig. 3. Running times

5 Conclusions

The goal of this paper was to investigate influence of grafting a 2-opt based local searcher into the standard genetic algorithm, for solving the

Fig. 4. Results for end sequence

Travelling Salesman Problem with Euclidean distance. It is known that genetic algorithms are very successful when implemented for many NPhard problems. However, they are much more effective if some specific knowledge about particular problem is utilized. In our first experiment we compared two direct techniques, with our grafted genetic algorithms. Solutions from Concorde and greedy algorithm were added for better comparison. Quantitative results on test cases from TSPLIB show that grafted algorithms have advantages. Even when both components have serious drawbacks, their grafted combinations exhibits a very good behaviour. Results on examples from TSPLIB show that this method combines good qualities from both methods applied and significantly outperforms each individual method. In the second part of an experiment an influence of partial grafting a 2-opt local searcher into genetic algorithm was studied. The best performance was achieved in a configuration with 90% frequency with end sequence. In a comparison with a performance of GGAemc the same quality of results was achieved in a shorter time, on average a 7% of running time was spared. The cases with 10% frequency use of local search provides fast and far from optimal solutions but still better then the GAemc, with small increase in time. The configurations with 50% frequency use of local searcher present a good examples of trade-off between a running time and quality, especcialy in setting with ending sequence of local searcher. From the results obtained in Table 2, we can conclude that the best gain is attained when a local searcher is used in an ending sequence of the algorithm and in frequency not less then 50% and not more than 90%. There are several issues for future research, such as investigating the effects of a different use of the local optimisation and other metaheuristic algorithms, analyzing the individual performance gains provided by the local search, and to look at how to scale up the algorithm for solving large instances of TSP.

References

1. Applegate, D., Bixby, R., Chvátal, V., Cook, W.: TSP cuts which do not conform to the template paradigm. In: Computational Combinatorial Optimization (2001) 261–304

2. Djordjevic, M.: Influence of Grafting a Hybrid Searcher Into the Evolutionary Algorithm. In: Proceedings of the Seventeenth International Electrotechnical and Computer Science Conference. Slovenian Section IEEE (2008) 115–118

3. Djordjevic, M., Tuba, M., Djordjevic, B.: Impact of Grafting a 2opt Algorithm Based Local Searcher Into the Genetic Algorithm. In: Proceedings of the 9th WSEAS international conference on Applied informatics and communications. World Scientific and Engineering Academy and Society (WSEAS) (2009) 485–490

4. Bosman, P., Thierens, D.: On the modelling of evolutionary algorithms. In: Proceedings of the Eleventh Belgium-Netherlands Conference on Artificial Intelligence BNAIC (1999) 67–74

5. Engels, C., Manthey, B.: Average-case approximation ratio of the 2-opt algorithm for the TSP. Operations Research Letters 37 (2009) 83–84

6. Freisleben, B., Merz, P.: New genetic local search operators for the traveling salesman problem. In: Proceedings of the 4th International Conference on Parallel Problem Solving from Nature (1996) 890–899

7. Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. WH Freeman & Co, New York (1979)

8. Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research 126 (2000) 106–130

9. Holland, J.: Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor (1975)

10. Hoos, H., Stutzle, T.: Stochastic local search: Foundations and applications. Morgan Kaufmann (2005)

11. Merz, P., Freisleben, B.: Memetic algorithms for the traveling salesman problem. Complex Systems 13 (2001) 297–346

12. Sels, V., Vanhoucke, M.: A hybrid dual-population genetic algorithm for the single machine maximum lateness problem. In: Proceedings of the 11th European conference on Evolutionary computation in combinatorial optimization (2011) 14–25