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.
1 #!/usr/bin/env python
2
3 # author: Danillo Souza <danillo012@gmail.com>
4 # 2013-01-18
5
6 import string
7 from random import randint, choice
8 from optparse import OptionParser
9
10 (GEN_SIZE, COMMUNITY_SIZE, ITER_LIMIT) = (0,0,0)
11 SPECIAL_CHARS = ' .!?:'
12 CHARS_AVAILABLE = list(''.join([string.ascii_lowercase, string.ascii_uppercase, SPECIAL_CHARS]))
13
14
15 def initialize():
16 return ''.join([choice(CHARS_AVAILABLE) for i in range(GEN_SIZE)])
17
18 def fitness(target, source):
19 """
20 Calculates fitness based on Levenshtein Distance. (perfect = 0)
21 """
22 if len(target) < len(source): return lev_distance(source, target)
23 if not len(source): return len(target)
24
25 previous_row = xrange(len(source) + 1)
26
27 for x, c1 in enumerate(target):
28 current_row = [x + 1]
29
30 for y, c2 in enumerate(source):
31 current_row.append(min(previous_row[y + 1] + 1, current_row[y] + 1, previous_row[y] + (c1 != c2)))
32
33 previous_row = current_row
34
35 return previous_row[-1]
36
37 def mutagen(gen):
38 qtd = randint(1,4)
39
40 for i in range(qtd):
41 tmp = list(gen)
42 tmp[randint(0,GEN_SIZE-1)] = choice(CHARS_AVAILABLE)
43 gen = ''.join(tmp)
44
45 return gen
46
47 def circle_of_life(search="foo"):
48 community = {initialize():None for i in range(COMMUNITY_SIZE)}
49 winner = None
50
51 while not winner:
52 # calculate fitness of each gen (perfect = 0)
53 for gen in community.keys():
54 if community[gen] != 0:
55 community[gen] = fitness(gen, search)
56
57 print "%s : %d" % (gen, community[gen])
58
59 mutant = mutagen(gen)
60 mutant_fitness = fitness(mutant, search)
61
62 if community[gen] > mutant_fitness:
63 del community[gen]
64 community[mutant] = mutant_fitness
65
66 else:
67 winner = gen
68
69 print "\nWinner: %s" % winner
70
71
72 if __name__ == '__main__':
73
74 parser = OptionParser(usage="usage: %prog [options]", version="%prog 1.0")
75
76 parser.add_option('-s', '--string', dest='string', help="The result you're hoping to find.", default='foo')
77 parser.add_option('-c', '--community-size', dest='community_size', help="The size of the evolving community.", default=10)
78
79 (options, args) = parser.parse_args()
80
81 GEN_SIZE = len(options.string)
82 COMMUNITY_SIZE = int(options.community_size)
83
84 circle_of_life(options.string)
