sequential-annealing/annealing.py at master · yashke/sequential-annealing · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
import random
from itertools import *
from helpers import *

def flatten(l):
    return [x for x in chain.from_iterable(l)]

def uniq(l):
    return [x for x in unique_everseen(l)]

def unique_everseen(iterable):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = []
    for element in iterable:
        if not element in seen:
            seen.append(element)
            yield element
        else:
            print element

class SequentialAnnealing(object):
    "Sequential Annealing for Delivery Problem algorithm"

    ALPHA = 0.9

    def __init__(self):
        self.clients = []
        self._squared_length = None

    def append_client(self, client_tuple):
        self.clients.append(client_tuple)

    def random_solution(self):
        tmp_clients = self.clients[:]
        random.shuffle(tmp_clients)
        solution = triangularize(tmp_clients)
        return solution

    def squared_length(self):
        if self._squared_length:
            return self._squared_length
        else:
            self._squared_length = len(self.clients)**2
            return self._squared_length

    def solve(self):
        old_solution = self.random_solution()
        best_solution = list(old_solution)
        equilibrium_counter = 0
        temp = cost(best_solution, self.base)
        while equilibrium_counter <= 20:
            for i in xrange(self.squared_length()):
                old_solution, best_solution, equilibrium_counter, temp = self.annealing_step(old_solution, best_solution, equilibrium_counter, temp)
            temp = temp * self.ALPHA
            equilibrium_counter += 1
        return best_solution

    def annealing_step(self, old_solution, best_solution, equilibrium_counter, temp):
        customer = random.choice(self.clients)
        customer_route = filter(lambda x: customer in x, old_solution)[0]
        routes_without_customer = map(lambda x: list(x), filter(lambda x: x != customer_route, list(old_solution)))

        for_select = list(routes_without_customer)
        for_select.append([])
        route = random.choice(for_select)

        new_solution = None
        if len(route) < 3:
            new_solution = filter(lambda x: route != x, routes_without_customer)
            route.append(customer)
            new_solution.append(route)
            new_solution.append(filter(lambda x: customer != x, customer_route))
        else:
            new_solution = filter(lambda x: route != x, routes_without_customer)
            customer2 = random.choice(route)
            route1 = filter(lambda x: customer != x, customer_route)
            route2 = filter(lambda x: customer2 != x, route)
            route1.append(customer2)
            route2.append(customer)
            new_solution.append(route1)
            new_solution.append(route2)

        new_solution = filter(lambda x: len(x) > 0, new_solution)

        x = random.random()
        delta = cost(new_solution, self.base) - cost(old_solution, self.base)

        if delta < 0 or x < temp / (temp + delta):
            old_solution = list(new_solution)
            if cost(new_solution, self.base) < cost(best_solution, self.base):
                best_solution = list(new_solution)
                equilibrium_counter = 0

        return old_solution, best_solution, equilibrium_counter, temp


class AnnealingApp(object):
    """
    Sequential Annealing for Delivery Problem main app.
    """

    def __init__(self):
        pass

    def run(self):
        self.solver = SequentialAnnealing()
        self.read_data()
        best_solution = self.solver.solve()
        print best_solution
        print cost(best_solution, self.solver.base)

    def read_line_vars(self):
        return [int(x) for x in raw_input().strip().split(" ")]

    def read_data(self):
        self.solver.size = self.read_line_vars()
        self.solver.base = self.read_line_vars()
        self.solver.clients_count, = self.read_line_vars()
        for i in range(self.solver.clients_count):
            self.solver.append_client(self.read_line_vars())


if __name__ == "__main__":
    random.seed()
    app = AnnealingApp()
    app.run()