Example metaheuristic – genetic algorithms

Examples include the traveling salesman problem, where a tour of the shortest path connecting n cities has to be found. With a O(n!) runtime complexity, only 20 cities prove to be computationally very expensive, but it can be solved well enough for a very large n by starting off with a random order of cities (tour), and then repeatedly recombining or randomly changing (mutating) several of these tours only to select the best ones and restarting the process with these.

Using the rsgenetic crate (https://crates.io/crates/rsgenetic), implementing the solution becomes a matter of implementing the TspTour trait, which requires a fitness() function to be supplied so that a solution can be evaluated, the crossover() function to recombine two parents into a new offspring tour, and the mutate() function to apply random changes to a tour:

impl Phenotype<TourFitness> for TspTour {
    ///
    /// The Euclidean distance of an entire tour.
    ...