Simulated Annealing for TSP

SimulatedAnnealing.swift

/// 1- Generate a random solution

func randomSolution(tspProblem: [[Int]]) -> [Int] {
    var cities = Array(1...tspProblem.count)
    var randomSoultion:[Int] = []

    randomSoultion.append(1)
    cities.removeAll(where: { $0 == 1})
    for _ in 1 ..< tsp.count  {
        let randomCity = cities.shuffled().last!
        randomSoultion.append(randomCity)
        cities.removeAll(where: { $0 == randomCity })
    }
    randomSoultion.append(1)
    return randomSoultion
}



/// 2-  Route Length for a solution
func routeLength(for solution: [Int], in tsp: [[Int]]) -> Int {
    var totalRouteLength = 0
    for  cityIndex in 0 ... tsp.count - 1  {
        let distanceFrom = solution[cityIndex]
        let distanceTo = solution[cityIndex + 1]

        let length = tsp[distanceFrom - 1][distanceTo - 1]
        //print("Should get distance from city \(distanceFrom) to city \(distanceTo) is: \(length)")
        totalRouteLength += length

    }

    return totalRouteLength
}

/// Get Neighbours of a given solution, without changing first element, and last element
/// - Parameter solution: an array of numbers
/// - Returns: array of array of numbers, where each array is a neighbor
func getNeighbours(of solution: [Int]) -> [[Int]] {
    var neighbours: [[Int]] = []
    for i in 1 ... solution.count - 2 {
        for j in 1 ... solution.count - 2 {
            var neighbour = solution
            neighbour[i] = solution[j]
            neighbour[j] = solution[i]
            neighbours.append(neighbour)
            //print(neighbour)
        }
    }
//    print(neighbours)
    return neighbours
}

/// Implemntion for Simulating Annealing problem
/// - Parameters:
///   - tsp: the distance matrix for cities
func SimulatedAnnealing(tsp: [[Int]], coolingFunction: (Int) -> Float) {
    // 1- Generate first solution x₀
    var currentSolution = randomSolution(tspProblem: tsp)

    // 2- get the current routeLength of solution, f(x₀)
    var currentRouteLength = routeLength(for: currentSolution, in: tsp)

 
    var randomSolution:[Int]

    var randomSolutionLength: Int


    // 5- the implention of algroithm
    for currentIteration in 0 ... 100 {

        randomSolution = getNeighbours(of: currentSolution).randomElement()!



        randomSolutionLength = routeLength(for: randomSolution, in: tsp)

        if randomSolutionLength <= currentRouteLength {
            currentRouteLength = randomSolutionLength
            currentSolution = randomSolution
        } else {
            let randomNumber = Float.random(in: 0 ... 1)

            let expValue = Float(currentRouteLength - randomSolutionLength) / coolingFunction(currentIteration)

            if randomNumber < exp(expValue) {
                currentRouteLength = randomSolutionLength
                currentSolution = randomSolution
            }

        }

        print("best distance is for \(currentSolution) which is \(currentRouteLength) for index \(currentIteration)")

    }

}


var tsp = [
    [0,4,10,19,13,15,12,5],
    [4,0,11,15,14,16,16,9],
    [10,11,0,9,3,5,8,6],
    [19,15,9,0,6,5,11,15],
    [13,14,3,6,0,2,5,9],
    [15,16,5,5,2,0,7,11],
    [12,16,8,11,5,7,0,7],
    [5,9,15,18,12,14,7,0]
]

var linearFunction: (Int) -> Float = { k in
    let To: Float = 10 //100 will increase the exploration over explotiaion
    let η: Float = 0.1 //0.1 provides best / fastest values after 18 iteration 48, or 49 after 15
    let Tminimum: Float = 1
    return max(To - η * Float(k), Tminimum)
}



SimulatedAnnealing(tsp: tsp, coolingFunction: linearFunction)