* Add 2opt-based algorithm with MonteCarlo perturbations

1 files changed, 32 insertions, 1 deletions

diff --git a/tsp.py b/tsp.py
index 5530fb0..02ff7f9 100755
--- a/tsp.py
+++ b/tsp.py
@@ -50,7 +50,7 @@ INIT_GREEDY = "Greedy"
 INIT_GREEDY_BEST = "Greedy (Best)"
 
 INITS = [INIT_RANDOM, INIT_GREEDY, INIT_GREEDY_BEST]  # Init methods choices
-ALGOS = ["2opt", "Annealing"] # Algorithms choices 
+ALGOS = ["2opt", "MonteCarlo", "Annealing"] # Algorithms choices 
 COUNTS = [10, 25, 50, 100, 250] # City counts choices
 
 # Default settings
@@ -324,6 +324,37 @@ based on the current number of iterations (or so)'''
         '''Temperature law: t = t0 - accepted_updates * 0.001 (min'd to 0.1)'''
         return max (self.t0 - self.updates * 0.001, 0.1)
 
+class Algo_MonteCarlo (Algo_2opt):
+    '''2opt-based algorithm with Monte-Carlo perturbations'''
+
+    unsuccessful_loops      = 0
+    MAX_UNSUCCESSFUL_LOOPS  = 1000
+
+    def run (self, path = None):
+        '''Algorithm main loop'''
+        if not path:
+            path = self.context.nearest_neighbours_best ()
+        current = path
+        while True:
+            yield path
+            path = self.do_2opt (current)
+            if path.length < current.length:
+                current = path
+                self.unsuccessful_loops = 0
+            else:
+                '''If we did not find a better result, increment this'''
+                self.unsuccessful_loops += 1
+            '''After MAX_UNSUCCESSFUL_LOOPS, perturbate the current path'''
+            if self.unsuccessful_loops > self.MAX_UNSUCCESSFUL_LOOPS:
+                path = current = self.perturbate (current)
+                self.unsuccessful_loops = 0
+
+    def perturbate (self, path):
+        '''Perturbate a path by exchanging two points'''
+        i, j = random.sample (xrange (len (path)), 2)
+        path[j], path[i] = path[i], path[j]
+        return Path (self.context, path)
+
 class AlgoThread (threading.Thread):
     '''Threading running a given algorithm'''