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/ev.py       | 33 ------------------------
 string_evolution/genepool.py | 61 ++++++++++++++++++++++++++++++++++++++++++++
 string_evolution/naive.py    | 33 ++++++++++++++++++++++++
 3 files changed, 94 insertions(+), 33 deletions(-)
 delete mode 100644 string_evolution/ev.py
 create mode 100644 string_evolution/genepool.py
 create mode 100644 string_evolution/naive.py

diff --git a/string_evolution/ev.py b/string_evolution/ev.py
deleted file mode 100644
index 4fbf52e..0000000
--- a/string_evolution/ev.py
+++ /dev/null
@@ -1,33 +0,0 @@
-### http://www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolving-hello-world/
-
-import random
-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)
-
-def mutate(source):
-    charpos = random.randint(0, len(source) - 1)
-    parts = list(source)
-    parts[charpos] = chr(ord(parts[charpos]) + random.randint(-1,1))
-    return(''.join(parts))
-
-fitval = fitness(source, target)
-i = 0
-while True:
-    i += 1
-    m = mutate(source)
-    fitval_m = fitness(m, target)
-    if fitval_m < fitval:
-        fitval = fitval_m
-        source = m
-        print "%5i %5i %14s" % (i, fitval_m, m)
-        sleep(0.1)
-    if fitval == 0:
-        break
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
diff --git a/string_evolution/naive.py b/string_evolution/naive.py
new file mode 100644
index 0000000..4fbf52e
--- /dev/null
+++ b/string_evolution/naive.py
@@ -0,0 +1,33 @@
+### http://www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolving-hello-world/
+
+import random
+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)
+
+def mutate(source):
+    charpos = random.randint(0, len(source) - 1)
+    parts = list(source)
+    parts[charpos] = chr(ord(parts[charpos]) + random.randint(-1,1))
+    return(''.join(parts))
+
+fitval = fitness(source, target)
+i = 0
+while True:
+    i += 1
+    m = mutate(source)
+    fitval_m = fitness(m, target)
+    if fitval_m < fitval:
+        fitval = fitval_m
+        source = m
+        print "%5i %5i %14s" % (i, fitval_m, m)
+        sleep(0.1)
+    if fitval == 0:
+        break
-- 
cgit v1.3.1