Genetic Algorithms in Swift: Solving TSP

Traveling salesman problem is a well-known problem in computing. The problem is: the salesman has to visit every city on his list, he has to visit each city only once and he has to take the shortest possible route. In this blog article we'll see how to solve this problem using genetic algorithms.Long long time ago, when I was a student, I wrote a paper on genetic algorithms. This is a really exiting topic for me and I always wanted to create something for iOS using genetic algorithms. This article was a long time coming, I hope you’ll enjoy it…

Traveling salesman problem is a well-known problem in computing. The problem is: the salesman has to visit every city on his list, he has to visit each city only once and he has to take the shortest possible route. In this blog article we’ll see how to solve this problem using genetic algorithms.

Some Theory

Before jumping in the code let’s cover some basics of how genetic algorithms work.

If you’re familiar with evolution and natural selection you know that most biological organisms reproduce, create an offspring (or children) who reproduce, and so on. Children share the properties of their parents and during the creation of the child there’s a very slight possibility that some of those properties will randomly mutate. Parents die, and the children will start the process again and create a new generation, and so on and so on…

This very, very slight possibility of mutation is the engine behind biological evolution. You would think that adding random features to an entity is crazy and dangerous, and in most cases it is, for the entity. But every now and then a very useful feature comes along, and that feature is extremely useful for the whole population. Because an entity with useful features has higher chances of reproduction and passing those features to the next generation.

If you think of it in human timeframe, you might find it difficult to believe. But if you speed the time up, it makes a lot more sense. These tiny mutations is what gave us our eyes, our advanced brains, our intelligence…

We can clearly isolate three different features of evolution:

  • selection
  • reproduction
  • mutation

Each one of those individually won’t do much. But the three of them working together create a really powerful mechanism that created every living thing on this planet from a single cell.

Let’s see how we can use what we know about evolution and natural selection and apply it to computer science.

Genetic Algorithm

We need a bunch of individuals, or parents if you will. We need a way to measure them so we can select the best parents. Once we select two parents, we need to figure out a way for them to produce an offspring. At the end of that cycle, we have to find a way of mutating that child without corrupting the data.

Our genetic algorithm will have a population of 500 individuals. When we initialize the class we’ll seed this population with random individuals and kick off the algorithm.

Individual

From the traveling salesman problem it’s easy to identify what our individual should be. It should be the actual route the salesman should take. A route is just a collection of cities with coordinates. Each route has a distance, we’ll be measuring the round trip distance. The salesman should return to the city from which he started his journey.

Selection

Selecting individuals is one of the crucial parts of the algorithm. This is called calculating the fitness. We already know that we want the shortest route, but how can we identify which individuals have the best routes. We’ll calculate the total distance of all the individuals in a generation and compare the distance of an individual with the total distance. This will give us a ranking and we’ll easily identify the best individuals. Once we have the individuals ranked, we’ll use a roulette method to select the next two parents for reproduction. The individuals with the highest fitness will have the best chances of being selected. Individuals with the lowest fitness still have chances of being selected, but those chances are slim.

Reproduction

How do you combine two routes to create a third one? It’s quite simple really. After the selection we, have our two parents. We select a random point in the array and copy all the cities in the route up until that point from the first parent to the child. Then, we simply start copying the second part of the array from the second parent. The only thing to look out for is not to add a city to the route if it’s already in the route. If we reach the end of the second parents’ route, we simply start from the beginning.

Mutation

A child has been created. We need to mutate it πŸ™‚ Mutation is actually very important in genetic algorithms because it will make sure you don’t hit the local minimum/maximum. Genetic algorithms converge to a solution, and it would be easy for them to be stuck at a local minimum. So we need mutation to get us out of this hole.

Chances for mutation are really small. In our case it’ll be 1.5% (usually they’re even smaller than that). We’ll mutate the child by selecting two random points in the route and swapping the cities. It wouldn’t make sense to randomly change the locations of the cities, or start shuffling the array. We need to keep the child in a consistent state.

Enough of the boring stuff, let’s code.

The Code

Believe it or not, we’ll need less than 150 lines of code to make this work. First off, we’ll need our city:

struct City: Equatable
{
    static func ==(lhs: City, rhs: City) -> Bool {
        return lhs.location == rhs.location
    }
    
    let location: CGPoint
    
    func distance(to: City) -> CGFloat {
        return sqrt(pow(to.location.x - self.location.x, 2) + pow(to.location.y - self.location.y, 2))
    }
}

This is a simple struct. We’ll be using a CGPoint as our location. In a real-world example you’ll probably want to use lat/lon instead. We’ll also need a function to calculate distance to another city.

Next up is the actual route:

class Route
{
    let cities: [City]
    
    var _distance: CGFloat?
    var distance: CGFloat {
        if _distance == nil {
            _distance = calculateDistance()
        }
        return _distance ?? 0.0
    }
    
    init(cities: [City]) {
        self.cities = cities
    }
    
    private func calculateDistance() -> CGFloat {
        var result: CGFloat = 0.0
        var previousCity: City?
        
        cities.forEach { (city) in
            if let previous = previousCity {
                result += previous.distance(to: city)
            }
            previousCity = city
        }
        
        guard let first = cities.first, let last = cities.last else { return result }
        
        return result + first.distance(to: last)
    }
    
