liveBook · Manning

Transition operator

As explained in Advanced Algorithms and Data Structures

A transition operator is a rule that generates a new candidate solution from the current solution.

A transition operator generates a candidate solution from the current solution. In simulated annealing for the traveling-salesperson problem, it changes a tour while the temperature schedule determines how the search accepts candidates. section 17.2.4

An ensemble transition step

Choose a random number, apply an adjacent swap with probability 0.1, a random swap with probability 0.7, and a random permutation otherwise. Tune these probabilities and the cooling rate against measured solution costs.

How Advanced Algorithms and Data Structures covers it

How deep it goes
Defines three tour mutations, gives probabilistic pseudocode, and compares costs while deferring formal operator analysis.
Examples
Uses adjacent swaps, random swaps, random permutations, probabilistic mixtures, and measured tour costs.
What it assumes
Assumes a tour representation, a cost function, simulated annealing, and basic random selection.
What you can do after
Apply transition operators in simulated annealing and tune their mixture using recorded mean or median solution costs.
How it connects
Connects transition operators to simulated annealing, the traveling-salesperson problem, cooling schedules, and ensemble methods.
Cover of Advanced Algorithms and Data Structures
liveBookmanning.com
Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Related concepts

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.