summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGuillaume Seguin <guillaume@segu.in>2007-12-18 01:59:02 +0100
committerGuillaume Seguin <guillaume@segu.in>2007-12-18 01:59:02 +0100
commit3486d364a59e20253209b3ea4f43b3242160a041 (patch)
tree9865cb147988217597d4bdf279b071b9080ea0c1
parent2338bc9f493a8bc2e3a7b33b90cb6a633b28e7ff (diff)
downloadtsp-3486d364a59e20253209b3ea4f43b3242160a041.tar.gz
tsp-3486d364a59e20253209b3ea4f43b3242160a041.tar.bz2
* Cleanup 2opt and add swap and insert pertubation methods
-rwxr-xr-xtsp.py45
1 files changed, 31 insertions, 14 deletions
diff --git a/tsp.py b/tsp.py
index 3a0aa42..d6b2f6d 100755
--- a/tsp.py
+++ b/tsp.py
@@ -254,21 +254,13 @@ class Algo:
def run (self):
'''Implement this in your algorithm subclass'''
-class Algo_2opt (Algo):
- '''Classic 2opt algorithm'''
-
- def run (self, path = None):
- '''Algorithm main loop'''
- if not path:
- path = self.context.nearest_neighbours_best ()
- best = path
- while True:
- yield path
- path = self.do_2opt (best)
- if path.length < best.length:
- best = path
+ def random_swap (self, path):
+ '''Randomly exchange two points'''
+ i, j = random.sample (xrange (len (path)), 2)
+ path[j], path[i] = path[i], path[j]
+ return Path (self.context, path)
- def do_2opt (self, path):
+ def random_reverse (self, path):
'''Do a simple transformation: given two points i and j, reverse the
path between i and j (e.g. [0, 1, 2, 3, 4, 5] with i = 1 and j = 4 becomes
[0, 1, 3, 2, 4, 5]. This is better than just exchanging two points because the
@@ -284,6 +276,31 @@ former only breaks 2 links while the latters breaks 4.'''
segment.reverse ()
return Path (self.context, path[j:i + 1] + segment)
+ def random_insert (self, path):
+ '''Remove a random point from path and reinsert it elsewhere'''
+ x = random.choice (path)
+ path.remove (x)
+ i = random.randint (0, self.context.count - 1)
+ path.insert (i, x)
+ return Path (self.context, path)
+
+class Algo_2opt (Algo):
+ '''Classic 2opt algorithm'''
+
+ def run (self, path = None):
+ '''Algorithm main loop'''
+ if not path:
+ path = self.context.nearest_neighbours_best ()
+ best = path
+ while True:
+ yield path
+ path = self.do_2opt (best)
+ if path.length < best.length:
+ best = path
+
+ def do_2opt (self, path):
+ return self.random_reverse (path)
+
class Algo_Annealing (Algo_2opt):
'''Simulated annealing algorithm'''