Created
February 22, 2017 17:42
-
-
Save peter-jung/ea8d88c4c4886ad362f21221fb1dc582 to your computer and use it in GitHub Desktop.
Minimal implementation of Dawkins Weasel in Python. The aim is to demonstrate that Evolution (Mutation + Selection) is different from pure chance.
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
# DawkinsWeasel.py | |
import random | |
chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ .,-' | |
target = 'The aim is to demonstrate that the process that drives evolutionary systems, random variation combined with non-random cumulative selection, is different from pure chance.' | |
print len(chars), len(target) | |
#b | |
def randchar(): | |
i = random.randint(0,len(chars)-1) | |
return chars[i] | |
p_change = .01 | |
n_generation = 100 | |
def lev(a, b): | |
if not a: return len(b) | |
if not b: return len(a) | |
return min(lev(a[1:], b[1:])+(a[0] != b[0]), lev(a[1:], b)+1, lev(a, b[1:])+1) | |
def distance(a,b): | |
#return lev(a,b) | |
assert(len(a)==len(b)) | |
dist = len(a) | |
for x,y in zip(a,b): | |
if x==y: | |
dist-=1 | |
return dist | |
def givebirth(parent): | |
child = '' | |
for c in parent: | |
if random.random() < p_change: | |
child += randchar() | |
else: | |
child += c | |
return child | |
def dawkinsWeasel(): | |
mystring = ''.join([randchar() for _ in range(len(target))]) | |
distance(mystring, target) | |
print mystring, distance(mystring, target) | |
ix = 0 | |
while distance(mystring, target) > 0: | |
ix+=1 | |
newstrings = [givebirth(mystring) for _ in range(n_generation)] | |
beststring = mystring | |
bestdist = distance(mystring, target) | |
bestidx = -1 | |
for e, ns in enumerate(newstrings): | |
if distance(ns, target) < bestdist: | |
bestdist = distance(ns, target) | |
bestidx = e | |
if bestidx != -1: | |
mystring = newstrings[bestidx] | |
print ix,mystring, distance(mystring, target) | |
#print lev('abc','def') | |
dawkinsWeasel() | |
''' | |
a='aim1' | |
b='aim2' | |
import time | |
for x in range(1,10): | |
t0=time.time() | |
print x, lev(x*a,b), time.time()-t0 | |
''' |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment