COMBINATION OF CROSSOVER OPERATORS FOR THE TSP
MARJAN MERNIK, MATEJ ý5(3,1â(.VILJEM ä80(5
University of Maribor
Faculty of Electrical Engineering and Computer Science
Smetanova 17, 2000 Maribor, Slovenia
{marjan.mernik, matej.crepinsek, zumer}@uni-mb.si
Abstract
In the paper the metaevolutionary approach in searching of the best combination of crossover operators for traveling salesman problem is described. Since different crossover operators preserve different useful properties the combination of operators may out-perform single operator. Rather than randomly search for best combination of crossover operators the metaevolutionary approach is used. Preliminary results confirm this hypothesis.
Keywords
evolution algorithm, genetic algorithm, traveling salesman problem, metaevolutionary approach
1. Introduction
Evolution algorithm [Bäck 1996, Michalewicz 1996] is a search and optimization technique based on the principles and mechanisms of natural selection and survival of the fittest. Evolution algorithms (genetic algorithm, evolution strategies, evolutionary programming, and genetic programming) have been successfully used in a wide variety of combinatorial optimization problems such as boolean satisfiability problem, traveling salesman problem, scheduling problems, etc. Generally, the evolution algorithm consists of three genetic operators: selection, crossover, and mutation. The selection operator uses fitness values to select individuals that will be parents of the next generation. Parent individuals are mated and used to produce offspring by the crossover and mutation operators. It is widely recognized, that the crossover operator has a great influence on performance of evolution algorithms. For the traveling salesman problem many crossover operators, such as PMX, OX, CX, ERX, SSX, DPX, CSEX have been proposed. The question is which of the proposed crossover operator is superior to others and if combination of operators is superior to single operator. To answer this question we used a metaevolutionary approach. The basic idea of metaevolutionary approach is to consider the search for
the best evolutionary algorithm as an optimization problem and use another evolutionary algorithm to solve it. In other words, to determine the best evolutionary algorithms, that means to determine the best evolutionary operators and their parameters settings such as: population size, the crossover probability, and the mutation probability, another evolutionary algorithm is used.
This paper is organized as follows. In the section 2 the traveling salesman problem is described. The metaevolutionary approach in searching of the best combination of crossover operators for traveling salesman problem is described in section 3. Results and conclusions are presented in section 4 and 5.
2. Traveling salesman problem (TSP)
The objective of the traveling salesman problem is to find the shortest Hamiltonian path or cycle in a complete graph of N-nodes. The size of the search space of the traveling salesman problem is N! This problem is a classic example of an NP-hard problem. In the case when N is very large, it is important to have approximation algorithms that can find near-optimal or optimal solution within reasonable computation times. For the traveling salesman problem many approximation algorithms, such as the 2-opt, 3-opt, randomized arbitrary insertion [Brest 1999] and other approximation approaches such as simulated annealing, tabu search, ant colony, neural networks and evolutionary algorithms, have been proposed. In this paper only genetic algorithm for traveling salesman problem has been investigated.
Standard genetic algorithm assume that the problem can be represented as a binary string. This allowed us to use binary mutation and crossover. However, this is not a case for traveling salesman problem. There is no practical way to encode a traveling salesman problem as a binary string that does not require some sort of repair algorithm. To solve this problem some variation on standard genetic crossover must be used. Therefore, several other more suitable representations for chromosomes have been developed such as vector and matrix representation. Vector representation can be further divided into adjacency, ordinal and path representation. Each of these representations has its own crossover operators. Among
these representations the path representation is the most natural and successful. For path representation many different crossover operators have been proposed such as partially mapped crossover (PMX), order crossover (OX), cycle crossover (CX), and edge recombination crossover (ERX). The PMX operator [Goldberg 1985] builds an offspring by choosing a subsequence of a tour from one parent and preserving the order and position of as many cities as possible from the other parent. The OX operator [Oliver 1987] builds an offspring by choosing a subsequence of a tour from one parent and preserving the relative order of cities from the other parent. The CX operator [Oliver 1987] builds an offspring in such a way that each city and its position come from one of the parents. The ERX operator [Whitley 1989] builds an offspring preserving edges from both parents. After this initial crossover operators many new and modified operators which out-perform above operators have been developed such as SSX, DPX, CSEX. In this study we are looking for the best combination of crossover operators for traveling salesman problem among PMX, OX, CX, and ERX operators. In [Oliver 1987] authors reported that among PMX, OX and CX operators for traveling salesman problem the best performance was achieved by OX, followed by PMX, with CX as the poorest among them. Further, in [Whitley 1989] authors reported that the ERX operator out-performs above three operators. Before, we start with this study the performances of these operators have already been known. Since the quest for an evolution program for the traveling salesman problem, which would include the best representation and best genetic operators is still going on [Michalewicz 1996], our idea was that some combinations of these operators may out-perform single operator. Rather than randomly search for best combination of crossover operators we decided to use metaevolutionary approach.
3. Metaevolutionary approach
It has long been acknowledged that the parameters that control an evolution algorithm can have significant impact on its performance. Therefore, the designer of evolutionary algorithm has a problem with deciding what operators and control parameters settings are likely to produce best results. Researchers usually used experience from previous similar application scenarios. A more promising approach is to consider the search for the best evolutionary algorithm for a given problem as an optimization problem itself which can be solved by evolutionary algorithm, leading to metaevolutionary approach.
Several metaevolutionary approaches have already been proposed. In [Grefenstette 1986] the metaevolutionary approach was used to determine population size, crossover probability, mutation rate, generation gap, scaling window, and selection strategy. In [Freisleben 1993] the metaevolutionary approach was used to determine a large set of 20 components of genetic
algorithm for traveling salesman problem, divided into decisions (selection method, elitist model, crossover method, mutation method, etc) and parameters (population size, crossover probability, mutation probability, etc). The crossover method can be chosen between PMX, CX and OX operators. The OX operator clearly out-perform PMX and CX operators. The experiment [Freisleben 1993] show that the choice of crossover method is far less significant than the choice of the mutation method or the use of the elitist model. To our knowledge none of the previous (meta)evolutionary approaches were used to determine the best combination of crossover operators for the traveling salesman problem. The pseudocode which we used for evolutionary algorithm that implements metaevolutionary approach is given in fig. 1.
In metaevolutionary approach two populations exists: a meta-level population and a base-level population (fig. 2). Both populations undergo evolutionary process. However, the base-level population undergo evolutionary process which is controlled by meta-level population. Parameters needed for evolutionary process can be encoded in the meta-level population such as: population size, crossover probability, mutation probability, crossover operators, etc. Since in our case the goal is to determine the best combination of crossover operators for traveling salesman problem, a chromosome of meta-level population determine which crossover operators, chosen from PMX, OX, CX and ERX operators, are going to be applied to base-level population. For example in the chromosome ABDD of meta-level population the following information is encoded. In the first generation the PMX operator, in the second generation the OX operator and in the last two generations the ERX operator are going to be applied. Therefore, the number of generations for base-level population define also the length of a chromosome in a meta-level population, while the length of chromosome in a base-level is determined by the number of cities which traveling salesman has to visit. The fitness of the best chromosome of base-level population in the entire run is taken to be the fitness of the chromosome in meta-level population. Other parameters of evolutionary process: population size (pop_size_ml, pop_size_bl), number of generations (G_ml, G_bl), crossover probability (pc_ml, pc_bl) and mutation probability (pm_ml,
pm_bl) are defined separately for both populations.For solving traveling salesman problem with metaevolutionary approach a tool METATSPGA is developed, where users can define parameters for evolutionary process, select a traveling salesman problem from the TSPLIB library [Reinelt 1991], and define parameters for reports. In the tool METATSPGA also graphical presentation of previously best known solution from TSPLIB and founded solution are presented.
procedure Meta_Evolutionary_Algorithm begin
t_ml ← 0
P0_bl ← initialize P_bl // base-level population initialize P_ml(t_ml) // meta-level population while (not ml_termination-condition) do begin
//evaluate P_ml(t_ml)
t_bl ← 0
P_bl(t_bl) ← P0_bl evaluate P_bl(t_bl)
while (not bl_termination-condition) do begin
t_bl ← t_bl + 1
select P_bl(t_bl) from P_bl(t_bl-1) alter P_bl(t_bl, P_ml(t_ml)) evaluate P_bl(t_bl) end
end // end evaluate P_ml(t_ml) t_ml ← t_ml + 1
select P_ml(t_ml) from P_ml(t_ml-1) alter P_ml(t_ml) end end
Fig.1. Evolutionary algorithm which implements metaevolutionary approach
rhÃÃyrry parameters for meta - level :rupÃripop_size _mlG_mlpc_mlpm_mlnumber of crossover operatorsControlmeta GArhÃÃyrryÃyhvBAAA...AABB...BBÃBr)Ã6ÃÃQHYÃ7ÃÃPYÃ8ÃÃ8YÃ9ÃÃ@SYBDD...AByrtuÃpurÃ2ÃBfiDrhyhvsvrpop_size _blG_blpc_blpm_bl Objective function meta - level = crossover methodparameters for base - levelrupÃri&RQWUROGAihrÃÃyrryÃÃyhvÃÃÃÃÃÃÃÃÃ ÃphvhyÃsÃurÃ@rÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃÃpvvrÃ)Ã6ÃÃFAEKHIJGDFBCHEJCDFBAGKIrhyhvsvrObjective function base - levelihrÃÃyrry
Fig. 2. Base-level and meta-level populations for traveling salesman problem
4. Results
The proposed metaevolutionary approach is very flexible and enable us to test different scenarios in a single framework. Different scenarios (a-d) are achieved simply by appropriate settings of parameters for meta-level population, where number of generation is 0 means just initial random generation. The following experiments were performed:
a) single run of genetic algorithm b) multiple runs of genetic algorithm
c) searching for the best combination of crossover operators by random search
d) searching for the best combination of crossover operators by evolutionary approach.
Since the metaevolutionary approach require high amount of computation time we tested very small traveling salesman problems (11 and 48 cities). Results show that applying different crossover operators in different generations are better then applying single crossover operator all the time. The explanation of this is very intuitive since different crossover operators preserve different properties, which could be very useful for search in different directions in the problem space. While the PMX operator preserves the order and positions, the OX operator preserves the relative order, and CX operator preserves the absolute positions, the ERX operator preserves the edges. From table 1 and 2 (scenarios a and b) and fig. 3 we can notice that ERX and OX operators out-perform PMX and CX operators. Similar results were obtained from other experiments [Oliver 1987, Whitley 1989, Freisleben 1993]. Surprisingly random combination of crossover operators have better performance than PMX and CX operators (table 2 scenario c). For small problems (11 cities) random combination even out-perform ERX and OX operators (table 1, scenario c). When combination of crossover operators is tuning by evolutionary process (table 1 and 2, scenario d), such combination clearly out-perform all included crossover operators (PMX, CX, OX, ERX). The best chromosome in base-level population is obtained when chromosome in meta-level have much more occurrences of ERX and OX operators than PMX and CX operators (14 occurrences of PMX, 20 occurrences of OX, 14 occurrences of CX, and 27 occurrences of ERX). This findings found by evolutionary process also confirm that ERX and OX operators are better than PMX and CX operators. However, there is still need for PMX and CX operators for searching in different directions. From table 1 (scenario a) we can notice that the best chromosome is found very early, in generations between 17 and 28. After that, the search was going in wrong directions and no better chromosome was found. This is another evidence, that we need search in other directions too. By combination of crossover operators (table 1, scenario c and d) the exact solution is found by random combination in 47th generation and in 14th generation by evolutionary combination. Further, more than 200 different test were performed, where different parameters are used: pc_bl: 0% to 100% by 10%, pm_bl:
0% to 10% by 1%, pop_size_bl: 50 do 125 by 25, G_bl:50 to 250 by 25. In table 3 the best results from different test are presented and again the best result is achieved with evolutionary combination of operators.
5. Conclusions
In this paper an experimental study on determining the best combination of crossover operators among PMX, OX, CX and ERX for traveling salesman problem is presented. The proposed approach was based on the idea that some combinations of crossover operators may outperform single operator. Rather to random search for best combination of crossover operators the metaevolutionary approach is used. Results show that applying different crossover operators in different generations are better then applying single crossover operator all the time. The explanation of this is very intuitive since different crossover operators preserve different properties, which could be very useful for search in different directions in the problem space.
References
[Bäck 1996] Bäck T., Fogel D.B., Michalewicz Z. Handbook of Evolutionary Computations. University Oxford Press, New York, 1996.
>%UHVWAlgorithm @for %UHVWthe -Asymmetric äHURYQLN-Traveling $Q$SSUR[LPDWLRQSalesman Problem. Ricerca Operativa, vol. 28, pp. 59-67, 1999. [Freisleben 1993] Freisleben B., Härtfelder M. In search of the best genetic algorithm for the traveling salesman problem. Proceedings of 9th International Conference on Control Systems and Computer Science, Bucharest, pp. 485 - 93, 1993.
[Goldberg 1985] Goldberg D.E., Lingle R. Alleles, Loci, and the TSP. Proceedings of the First International Conference on Genetic Algorithms, pp. 154 - 159, 1985. [Grefenstette 1986] Grefenstette J.J. Optimization of Control Parameters for Genetic Algorithms. IEEE Transactions on Systems, Man & Cybernetics SMC-16, No. 1, pp. 122 -128, 1986.
[Michalewicz 1996] Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Third Edition. Springer-Verlag, 1996.
[Oliver 1987] Oliver I.M., Smith D.J., Holland J.R.C. A Study of Permutation Crossover Operators on the Traveling Salesman Problem. Proceedings of the Second International Conference on Genetic Algorithms, pp. 224 - 230, 1987.
[Reinelt 1991] Reinelt G. TSPLIB – a Traveling Salesman Problem Library. European Journal of Operations Research, Vol. 52, pp. 125, 1991.
[Whitley 1989] Whitley D., Starkweather T., Fuquay D'A. Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator. Proceedings of the Third International Conference on Genetic Algorithms pp. 133 - 140, 1989.
Table 1: Fitness of the best chromosomes and their generations (11 cities, pop_size_bl=100, G_bl=50, pc_bl=60%, pm_bl=5%)
PMX OX CX ERX
combination
scenario a) G_bl fitness 25 568 23 514 28 568 17 538
scenario b)
G_bl fitness 35 477 47 466 47 488 27 469
scenario c)
G_bl fitness 47 455
scenario d)
G_bl fitness 14 455
Table 2: Fitness of the best chromosomes and their generations
(48 cities, pop_size_bl=100, G_bl=75, pc_bl=60%, pm_bl=5%)
PMX OX CX ERX
combination
scenario a) G_bl fitness 73 68597 72 68110 71 89466 74 61245
scenario b)
G_bl fitness 74 64846 72 56510 72 67182 72 55093
scenario c)
G_bl fitness 74 64330
scenario d)
G_bl fitness 69 51835
Table 3: Best results from different tests (48 cities)
PMX OX CX ERX
random combin. evol. combin.
pc_bl 60% 100% 100% 70% 100% 70%
pm_bl 5% 7% 10% 3% 3% 5%
pop_size_bl 125 125 125 125 125 125
G_bl 225 250 250 200 250 250
pop_size_ml 1 1 1 1 100 40
G_ml 0 0 0 0 0 20
fitness 60075 44265 57213 47245 55392 41026
# \"r ! upà riÃr(uÃsÃ'r&vs%$*HQHUDWLRQQHYPY8Y@SYpÃprhvqÃprhv
Fig 3: The comparison of scenarios b, c and d for 48 cities (table 2)
因篇幅问题不能全部显示，请点此查看更多更全内容