Better fitness method

[jackwilsdon]

Something I've noticed in the Python version of the algorithm is that it sometimes never ends. I'm not entirely sure why this is, but I'm starting to think it could be fitness related.

I'm saying this because I have made some changes to the fitness algorithm which seems to have greatly improved it's speed, going from 30 generations (or greater, sometimes never finishing) to about 15.

The modifications I have made are focused around the fitness algorithm itself, as well as how you order fitnesses.

I thought it made sense to make higher fitnesses "fitter", as in they are closer to the target text. I also changed the fitness classification method so that fitness is higher for every similar character.

Here is a diff of the changes I've made:

@@ -83,7 +83,8 @@
         """
         fitness = 0
         for a, b in zip(gene, Chromosome._target_gene):
-            fitness += abs(ord(a) - ord(b))
+            if a == b:
+                fitness += 1

         return fitness

@@ -121,7 +122,7 @@

         buf = []
         for i in range(size): buf.append(Chromosome.gen_random())
-        self.population = list(sorted(buf, key=lambda x: x.fitness))
+        self.population = list(sorted(buf, key=lambda x: x.fitness, reverse=True))

     def _tournament_selection(self):
         """
@@ -131,7 +132,7 @@
         best = choice(self.population)
         for i in range(Population._tournamentSize):
             cont = choice(self.population)
-            if (cont.fitness < best.fitness): best = cont
+            if (cont.fitness > best.fitness): best = cont

         return best

@@ -168,7 +169,7 @@
                     buf.append(self.population[idx])
                 idx += 1

-        self.population = list(sorted(buf[:size], key=lambda x: x.fitness))
+        self.population = list(sorted(buf[:size], key=lambda x: x.fitness, reverse=True))

 if __name__ == "__main__":
    maxGenerations = 16384
@@ -176,7 +177,7 @@

    for i in range(1, maxGenerations + 1):
        print("Generation %d: %s" % (i, pop.population[0].gene))
-       if pop.population[0].fitness == 0: break
+       if pop.population[0].gene == Chromosome._target_gene: break
        else:pop.evolve()
    else:
        print("Maximum generations reached without success.")

Sadly you can't use the patch tool to apply this patch due to the loss of the CRLF line breaks on GitHub.