summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGuillaume Seguin <guillaume@segu.in>2007-12-18 02:16:18 +0100
committerGuillaume Seguin <guillaume@segu.in>2007-12-18 02:16:18 +0100
commit9e32667455ce80f4736a89fcdb53cc4fc74c26c3 (patch)
tree38c7a76da1ad0d6c9c304bd2d322b9be9b03b8cf
parent8de4e77c4054978b06aef0bc51a8461bde67e2fd (diff)
downloadtsp-master.tar.gz
tsp-master.tar.bz2
* Add Genetic algorithmHEADmaster
-rwxr-xr-xtsp.py120
1 files changed, 119 insertions, 1 deletions
diff --git a/tsp.py b/tsp.py
index 5c9b2cb..07f3576 100755
--- a/tsp.py
+++ b/tsp.py
@@ -51,7 +51,8 @@ INIT_GREEDY = "Greedy"
INIT_GREEDY_BEST = "Greedy (Best)"
INITS = [INIT_RANDOM, INIT_GREEDY, INIT_GREEDY_BEST] # Init methods choices
-ALGOS = ["2opt", "MonteCarlo", "Annealing"] # Algorithms choices
+# Algorithms choices
+ALGOS = ["2opt", "MonteCarlo", "Annealing", "Genetic"]
COUNTS = [10, 25, 50, 100, 250] # City counts choices
# Default settings
@@ -373,6 +374,123 @@ 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_Genetic (Algo):
+ '''Genetic/Evolutionnary algorithm'''
+
+ need_init = False
+
+ population = []
+ POPULATION_SIZE = 50
+ MUTATION_PROBA = 0.15
+ MAX_OPT_FAILS = 20
+
+ def run (self):
+ '''Algorithm main loop'''
+ self.init_population ()
+ while True:
+ parent1, parent2 = self.select_parents ()
+ child = self.crossover (parent1, parent2)
+ child = self.optimize (child)
+ if random.random () <= self.MUTATION_PROBA:
+ child = self.mutate (child)
+ if self.select_child (child):
+ self.population.pop () # Remove the last path of the list
+ self.insert_path (child)
+ yield child
+
+ def init_population (self):
+ '''Initialize population'''
+ for i in range (0, self.POPULATION_SIZE):
+ path = self.context.random_path ()
+ path = self.optimize (path)
+ self.insert_path (path)
+
+ def optimize (self, path):
+ '''Locally optimize a path by applying a 2opt algorithm. Keep applying
+transformations until we fail improving the path for MAX_OPT_FAILS loops'''
+ failures = 0
+ best = path
+ while failures < self.MAX_OPT_FAILS:
+ path = self.random_reverse (best)
+ if path.length < best.length:
+ best = path
+ failures = 0
+ else:
+ failures += 1
+ return best
+
+ def select_parents (self):
+ '''Select two parents for reproduction'''
+ return random.sample (self.population, 2)
+
+ def crossover (self, parent1, parent2):
+ '''Apply a crossover on two paths. The crossover method is:
+* Take first city of the second parent as first city of the child and as the
+ current city
+* Loop until the path is complete:
+ o Find the cities which come right after the current city in each parent
+ - If both cities are already in the child path, randomly choose next city
+ - If one of the cities is already in the child path, choose the other one
+ - Otherwise, choose the nearest one'''
+ remaining = range (0, self.context.count)
+ start = parent2[0]
+ remaining.remove (start)
+ child = [start]
+ while len (remaining) > 0:
+ index1 = parent1.index (child[-1])
+ index2 = parent2.index (child[-1])
+ next1 = parent1[(index1 + 1) % self.context.count]
+ next2 = parent2[(index2 + 1) % self.context.count]
+ dist1 = self.context.dists[child[-1]][next1]
+ dist2 = self.context.dists[child[-1]][next2]
+ if next1 not in remaining:
+ if next2 not in remaining:
+ next = random.choice (remaining)
+ else:
+ next = next2
+ elif next2 not in remaining:
+ next = next1
+ elif dist1 < dist2:
+ next = next1
+ else:
+ next = next2
+ child.append (next)
+ remaining.remove (next)
+ return Path (self.context, child)
+
+ def mutate (self, path):
+ '''Mutate a path (i.e. apply a small transformation on it)'''
+ def mutate_swap (path):
+ return self.random_swap (path)
+ def mutate_reverse (path):
+ return self.random_reverse (path)
+ def mutate_insert (path):
+ return self.random_insert (path)
+ mutations = [mutate_swap, mutate_reverse, mutate_insert]
+ mutation = random.choice (mutations)
+ return mutation (path)
+
+ def select_child (self, child):
+ '''Decide whether or not to keep a child'''
+ if child.length >= self.population[-1].length:
+ return False
+ for path in self.population:
+ if path.length > child.length:
+ break
+ elif path.length == child.length:
+ return False
+ return True
+
+ def insert_path (self, path):
+ '''Insert a path in the population'''
+ i = 0
+ count = len (self.population)
+ while i < count: # Find new path index
+ if path.length <= self.population[i].length:
+ break
+ i += 1
+ self.population.insert (i, path)
+
class AlgoThread (threading.Thread):
'''Threading running a given algorithm'''