Algorithm · Optimization · Springer 2020

Mutation Triggering Method for
Genetic Algorithm on TSP

A published Springer research paper introducing a Mutation Triggering Method (MTM) that combines three mutation operators — Swap, Insertion, and 2-opt — and selects between them based on generation progression. Random mutations provide speed and diversity in early generations; knowledge-based 2-opt is triggered in the final phase for high-quality convergence. Tested on nine TSPLIB benchmark instances.

Genetic Algorithm Traveling Salesman Problem 2-opt Mutation Swap & Insertion Mutation TSPLIB Python Springer · Industry 4.0

Language

Python

Dataset

TSPLIB — 9 instances

Mutation Operators

Swap · Insertion · 2-opt

Published

Springer · Embracing Industry 4.0 · pp. 159–170

Institution

Daffodil International University, Bangladesh

Links

GitHub Repo ↗ Springer Link ↗

01About

The Traveling Salesman Problem (TSP) is one of the most studied NP-hard combinatorial optimization problems: given a set of cities, find the shortest possible tour that visits each city exactly once and returns to the origin. With n cities the search space has (n−1)! possibilities — brute force is infeasible even for modest sizes.

Genetic Algorithms (GA) are a natural metaheuristic fit for TSP, but mutation operators present a critical design challenge. A high mutation probability causes divergence and large computation time; a low mutation probability causes premature convergence to local optima. Prior work applied each operator in isolation or at fixed probabilities, leaving untapped the complementary strengths of different mutation types.

This paper proposes the Mutation Triggering Method (MTM): a strategy that combines Swap, Insertion, and 2-opt mutations and selects between them based on the progression of the generation. The core idea is that different phases of the search benefit from different mutation types. Early generations need the speed and diversity of random mutations; late generations need the optimality of knowledge-based heuristic mutation.

MTM is benchmarked against Traditional GA (T-GA) with each operator in isolation and against RCDM-GA (random crossover, dynamic mutation) across nine TSPLIB instances. MTM found the best travel cost on 6 out of 9 instances, while completing in a fraction of T-GA (2-opt)'s computation time.

02Algorithm

Algorithm Flowchart

The proposed algorithm follows the standard GA structure except for the mutation phase, which is replaced by the MTM block (dotted region). MTM computes an adaptive probability Pm, evaluates the selector equation, then routes to 2-opt, Swap, or Insertion accordingly.

Fig. 1 — MTM-GA Flowchart · Dotted region = area of contribution Crossover: Order Crossover (OX) · Selection: Tournament Selection

03Mutation Operators

The key insight driving MTM is that mutation operators have a speed-quality tradeoff. Random-based mutations (Swap and Insertion) are fast but produce low-quality solutions. Knowledge-based mutation (2-opt) is computationally expensive but reliably removes crossing paths and drives toward optimality. MTM captures the benefit of all three by scheduling them across the generation timeline.

Phase 1 — First 80%

Swap Mutation

coin toss → 50% prob

Two randomly selected genes (cities) in the chromosome are swapped. Applied during the first 80% of maximum generations via a 50/50 coin toss against Insertion mutation. Fast and lightweight — provides rapid exploration of the search space and diverse initial feasible solutions.

Random-based · Fast · Early Phase

Phase 1 — First 80%

Insertion Mutation

coin toss → 50% prob

A randomly selected gene is removed from its position and re-inserted at a different random position in the chromosome. Applied alongside Swap mutation in the first 80% of generations. Also random and fast — together with Swap it ensures the population doesn't converge before 2-opt is applied.

Random-based · Fast · Early Phase

Phase 2 — Last 20%

2-opt Mutation

selector = maxGen − (factor × maxGen)

Two edges in the tour are removed and reconnected to eliminate crossing paths. Triggered when the current generation exceeds the selector threshold (e.g., the last 20% of generations). Computationally expensive but highly effective at removing sub-optimal tour segments — applied only when the population has already reached near-feasible solutions worth refining.

★ Knowledge-based · Heuristic · Late Phase

04MTM Algorithm

Algorithm 1 shows the complete MTM logic. The mutation probability Pm decreases with generation progression via a square-root decay function, ensuring the algorithm converges rather than diverges. The selector equation determines the generation threshold at which 2-opt takes over from Swap/Insertion. A fair coin toss between Swap and Insertion ensures equal diversity pressure from both random operators during Phase 1.

Algorithm 1 — MTM

1: k ← range [0, 1] 2: factor ← range [0, 1] 3: find current_gen, max_gen 4: Pm ← k / √(current_gen) 5: r1 ← random(0,1) 6: r2 ← random(0,1) 7: if r1 < Pm then 8: selector ← max_gen − (factor × max_gen) 9: if current_gen > selector then 10: Apply 2-opt mutation ← last 20% 11: else if r2 < 0.5 then 12: Apply Swap mutation ← first 80% 13: else 14: Apply Insertion mutation ← first 80% 15: end if 16: end if

Parameter Definitions

k — Constant Factor

Chosen from range [0, 1]. Scales the mutation probability to keep Pm within a probabilistic range across all generations.

Pm — Adaptive Mutation Probability

Decreases as generation number increases. Ensures convergence: high early diversity, lower later mutation pressure.

Pm = k / √(current generation)

