Genetic Algorithms in Rust for Autonomous Agents: An Introduction
This article discusses a possible genetic algorithm implementation in Rust applied to the travelling salesman problem.
Autonomous agents that navigate the real world in real-time such as robots should have the capacity to decide what’s the best course of action to take. There are many factors to consider and many possible combinations of actions; which is the best one?
For example, suppose you have a robot and you want it to put items in a box. However, there are a lot of items and it is impossible to fit them all in that box which has dimension constraints and a weight limit. How does the robot choose which items to put in that box? Each item can be assigned a value and the robot should maximize the total value of chosen items given the constraints. This is a combinatorial optimization problem — a packing problem. Given the many variables involved, testing all possible solutions is inefficient, time-consuming, and impractical.
Say we’ve solved the problem above and now the robot has to pick up all the items but they are located at different places in the room. To save energy and time, the robot should find the shortest route to get all the items and then go to the box. This is another famous combinatorial optimization problem — the travelling salesman problem.
There are many traditional ways to tackle these kinds of problems without resorting to brute-force, like a calculus-based “hill-climbing ” technique and random search algorithms; each has its own pros and cons. One approach which has some advantages over traditional methods is to use genetic algorithms.
Genetic Algorithms Overview
Genetic algorithms are search algorithms that are inspired by processes observed in natural evolution. They are randomized but exploit historical information to intelligently search the solution space which maximize or minimize a particular function.
The idea is that we have a population of candidate solutions (individuals) and they theoretically evolve to better solutions over each iteration. Each candidate solution has properties (DNA) .The more fit individuals are more likely to produce children and these children are more likely to be better than their parents. The children’s DNA are produced using operations inspired by how actual DNAs are altered. Each successive population is more likely to be better than the previous generation.
DNA and FITNESS
To illustrate how genetic algorithms work, let’s apply it to the travelling salesman problem. Say we have a set of five cities: 0, 1, 2, 3, and 4 each on a location represented by two numbers ( Px, Py) given a range of float numbers.
First let’s make a genetic representation of the solution domain (DNA). In this case, this is the order of the cities. The solution is a permutation of cities like [1, 0, 2, 3, 4] and [4, 3, 1, 0, 2] which we can represent as an array of integers. We also have to define a fitness function which we will use to quantify and evaluate if the solution is better or worst. In this case, we want to get the shortest route, we can define our fitness function to be one divided by the sum of the squares of the distances from one city to the next.
How it Works
Now we simulate the evolution process.
First we initialize a set of individuals with DNA. We can seed the first solution space if we already know which set order of cities are more likely candidates . For simplicity, let’s just randomly select a set of city orders. We can evaluate the individual’s fitness given its DNA and our fitness function. The fittest individual in this population is best solution we’ve seen so far, let’s call it the champion.
For each iteration, we should generate a new population from the previous one. Each population has its own fittest individual, a challenger which could replace the champion . Essentially, each iteration we find the champion which is the best solution we’ve seen so far . After the series of iterations, the final champion’s DNA is the best solution we’ve seen. We can call this a run. We might have to run a simulation several times to get the best solution, if at all, because the algorithm is probabilistic in nature. Repeat this until you’re happy with the results!
The population size of each and number of iterations per run is something that we can tune.
How to generate the next population?
As mentioned earlier, the more fit individuals are more likely to produce children. We need to define a way to probabilistically select individuals that produce children based on their fitness. Let’s make it such that the probability of selecting these individuals are proportional to their relative fitness relative to the population, this is also known as weighted choice or roulette wheel selection.
Let’s take two parents and use them to generate two children until we have a population the size that we’ve indicated. We can actually use any number of parents to produce any number of children but for simplicity let’s use two parents and two children.
Also mentioned earlier, the children’s DNA are produced using operations inspired by how actual DNAs are altered based on the parent’s DNA. There are many ways to do this, for simplicity, let’s probabilistically alter using types of crossover and mutate operations. We’ll discuss these two in the next section. Let’s define two more parameters to tune which is the probability of crossover and probability of mutation. The crossover probability is the probability that we will perform the crossover operation. We don’t need to perform the crossover all the time, we can directly clone the parents sometimes. There is a probability that the parents are already a good candidate solution and that the crossover is an unnecessary expensive operation that might make the solution set worse. Similarly, mutation probability is the probability that a mutation is performed.
Crossover and Mutate
The crossover operation resembles the biological crossing over and recombination of chromosomes in cell meiosis. There are many ways to define a crossover operation. In this case, what we can do is first select two parents, select a random sequence of one parent’s DNA and copy it to the DNA of the child and get the rest the from the other parent. This is recombining portions of good individuals which will likely create even better individuals.
Mutation is a random modification. The purpose of mutation is to maintain the diversity within a population. Mutation also happens in the recombination of DNA in biological systems. If we don’t introduce mutations, we might converge to a local maximum instead of getting to the global maximum. For simplicity, my mutation function just randomly selects a city in the DNA and swap it with an adjacent city.
Putting Everything Together
A SIMULATION RUNInitialize
- Randomly initialize a population of individuals
- Determine the fittest individual so far "CHAMPION"Repeat for a number of iterations
- Generate the next population of individuals based on the previous
- Select parents
- Perform genetic operations such as crossover or clone
- to produce children and possibly mutate
- Get the fittest individual in this population "challenger"
- Replace the "champion" with the "challenger" if it is more fitThe champion's DNA is the best solution we've seen in this simulation run. You might need to make multiple runs to get a better solution.
You need to specify the some parameters for a simulation run such as:
1. Number of iterations
2. Population size
3. Crossover probability
4. Mutation probabilityYou also have to define the following given your specific problem:
1. DNA representing the solution
2. The fitness function
3. The selection function
4. Genetic operations such as crossover, clone, and mutationThis article introduced the genetic algorithm and illustrated how it can be used by applying it to the travelling salesman problem. For the whole solution and animated visualizations of the search you can check my repository! Star if you like it!
IMPORTANT NOTE: More sophisticated algorithms such as Lin-Kernighan heuristic is known to be better suited to solve travelling salesman problems!
References: Jenna Carr 2014 + Vijini Mallawaarachchi
