A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem

1. INTRODUCTION

• GA performance depends on encoding and genetic-operator choices, particularly selection, crossover, and mutation.Crossover operators have been adapted to permutation representations used in combinatorial optimization.Source: §1 · p. 1
• TSP is a well-studied combinatorial optimization problem with practical uses including vehicle routing and drilling.The objective is a minimum-total-cost Hamiltonian cycle.Source: §1 · p. 1
• The paper empirically compares crossover operators for solving the TSP.It studies the impact of different crossover operators and analyzes the experimental results.Source: §1 · p. 2

2. TRAVELING SALESMAN PROBLEM

• TSP asks for a minimum-cost Hamiltonian cycle that visits each city once and returns to its starting city.A tour is a permutation of the cities, and the search space contains n! possible tours.Source: §2 · p. 2

2.1 Deterministic algorithm

• The TSP can be formulated as an integer linear program, but the deterministic approach has exponential complexity, high memory demands, and cannot be used for large problems.The section also mentions separation-and-evaluation and cutting-plane methods.Source: §2.1 · p. 3

2.2 Approximation algorithm

• Approximation algorithms seek near-optimal solutions in reasonable, at most polynomial, time, without guaranteeing the optimum.The section identifies genetic algorithms, ant colony methods, and tabu search as examples.Source: §2.2 · p. 3

• GAs combine mating and mutation, evaluate new parameter sets for fitness, and iterate until convergence.Mating exchanges parameter values between parents, while some parameters mutate.Source: §3 · p. 3, Figure 1 · p. 3
• GAs can optimize disparate and real-valued, binary, or integer variables, process many variables, and return a list of strong solutions.The section also describes them as able to sample multiple cost-surface regions and adapt to parallel computation.Source: §3 · p. 3
• The section says GAs are good at finding global rather than local minima and can simultaneously sample different portions of a cost surface.Source: §3 · p. 3
• GAs lack viable convergence proofs and are not known for speed, although careful parameter choice can improve speed.Source: §3 · p. 3
• Genetic algorithms are modeled on natural evolution and incorporate selection, crossover, and mutation; Holland developed their basic principles.Goldberg applied these principles to an optimization problem.Source: §3 · p. 3

• A GA encodes candidate solutions as chromosomes and creates an initial population, evaluates solutions with a fitness function, and selects individuals for reproduction.Source: §3.1 · p. 4
• Crossover combines two parent chromosomes into children with probability Px, while mutation modifies selected chromosome genes with probability Pm.Source: §3.1 · p. 4
• Insertion decides which individuals remain, and a stopping test checks the optimality of the solution obtained.Source: §3.1 · p. 4
• Choices among coding, selection, genetic operators and their probabilities, insertion, and stopping tests create different GA variants.Source: §3.1 · p. 4
• The section presents path representation for the TSP and asks which settings create an efficient genetic variant for solving it.Source: §3.1 · p. 4

• Initial population conditions the algorithm’s speed and convergence.Source: §4.2 · p. 4
• One method generates the initial population randomly.Source: §4.2 · p. 4
• Another method generates one random individual and mutates it N-1 times to form the population.Source: §4.2 · p. 4
• A heuristic method selects the next city by shorter distance, then mutates the resulting route to generate N-2 additional individuals.Source: §4.2 · p. 4

• Roulette wheel selection assigns each individual a probability Pi of selection directly proportionate to its fitness.Source: §4.3 · p. 4
• Individuals with low fitness-function values may have a high chance of being selected for crossing.Source: §4.3 · p. 4

4.4 Crossover Operator

• The basic crossover method is not suitable for TSP, motivating operators adapted to permutation representations.A tour is represented as an array of integers encoding city successor and predecessor relationships.Source: §4.4 · p. 4

4.4.1 Uniform crossover operator

• Uniform crossover forms a child by alternating randomly between the two parents.Source: §4.4.1 · p. 5

