Source-linked AI summary
Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem
Otman Abdoun, Jaafar Abouchabaka, Chakir Tajani
TL;DR
The paper asks how to configure genetic algorithms effectively for the TSP, where the authors note that deterministic methods face time and memory demands on large problems. It compares mutation operators in a genetic-algorithm setup and reports that RSM performs best, followed closely by PSM.
Problem
Method
The authors compare mutation operators using OX crossover, roulette selection, and 50 reused initial populations for each operator.
Source: §5.2 · p. 15Results
RSM is the most efficient mutation operator in the reported OX comparison, followed closely by PSM.
Source: §5.2 · p. 15Takeaways & Limitations
For the tested TSP, RSM and PSM yield the best solutions, while other operators may be effective on problems with different solution spaces.
Source: §6 · p. 16Adjacency representation does not support classical crossover, so a repair algorithm might be necessary.
Source: §4.1 · p. 7
Abstract
from arXiv · showhide
The genetic algorithm includes some parameters that should be adjusted, so as to get reliable results. Choosing a representation of the problem addressed, an initial population, a method of selection, a crossover operator, mutation operator, the probabilities of crossover and mutation, and the insertion method creates a variant of genetic algorithms. Our work is part of the answer to this perspective to find a solution for this combinatorial problem. What are the best parameters to select for a genetic algorithm that creates a variety efficient to solve the Travelling Salesman Problem (TSP)? In this paper, we present a comparative analysis of different mutation operators, surrounded by a dilated discussion that justifying the relevance of genetic operators chosen to solving the TSP problem.
1 INTRODUCTION
Genetic algorithms’ performance depends on problem encoding and the choice of selection, crossover, and mutation operators. This paper empirically examines these operators for the TSP.
1 INTRODUCTION
- Genetic-algorithm performance depends on encoding and on the choice of selection, crossover, and mutation operators.The introduction notes that operators have been developed for permutation representations used in combinatorial optimization, including the TSP.Source: §1 · p. 1
- The paper empirically studies how selection, crossover, and multiple mutation operators affect solving the NP-complete TSP.It analyzes experimental results to investigate which genetic-algorithm settings can address this combinatorial problem.Source: §1 · p. 2
- The TSP is NP-complete, and the paper contrasts genetic algorithms’ potentially good, not necessarily optimal solutions with exact methods’ computing-time or memory demands.The authors motivate studying genetic algorithms as an approach to this problem.Source: §1 · p. 2
2 TRAVELING SALESMAN PROBLEM
The TSP seeks a minimum-cost tour that visits each city once and returns to the start; its permutation search space grows factorially. The section contrasts deterministic and approximation approaches to this problem.
2 TRAVELING SALESMAN PROBLEM
- The TSP search space contains n! city permutations, and the optimal tour is the permutation with minimum cost.A tour visits every city exactly once and returns to the starting city; its total travel cost is minimized.Source: §2 · p. 2
- The TSP is NP-hard, with a stated complexity of O(n!) in the number of cities.Figure 1 is described as showing the combinatorial explosion of the TSP.Source: §2 · p. 3
2.1 Deterministic algorithm
- Deterministic algorithms have exponential-order complexity, high memory demands, and high computation time, making them unusable for large problems.The section also mentions separation-and-evaluation and cutting-plane methods among deterministic algorithms.Source: §2.1 · p. 4
2.2 Approximation algorithm
- Approximation algorithms, including genetic algorithms, Ant Colony, and Tabu Search, seek solutions close to the optimum in reasonable time but do not guarantee the best solution.The passage describes this reasonable time as at most polynomial time.Source: §2.2 · p. 4
3 GENETIC ALGORITHM
Genetic algorithms evolve a population of encoded solutions using selection and genetic operators. The paper describes their components and frames its study around finding effective settings for the TSP.
3 GENETIC ALGORITHM
- A genetic algorithm evolves a population using operators inspired by biological evolution, including selection and reproduction.The passage traces foundational work to Holland and Goldberg.Source: §3 · p. 5
- Genetic algorithms evaluate an objective function without requiring properties such as continuity or differentiability, and process several population members in parallel.The section also identifies probabilistic transition rules for crossover and mutation as an advantage over deterministic transitions.Source: §3 · p. 5
- Crossover combines two parent chromosomes to produce offspring, while mutation modifies selected chromosome genes with probability Pm.The passage says mutation avoids a uniform population unable to evolve; insertion determines which individuals remain.Source: §3 · pp. 5–6
- A genetic algorithm’s configuration combines coding, initial population, fitness evaluation, selection, crossover and mutation probabilities, insertion, and stopping test.Different choices for these steps create different variants; the paper asks which settings yield an efficient variant for the TSP.Source: §3 · pp. 5–6
4 APPLIED GENETIC ALGORITHMS TO THE TRAVELING SALESMAN PROBLEM
The section assembles a TSP genetic algorithm from choices of representation, initialization, selection, crossover, mutation, and insertion. It compares several mutation designs while specifying the other operators used in the algorithm.
4.1 Problem representation methods
- The adjacency representation encodes a tour as a city list, but it does not support classical crossover and may require repair.The ordinal and path representations are also described; the path representation uses integers for each city's successor and predecessor.Source: §4.1 · p. 7
4.2 Generation of the initial population
- The initial population can be random, generated by repeatedly mutating one random individual, or seeded from a heuristic route and expanded by mutation.Roulette-wheel selection assigns selection probabilities in proportion to fitness.Source: §4.2 · pp. 7–8
4.3 Crossover Operator
- The study chooses Ordered Crossover (OX), applying crossover to selected parents according to crossover probability Px.The authors describe OX as suited to order-based problems and cite it as a strong operator for TSP.Source: §4.3 · p. 9
4.4 Mutation Operators
- Mutation is presented as a way to maintain population diversity and explore the search space, complementing crossover's exploitation of current solutions.The authors also note that hill-climbing mutation can accelerate search but may reduce diversity and encourage convergence toward local optima.Source: §4.3 · p. 9, §4.4 · pp. 10–11
- The mutation operators vary the gene rearrangement: Twors swaps two genes, centre inverse reverses genes within each of two sections, and RSM reverses a randomly bounded sequence.The section also describes a three-gene rotation, a three-position permutation, and Partial Shuffle Mutation, which changes part of the gene order.Source: §4.4 · pp. 11–13
4.5 Insertion Method
- The insertion method copies the best chromosome from the old population and supplements it with crossover and mutation offspring while keeping population size fixed.Source: §4.5 · p. 13
5. NUMERICAL RESULTS AND DISCUSSION
The numerical study tests mutation operators on the BERLIN52 instance and reports RSM as most efficient, followed closely by PSM. The comparison uses OX crossover and roulette selection.
5. NUMERICAL RESULTS AND DISCUSSION
- The BERLIN52 test instance covers 52 Berlin locations, uses total journey distance as its criterion, and has a known optimum of 7542 m.Figures 3 and 4 show the locations and optimal solution, respectively.Source: §5 · pp. 13–14
5.1 Environment
- The operators and their modalities are grouped in Table 10, while the study changes one parameter at a time and runs the algorithm 50 times.The passage identifies the table's scope but does not provide its parameter values.Source: §5.1 · p. 15, Table 10 · p. 15
5.2 Results and Discussion
- Mutation operators are compared individually on 50 reused initial populations, with OX crossover and roulette selection favoring the shortest route.The evolutionary algorithm applies one mutation operator after OX crossover.Source: §5.2 · p. 15
- RSM is reported as the most efficient mutation operator, followed closely by PSM, when combined with OX crossover.The authors identify these as the two operators causing the least disturbance by moving or overturning a segment.Source: §5.2 · pp. 15–16
6. CONCLUSION
For the TSP studied, RSM and PSM yield the best solutions. The authors associate the advantage with sequence-moving mutation and note that operator effectiveness may vary with the problem's solution space.
6. CONCLUSION
- RSM and PSM produce the best solutions for the TSP instance presented.The computational study concludes that moving a sequence performs better than mixing a sequence.Source: §6 · p. 16
- Other mutation operators may be effective on other problems because their solution spaces differ.The authors frame operator effectiveness as dependent on the problem's solution space.Source: §6 · p. 16
- The authors attribute the moving-sequence advantage to passing above-average individual characteristics to descendants during crossover and mutation.Source: §6 · p. 16