Instantly share code, notes, and snippets.

bellbind/genetic.py

Created December 15, 2010 10:46
Show Gist options
• Save bellbind/741853 to your computer and use it in GitHub Desktop.
[python]Genetic Algorithm example
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 """Genetic Algorithmn Implementation see: http://www.obitko.com/tutorials/genetic-algorithms/ga-basic-description.php """ import random class GeneticAlgorithm(object): def __init__(self, genetics): self.genetics = genetics pass def run(self): population = self.genetics.initial() while True: fits_pops = [(self.genetics.fitness(ch), ch) for ch in population] if self.genetics.check_stop(fits_pops): break population = self.next(fits_pops) pass return population def next(self, fits): parents_generator = self.genetics.parents(fits) size = len(fits) nexts = [] while len(nexts) < size: parents = next(parents_generator) cross = random.random() < self.genetics.probability_crossover() children = self.genetics.crossover(parents) if cross else parents for ch in children: mutate = random.random() < self.genetics.probability_mutation() nexts.append(self.genetics.mutation(ch) if mutate else ch) pass pass return nexts[0:size] pass class GeneticFunctions(object): def probability_crossover(self): r"""returns rate of occur crossover(0.0-1.0)""" return 1.0 def probability_mutation(self): r"""returns rate of occur mutation(0.0-1.0)""" return 0.0 def initial(self): r"""returns list of initial population """ return [] def fitness(self, chromosome): r"""returns domain fitness value of chromosome """ return len(chromosome) def check_stop(self, fits_populations): r"""stop run if returns True - fits_populations: list of (fitness_value, chromosome) """ return False def parents(self, fits_populations): r"""generator of selected parents """ gen = iter(sorted(fits_populations)) while True: f1, ch1 = next(gen) f2, ch2 = next(gen) yield (ch1, ch2) pass return def crossover(self, parents): r"""breed children """ return parents def mutation(self, chromosome): r"""mutate chromosome """ return chromosome pass if __name__ == "__main__": """ example: Mapped guess prepared Text """ class GuessText(GeneticFunctions): def __init__(self, target_text, limit=200, size=400, prob_crossover=0.9, prob_mutation=0.2): self.target = self.text2chromo(target_text) self.counter = 0 self.limit = limit self.size = size self.prob_crossover = prob_crossover self.prob_mutation = prob_mutation pass # GeneticFunctions interface impls def probability_crossover(self): return self.prob_crossover def probability_mutation(self): return self.prob_mutation def initial(self): return [self.random_chromo() for j in range(self.size)] def fitness(self, chromo): # larger is better, matched == 0 return -sum(abs(c - t) for c, t in zip(chromo, self.target)) def check_stop(self, fits_populations): self.counter += 1 if self.counter % 10 == 0: best_match = list(sorted(fits_populations))[-1][1] fits = [f for f, ch in fits_populations] best = max(fits) worst = min(fits) ave = sum(fits) / len(fits) print( "[G %3d] score=(%4d, %4d, %4d): %r" % (self.counter, best, ave, worst, self.chromo2text(best_match))) pass return self.counter >= self.limit def parents(self, fits_populations): while True: father = self.tournament(fits_populations) mother = self.tournament(fits_populations) yield (father, mother) pass pass def crossover(self, parents): father, mother = parents index1 = random.randint(1, len(self.target) - 2) index2 = random.randint(1, len(self.target) - 2) if index1 > index2: index1, index2 = index2, index1 child1 = father[:index1] + mother[index1:index2] + father[index2:] child2 = mother[:index1] + father[index1:index2] + mother[index2:] return (child1, child2) def mutation(self, chromosome): index = random.randint(0, len(self.target) - 1) vary = random.randint(-5, 5) mutated = list(chromosome) mutated[index] += vary return mutated # internals def tournament(self, fits_populations): alicef, alice = self.select_random(fits_populations) bobf, bob = self.select_random(fits_populations) return alice if alicef > bobf else bob def select_random(self, fits_populations): return fits_populations[random.randint(0, len(fits_populations)-1)] def text2chromo(self, text): return [ord(ch) for ch in text] def chromo2text(self, chromo): return "".join(chr(max(1, min(ch, 255))) for ch in chromo) def random_chromo(self): return [random.randint(1, 255) for i in range(len(self.target))] pass GeneticAlgorithm(GuessText("Hello World!")).run() pass

Zortog commented Mar 27, 2013

Hello! I have a question about using this code as an example. I am working on a poster for university that will be displayed publically. I was wondering if I might be able to use this code as a simple example of a genetic algorithm. Of course I would attribute it to you and give you all the credit that you are due, but I could not find the copyright info for this work, so I figured that I would ask in the comments. Thanks in advance!

hiteshchalise commented Apr 2, 2018

dude what is that r inside a function, just before return.

oleksandrzelentsov commented Apr 10, 2018

why do you use raw strings as docstrings?

Hi!!!!