    // Probability of being selected from 0 to 1
    func fitness(withTotalDistance totalDistance: CGFloat) -> CGFloat {
        return 1 - (distance/totalDistance)
    }
}

This class has an array of cities. The order of the cities in the array is the order in which the salesman travels. We also have a function that calculates the round trip distance for the entire route. At the bottom of the class we have a function that calculates the fitness. This function will take in a total distance and it will calculate a relative distance and subtract it from 1. This way we’ll give higher relative values to the routes with the shortest distance. Exactly what we need.

The Algorithm

No need to copy paste all the code here, I’ll just go over the most important bits. The actual evolution method will run continuously until explicitly stopped, and it looks like this:

    public func startEvolution() {
        evolving = true
        DispatchQueue.global().async {
            while self.evolving {
                
                let currentTotalDistance = self.population.reduce(0.0, { $0 + $1.distance })
                let sortByFitnessDESC: (Route, Route) -> Bool = { $0.fitness(withTotalDistance: currentTotalDistance) > $1.fitness(withTotalDistance: currentTotalDistance) }
                let currentGeneration = self.population.sorted(by: sortByFitnessDESC)
                
                var nextGeneration: [Route] = []
                
                for _ in 0..<self.populationSize {
                    guard
                        let parentOne = self.getParent(fromGeneration: currentGeneration, withTotalDistance: currentTotalDistance),
                        let parentTwo = self.getParent(fromGeneration: currentGeneration, withTotalDistance: currentTotalDistance)
                        else { continue }
                    
                    let child = self.produceOffspring(firstParent: parentOne, secondParent: parentTwo)
                    let finalChild = self.mutate(child: child)
                    
                    nextGeneration.append(finalChild)
                }
                self.population = nextGeneration
                
                if let bestRoute = self.population.sorted(by: sortByFitnessDESC).first {
                    self.onNewGeneration?(bestRoute, self.generation)
                }
                self.generation += 1
            }
        }
    }

The meat of the function is the for loop where we iterate over the population. We’re creating parents with a function:

    private func getParent(fromGeneration generation: [Route], withTotalDistance totalDistance: CGFloat) -> Route? {
        let fitness = CGFloat(Double(arc4random()) / Double(UINT32_MAX)) // PR: github/polac24
        
        var currentFitness: CGFloat = 0.0
        var result: Route?
        generation.forEach { (route) in
            if currentFitness <= fitness {
                currentFitness += route.fitness(withTotalDistance: totalDistance)
                result = route
            }
        }
        
        return result
    }

In this function we’re using a roulette mechanism to select a parent. Parent with the highest fitness has the highest chances of being selected.

Now we have to make an offspring:

    private func produceOffspring(firstParent: Route, secondParent: Route) -> Route {
        let slice: Int = Int(arc4random_uniform(UInt32(firstParent.cities.count)))
        var cities: [City] = Array(firstParent.cities[0..<slice])
        
        var idx = slice
        while cities.count < secondParent.cities.count {
            let city = secondParent.cities[idx]
            if cities.contains(city) == false {
                cities.append(city)
            }
            idx = (idx + 1) % secondParent.cities.count
        }
        
        return Route(cities: cities)
    }

Like mentioned earlier. We select a random index in the array, and slice the first parent up until that index. We start filling the ‘cities’ array with the cities from the second parent (starting from the slice). We have to check if the city is already in the ‘cities’ array, and when we reach the end of the array, we start from the beginning.

There should be a slight possibility of mutation. We’re mutating the offspring with this function:

    private func mutate(child: Route) -> Route {
        if self.mutationProbability >= Double(Double(arc4random()) / Double(UINT32_MAX)) {
            let firstIdx = Int(arc4random_uniform(UInt32(child.cities.count)))
            let secondIdx = Int(arc4random_uniform(UInt32(child.cities.count)))
            
            var cities = child.cities
            cities.swapAt(firstIdx, secondIdx)
            
            return Route(cities: cities)
        }
        
        return child
    }

We’re simply swapping two locations in the route, if the mutation should occur.

That’s pretty much it.

Show It To Me

Some people like to see the code, some people like to see it on the UI. I made a small app that demonstrates this algorithm. The app is simple, the UI i crap, and it’s full of bugs. But hey, it was 2 a.m. and we’re talking about algorithms here πŸ˜€ Here’s how the algorithm looks like when run in the app:

As you can see from the animation. The algorithm is pretty fast at finding the shortest path.

Conclusion

Genetic algorithms are great for solving search problems and optimizations. What gets me all excited about them is how from the initial chaos of the original population we reach a solution.

That being said, genetic algorithms won’t give you a best solution, compared to all the other solutions. Meaning, there might be a better solution, a shorter path, but the algorithm simply didn’t find it yet. Given enough time, a genetic algorithm will always reach the best solution. But we have to be reasonable, how long is ‘enough time’ and when it reaches the best solution, how will you know it’s the best. It constantly improves on the solution and experiments trying to find the best one. There’s something really cool about that.

I hope you enjoyed this little break from the usual design patterns and algorithms you can find on this blog. And, more importantly, I hope I peaked your interest in genetic algorithms and that you will create something cool with it. You can find the demo project on my GitHub account.

As always, have a nice day πŸ™‚

Dejan.

More resources

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.