factor — Phase Boundary

Controls when 2-opt takes over. A factor of 0.2 means 2-opt fires in the last 20% of generations; Swap and Insertion fill the first 80%.

selector = max_gen − (factor × max_gen)

r1, r2 — Random Numbers

r1 controls whether any mutation fires (vs. Pm threshold). r2 is the fair coin toss that splits Phase 1 evenly between Swap and Insertion.

05Key Results

Overall Performance Verdict

Travel Cost (Solution Quality)

MTM-GA wins 6 of 9 instances

MTM-GA found the best travel cost on eil51, bier127, kroa100, kroa200, pr226, and st70. T-GA (2-opt) edged it on a280, lin318, and rat195 — but at dramatically higher computation cost. T-GA (Swap), T-GA (Insertion), RCDM-GA (Swap), and RCDM-GA (Insertion) all converged to local optima on most instances.

Computation Time

MTM-GA: fast vs. 2-opt, optimal vs. random

T-GA (2-opt) is the most accurate baseline but is prohibitively slow — e.g., 2,453s for lin318 vs MTM-GA's 663s. MTM-GA is slower than pure Swap/Insertion approaches but achieves far superior solution quality, making it the best overall tradeoff between time and travel cost.

Table 1 — Optimal Travel Cost by Algorithm · All 9 TSPLIB Instances

Instance	Known Optimal	T-GA Swap	T-GA Insert	T-GA 2-opt	RCDM Swap	RCDM Insert	MTM-GA
eil51	426	754	871	433	551	621	432 ★
a280	2,579	20,753	21,476	2,727 ★	151,518	27,779	2,756
bier127	118,282	365,293	374,119	123,294	469,925	411,091	119,416 ★
kroa100	21,282	82,631	79,085	21,846	149,170	69,010	21,666 ★
kroa200	29,368	199,256	190,549	30,971	234,087	242,155	30,697 ★
lin318	42,029	384,807	388,311	43,702 ★	1,479,572	698,061	44,563
pr226	80,369	1,025,700	976,004	81,132	1,228,103	1,089,287	80,728 ★
st70	675	1,886	1,680	681	1,133	31,093	678 ★
rat195	2,323	13,061	13,321	2,419 ★	19,665	87,280	2,450

Table 2 — Computation Time (seconds) · All 9 TSPLIB Instances

Instance	T-GA Swap	T-GA Insert	T-GA 2-opt	RCDM Swap	RCDM Insert	MTM-GA
eil51	2.30	2.48	13.23	4.09	5.94	5.30
a280	40.11	42.06	1,313.95	49.09	64.69	354.79
bier127	10.67	10.63	157.77	13.68	19.65	50.54
kroa100	6.38	6.85	93.92	9.58	13.29	27.16
kroa200	21.35	22.92	657.78	27.28	29.63	185.74
lin318	51.07	52.46	2,453.97	53.13	81.28	663.22
pr226	26.22	27.02	992.72	33.77	43.85	229.39
st70	4.06	3.88	31.67	6.39	9.56	11.55
rat195	21.44	21.46	570.57	25.43	36.15	155.37

06Contributions

01 Mutation Triggering Method design — Designed the MTM selector function that divides the generation timeline into two phases and routes mutation to the appropriate operator: Swap/Insertion for early diversity, 2-opt for late-stage quality improvement.
02 Adaptive mutation probability — Implemented the generation-dependent Pm formula (k / √current_gen) so that mutation pressure decreases smoothly over time, ensuring the algorithm converges rather than diverges as it approaches the final generations.
03 Three-operator benchmarking — Implemented and compared T-GA with each of the three mutation operators in isolation, RCDM-GA with Swap and Insertion, and MTM-GA across all nine TSPLIB instances, measuring both travel cost and computation time as evaluation criteria.
04 Convergence analysis — Ran all algorithms for 1,000 generations on the rat195 instance and analysed convergence curves to show that MTM-GA avoids the stagnation of pure random mutations and the computational expense of pure 2-opt, reaching near-optimal solutions efficiently.
05 Springer publication — Prepared and published in Embracing Industry 4.0 (Springer, Singapore, 2020, pp. 159–170), with formal algorithm pseudocode, full experimental tables, and convergence graphs across nine standard TSPLIB benchmark instances.

Language	Python
Problem	Traveling Salesman Problem (TSP) — symmetric, Euclidean
Method	Mutation Triggering Method (MTM) — Swap + Insertion + 2-opt
Crossover	Order Crossover (OX)
Selection	Tournament Selection
Pm Formula	k / √(current generation number)
Selector Eq.	max_gen − (factor × max_gen)
Baselines	T-GA (Swap / Insertion / 2-opt) · RCDM-GA (Swap / Insertion)
Benchmark	TSPLIB — eil51, a280, bier127, kroa100, kroa200, lin318, pr226, st70, rat195
Published	Springer · Embracing Industry 4.0 · pp. 159–170 · Singapore · 2020

Read the full paper & source code

Published in Springer Embracing Industry 4.0, 2020, pp. 159–170.

GitHub Repo ↗ Springer Link ↗ All Projects

Mutation Triggering Method for Genetic Algorithm on TSP

Read the full paper & source code

Mutation Triggering Method for
Genetic Algorithm on TSP