# 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

of candidate solutions (**population**

) and they theoretically **individuals***evolve* to better solutions over each iteration. Each candidate solution has properties (

) .The more **DNA**

individuals are more likely to produce **fit****children**** **and these `children`

are more likely to be better than their** **

. The children’s **parents**`DNA `

are produced using operations inspired by how actual `DNA`

s 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****: **

and **0, 1, 2, 3,**

each on a location represented by two numbers ( **4**

, **Px**

) given a range of float numbers.**Py**

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

and **[1, 0, 2, 3, 4]**

which we can represent as an array of integers. We also have to define a **[4, 3, 1, 0, 2]**

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**` 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

**per**

*number of iterations*`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 `DNA`

s 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 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!

References: Jenna Carr 2014 + Vijini Mallawaarachchi