summaryrefslogtreecommitdiff
path: root/tsp.py
diff options
context:
space:
mode:
authorGuillaume Seguin <guillaume@segu.in>2007-12-17 03:06:41 +0100
committerGuillaume Seguin <guillaume@segu.in>2007-12-17 03:06:41 +0100
commitdf55d37c0d43be392ec506d46ea8f7e51c2283ae (patch)
treec0941d430a6fc49e1f5805dc52b25a13e46d212d /tsp.py
parentf92251f0d3081b5ebf0c9e9497f236f5b1857e62 (diff)
downloadtsp-df55d37c0d43be392ec506d46ea8f7e51c2283ae.tar.gz
tsp-df55d37c0d43be392ec506d46ea8f7e51c2283ae.tar.bz2
* Add Simulated Annealing algorithm and use it by default
Diffstat (limited to 'tsp.py')
-rwxr-xr-xtsp.py39
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