* Add Simulated Annealing algorithm and use it by default

1 files changed, 37 insertions, 2 deletions

diff --git a/tsp.py b/tsp.py
index 55278a8..1b55713 100755
--- a/tsp.py
+++ b/tsp.py
@@ -45,11 +45,11 @@ CITY_RADIUS = 3
 SHOW_NAMES = True
 
 INITS = ["Random", "Greedy"]
-ALGOS = ["2opt"]
+ALGOS = ["2opt", "Annealing"]
 COUNTS = [10, 25, 50, 100, 250]
 
 DEFAULT_INIT = "Random"
-DEFAULT_ALGO = "2opt"
+DEFAULT_ALGO = "Annealing"
 DEFAULT_COUNT = 50
 
 class Color:
@@ -229,6 +229,41 @@ class Algo_2opt (Algo):
             segment.reverse ()
             return Path (self.context, path[j:i + 1] + segment)
 
+class Algo_Annealing (Algo_2opt):
+
+    t0      = 10
+    updates = 0
+
+    def run (self, path = None):
+        self.updates = 0
+        if not path:
+            path = self.context.nearest_neighbours_best ()
+        current = best = path
+        while True:
+            yield current
+            next = self.do_2opt (current)
+            if next.length < best.length:
+                current = best = next
+                self.updates += 1
+            elif next.length <= current.length \
+              or self.accept_change (current, next):
+                current = next
+                self.updates += 1
+
+    def accept_change (self, current, next):
+        delta = next.length - current.length
+        p0 = random.random ()
+        t0 = 1
+        p = math.exp (- delta / self.temp ())
+        #print self.temp ()
+        if p0 <= p:
+            return True
+        else:
+            return False
+
+    def temp (self):
+        return max (self.t0 - self.updates * 0.001, 0.1)
+
 class AlgoThread (threading.Thread):
 
     context   = None