Recently I've been learning Rust and experimenting with compiling it to WebAssembly. In this series of three posts I'm going to relate my journey of building a Genetic Algorithm to solve the travelling salesman problem in Rust, and then the work to compile it into WebAssembly in order to run the algorithm in the browser. I'm still quite new to Rust, so any feedback is welcome in the comments or on the repos provided.
All code for this article can be found here.
Photo by Adrien Converse on Unsplash
A Genetic Algorithm is an optimisation algorithm inspired by the process of natural selection. It uses a population of possible solutions across the search space; the fittest individuals in the population survive, and the processes of breeding and mutation mean that better solutions evolve over successive generations. For more in depth explanation of Genetic Algorithm see this article.
The application that I've chosen for my use of the Genetic Algorithm is the travelling salesman problem, which can be summarised as - Given a list of cities what is the shortest path that visits all cities? The brute force approach of generating all possibilities and evaluating each quickly becomes impractical, as the number of permutations is the factorial of the number of cities. For examples with:
- 5 cities: 5! = 120 possible solutions
- 10 cities: 10! = 3 628 800 possible solutions
- 20 cities: 20! = Approximately 2 quintillion ( ~2.43 x 10^18 )
An optimisation algorithm, such as a Genetic Algorithm, can be used to search for the optimal solution, but unlike with a brute force, or an alternate exact algorithm, there is no guarantee of getting the optimal solution.
The first step is to decide how to structure the solution to our problem. A solution for this problem is an ordered list of nodes to visit. The Path struct stores the ordered list of nodes travelled, as well as the fitness of the solution which will be calculated when the individual is created. The methods that are implemented for Path allow individuals to breed and mutate, and for the fitness of a solution to be calculated.
pub struct Path {
fitness: f64,
order: Vec<usize>
}
The fitness of a solution is calculated using the order list of nodes and the city list which stores the coordinates of each city. The cost of the path is calculated as the sum of the cartesian distance between the cities in the list. The aim of the algorithm is to maximise the fitness, in this case the inverse of the cost.
pub struct City {
x: f64,
y: f64,
}
impl Path {
pub fn calculate_fitness(path: &Vec<usize>, city_list: &Vec<City>) -> f64 {
let path_length = city_list.len();
let mut cost = 0.0;
for i in 0..path_length - 1 {
let a = &city_list[path[i]];
let b = &city_list[path[i + 1]];
cost = cost + ((a.x - b.x).powf(2.0) + (a.y - b.y).powf(2.0)).sqrt();
}
1.0 / cost
}
}
An individual will breed with another member of the population, and create an offspring. A uniform probability distribution from the rand crate is used to select a crossover point, the nodes from the mother are selected from the start of the list up to the crossover point, with the remainder selected from the father.
impl Path {
pub fn breed(&self, other: &Path, city_list: &Vec<City>) -> Path {
let order = Path::crossover_order(&self.order, &other.order);
let fitness = Path::calculate_fitness(&order, city_list);
Path { fitness, order }
}
fn crossover_order(mother: &Vec<usize>, father: &Vec<usize>) -> Vec<usize> {
let mut rng = thread_rng();
let crossover_point = Uniform::new(0, mother.len()).sample(&mut rng);
let mother_dna = &mother[0..crossover_point];
let mut father_dna: Vec<usize> = father.iter().filter_map(|d| {
if !mother_dna.contains(d) {
return Some(*d)
}
None
}).collect();
let mut child = Vec::new();
child.extend_from_slice(mother_dna);
child.append(&mut father_dna);
child
}
}
Some of the population of each generation will undergo mutation, which involves randomly selecting two nodes in the path and swapping them. After mutating, the Path's fitness is recalculated.
pub fn mutate(&mut self, city_list: &Vec<City>) {
let mut rng = thread_rng();
let point_one = Uniform::new(0, self.order.len()).sample(&mut rng);
let point_two = Uniform::new(0, self.order.len()).sample(&mut rng);
self.order.swap(point_one, point_two);
self.fitness = Path::calculate_fitness(&self.order, &city_list);
}
The Simulation struct is used to orchestrate the creation of successive generations and selection of the best solution. It stores the population along with parameters for the Genetic Algorithm including:
- the maximum number of iterations desired,
- the crossover rate, the fraction of the population to use for breeding,
- the mutation rate, the chance each individual will mutate each iteration,
- the survival rate, the fraction of the breeding population that will continue into the next generation.
pub struct Simulation {
population: Vec<Path>,
city_list: Vec<City>,
max_iterations: usize,
crossover_rate: f64,
mutation_rate: f64,
survival_rate: f64,
}
The Simulation has a run method which creates the next generation and finds the new fittest individual for each iteration. Generating the next generation involves:
- Selecting the breeding population from the best individuals,
- Generating offspring,
- Selecting the surviving parents from the breeding population,
- Selecting a few weak individuals to help genetic diversity,
- Mutating individuals in the population.
pub fn run(&mut self) -> () {
let mut fittest = self.find_fittest();
println!("starting iterations");
for _ in 0..self.max_iterations {
self.generate_next_generation();
let challenger = self.find_fittest();
if challenger.fitness > fittest.fitness {
fittest = challenger;
}
}
println!("{}", fittest);
}
The complete code can be found here.
In this article I have outlined an approach for a Genetic Algorithm for the travelling salesman in Rust. In the next article in this series I'll take the foundations laid here and build it into a web application using WebAssembly.
Top comments (1)
Hey. Great post!
I am looking for a Rust pal to learn the language and to create anything like simple games or simple devops tools. Take a look to this example: github.com/Mec-iS/loopscape and show up if you are interested.
Cheers!