summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGuillaume Seguin <guillaume@segu.in>2007-12-17 22:12:34 +0100
committerGuillaume Seguin <guillaume@segu.in>2007-12-17 22:12:34 +0100
commit12c0dbe7ae88bafb62dabdc21a100e20c1e03307 (patch)
tree9a8f31ca76eedb8ff8371489feb0b798250ab590
parentcbe1b06930d3811ac8161b3e81b1e95a0c98bdfa (diff)
downloadtsp-12c0dbe7ae88bafb62dabdc21a100e20c1e03307.tar.gz
tsp-12c0dbe7ae88bafb62dabdc21a100e20c1e03307.tar.bz2
* Add 2opt-based algorithm with MonteCarlo perturbations
-rwxr-xr-xtsp.py33
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'''