Mownit - TSP

import random

import math
from matplotlib import pyplot as plt


class RandomPointsGenerator:
    def random_uniform(self, number, x0, x1, y0, y1):
        points = []
        for i in range(number):
            points.append((random.uniform(x0, x1), random.uniform(y0, y1)))
        random.shuffle(points)
        return points

    def group_random(self, number, x, y, group_num, e=0.3):
        points = []
        segment_x = x / group_num
        segment_y = y / group_num
        for i in range(group_num):
            for j in range(group_num):
                group_x0 = i * segment_x + segment_x * e
                group_x1 = (i + 1) * segment_x - segment_x * e
                group_y0 = j * segment_y + segment_y * e
                group_y1 = (j + 1) * segment_y - segment_y * e
                points += self.random_uniform(int(number / (group_num * group_num)), group_x0, group_x1, group_y0,
                                              group_y1)
        random.shuffle(points)
        return points


class Plot:
    def plot_points(self, cities, dx, dy):
        fig = plt.figure()
        canvas = fig.add_subplot(1, 1, 1)

        canvas.clear()
        canvas.set_xlim(0, dx)
        canvas.set_ylim(0, dy)

        for (x1, y1) in cities:
            plt.plot(x1, y1, color='b', linewidth=0.4, marker='o')
        plt.show()

    def plot_energy_history(self, information):
        iterations = [x['iteration'] for x in information]
        energies = [x['energy'] for x in information]
        plt.plot(iterations, energies, '.')
        plt.show()

    def plot_result(self, cities, x, y):
        fig = plt.figure()
        canvas = fig.add_subplot(1, 1, 1)

        canvas.clear()
        canvas.set_xlim(0, x)
        canvas.set_ylim(0, y)

        for ((x1, y1), (x2, y2)) in zip(cities, cities[1:]):
            plt.plot([x1, x2], [y1, y2], color='b', linestyle='-', linewidth=0.4, marker='o')

        x1, y1 = cities[0]
        x2, y2 = cities[-1]
        plt.plot([x1, x2], [y1, y2], color='b', linestyle='-', linewidth=0.4, marker='o')

        plt.show()


class Swap:
    def consecutive_swap(self, cities):
        new_cities = list(cities)
        l = len(cities)
        i = random.randint(0, l - 1)
        j = (i + 1) % l
        new_cities[i], new_cities[j] = new_cities[j], new_cities[i]
        return new_cities

    def arbitrary_swap(self, cities):
        new_cities = list(cities)
        l = len(cities)
        j = i = random.randint(0, l - 1)
        while j == i:
            j = random.randint(0, l - 1)

        new_cities[i], new_cities[j] = new_cities[j], new_cities[i]
        return new_cities


class CoolingFunctions:
    def fun1(self, rate):
        def f(temperature):
            new_temperature = temperature*rate
            return new_temperature
        return f

    def fun2(self, rate):
        def f(temperature):
            new_temperature = temperature - rate
            return new_temperature
        return f


class TSP:
    def distance(self, x, y):
        (a, b) = x
        (c, d) = y
        return math.sqrt((a - c) ** 2 + (b - d) ** 2)

    def current_energy(self, cities):
        return sum([self.distance(a, b) for (a, b) in zip(cities, cities[1:])])

    def simulate_annealing(self, cities, max_iterations, starting_temperature, cooling_function, swap_function, t_min=0.1):
        energy = self.current_energy(cities)

        iteration = 0
        temperature = starting_temperature
        energy_history = []
        best_configuration = {'energy': energy, 'cities': cities}

        for i in range(max_iterations):
            energy_history.append({'iteration': iteration, 'energy': energy})
            new_cities = swap_function(cities)
            if iteration % 1000 == 0:
                print('Iteration {}, energy {}'.format(iteration, energy))
            new_energy = self.current_energy(new_cities)
            if new_energy < best_configuration['energy']:
                best_configuration = {'energy': new_energy, 'cities': new_cities}
                cities = new_cities
                energy = new_energy
            elif math.exp((energy - new_energy) / temperature) > random.random():
                cities = new_cities
                energy = new_energy

            temperature = cooling_function(temperature)
            if temperature < t_min:
                print("Return due to temperature")
                return best_configuration, energy_history
            iteration += 1
        print("Return due to iterations")
        return best_configuration, energy_history


if __name__ == "__main__":
    generator = RandomPointsGenerator()
    n = 40
    x = 10
    y = 10
    # points = generator.group_random(n, x, y, 3, 0.25)
    points = generator.group_random(n, x, y, 2, 0.2)
    plot = Plot()
    swap = Swap().arbitrary_swap
    cooling = CoolingFunctions().fun1(0.99999)
    best_configuration, energy_history = \
        TSP().simulate_annealing(cities=points, max_iterations=2000000, starting_temperature=20,
                                 cooling_function=cooling, swap_function=swap, t_min=0.001)

    plot.plot_result(best_configuration['cities'], x, y)

    plot.plot_energy_history(energy_history)