Algoritmo genético mega simples que muta uma communidade de strings até encontrar o resultado esperado, exibindo todos os gens gerados/mutados e sua proximidade da palavra esperada calculada usando Distância de Levenshtein.

Valor apenas didático, na prática não teria porque usar um algoritmo genético pra procurar algo que já se tem em mãos, esse algoritmo serve apenas para ilustrar a forma de funcionamento do modo mais claro possível.

# author: Danillo Souza <danillo012@gmail.com>
# 2013-01-18

import string
from random import randint, choice
from optparse import OptionParser

(GEN_SIZE, COMMUNITY_SIZE, ITER_LIMIT) = (0,0,0)
SPECIAL_CHARS = ' .!?:'
CHARS_AVAILABLE = list(''.join([string.ascii_lowercase, string.ascii_uppercase, SPECIAL_CHARS]))


def initialize():
        return ''.join([choice(CHARS_AVAILABLE) for i in range(GEN_SIZE)])

def fitness(target, source):
        """
        Calculates fitness based on Levenshtein Distance. (perfect = 0)
        """
        if len(target) < len(source): return lev_distance(source, target)
        if not len(source): return len(target)

        previous_row = xrange(len(source) + 1)

        for x, c1 in enumerate(target):
                current_row = [x + 1]

                for y, c2 in enumerate(source):
                        current_row.append(min(previous_row[y + 1] + 1, current_row[y] + 1, previous_row[y] + (c1 != c2)))

                previous_row = current_row

        return previous_row[-1]

def mutagen(gen):
        qtd = randint(1,4)

        for i in range(qtd):
                tmp = list(gen)
                tmp[randint(0,GEN_SIZE-1)] = choice(CHARS_AVAILABLE)
                gen = ''.join(tmp)

        return gen

def circle_of_life(search="foo"):
        community = {initialize():None for i in range(COMMUNITY_SIZE)}
        winner = None

        while not winner:
                # calculate fitness of each gen (perfect = 0)
                for gen in community.keys():
                        if community[gen] != 0:
                                community[gen] = fitness(gen, search)

                                print "%s : %d" % (gen, community[gen])

                                mutant = mutagen(gen)
                                mutant_fitness = fitness(mutant, search)
                                
                                if community[gen] > mutant_fitness:
                                        del community[gen]
                                        community[mutant] = mutant_fitness
                        
                        else:
                                winner = gen

        print "\nWinner: %s" % winner


if __name__ == '__main__':
        
        parser = OptionParser(usage="usage: %prog [options]", version="%prog 1.0")

        parser.add_option('-s', '--string', dest='string', help="The result you're hoping to find.", default='foo')
        parser.add_option('-c', '--community-size', dest='community_size', help="The size of the evolving community.", default=10)

        (options, args) = parser.parse_args()

        GEN_SIZE = len(options.string)
        COMMUNITY_SIZE = int(options.community_size)

        circle_of_life(options.string)