* Add Genetic algorithmHEADmaster

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'''