diff options
-rwxr-xr-x | tsp.py | 58 |
1 files changed, 29 insertions, 29 deletions
@@ -301,6 +301,35 @@ class Algo_2opt (Algo): def do_2opt (self, path): return self.random_reverse (path) +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''' + return self.random_swap (path) + class Algo_Annealing (Algo_2opt): '''Simulated annealing algorithm''' @@ -344,35 +373,6 @@ 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''' - return self.random_swap (path) - class AlgoThread (threading.Thread): '''Threading running a given algorithm''' |