diff options
author | Guillaume Seguin <guillaume@segu.in> | 2007-12-17 22:12:34 +0100 |
---|---|---|
committer | Guillaume Seguin <guillaume@segu.in> | 2007-12-17 22:12:34 +0100 |
commit | 12c0dbe7ae88bafb62dabdc21a100e20c1e03307 (patch) | |
tree | 9a8f31ca76eedb8ff8371489feb0b798250ab590 /tsp.py | |
parent | cbe1b06930d3811ac8161b3e81b1e95a0c98bdfa (diff) | |
download | tsp-12c0dbe7ae88bafb62dabdc21a100e20c1e03307.tar.gz tsp-12c0dbe7ae88bafb62dabdc21a100e20c1e03307.tar.bz2 |
* Add 2opt-based algorithm with MonteCarlo perturbations
Diffstat (limited to 'tsp.py')
-rwxr-xr-x | tsp.py | 33 |
1 files changed, 32 insertions, 1 deletions
@@ -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''' |