Random swap mutation

As explained in Advanced Algorithms and Data Structures

Random swap mutation modifies a tour by swapping vertices selected from arbitrary pairs rather than only adjacent pairs.

Random swap mutation modifies a TSP tour by exchanging vertices chosen from arbitrary pairs rather than restricting changes to adjacent vertices. section 18.2.4

Used as a genetic-algorithm mutation operator, it can continue improving populations where crossover alone plateaus. Experiments compare operator chances, population sizes, and mutation-only evolution by tour cost. section 18.2.4

Figure 18.16 How TSP population evolves when only mutations versus only crossover are enabled. Crossover-only evolution plateaus soon enough, while the mutation operator swapping random pairs is the most successful. On the x axis, there is the number of generations, while on the y axis is the cost of the tour.

Compare mutation-only and crossover-only evolution across generations; random-pair swapping is reported as the most successful operator in the displayed experiment. section 18.2.4

How Advanced Algorithms and Data Structures covers it

How deep it goes

Compares mutation with crossover through population experiments and parameter tuning, without detailing the swap implementation.

Examples

Uses 50-vertex random-weight complete graphs, mutation-only runs, and operator-chance tables reporting average tour costs.

What you can do after

Evaluate mutation and crossover settings by comparing population evolution and resulting tour costs.

How it connects

Connects genetic algorithms, crossover, simulated annealing, and the traveling salesman problem.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.