4.4.2 Cycle Crossover

• CX builds offspring so each city and its position come from one of the parents.The paper attributes the operator to Oliver.Source: §4.4.2 · p. 5

4.4.3 Partially-Mapped Crossover (PMX)

• PMX copies the outer parent sequences and fills the child's middle sequence with genes from the other parent, skipping genes already placed.Source: §4.4.3 · p. 5

4.4.4 The uniform partially-mapped crossover (UPMX)

• UPMX uses PMX's technique but selects correspondence probabilistically at each iteration instead of using crossover points.The paper attributes UPMX to Cicirello and Smith.Source: §4.4.4 · p. 5

4.4.5 Non-Wrapping Ordered Crossover (NWOX)

• NWOX creates and fills holes while preserving the absolute order of genes.The paper attributes the operator to Cicirello.Source: §4.4.5 · p. 6

4.4.6 Ordered Crossover (OX)

• OX selects two crossover points; a child inherits its left and right sections from one parent, with its middle section determined separately.The paper cites Goldberg [8] and describes OX as suited to order-based problems.Source: §4.4.6 · p. 6

4.4.7 Crossover with reduced surrogate

• Reduced-surrogate crossover restricts crossover points to positions where the parents' gene values differ, producing new individuals whenever possible.Source: §4.4.7 · p. 6

• Mutation is described as maintaining genetic variety so the search can use the solution space and avoid losing genetic material.Source: §4.5 · p. 6
• The study chooses Reverse Sequence Mutation (RSM) as its mutation operator.Source: §4.5 · p. 6
• RSM randomly selects positions i and j with i<j, then reverses the gene order in the intervening sequence.Source: §4.5 · p. 6

• Elitism copies the best chromosome into the new population alongside crossover and mutation solutions, keeping population size fixed.Source: §4.6 · p. 7
• Without elitism, convergence to limiting distributions is shown only under conditions on mutation probabilities and does not guarantee the global optimum; retaining the best string is stated to ensure convergence to the global optimum.The convergence claims are attributed to Davis and Principe, with [16] also appearing in the passage.Source: §4.6 · p. 7

5. NUMERICAL RESULTS AND DISCUSSION

• The test instance is BERLIN52, comprising 52 Berlin locations, with journey distance as the sole optimization criterion and a known optimum of 7542 m.Figures 9 and 10 show the locations and optimal solution, respectively.Source: §5 · p. 7, Figure 9 · p. 7, Figure 10 · p. 7

5.1 Environment

• The environment description states that one parameter was changed at a time and the others were fixed, with 50 algorithm executions.It also reports a C++ implementation on a Core2Quad 2.4GHz PC with 2GB RAM and CentOS 5.5.Source: §5.1 · p. 7

5.2 Results and Discussion

• Operators were compared on 50 different initial populations, which were reused for each operator.Source: §5.2 · p. 7
• For crossover comparisons, the evolutionary algorithm uses the crossover algorithms as variation operators and roulette selection to choose the shortest route.The algorithm is shown in Figure 11.Source: §5.2 · pp. 7–8, Figure 11 · p. 7
• OX has not reached its evolution shelf, while NWOX is on a quasi-shelf in the crossover statistics.The statistics are shown in Figure 12.Source: §5.2 · p. 8, Figure 12 · p. 8
• NWOX has a higher standard deviation of the best final individuals across 50 initial populations than every other operator, indicating greater sensitivity to the initial population.Source: §5.2 · p. 8

6. CONCLUSION

• The paper discusses crossover operators in the TSP context, noting their role in developing robust genetic algorithms.Source: §6 · p. 8
• OX obtained the best-known solution for the TSP instance BERLIN52 among the six crossover procedures and their modifications tested.The results also showed high performance for crossover operators based on creating and filling holes.Source: §6 · p. 8
• Developing innovative crossover operators for the traveling salesman problem may be a subject of future research.Source: §6 · p. 8