Figures
Abstract
Genetic algorithms are powerful search methods inspired by Darwinian evolution. To date, they have been applied to the solution of many optimization problems because of the easy use of their properties and their robustness in finding good solutions to difficult problems. The good operation of genetic algorithms is due in part to its two main variation operators, namely, crossover and mutation operators. Typically, in the literature, we find the use of a single crossover and mutation operator. However, there are studies that have shown that using multi-operators produces synergy and that the operators are mutually complementary. Using multi-operators is not a simple task because which operators to use and how to combine them must be determined, which in itself is an optimization problem. In this paper, it is proposed that the task of exploring the different combinations of the crossover and mutation operators can be carried out by evolutionary computing. The crossover and mutation operators used are those typically used for solving the traveling salesman problem. The process of searching for good combinations was effective, yielding appropriate and synergic combinations of the crossover and mutation operators. The numerical results show that the use of the combination of operators obtained by evolutionary computing is better than the use of a single operator and the use of multi-operators combined in the standard way. The results were also better than those of the last operators reported in the literature.
Citation: Contreras-Bolton C, Parada V (2015) Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem. PLoS ONE 10(9): e0137724. https://doi.org/10.1371/journal.pone.0137724
Editor: Ben J. Mans, Onderstepoort Veterinary Institute, SOUTH AFRICA
Received: March 5, 2015; Accepted: August 21, 2015; Published: September 14, 2015
Copyright: © 2015 Contreras-Bolton, Parada. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited
Data Availability: All relevant data are within the paper.
Funding: The authors would like to thank the Complex Engineering Systems Institute: P-05-004-F, CONICYT: FBO16, ECOS/CONICYT: C13E04.
Competing interests: The authors have declared that no competing interests exist.
Introduction
The traveling salesman problem (TSP) has been studied since the early 19th century; it is a classic problem of operations research and continues to be a challenge today. It is an apparently simple problem consisting of finding a minimum cost route that goes through several cities that the salesman must visit, returning to the starting point without repeating any city. This task is not simple when trying to find the best solution because the problem belongs to the combinatorial optimization class of problems known as NP-complete [1]. Therefore, there is no algorithm that guarantees finding the optimum solution in a polynomial number of steps. A complete historical development of the TSP and other related problems can be found in the work of Reinelt [2] and Applegate et al. [3]. Moreover, the various studies on this problem are associated with applications such as truck routing, itineraries for the sequencing of DNA, and the design of microchips, among others [3]. Because it has been studied extensively in the literature, we now have various algorithms as well as various types of testing instances. Typically, the TSP is considered one of the favorite problems for testing any new algorithmic idea leading to a search process.
Genetic algorithms (GA) are powerful search methods inspired by Darwin’s theory of survival of the fittest, and they were proposed by Holland [4]. To date, GAs have been applied to the solution of many optimization problems because of the easy use of their properties and their robustness in finding good solutions to difficult problems [5]. The efficiency of GAs depends on many parameters, such as the initial population, representation of the individuals, selection strategy, and recombination operators: crossover and mutation.
Crossover and mutation are the two main variation operators in a GA, of which various types have been proposed, and their individual properties have been extensively investigated [6]. The crossover operators generate new solutions by mixing two solutions, while the mutation operators often retain the diversity of the solution in a population by a slight perturbation of the solutions, expanding the search in the solution space. Typically, a single type of operator has been used for crossover and for mutation in the GAs. However, the crossover and mutation operators can complement each other, generating a synergy due to their different styles of space coverage. Esquivel et al. [7] proposed multi-operators, finding that an operator can function very well in an early stage of the process of evolution and function poorly in a later stage, or vice versa. Other studies have followed this line of research, using multi-operators for only mutation and only crossover. In some of these studies, multi-operators were tested for both at the same time [8–11]. There are few studies of complex problems. Some of the complex problems approached with multi-operators are constrained optimization problems, such as when Elsayed et al. [12] proposed a GA with a multi-operator, obtaining better results than traditional algorithms, thus showing the advantage of using the multi-operator search process. Other more recent research also applied multi-operators with good results for routing problems [13], the flow shop scheduling problem [14], the multiobjective traveling salesman problem [15], and the optimal frequency assignment problem [16].
Not all the results based on multi-operator approaches have yielded good results. Such is the case of the work of Yoon and Moon [17], who studied multi-operators for the TSP and the bisection of graphs, without finding strong synergic effects in either problem. Two operators have synergy when they generate a better computational performance working in combination than the best performance of both operators working individually. At first, multi-operators were doubted in the work of Murata and Ishibuch [18], who examined the behavior of different variants of GAs with two types of genetic operators for the solution of flow shop scheduling problems. The authors showed that a good operator, evaluated independently, may not function well when used in combination with another operator. They also found that the combined effect of two operators could be positive or negative and that it could determine the efficiency of the algorithm. This means that the choice of the operators is important in the design of a high performance GA. This choice is often made by trial and error. Furthermore, It has been known for a long time that the choice of the operator’s adjustments has a significant impact on the performance of the GA. However, finding a good combination is a great challenge because of the large number of existing possibilities [19, 20]. The appropriate values depend on the other components of the GA, such as the population model, the problem to be solved, its representation, and the operators used.
The combinations of operators made by the various authors have had good results for different problems. However, poorer results have also been found because the combinations used thus far constitute a much reduced space of the many combinations that can be made among the different operators. In this paper, it is proposed that the complex task of exploring the different combinations of the crossover and mutation operators for solving the TSP can be carried out by an evolutionary computation algorithm. This algorithm is a simple GA encoding in each individual the probability of occurrence of 14 crossover operators and 14 mutation operators by using a permutation representation. To evaluate the fitness of each individual, a GA is built with the selected operators evaluating their performance with three training instances. As a result five new GAs are obtained which are evaluated with 14 instances. In this way, successful and synergic combinations of the crossover and mutation operators can be obtained that are comparatively superior to the operators individually or combined in the standard way. Determining that a multi-operator GA outperforms the same GA using the same operators individually would allow the re-examination of many current approaches for several optimization problems in which the GA did not produce a good performance. Perhaps this result was obtained because multi-operators were not used or because the combination of operators used was not appropriate for the problem.
The following section of this paper describes the procedures for the automatic combination of crossover and mutation operators; the third section presents and discusses the computational results of the generated combinations; and the last section presents the conclusions of the study.
Procedure for the combination of operators
This section presents the procedures for combining operators automatically, the functioning and characteristics of the evolutionary algorithm that generates the automatic combinations of the operators, and the functioning and characteristics of the GA that is evolved, which solves the TSP.
Evolutionary process
To carry out the evolution of the GAs that solve the TSP, an evolutionary algorithm (EA) is designed that operates in a genotype-phenotype mode. A binary representation of two chromosomes is used as a genotype. The first one represents the occurrence probability of a set of crossover operators, and the second one represents the occurrence probability of a set of mutation operators, while the phenotype is a simple GA that solves the TSP (GA-TSP) in which the probabilities of each genetic operator (crossover and mutation) are set. The evolution of a fixed size population is carried out with the binary tournament selection operators, two-point crossover, and two mutation operators, similar to the bitwise operator [21]. The following section explains the characteristics of the EA in detail.
Each individual in the new population of the EA is composed of two binary chromosomes, which are obtained from the present population. Every time an individual is generated, the evaluation function measures its quality, which is given by the performance of the individual in a set of test instances, with the set occurrence probabilities of the genetic operators. The architecture of the evolutionary algorithm is shown in Fig 1, where the stages involved in the generation of population P(t+1) from population P(t) are described.
Evolutionary algorithm, EA
The evolutionary algorithm operates in a standard manner and typically uses the classic operators. The representation used by the EA considers two binary chromosomes. Each gene represents the occurrence probability of 14 genetic crossover operators for the first chromosome and 14 mutation operators for the second chromosome.
A gene is composed of seven alleles, so each gene can take values between 0 and 127. The sum of the occurrence probabilities of all the operators must add up to 1. To satisfy this restriction, all the values of the operators are added, and then, the values of each operator are divided by the sum. Fig 2 shows a crossover chromosome of length 28 that represents four operators. To obtain the probability of each of the four, the sum and the division are made later.
To evaluate the performance of each individual, i.e., the quality of a combination of occurrence probabilities of crossover and mutation operators in a GA-TSP, a type of evaluation function employed in genetic programming is used, which, to compare the performance of the trees/programs, uses the average error of a group of training instances [22–24]. The proposed evaluation function minimizes the average relative error of the GA to solve a set of TSP instances. Because the GA is a stochastic algorithm, Ne executions are needed to obtain its performance. The evaluation function of the EA is shown in Eq 1, where tk is the kth GA-TSP to be evaluated, Nf corresponds to the number of instances, is the optimum cost of the route in instance i, and xij is the cost of the route in instance i for execution j.
(1)
The operators used in the EA are as follows:
- Selection: Binary tournament is used [21].
- Crossover: Two-point crossover is used for both chromosomes [21].
- Mutation: Two types of mutation based on bitwise operators are used [21]. The first one only changes one bit of the chromosome randomly, while the second one chooses a complete gene and sets all its alleles to 0. This operator is aimed at deactivating completely crossover or mutation operators of the GA-TSP.
- Replacement: Generational replacement is used. However, in each generation, 10% of the worst individuals generated are replaced by the best current parents, i.e., elitism.
Because each GA-TSP evaluates a set of instances and executes the evaluations in parallel multiple times, this is the most costly process in terms of the computing time of the evolutionary algorithm. For this reason, parallelization is used in the evaluation of each GA-TSP. For every individual tk, f(tk) is evaluated in parallel on a different processor with the set of instances. The evaluations are distributed to the processors from a waiting queue.
GA-TSP algorithm
The GA-TSP, which is executed repeatedly within the evolutionary algorithm to determine the best combination of occurrence probabilities of the crossover and mutation operators, is a simple GA, with the particularity that it has 14 crossover and mutation operators. The occurrence probabilities are the input delivered by the evolutionary algorithm. Algorithm 1 shows the GA-TSP that was used.
Algorithm 1: GA-TSP
Require: : occurrence probabilities of each operator i
Ensure: best individual
1: Generate initial population
2: Evaluate population
3: while termination condition do
4: Selection of individuals
5: Crossover ()
6: Mutation ()
7: Evaluate population
8: Elitism
9: Generate new population
10: end while
From an initial population, the GA-TSP evolves via the selection, crossover, mutation and replacement operators. The type of representation used, the definition of the evaluation function, and the operators are shown below.
From an initial population, the GA-TSP evolves via the selection, crossover, mutation and replacement operators. The type of representation used, the definition of the evaluation function, and the operators are shown below.
- Representation: The permutation representation is used.
- Evaluation function: It measures the cost of the route and is calculated using the sum of the Euclidean distances between each pair of cities with coordinates (xi,yi). The calculation of the cost of an instance i is shown in Eq 2, where Nc is the number of cities of the instance.
(2)
- Initial population: It is generated using the nearest neighbor algorithm [25].
- Selection: A tournament of size 5 is used [21].
- Crossover: Fourteen crossover operators are used, with each having an occurrence probability
, i = {1,2,3,…,14}. The operators used are PMX [26], OX1 [27], OX2 [28], MOX [29], POS [30], CX [31], DPX [32], AP [6], MPX [33], HX [34], IO [35], VR [36, 37], ER [38, 39], and GSTX [40, 41].
- Mutation: Fourteen mutation operators are used, with each having an occurrence probability
, i = {1,2,3,…,14}. The operators used are EM [42], SIM [4, 43], SM [30], DM [44], IVM [45, 46], ISM [44, 47], DBM [48–50], GSM [51], HM [52], NJ [53], DBM2, which is an extension of DBM with a local search, 2opt [54], SHMO [55] and simplified 3opt [48] because it is implemented with two cycles, and to select the third edges, instead of attempting all of them, only ten edges are attempted randomly.
- Replacement: Generational replacement is used, with 10% elitism.
A crossover operator has the probability of crossing over two individuals or
of mutating the individual. For example, if we assume that pc is 0.9 and
is the occurrence probability of the PMX operator, with a value of 0.3, then the probability that an individual is crossed with the PMX operator is 0.27.
To obtain better results, evolution was divided into two stages in a number of equal generations. This decision is supported by the evidence that in some periods of the evolution, it is more important to occupy certain values of the genetic operators [19, 20]. These two stages are employed with the idea of using different operators in each stage or the same operators but with different probabilities.
Results and Discussion
This section presents the configuration of the experiment, the results of the evolution process and the characteristics of the best combinations found. Additionally, the best GA-TSP is compared with several GAs with different combinations of operators as well as with the last operators reported in the literature.
Configuration of the experiment
In the experiment, the evolutionary algorithm is executed five times. In each evolution, the best combination of occurrence probabilities is obtained, generating five probability combinations.
The evolution of the EA was executed on equipment with an Intel Xeon CPU E7–4830 server with 32 CPUs at 2.13 GHz and 64 GB of RAM, using the Debian GNU/Linux 7.4 Wheezy operating system. The 32 CPUs were used in parallel for the evolution, while the validation of the sets of occurrence probabilities obtained was executed on equipment with an Intel Core i7–3537Uwith 4 CPUs at 2.00 GHz and 4 GB of RAM, using the Debian GNU/Linux testing Jessie operating system and the CPUs in a sequential manner.
To train and validate the occurrence probabilities of the crossover and mutation operators, the TSPLIB problem benchmarks [56] were used. Fourteen type EUC_2D instances were chosen to validate the GA-TSP because they are the most commonly used instances in the literature to validate algorithms; they are berlin52, kroA100, pr144, ch150, kroB150, pr152, rat195, d198, kroA200, ts225, pr226, pr299, lin318 and pcb442. To carry out the training, three of the smallest instances of the 14 were chosen. This selection is based on computing time because the more instances are chosen, the longer the evolution takes. The same reason is used for choosing the smallest ones.
The computational performance of the evolutionary algorithms is directly related to the parameters used [19, 20]. Following the literature recommendations and preliminary experiments, we used the following strategy to set the parameters of EA and GA-TSP: all parameters except the mutation probability and the number of generations were defined directly from the literature [57–60]. The two exceptions were determined by preliminary runs. The parameters set for the EA are 50 individuals for the population size, with 200 generations, 0.9 crossover probability and 0.2 mutation probability, while for the GA-TSP, 50 individuals were set for the population size, with 100 generations, 0.9 crossover probability and 0.2 mutation probability.
Evolution of parameters
The execution of the evolutionary process generates increasingly better individuals, until the final stages are reached in which there is a convergence toward populations that have individuals with similar quality. Fig 3 shows the performance of the five evolutionary processes. The ordinates show the fitness values, and the abscissas indicate the generation number. Every curve corresponds to the evolutionary process in which the best combinations of occurrence probabilities were found. Each curve is named GA-TSP followed by a number: GA-TSP1 is the result obtained at the first execution, GA-TSP2 is that obtained at the second execution, etc. Table 1 shows, for each of the five GA-TSPs, the average and standard deviation of the fitness, the evolution and the generation time in which the best individual was found. The best fitness is obtained with GA-TSP5, although it is not the best combination of occurrence probabilities. This is explained by the algorithm’s stochastic nature, where the same individual can give different results, but which are close to one another. On average, each evolution lasted 79081.70 seconds, while the total time to perform all the experiments was 395408.50 seconds. The best individual was generated, on average, in generation 185.40. It is seen that in generation 150, the populations of individuals start converging (Fig 3). Note that the computational time to evolve is high because to determine a robust set of operators it is necessary to test the performance of GA-TSP with the three training instances. This stage is consuming most of the computational time.
The five combinations obtained are competitive in solution quality as well as in computing time. The average performance with the 14 instances of the TSPLIB is seen in Table 2, which gives the maximum value, the average value and the best value for the average error, the computing time, the generation in which the best cost was found, and the number of optimums found for the 14 instances. The error obtained in all the experiments is given with respect to the optimum solution for each instance, so it corresponds to the relative error. The best average error obtained among the 20 executions for the 14 instances corresponds to GA-TSP4. The best errors were found among the 20 executions for each of the 14 instances. GA-TSP4 obtains 0.27% and GA-TSP5 0.33%. The combination of probabilities that requires the least computing time was obtained with GA-TSP2, which solved the 14 instances in 6.42 seconds on average. It was found that, on average, the best combination appears before the first 50 generations. In fact, the fastest GA to find the best costs is GA-TSP3, and this occurs, on average, in generation 31.51. As to the number of optimums found, GA-TSP4 found 8 hits and GA-TSP5 6 hits. Therefore, the best combination is that of GA-TSP4, which has the best error, average error and maximum error in addition to obtaining 8 optimums in the 14 instances as well as a competitive computing time.
During the evolution of the GA multi-operators, overtraining is detected in GA-TSP1, GA-TSP4 and GA-TSP5 with the set of evolution instances. This behavior can be observed from the results presented in Table 3, which contains the results of 100 executions of the algorithms with the original three instances of evolution (group A) and with the remaining 11 instances (group B). The three algorithms found optimal solutions only with the instances of group A. Furthermore, not only the average error increased with the instances of Group B, but also, the average range found in all individuals of the population increased.
The GAs have better performance when specific operators are defined for each stage of the crossover and the mutation. In the first stage, the operators work for a rapid convergence, and in the second stage, they work to escape from the local optimums. This is shown in Tables 4 and 5. The first column gives the name of the operator, and the following columns present the combination of operators used by each GA-TSP. These columns correspond to the percentage of each operator during the first and second stages. The best crossover combinations in the first stage contain DPX, GSTX and HX, and it is seen that the DPX and GSTX operators complement each other and make the GA-TSP converge rapidly to find good results. Better results are found when the HX operator participates, as in the case of GA-TSP4 and GA-TSP5. In the second stage, the crossover is diverse. Each GA-TSP has its own combination, but the operators that are always selected are OX1, IO and OX2 in different proportions. This diversity of operators can be attributed to the fact that the evolution changes the search from the local optimum regions to a global optimum region. Additionally, the best GA-TSP confirms that the most widely used operator is DPX, while for the mutation in the first stage, the most widely used operator is SHMO in a high proportion and 3opt to a lower extent. The greater the percentage of SHMO, the better the results, such as in GA-TSP2, GA-TSP4 and GA-TSP5. Meanwhile, for the second stage, the combinations of the operators that act are more diverse, with a tendency to use 3opt in combination with other operators. There is no clear combination of operators, presumably in an attempt to escape from the local optimums. The following section shows in detail the evolution of the best combination of operators (GA-TSP4).
Few differences are detected between the algorithms obtained. In fact the average error in the 14 evaluation instances is in the interval (0.94, 1.13)%, while the computational time is in (7.98, 13.78) seconds. In terms of its characteristics, the only algorithm that presents significant differences with others is the GA-TSP1. This algorithm uses PMX in 15.29% while in other algorithms it is practically not considered. Also, it uses DPX in a proportion lower than the other algorithms. However, no such difference is detected by analyzing the mutation operator.
Characteristics of the best combination
The evolution of the crossover and mutation operators has a diverse performance during the first generations at each stage. Toward the end of the evolution, some operators appear that are specialized in each stage. This process is seen in the follow-up of the evolution of the best individual of each of the 200 generations and is shown in Fig 4 for the crossover operators and in Fig 5 for the mutation operators. At the beginning of the evolutionary process, the combination of operators is diverse, but as the generations go by, both types of operator tend to become stabilized, similar to what happens with operators DPX and SHMO. However, there are also operators that have generation intervals in which they participate in large percentages but, at some instant, have less relevance, as in the case of HX in the first stage.
The successful operator combinations arise from the way in which the operators are complemented, generating a synergic effect. This analysis can be deduced more clearly when we look at the participation of each operator in each stage. Fig 6 shows a circular graph with the percentage participation of the crossover operators in both stages, similarly for mutation in Fig 7. The percentages chosen by evolution are not due to coincidence or chance, and this is ratified by the other combinations, which have similar operators that are found in similar proportions, but small details mark the differences that make GA-TSP4 the best. Furthermore, it is seen that in the first stage, intelligent operators are preferred, which rapidly cause the populations to converge to similar individuals, finding the best costs. This is shown by the only 38.2 average generations needed to find the best solution, finding individuals even in early generations such as 11. The main intelligent operator is DPX, which participates 58.33% and is characterized by its descendants having the same distance to each of their parents, i.e., the parent and the offspring do not differ in many ways in their routes between one another, and this distance is equal to the distance between the parents. However, this operator by itself does not cause the GA-TSP4 to obtain such good results; it needs the help of operators such as GSTX and HX, and others to a lesser extent.
The combination of operators does not present the same evolution in both stages. In the first stage, the most relevant operators are SHMO, DPX and 3opt. The choice of SHMO could be because the crossovers are primarily performed by the operator DPX, which generates similar individuals, as SHMO is a local search operator that generates small but systematic changes. In contrast, the operator 3opt, an exhaustive local search operator, participates in a lower percentage. Meanwhile, in the second step, no group more relevant than the others is detected. It is observed that the crossover and mutation operators are complementary, enabling individuals to distance themselves from each other and, in this way, avoiding being trapped in the local optimum. It appears that this is because the operators used by the GA-TSP4 are so numerous and varied.
Comparison with the literature
To show that the task of finding good combinations of crossover and mutation operators using an evolutionary algorithm is effective, a number of comparisons with GAs that use mono-operators and multi-operators is made. GA-TSP4 is also compared with the same probability ratios, but without using the two stages to validate the decision of dividing the search into two stages. A final comparison is made with the more advanced operators reported in the literature. The comparison of each of the GAs presented consists of 20 executions with each of the 14 TSPLIB instances, in addition to a statistical analysis to conclude if there are statistically significant differences between the algorithms. This analysis is based on the methodology recommended by [61] and [62], and the tests of Friedman, Holm and Wilcoxon are applied.
The proper combination of operators and the use of two stages are more effective than using only one crossover and one mutation operator. We used the operators that have given the best performance in various studies from the literature, such as those of [6], who suggest ER, OX1, OX2 and POS for the crossover and DM, IVM, ISM for the mutation. The SIM operator, which had the second best performance after the mutation operator proposed by [63], was also added. The 2opt operator, which showed the best performance in a recent study [64], was also considered. The combinations of the 4 crossover operators with the 5 mutation operators generated 20 GAs with a single operator. The results are shown in Table 6, where the best error, the average error with the 14 instances, and the average computing time to solve all the instances are reported. It is seen that for most of the mono-operators, although they solve each instance in less than one second on average, the results of the errors are very high, more than 100% for the best error and average error. The exception occurs when the 2opt operator is used, where the combination with the lowest errors is ER-2opt with an average error of 40.17% and a best error of 33.62%, far from the 0.94% average error and 0.27% best error of GA-TSP4.
GA-TSP4 has statistically significant differences with respect to all the mono-operators. The results of the Friedman, Holm and Wilcoxon tests are given in Table 7. Friedman’s statistical distribution according to χ2 with 20 degrees of freedom is 220.28, and the value of p is 0. Holm’s test rejects 16 of the 20 null hypotheses, i.e., GA-TSP4 has statistically significant differences with those 16 algorithms. No differences are found with the operators that have the 2opt mutation. Holm’s test does not give the differences with these algorithms due to the great difference between the results of the worst and best algorithms. Wilcoxon’s test detects these differences and rejects all the null hypotheses.
GA-TSP4 is superior with respect to the mono-operator algorithms because the evolution combines the operators to obtain a trade-off between the quality of the solution and computing time. Because the classic operators cannot compete against GA-TSP4, this algorithm was compared with the operators that evolution determined to be successful, which are DPX, GSTX and HX in the crossover and SHMO and 3opt in the mutation. The six combinations between these operators are shown in Table 8, with their average error and best error and the computing time corresponding to the 14 instances. The results confirm that the crossover operator DPX is the best among the three crossover operators. However, when it is used by itself, the performance is far from that of the combination of GA-TSP4. None of the combinations of the mono-operators in Table 8 exceeds GA-TSP4 in average error or in the best error in any of the 14 instances. They are only better in terms of computing time. There is a combination, DPX-3opt, which is more competitive, obtaining three better average errors than GA-TSP4 for the ch150, kroA200 and pr299 instances, and it also obtains a best error in the pr299 instance. However, the computing time required by this combination of mono-operators is almost three times longer than that of GA-TSP4; in the pcb442 instance, the required time is almost four times longer. The HX-3opt combination exceeds GA-TSP4 in the average error in instance pr152; however, in the overall mean with the 14 instances, both the overall mean average error and the overall mean best error are twice the error of GA-TSP4.
GA-TSP4 has statistically significant differences with respect to all the most successful mono-operators of evolution. Table 9 shows Friedman’s test, where the results of the statistical distribution according to χ2 with 6 degrees of freedom is 63.16 and the value of p is 0. Additionally, Holm’s test rejects five of the six null hypotheses, i.e., GA-TSP4 has statistically significant differences with those six algorithms except for the DPX-3opt combination, with which no differences are found. However, Wilcoxon’s test does find differences between GA-TSP4 and DPX-3opt.
The operators participating with low proportions in the different combinations of operators explored also cooperate to improve the overall performance. This effect is observed from the construction of two algorithms considering the best combinations of operators detected during the evolution, specifically, two crossover and two mutation operators with to the following combinations: DPX-GSTX-SHMO-3opt, in proportions of 50% for each crossover and mutation operator, and DPX-GSTX-HX-SHMO-3opt, with 50% for the mutation operator and 50%, 40% and 10% for the crossover operators. The results of both algorithms are presented in Table 10, and from this table, it is concluded that both algorithms have a lower performance than GA-TSP4. The overall mean best error of DPX-GSTX-HX-SHMO-3opt is 0.32%, while that of DPX-GSTX-SHMO-3opt is 0.43%; both values are higher than the value corresponding to GA-TSP4. Furthermore, the same behavior is detected for the overall mean average errors and computing time.
The performance of the two-step algorithm is more effective than the algorithm with a single stage. In Table 10, the performance of the algorithm A1S-GA-TSP4 running on a single stage is shown. This algorithm is implemented with the same operator proportions as in GA-TSP4, and it is observed that both the overall mean average error and the overall mean best error of A1S-GA-TSP4 are greater than those of GA-TSP4. However, the yield obtained by GA-TSP4 requires slightly more computing time. This confirms that the evolution rate discovers operator proportions suitable for solving the optimization problem.
GA-TSP4 has statistically significant differences with the three most successful multi-operator evolution algorithms. Table 11 shows the results of Friedman’s statistical distribution according to χ2 with three degrees of freedom, 9.13, and the value of p is 0.03, which is less than α. GA-TSP4 also obtains the best ranking, and Holm’s test, as well as Wilcoxon’s test, rejects the three null hypotheses.
The combination of operators in GA-TSP4 reflects a better computational performance than operators recently reported in the literature. For this comparison, the following operators were considered: GSTM [63], MIO [65], MA_IO [66], and IGP_IO [67]. The comparisons are shown in Table 12. The results of GA-TSP4 with regard to GSTM and MIO are better in the overall mean best error as well as in the number of hits. The GA with the GSTM mutation operator is better than GA-TSP4 in the overall mean average error for instance pr144. The MIO operator is more competitive; it is better than GA-TSP4 for 10 instances in the average error. The same result occurs with the average for all the instances, with 0.82% for MIO, while GA-TSP4 has a 0.94% overall mean average error. In terms of the amount of optimum hits, GA-TSP4 has 8 optimums, compared with only 2 found by MIO.
Despite the close results of the comparison of GA-TSP4 with MA_IO and IGP_IO, it can be said that the computational performance of GA-TSP4 is better than those of both algorithms by a narrow margin, obtaining a better overall mean best error in the 12 instances of the TSPLIB. This idea is reinforced by the number of hits found, where GA-TSP4 is better than MA_IO and IGP_IO. In Table 12, where the comparison with MA_IO is made without considering the LK, GA-TSP4 obtains a better average error in seven instances and has a better overall mean best error for all the 14 instances, 0.27% versus 0.35% for MA_IO. Additionally, for the number of optimums obtained, GA-TSP4 obtains 8 hits and MA_IO obtains 5 hits. MA_IO has not only a better average error than GA-TSP4 in seven instances but also a better overall mean average error. The computing time of MA_IO is very low, with an average of less than 1 second to solve the 14 instances, much better than GA-TSP4. In contrast, GA-TSP4 is better than IGP_IO in three instances of the average error and in five instances of the best error. Moreover, in the 14 instances, it has an overall mean average error of 0.27%, versus 0.35% for IGP_IO. The number of optimums found by GA-TSP4 is better, with 8 optimum hits versus 6 optimum hits for IGP_IO. IGP_IO has both smaller average errors than GA-TSP4 in 9 instances and smaller overall mean average errors for all 14 instances. The computing time required to solve the 14 instances is 3.61 seconds per instance on average for IGP_IO, versus an average of 10.57 seconds for GA-TSP4.
GA-TSP4 only has statistically significant differences with GSTM, and Wilcoxon’s test finds statistically significant differences between IGP_IO and GA-TSP4. The results of Friedman’s statistical test, presented in Table 13 and distributed according to χ2 with 4 degrees of freedom, give 27.56 and p = 0.000015, showing that the algorithms are not similar. However, the ordering is GSTM (4.86), MIO (2.57), MA_IO (2.54), IGP_IO (1.96) and GA-TSP4 (3.07). Table 14 shows the results of Holm’s test for each pair of algorithms. There are only four null hypotheses rejected, with GSTM always participating with the other algorithms, i.e., the remaining algorithms have statistically significant differences with GSTM. In the other pairs of algorithms, no statistically significant differences are found. However, Wilcoxon’s test shows that there are statistically significant differences in favor of IGP_IO compared with GA-TSP4. In the other pairs of algorithms, no statistically significant differences are found.
Conclusions
An evolutionary algorithm has been presented that combines automatically the variation operators of a genetic algorithm to solve the traveling salesman problem. The numerical results show that searching the crossover and mutation operator combinations is an effective option, despite the computing times required to find the adequate proportions. The way in which the proportions are obtained can be easily adapted to other combinatorial optimization problems.
The evolutionary process finds synergy between the different operators used, such as in the case of the DPX, GSTX and HX crossover operators with the SHMO and 3opt mutation operators. Additionally, the idea of dividing the evolution into two stages was also validated, finding that the first stage is useful for a rapid optimization and the second stage for avoiding being trapped in local optimums.
The combinations of the probabilities of the crossover and mutation operators are better than the classical operators by themselves, than the operators most widely used by the evolution individually, than the multi-operators with traditional proportions, and than GA-TSP4 when only one stage is used. The statistical analysis confirms this superiority, finding that there are statistically significant differences, with a significance level of 0.05. With respect to the comparison with the recent operators reported in the literature, GA-TSP4 is slightly better in terms of the overall mean best error and the number of hits. However, at the level of the statistical analysis, a statistically significance difference is found only with respect to the GSTM algorithm, not with the other algorithms.
Acknowledgments
The authors would like to thank the Complex Engineering Systems Institute: P-05-004- F, CONICYT: FBO16, ECOS/CONICYT: C13E04.
Author Contributions
Conceived and designed the experiments: CC VP. Performed the experiments: CC VP. Analyzed the data: CC VP. Contributed reagents/materials/analysis tools: CC VP. Wrote the paper: CC VP.
References
- 1.
Karp R. Reducibility among Combinatorial Problems. In: Miller R, Thatcher J, Bohlinger J, editors. Complexity of Computer Computations. The IBM Research Symposia Series. Springer US; 1972. p. 85–103.
- 2.
Reinelt G. The Traveling Salesman: Computational Solutions for TSP Applications. Berlin, Heidelberg: Springer-Verlag; 1994.
- 3.
Applegate DL, Bixby RE, Chvatal V, Cook WJ. The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton, NJ, USA: Princeton University Press; 2007.
- 4.
Holland JH. Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. The University of Michigan Press; 1975.
- 5.
Goldberg DE. Genetic Algorithms in Search, Optimization and Machine Learning. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.; 1989.
- 6. Larrañaga P, Kuijpers CMH, Murga RH, Inza I, Dizdarevic S. Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review. 1999;13(2):129–170.
- 7.
Esquivel SC, Leiva A, Gallard RH. Multiple Crossover Per Couple in genetic algorithms. In: Evolutionary Computation, 1997., IEEE International Conference on; 1997. p. 103–106.
- 8.
Hong I, Kahng AB, Moon BR. Exploiting synergies of multiple crossovers: initial studies. In: Evolutionary Computation, 1995., IEEE International Conference on. vol. 1; 1995. p. 245.
- 9. Hong TP, Wang HS. Automatically Adjusting Crossover Ratios of Multiple Crossover Operators. Journal of Information Science and Engineering. 1998;14(2):369–390.
- 10. Hong TP, Wang HS, Chen WC. Simultaneously applying multiple mutation operators in genetic algorithms. Journal of heuristics. 2000;4(6):439–455.
- 11. Hong TP, Wang HS, Lin WY, Lee WY. Evolution of Appropriate Crossover and Mutation Operators in a Genetic Process. Applied Intelligence. 2002;16(1):7–17.
- 12. Elsayed SM, Sarker RA, Essam DL. Multi-operator based evolutionary algorithms for solving constrained optimization problems. Computers & Operations Research. 2011;38(12):1877–1896.
- 13.
Osaba E, Onieva E, Carballedo R, Diaz F, Perallos A. An Adaptive Multi-Crossover Population Algorithm for Solving Routing Problems. In: Terrazas G, Otero FEB, Masegosa AD, editors. Nature Inspired Cooperative Strategies for Optimization (NICSO 2013). vol. 512 of Studies in Computational Intelligence. Springer International Publishing; 2014. p. 113–124.
- 14. Zhang L, Wang L, Zheng DZ. An adaptive genetic algorithm with multiple operators for flowshop scheduling. The International Journal of Advanced Manufacturing Technology. 2006 Feb;27(5–6):580–587.
- 15. Elaoud S, Teghem J, Loukil T. Multiple crossover genetic algorithm for the multiobjective traveling salesman problem. Electronic Notes in Discrete Mathematics. 2010;36:939–946.
- 16.
Acan A, Altincay H, Tekol Y, Unveren A. A genetic algorithm with multiple crossover operators for optimal frequency assignment problem. In: Evolutionary Computation, 2003. CEC’03. The 2003 Congress on. vol. 1; 2003. p. 256–263.
- 17. Yoon HS, Moon BR. An empirical study on the synergy of multiple crossover operators. Evolutionary Computation, IEEE Transactions on. 2002;6(2):212–223.
- 18.
Murata T, Ishibuchi H. Positive and negative combination effects of crossover and mutation operators in sequencing problems. In: Evolutionary Computation, 1996., Proceedings of IEEE International Conference on; 1996. p. 170–175.
- 19.
Eiben AE, Michalewicz Z, Schoenauer M, Smith JE. Parameter Control in Evolutionary Algorithms. In: Lobo F, Lima C, Michalewicz Z, editors. Parameter Setting in Evolutionary Algorithms. vol. 54 of Studies in Computational Intelligence. Springer Berlin Heidelberg; 2007. p. 19–46.
- 20. Eiben AE, Hinterding R, Michalewicz Z. Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation. 1999 Jul;3(2):124–141.
- 21.
Eiben AE, Smith JE. Introduction to evolutionary computing. Springer Berlin Heidelberg; 2003.
- 22.
Koza JR. Genetic programming: on the programming of computers by means of natural selection. Cambridge, MA: MIT Press; 1992.
- 23.
Poli R, Langdon WB, Mcphee NF. A Field Guide to Genetic Programming. Lulu Enterprises, UK Ltd; 2008.
- 24. Contreras-Bolton C, Gatica G, Parada V. Automatically Generated Algorithms for the Vertex Coloring Problem. PLoS ONE. 2013 03;8(3):e58551. pmid:23516506
- 25. Flood MM. The Traveling-Salesman Problem. Operations Research. 1956;4(1):61–75.
- 26.
Goldberg DE, Lingle R. Alleles, loci, and the traveling salesman problem. In: Grefenstette JJ, editor. Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Lawrence Erlbaum Associates, Publishers; 1985.
- 27.
Davis L. Applying Adaptive Algorithms to Epistatic Domains. In: Proceedings of the 9th International Joint Conference on Artificial Intelligence—Volume 1. IJCAI’85. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.; 1985. p. 162–164.
- 28.
Syswerda G. Uniform Crossover in Genetic Algorithms. In: Proceedings of the 3rd International Conference on Genetic Algorithms. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.; 1989. p. 2–9.
- 29.
Ray SS, Bandyopadhyay S, Pal SK. New operators of genetic algorithms for traveling salesman problem. In: Pattern Recognition, 2004. ICPR 2004. Proceedings of the 17th International Conference on. vol. 2; 2004. p. 497–500 Vol.2.
- 30.
Syswerda G. Schedule optimization using genetic algorithms. Handbook of Genetic Algorithms. 1991;p. 332–349.
- 31.
Oliver IM, Smith DJ, Holland JRC. A study of permutation crossover operators on the traveling salesman problem. In: Grefenstette J, editor. Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application. Hillsdale, NJ, USA: L. Erlbaum Associates Inc.; 1987. p. 224–230.
- 32.
Reisleben B, Merz P, Freisleben B. A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. In: Evolutionary Computation, 1996., Proceedings of IEEE International Conference on; 1996. p. 616–621.
- 33. Mühlenbein H, Gorges-Schleuter M, Krämer O. Evolution algorithms in combinatorial optimization. Parallel Computing. 1988;7(1):65–85.
- 34.
Grefenstette JJ. Incorporating problem specific knowledge into genetic algorithms. In: Davis L, editor. Genetic Algorithms and Simulated Annealing. Los Altos, CA: Morgan Kaufmann Publishers Inc.; 1987. p. 42–60.
- 35.
Tao G, Michalewicz Z. Inver-over operator for the TSP. In: Eiben A, Bäck T, Schoenauer M, Schwefel HP, editors. Parallel Problem Solving from Nature—PPSN V. vol. 1498 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 1998. p. 803–812.
- 36.
Mühlenbein H. Parallel Genetic Algorithms Population Genetics and Combinatorial Optimization. In: Proceedings of the 3rd International Conference on Genetic Algorithms. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.; 1989. p. 416–421.
- 37.
Mühlenbein H. Parallel genetic algorithms, population genetics and combinatorial optimization. In: Becker JD, Eisele I, Mündemann FW, editors. Parallelism, Learning, Evolution. vol. 565 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 1991. p. 398–406.
- 38.
Whitley LD, Starkweather T, Fuquay D. Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator. In: Proceedings of the 3rd International Conference on Genetic Algorithms. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.; 1989. p. 133–140.
- 39.
Whitley D, Starkweather T, Shaner D. The Traveling Salesman and Sequence Scheduling: Quality Solutions Using Genetic Edge Recombination. In Handbook of Genetic Algorithms. 1991;p. 350–372.
- 40.
Sengoku H, Yoshihara I. A fast TSP solver using GA on JAVA. In: Third International Symposium on Artificial Life, and Robotics (AROB III’98); 1998. p. 283–288.
- 41. Nguyen HD, Yoshihara I, Yamamori K, Yasunaga M. Greedy Genetic Algorithms for Symmetric and Asymmetric TSPs. IPSJ Transactions on Mathematical Modeling and Its Applications. 2002;43(10):165–175.
- 42. Banzhaf W. The “molecular” traveling salesman. Biological Cybernetics. 1990;64(1):7–14.
- 43.
Grefenstette JJ, Gopal R, Rosmaita BJ, Gucht DV. Genetic Algorithms for the Traveling Salesman Problem. In: Proceedings of the 1st International Conference on Genetic Algorithms. Hillsdale, NJ, USA: L. Erlbaum Associates Inc.; 1985. p. 160–168.
- 44.
Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. London, UK, UK: Springer-Verlag; 1994.
- 45.
Fogel DB. A Parallel Processing Approach to a Multiple Traveling Salesman Problem Using Evolutionary Programming. In: Canter L, editor. Proceedings on the Fourth Annual Parallel Processing Symposium. Fullterton, CA; 1990. p. 318–326.
- 46. Fogel DB. Applying evolutionary programming to selected traveling salesman problems. Cybernetics and Systems. 1993;24(1):27–36.
- 47. Fogel DB. An evolutionary approach to the traveling salesman problem. Biological Cybernetics. 1988;60(2):139–144.
- 48. Lin S. Computer Solutions of the Traveling Salesman Problem. Bell System Technical Journal. 1965;44(10):2245–2269.
- 49. Martin O, Otto SW, Felten EW. Large-Step Markov Chains for the Traveling Salesman Problem. Complex Systems. 1991;5:299–326.
- 50. Martin O, Otto SW, Felten EW. Large-step markov chains for the TSP incorporating local search heuristics. Operations Research Letters. 1992;11(4):219–224.
- 51.
Louis SJ, Tang R. Interactive Genetic Algorithms for the Traveling Salesman Problem. In: Banzhaf W, Daida J, Eiben AE, Garzon MH, Honavar V, Jakiela M, et al., editors. Proceedings of the Genetic and Evolutionary Computation Conference. vol. 1. Orlando, Florida, USA: Morgan Kaufmann Publishers Inc.; 1999. p. 385–392.
- 52.
Gen M, Cheng R. Genetic Algorithms and Engineering Design. John Wiley & Sons, Inc.; 1997.
- 53.
Tsai HK, Yang JM, Kao CY. Solving traveling salesman problems by combining global and local search mechanisms. In: Evolutionary Computation, 2002. CEC’02. Proceedings of the 2002 Congress on. vol. 2; 2002. p. 1290–1295.
- 54. Morton G, Land AH. A contribution to the ‘travelling-salesman’ problem. Journal of the Royal Statistical Society: Series B. 1955;17(2):185–194.
- 55.
Wang CX, Cui DW, Wang ZR, Chen D. A Novel Ant Colony System Based on Minimum 1-Tree and Hybrid Mutation for TSP. In: Wang L, Chen K, Ong Y, editors. Advances in Natural Computation. vol. 3611 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 2005. p. 1269–1278.
- 56. Reinelt G. TSPLIB–A Traveling Salesman Problem Library. ORSA Journal on Computing. 1991;3(4):376–384.
- 57.
De Jong KA. An analysis of the behavior of a class of genetic adaptive systems. University of Michigan. Ann Arbor, MI, USA; 1975.
- 58. Grefenstette JJ. Optimization of control parameters for genetic algorithms. Man and Cybernetics, IEEE Transactions on. 1986;00(February):122–128.
- 59.
Schaffer JD, Morishima A. An Adaptive Crossover Distribution Mechanism for Genetic Algorithms. In: Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application. Hillsdale, NJ, USA: L. Erlbaum Associates Inc.; 1987. p. 36–40.
- 60.
Eiben A, Karafotias G, Haasdijk E. Self-Adaptive Mutation in On-line, On-board Evolutionary Robotics. In: Self-Adaptive and Self-Organizing Systems Workshop (SASOW), 2010 Fourth IEEE International Conference on; 2010. p. 147–152.
- 61. García S, Molina D, Lozano M, Herrera F. A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 Special Session on Real Parameter Optimization. Journal of Heuristics. 2009;15(6):617–644.
- 62. Derrac J, García S, Molina D, Herrera F. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation. 2011;1(1):3–18.
- 63. Albayrak M, Allahverdi N. Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms. Expert Systems with Applications. 2011;38(3):1313–1320.
- 64.
Osaba E, Carballedo R, Diaz F, Perallos A. Analysis of the suitability of using blind crossover operators in genetic algorithms for solving routing problems. In: Applied Computational Intelligence and Informatics (SACI), 2013 IEEE 8th International Symposium on; 2013. p. 17–22.
- 65.
Wang Yt, Sun J, Li J, Gao K. A Modified Inver-over Operator for the Traveling Salesman Problem. In: Huang DS, Gan Y, Gupta P, Gromiha MM, editors. Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence. vol. 6839 of Lecture Notes in Computer Science. Springer Berlin Heidelberg; 2012. p. 17–23.
- 66. Wang Yt, Li Jq, Gao Kz, Pan Qk. Memetic Algorithm based on Improved Inver–over operator and Lin–Kernighan local search for the Euclidean traveling salesman problem. Computers & Mathematics with Applications. 2011;62(7):2743–2754.
- 67.
Tasgetiren MF, Buyukdagli O, Kızılay D, Karabulut K. A Populated Iterated Greedy Algorithm with Inver-Over Operator for Traveling Salesman Problem. In: Panigrahi B, Suganthan P, Das S, Dash S, editors. Swarm, Evolutionary, and Memetic Computing. vol. 8297 of Lecture Notes in Computer Science. Springer International Publishing; 2013. p. 1–12.