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 many 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
0, 1, 2, 3, and
4 each on a location represented by two numbers (
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
[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
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
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
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
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
Also mentioned earlier, the
DNA are produced using operations inspired by how actual
DNAs are altered based on the
DNA. There are many ways to do this, for simplicity, let’s probabilistically alter using types of
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
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
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
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 RUN
- 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 fit
The 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 probability
You 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 mutation
This 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!