METHINKS IT IS A WEASEL in Python DouKaku?

ランダムな文字からMETHINKS IT IS A WEASELを作るプログラムを作れ。

簡単に流れを書いてみます。

１：ランダムな２０文字を持つ文字列をもった３００個作ります。

２：その文字列が"METHINKSITISAWEASEL"に近いものからソートします。

３：それぞれの文字列のなか1文字を別の文字に変化させたものを３つ用意します。

４：それを２：のソートをして上位３００個残す。（９００個あるうちで上位３００個残すということです。）

５：以後３：と４：を繰り返す。

ランダムな文字変化は大文字だけでいいです。簡単にするために空白文字を外してあります。

METHINKS IT IS WEASELができたら終了。３と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。:-)

Rickard Dawkinsがブラインドウォッチメイカー(現題：盲目の時計職人）の３章で書いていた有名なものです。さらに一般化してもらってもいいです。

参考

http://home.pacbell.net/s-max/scott/weasel.html (JAVA アプレット)
http://en.wikipedia.org/wiki/Weasel_program

ごくごく素直にPythonで実装しました。増やす数(MULTIPLY)が3だと収束しなかったので、5にしてあります。

import random

GOAL = "METHINKSITISAWEASEL"

DOMAIN = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

SET_SIZE = 300
MULTIPLY = 5

def create_random():
    s = ""
    for i in range(len(GOAL)):
        s += random.choice(DOMAIN)
    return s

def initial_set():
    s = []
    for i in range(SET_SIZE):
        s += [create_random()]
    return s

def mutate(s):
    i = random.randrange(0, len(s))
    result = s[:i] + random.choice(DOMAIN) + s[i+1:]
    return result

def mutate_set(s):
    result = []
    for e in s:
        for i in range(MULTIPLY):
            result.append(mutate(e))
    return result

def distance(s):
    d = 0
    for c1, c2 in zip(s, GOAL):
        if c1 != c2:
            d += 1
    return d

def sorted_set(s):
    work = [(distance(e), e) for e in s]

    def mycmp(e1, e2):
        return cmp(e1[0], e2[0])
    work.sort(mycmp)
    return work

def main():
    s = initial_set()
    i = 0

    while True:
        new_s = mutate_set(s)
        s = [e for (d,e) in sorted_set(new_s)[:SET_SIZE]]
        print "%04d: %2d %s"%(i + 1, distance(s[0]), s[0])
        if s[0] == GOAL:
            break
        i += 1

if __name__=='__main__':
    main()

収束しないのでmutationしないものも次世代に持ち越してしまうようしてしまいましたが・・・。
     ng = ng + list(g.spawn_mutant()) + [g]

#!/usr/bin/python
# -*- encoding=us-ascii -*-
#
import random


class Gene(object):
  seed = 0
  base_alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  goal = "METHINKSITISAWEASEL"
  memoize = dict()
  def generate_rnd_code(self):
    return ''.join([random.choice(self.base_alpha) for i in range(len(self.goal))])

  def __init__(self, code=None):
    if code is None:
      self.code = self.generate_rnd_code()
    else:
      self.code = code

  def score(self):
    def score(goal, target):
      if goal:
        diff = ord(goal[0]) - ord(target[0])
        return diff * diff + score(goal[1:], target[1:])
        #return abs(diff) + score(goal[1:], target[1:])
      else:
        return 0
    s = score(self.goal, self.code)
    return s
  def which_base_to_mutate(self):
    return random.randint(0, len(self.goal)-1)

  def substitute_candidates(self, base, count):
    #cand = self.base_alpha.replace(base, '')
    cand = self.base_alpha[:]
    cand=list(cand)
    cand.remove(base)
    random.shuffle(cand)
    return cand[:count]

  def spawn_mutant(self, n_children=None):
    if n_children is None:
      n_children = 3
    nth = self.which_base_to_mutate()
    old_base = self.code[nth]
    for new_base in self.substitute_candidates(old_base, n_children):
      yield Gene(code= self.code[:nth] + new_base + self.code[nth+1:])

class GeneVat(object):
  def __init__(self, mass, n_children):
    self.genes = [Gene() for i in range(mass)]
    self.n_children = n_children
    self.mass = mass

  def create_ng(self):
    ng = list()
    for g in self.genes:
      ng = ng + list(g.spawn_mutant()) + [g]
    return ng

  def filter(self, xs):
    def cmp_by_score(x, y):
      xs = x.score()
      ys = y.score()
      if xs < ys:
        return -1
      elif xs > ys:
        return 1
      else:
        assert(xs == ys)
        return 0
    xs.sort(cmp_by_score)
    return xs[:self.mass]

  def evolve(self):
    self.genes = self.filter(self.create_ng())

  def head(self):
    for g in self.genes[:5]:
      print g.score(), g.code


vat = GeneVat(300, 3)
vat.head()
i = 0
while vat.genes[0].score()!= 0:
  i += 1
  vat.evolve()
  print 'generation %i'%i
  vat.head()

お題を次のように変更しました。

1. 目標文字列は "METHINKS IT IS LIKE A WEASEL" を使う。
2. お題では変化させた文字列３通りだけをソートするようになってい（ると思い）ますが、収束を保証できないので、元の文字列も残すようにする。
3. 変化は３通りでなくて、１通りとする。

手元で一回走らせた限りでは、200回程度で収束しました。

import string
import random
import itertools

def main():
    goal = "METHINKS IT IS LIKE A WEASEL"
    count = 300
    def char():
        return random.choice(string.ascii_uppercase + " ")
    a = ["".join(char() for _ in goal) for _ in xrange(count)]
    for generation in itertools.count(1):
        def key(s):
            return sum(int(c1 != c2) for c1, c2 in itertools.izip(goal, s))
        a.sort(key=key)
        del a[count:]
        print "%4d: %s" % (generation, a[0])
        if a[0] == goal:
            break
        for s in a[:]:
            i = random.randint(0, len(s) - 1)
            a.append(s[:i] + char() + s[i+1:])

if __name__ == '__main__':
    main()

DouKaku?

METHINKS IT IS A WEASEL

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq