From ac413f38d249214d35701f2dbe934dc4ab77d52e Mon Sep 17 00:00:00 2001
From: Yuval Adam <yuv.adm@gmail.com>
Date: Wed, 28 Sep 2011 14:41:47 +0300
Subject: genepool variant

---
 string_evolution/genepool.py | 61 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 61 insertions(+)
 create mode 100644 string_evolution/genepool.py

(limited to 'string_evolution/genepool.py')

diff --git a/string_evolution/genepool.py b/string_evolution/genepool.py
new file mode 100644
index 0000000..10cb6cb
--- /dev/null
+++ b/string_evolution/genepool.py
@@ -0,0 +1,61 @@
+### http://www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolving-hello-world/
+
+import random
+import string
+from time import sleep
+
+source = "jiKnp4bqpmAbp"
+target = "Hello, World!"
+
+def fitness(source, target):
+    fitval = 0
+    for i in range(0, len(source)):
+        fitval += (ord(target[i]) - ord(source[i])) ** 2
+    return(fitval)
+
+GENSIZE = 20
+genepool = []
+for i in range(0, GENSIZE):
+    dna = [random.choice(string.printable[:-5]) for j in range(0, len(target))]
+    fit = fitness(dna, target)
+    candidate = {'dna': dna, 'fitness': fit }
+    genepool.append(candidate)
+
+def mutate(parent1, parent2):
+    child_dna = parent1['dna'][:]
+
+    # Mix both DNAs
+    start = random.randint(0, len(parent2['dna']) - 1)
+    stop = random.randint(0, len(parent2['dna']) - 1)
+    if start > stop:
+        stop, start = start, stop
+    child_dna[start:stop] = parent2['dna'][start:stop]
+
+    # Mutate one position
+    charpos = random.randint(0, len(child_dna) - 1)
+    child_dna[charpos] = chr(ord(child_dna[charpos]) + random.randint(-1,1))
+    child_fitness = fitness(child_dna, target)
+    return({'dna': child_dna, 'fitness': child_fitness})
+
+def random_parent(genepool):
+    wRndNr = random.random() * random.random() * (GENSIZE - 1)
+    wRndNr = int(wRndNr)
+    return(genepool[wRndNr])
+
+i = 0
+while True:
+    i += 1
+    genepool.sort(key=lambda candidate: candidate['fitness'])
+    
+    print "%5i %5i %14s" % (i, genepool[0]['fitness'], ''.join(genepool[0]['dna']))
+    sleep(0.1)
+    
+    if genepool[0]['fitness'] == 0:
+        break
+
+    parent1 = random_parent(genepool)
+    parent2 = random_parent(genepool)
+
+    child = mutate(parent1, parent2)
+    if child['fitness'] < genepool[-1]['fitness']:
+        genepool[-1] = child
-- 
cgit v1.3.1