DouKaku?beta

challenge METHINKS IT IS A WEASEL

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

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

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

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

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

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

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

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

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

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

参考

post comment

Posted feedbacks - Flatten

Nested Hidden

近さのうまい定義ってそんなに自明じゃないんですね。下のプログラムではアスキーコードの差を足していますが、もっといい方法がありそうです。

文字変化のやり方も焼きなまし法を使うとかいろいろ考えられそうです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
(defun random-char (&optional random-state)
  (code-char (+ 65 (random 26 random-state))))

(defun random-string (length &optional random-state)
  (let ((s (make-string length)))
    (dotimes (i length)
      (setf (elt s i) (random-char random-state)))
    s))

(defun modify (s &optional random-state)
  (let ((i (random (length s) random-state))
        (r (copy-seq s)))
    (setf (elt r i)
          (code-char (+ (random 3 random-state)
                        (char-code (elt s i))
                        -1)))
    r))

(defun weasel (target)
  (let ((state (make-random-state t)))
    (flet ((key (s)
             (loop for c1 across s and c2 across target
               sum (abs (- (char-code c1) (char-code c2))))))
      (do ((strings (loop repeat 300
                      as s = (random-string (length target) state)
                      collect (cons s (key s)))
                    (sort (mapcan (lambda (p)
                                    (loop repeat 3
                                      as s = (modify (car p) state)
                                      collect (cons s (key s))))
                                  strings)
                          #'< :key #'cdr))
           (i 1 (1+ i)))
          ((string= target (caar strings))
           (format t "~D: ~A (~D)~%" i (caar strings) (cdar strings))
           (format t "Finished after ~D steps.~%" i))
        (setf (cdr (nthcdr 299 strings)) nil)
        (format t "~D: ~A (~D)~%" i (caar strings) (cdar strings))))))

(weasel "METHINKSITISAWEASEL")

安直な実装。 派生文字列が3つだとうまく収束しなかったので、10個にしています。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#!/usr/bin/perl

use strict;
use warnings;

my @alphabets = "A" .. "Z";
my @strings   = ();
my $goal      = "METHINKSITISAWEASEL";

sub random_int($) { int rand shift }

sub similarity($) {
    my $str   = shift;
    my $score = 0;

    for ( 0 .. length($str) - 1 ) {
        $score++ if substr( $str, $_, 1 ) eq substr( $goal, $_, 1 );
    }
    return $score;
}

sub derive_string($) {
    my $origin_string   = shift;
    my @derived_strings = ();
    for ( 1 .. 10 ) {
        my $derived_string = $origin_string;
        substr( $derived_string, random_int length $origin_string, 1 ) =
          $alphabets[ random_int @alphabets ];
        push @derived_strings, $derived_string;
    }

    return @derived_strings;
}

for ( 1 .. 300 ) {
    my $string = "";
    $string .= $alphabets[ random_int @alphabets ] for 1 .. length $goal;
    push @strings, $string;
}

my $count = 0;
until ( $strings[0] eq $goal ) {
    my @next_gen = ();
    print $count++, ": ", $strings[0], "\n";
    push @next_gen, derive_string $_ for @strings;
    @strings =
      ( map { $_->[1] }
          sort { $b->[0] <=> $a->[0] } map { [ similarity $_, $_ ] } @next_gen )
      [ 0 .. 299 ];
}

print $count, ": ", $strings[0], "\n";

距離関数の定義がなかったので、とりあえず一致しない文字数を距離の定義としてみました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;


public class Sample177 {
    private static final char[] CHARACTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
    private static final int INITIAL_COUNT = 300;
    private static final int CREATE_COUNT = 3;


    private final Random random_ = new Random();
    private List<String> cache_ = new ArrayList<String>();

    private final String target_;
    private final Comparator<String> comparator_;


    public Sample177(String target) {
        target_ = target;
        comparator_ = new StringDistanceComparator(target);
        init();
    }
    private void init() {
        for (int count = 0; count < INITIAL_COUNT; count++) {
            cache_.add(createString(target_.length()));
        }
        Collections.sort(cache_, comparator_);
    }
    private String createString(int length) {
        StringBuilder builder = new StringBuilder(length);
        for (int index = 0; index < length; index++) {
            builder.append(CHARACTERS[random_.nextInt(CHARACTERS.length)]);
        }
        return builder.toString();
    }

    public String getTop() {
        return cache_.get(0);
    }

    public void nextStep() {
        for (String str: cache_.toArray(new String[0])) {
            for (int index = 0; index < CREATE_COUNT; index++) {
                cache_.add(changeCharacter(str));
            }
        }
        Collections.sort(cache_, comparator_);
        cache_ = cache_.subList(0, INITIAL_COUNT);
    }
    public String changeCharacter(String str) {
        StringBuilder builder = new StringBuilder(str);
        builder.setCharAt(random_.nextInt(str.length()), CHARACTERS[random_.nextInt(CHARACTERS.length)]);
        return builder.toString();
    }


    static class StringDistanceComparator implements Comparator<String> {
        private final String target_;
        public StringDistanceComparator(String target) {
            target_ = target;
        }

        @Override
        public int compare(String o1, String o2) {
            return calcDistance(o1) - calcDistance(o2);
        }
        private int calcDistance(String other) {
            int distance = 0;
            for (int index = 0, len = target_.length(); index < len; index++) {
                distance += (target_.charAt(index) == other.charAt(index))? 0 : 1;
            }
            return distance;
        }
    }


    public static void main(String[] args) {
        String target = "METHINKSITISAWEASEL";
        Sample177 sample = new Sample177(target);

        int index = 1;
        String top = sample.getTop();
        System.out.println(index++ + ":" + top);
        while (!top.equals(target)) {
            sample.nextStep();
            top = sample.getTop();
            System.out.println(index++ + ":" + top);
        }
    }
}

>近さのうまい定義ってそんなに自明じゃないんですね。下のプログラムではアスキーコードの差を足しています

そうなんですよね。うまい定義はどうするか？ってありますね。僕も作成した時はアスキーコードの差を利用したように記憶しています。:-)


お題とは外れますが、せっかくなのでGAで書いてみました。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

const char TargetString[] = "METHINKSITISAWEASEL";
const int TargetStringLength = 20;

const char AlphabetTable[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int AlphabetNum = strlen(AlphabetTable);


int getScore(char *s)
{
    //完全マッチで0が帰る。
    int score = 0;    
    for(int i = 0; i < TargetStringLength; ++i) {
        int d = TargetString[i] - s[i];
//        score -= d > 0 ? d : -d;    //差
        score -= !!d;                //ハミング距離
    }
    return score;    
}


void kousa(char *s1,char *s2)
{
    int r = rand() % TargetStringLength;
    //rの位置で交差させる
    for(int i = r; i < TargetStringLength; ++i){
        char t;
        t = s1[i];
        s1[i] = s2[i];
        s2[i] = t;
    }
}

void henni(char *s)
{
    //1文字を別の文字に変化させる
    s[rand() % (TargetStringLength - 1)] = AlphabetTable[rand() % AlphabetNum];
}

struct Gene{
    char gene[TargetStringLength];
    int result;
};

void GeneToResult(Gene *g)
{
    g->result = getScore(g->gene);
}


int compare(const void *_a,const void *_b)
{
    const Gene *a = (Gene*)_a;
    const Gene *b = (Gene*)_b;
    
    if (a->result > b->result){
        return -1;
    } else if (a->result < b->result) {
        return 1;
    }

    return 0;
}


int main()
{
    srand((unsigned int)time(NULL));

    //初期化
    const int GeneMax = 300;
    Gene genePool[GeneMax];

    for(int i = 0; i < GeneMax; ++i){
        //ランダムな文字列で埋め尽くす
        for(int j = 0; j < TargetStringLength - 1; ++j){
            genePool[i].gene[j] = AlphabetTable[rand() % AlphabetNum];
        }
        genePool[i].gene[TargetStringLength -1] = '\0';
        GeneToResult(&genePool[i]);    //スコアの取得
    }


    //進化させる
    for(int t = 0; t < 1000; t++) {
        //sort
        qsort(genePool,GeneMax,sizeof(Gene),&compare);

        //上位をprint
        printf("times = %d --------------------\n", t);
        for(int i = 0; i < 10; ++i){
            printf("Gene = %s, score = %d \n", genePool[i].gene, genePool[i].result);
        }
        getchar();

        //交叉、突然変異
        for(int i = GeneMax/2; i < GeneMax; i+=2){    //スコアの下位半分を捨てる
            char g1[TargetStringLength];
            char g2[TargetStringLength];
            strcpy(g1 , genePool[rand()%(GeneMax/2)].gene);    //適当な上位を選択
            strcpy(g2 , genePool[rand()%(GeneMax/2)].gene);
            kousa(g1, g2);    //交差
            henni(g1);        //変異
            henni(g2);
            strcpy(genePool[i].gene , g1);
            strcpy(genePool[i+1].gene , g2);
        }
        //評価
        for(int i = 0; i < GeneMax; ++i){
            GeneToResult(&genePool[i]);
        }
    }
}

お題の通りに実装すると収束しませんね。突然変異の確率が高すぎるのが良くないようです。変異する文字数を1にすれば収束しました。(変異がおこる確率をいじるとさらに早く、80世代ほどで終わります)


すいません。問題の設定が甘くて　お許しください。


ごくごく素直にPythonで実装しました。増やす数(MULTIPLY)が3だと収束しなかったので、5にしてあります。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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()

Squeak Smalltalk で。

ソートの際の比較は、文字とその位置の一致の数を調べる #howManyMatch: を使っています。三つでは収束しないので五つに変えました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| ゴール 全英字 文字数 上位群 世代数 |
ゴール := 'METHINKSITISWEASEL'.
文字数 := ゴール size.
全英字 := Character alphabet asUppercase.
上位群 := OrderedCollection new.
300 timesRepeat: [
    | 元文字列 |
    元文字列 := ((1 to: 文字数) collect: [:idx | 全英字 atRandom]) as: String.
    上位群 add: {元文字列 howManyMatch: ゴール. 元文字列}].
世代数 := 0.

World findATranscript:  nil.
[上位群 first last = ゴール] whileFalse: [
    | 候補群 |
    候補群 := OrderedCollection new.
    上位群 do: [:each |
        5 timesRepeat: [
            | 変異文字列 |
            変異文字列 := each last copy.
            変異文字列 at: 文字数 atRandom put: 全英字 atRandom.
            候補群 add: {変異文字列 howManyMatch: ゴール. 変異文字列}]].
    候補群 := 候補群 asArray sort: [:a :b | a first > b first].
    上位群 := 候補群 first: 300.
    Transcript cr; show: (世代数 := 世代数 + 1) -> 上位群 first].
^世代数

3だとなかなか収束しないですね。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    public static class MethinksItIsLikeAWeasel
    {
        const int CANDIDATE_COUNT = 300;
        const int VALIDATION_COUNT = 3;
        const string GOAL = "METHINKSITISAWEASEL";
        static Random _rnd = new Random();

        internal static void Start()
        {
            var strs = CANDIDATE_COUNT
                .Make( () => new string( GOAL.Length.Make( () => GetChar() ).ToArray() ) )
                .ToArray();

            int g = 0;
            while( strs.First() != GOAL )
            {
                strs = strs
                    .SelectMany( str => VALIDATION_COUNT.Make( () => Replace( str ) ) )
                    .ToArray()
                    .OrderByDescending( s => CalcPoint( s ) )
                    .Take( CANDIDATE_COUNT )
                    .ToArray();
                Console.WriteLine( "{0} {1} {2}", g, CalcPoint( strs.First() ), strs.First() );
                g++;
            }
        }

        static int CalcPoint( string str )
        {
            return str.Select( ( c, i ) => c == GOAL[ i ] ? 1 : 0 ).Sum();
        }

        static string Replace( string str )
        {
            int index = _rnd.Next( str.Length );
            return str.Remove( index, 1 ).Insert( index, GetChar().ToString() );
        }

        static char GetChar()
        {
            return (char)( _rnd.Next( 26 ) + 65 );
        }

        public static IEnumerable<T> Make<T>( this int count, Func<T> func )
        {
            return Enumerable.Range( 0, count ).Select( _ => func() );
        }
    }
}

3だと収束しないので5で。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import scala.util.Sorting.stableSort
class Weasel(val target:String) {
  val rnd = new Random
  val len = target.size
  val chars = (65 to 90).map(_.asInstanceOf[char])
  def newchar = chars(rnd.nextInt(chars.size))

  def similarity(s:String) = (len /: (0 until len)){(r,i) => 
    r-(if(target(i) == s(i)){1}else{0})
  }

  def sort(lst:Seq[String]) = stableSort(lst, similarity _).toList

  def mutate(s:String) = (1 to 5).map{x=> 
    var a = s.toArray
    a(rnd.nextInt(len)) = newchar
    a.mkString("")
  }
 

  def start = {
    val lst = sort((1 to 300).map(x=>(1 to len).map(y=>newchar).mkString("")))
    def iter(ss:List[String], generation:int):unit = {
      printf("Generation %d\n%s\n%s\n\n", generation, "-"*40, ss.take(5).mkString("\n"))
      ss match {
        case head::rest if head == target => ()
        case x => 
          iter(sort(x.flatMap(mutate)).take(300), generation+1)
      }
    }
    iter(lst, 0)
  }
}

new Weasel("METHINKSITISAWEASEL").start

密かに20文字じゃなくて19文字じゃないかと。。。。 ちょっと無駄なところを省いて動いています。 perlが入っていれば第一引数の任意の文字列で同じことができます。(コマンドライン|ターミナル)からも動くので遊んでみてください。 正規表現で最初点数つけていたのですが まったく速度的に異常なことに.... いろいろ考えさせてもらって楽しかったですytakenakaさんありがとう!! 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
use strict;

my $goal = uc(@ARGV[0]) || q{METHINKSITISAWEASEL};

my @table;
     # $table[$id]->[0] 文字列
     # $table[$id]->[1] 近似スコア
my $total_calc;
     #キャッシュ数
my $cash = 3; 


$|=1; # 計算途中に結果を見たいのでバッファオフ


INIT: 
      #@tableに300個ランダムな文字列を生成
    for my $id (0..299){
     my @alpha = ("A".."Z");
      for(0..(length($goal)-1)){
        $table[$id]->[0] .= $alpha[int rand(26)];
      }
    }
    
BEGIN:
    ++$total_calc;
    
        #各項目を1文字何かに変えて$cash数分配
    for my $cnt (0..$#table){
     for(1..$cash) {
     $table[$cnt + $_ * 300] = [one_chr_enig($table[$cnt]->[0]),undef];
     }
    }
        #各項目を点数化 0 -> undef
    @table = set_score(@table);
        # 順列にソート
    @table = sort{$b->[1]<=>$a->[1]} @table;
        #@tabel の299以下の要素を切り捨てる
    $#table = 299;

        #結果出力
    print ($table[0]->[0]
              .  q{ (score) : } . $table[0]->[1]
              .  q{ (steps) : } ." $total_calc  \n"
          );
    
unless($table[0]->[1] == length($goal))
 {goto BEGIN};

    #計算結果を算出    
sub set_score {
   my @table = @_;
         for (0..$#table){
              my $str = $table[$_]->[0];
              my @pre =split//,$goal;
              my $score = undef;
                for (0..(length($goal)-1)){
                  if (substr($str, $_, 1) eq $pre[$_]){
                   ++$score;
                  }
                }
              $table[$_]->[1] = $score;
         }
  return @table;
}

    #与えた文字列をランダムに一文字交換
sub one_chr_enig {
  my @str = split//,shift;
  my @alpha = ("A".."Z");
  $str[int rand(length($goal))] =  $alpha[int rand(26)];
  return join("",@str);
}

訂正 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    #与えた文字列をランダムに一文字交換
sub one_chr_enig {
  my @str = split//,shift;
  my @alpha = ("A".."Z");
  $str[int rand(length($goal))] =  $alpha[int rand(26)];
  return join("",@str);
}

よりも下記のほうが俄然早いです。

    #与えた文字列をランダムに一文字交換
sub one_chr_enig {
  my $str = shift;
  my @alpha = ("A".."Z");
  substr($str,int rand(length($goal)),1) = $alpha[int rand(26)];
  return $str;
}


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#!/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()

他と同じく、3だと収束しないので5です。 また、ブラウザが固まらないようにsetTimeoutを使っています。Rhinoなどで実行する場合は、setTimerのところをwhileループにでもして下さい。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
function test() {
  var x = "METHINKSITISAWEASEL";
  var data = sort(initialData(300, x.length), x);
  var mutate = 5;
  setTimer(x, data, mutate, 0, 100);
}
function setTimer (x, data, mutateNum, count, interval) {
  setTimeout(function() {
    print(count + " " + data[0] + " " + data[0].differenceFrom(x));
    if (data[0].differenceFrom(x) == 0) {
      return;
    }
    data = mutateAndSelect(x, data, mutateNum);
    setTimer (x, data, mutateNum, count+1, interval);
  }, interval);
}

function mutateAndSelect (x, data, mutateNum) {
  var ar = new Array(data.length * mutateNum);
  for (var i=0, n=data.length; i<n; i++) {
    for (var j=0; j<mutateNum; j++) {
      ar[i*mutateNum + j] = data[i].mutate();
    }
  }
  return sort(ar, x).slice(0, data.length);
}

function sort(data, x) {
  var cache = {};
  data.sort(function (a, b) {
    var da = cache[a] || (cache[a] = a.differenceFrom(x));
    var db = cache[b] || (cache[b] = b.differenceFrom(x));
    return da - db;
  });
  return data;
}

function initialData(num, len) {
  var ar = new Array(num);
  for (var i = 0; i<num; i++) {
    ar[i] = randomString(len);
  }
  return ar;
}
function randomString(len) {
  var chars = new Array(len);
  for (var i = 0; i<len; i++) {
   chars[i] = 65 + Math.floor(26*Math.random());
  }
  return String.fromCharCode.apply(null, chars);
}

String.prototype.differenceFrom = function (str) {
  var diff = Math.abs(this.length - str.length);
  for ( var i=0, n = Math.min(this.length, str.length); i<n; i++) {
    if( this.charAt(i) != str.charAt(i)) diff++;
  }
  return diff;
}

String.prototype.mutate = function () {
  var x = Math.floor(Math.random() * this.length);
  return this.substr(0, x) + 
    String.fromCharCode(65 + Math.floor(26*Math.random()))
         + this.substr(x+1, this.length);
}

var infoArea = document.body.appendChild(document.createElement("div"));
infoArea.innerHTML = " ";
function print(str) {
  infoArea.firstChild.nodeValue = str;
}

test();

みんな言ってるけど、３じゃだめですね・・・。 評価関数を工夫してどうにかしようと奮闘したけどだめでした。

遺伝子（と呼びたい）に、ムダな領域を追加すると、３でも収束します。実質、変異率を下げたのと同じことですが。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
using System;
using System.Text;
using System.Collections.Generic;

namespace Methinks
{
    class Program
    {
        static String GOAL = "METHINKSITISAWEASEL";
        static String CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        public static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            
            int CAPACITY_SMALL = 300;    //容量
            int CHILDREN = 3;            //子供の数
            int INTRON = 4;                //ムダ領域
            SortedList<int, String>[] pools = new SortedList<int, String>[] {
                new SortedList<int, String>(),
                new SortedList<int, String>()
            };
            Random rand = new Random();
            
            for (int i = 0; i < CAPACITY_SMALL; i++) {
                StringBuilder sb = new StringBuilder();
                for (int n = 0; n < (GOAL.Length + INTRON); n++) {
                    sb.Append(CHARS[rand.Next(CHARS.Length)]);
                }
                AddMember(pools[0], sb.ToString());
            }

            int g = 0;
            int turn = g % 2;
            while (pools[turn].Values[0].Substring(0, GOAL.Length) != GOAL) {
                Console.WriteLine("{0}: Top = [{1}], {2}", g, pools[turn].Values[0], pools[turn].Keys[0]);

                int next = (g + 1) % 2;
                pools[next].Clear();
                for (int i = 0; i < CAPACITY_SMALL; i++) {
                    
                    for (int c = 0; c < CHILDREN; c++) {
                        int pos = rand.Next(GOAL.Length + INTRON);
                        StringBuilder child = new StringBuilder();
                        child.Append(pools[turn].Values[i].Substring(0,pos));
                        child.Append(CHARS[rand.Next(CHARS.Length)]);
                        child.Append(pools[turn].Values[i].Substring(pos+1));
                        AddMember(pools[next], child.ToString());
                    }
                }
                g++;
                turn = g % 2;
            }
                
            Console.WriteLine("{0}: Top = [{1}], {2}", g, pools[turn].Values[0], pools[turn].Keys[0]);
            Console.Write("Press any key to continue . . . ");
            Console.ReadKey(true);
        }
        static void AddMember(SortedList<int, String> pool, String member) {
            int score = GetScore(member);
            while (pool.ContainsKey(score)){
                score++;
            }
            pool.Add(score, member);
        }
        static int GetScore(String s) {
            int score = 0;
            for (int i = 0; i < GOAL.Length; i++){
                if (s[i] == GOAL[i]){
                    score--;
                }
            }
            return score * 1000;
        }
    }
}

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

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

手元で一回走らせた限りでは、200回程度で収束しました。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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()

問題文そのまま。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
private import std.stdio, std.string, std.algorithm, std.random, std.contracts;

const target = "METHINKSITISAWEASEL";
const capacity = 300;
const children = 5;

Random rand;
static this() {
    rand = Random(unpredictableSeed);
}

void main() {
    auto strings = new string[capacity];
    foreach(ref s; strings) s = randomString;

    int generation;
    do {
        auto temp = new string[strings.length * children];
        foreach(i, ref s; temp) s = changeChar(strings[i/children]);
        schwartzSort!(distance)(temp);
        strings = temp[0..capacity];

        writefln("[%s] %s (%s)", ++generation, strings[0], distance(strings[0]));
    } while(strings[0] != target);
    writefln("Now, we have %s!", target);
}

char randomChar() {
    alias UniformDistribution!(int, "[]") Dist;

    return Dist('A', 'Z').next(rand);
}

string randomString() {
    auto result = new char[target.length];
    foreach(ref c; result) c = randomChar;
    return assumeUnique(result);
}

string changeChar(string str) {
    alias UniformDistribution!(int) Dist;

    auto result = str.dup;
    result[Dist(0, result.length).next(rand)] = randomChar;
    return assumeUnique(result);
}

int distance(string str) {
    int d;
    assert(str.length == target.length);
    foreach(i; 0..target.length) {
        if(str[i] != target[i]) ++d;
    }
    return d;
}

C++に移植してみました。

see: 乱数の範囲を限定する 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib> // rand, RAND_MAX
#include <cassert>
#include <ctime>

const std::string goal = "METHINKS IT IS LIKE A WEASEL";

size_t random(size_t n) // [0, n)
{
    assert(n > 0);

    return static_cast<size_t>(std::rand() * (n + 1.0) / (RAND_MAX + 1.0));
}

char random_char()
{
    static const char table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";

    return table[random(sizeof(table))];
}

std::string random_string()
{
    std::string s;

    s.resize(goal.size());

    std::generate(s.begin(), s.end(), random_char);

    return s;
}

class sentence
{
public:
    explicit sentence(const std::string& s = random_string());

    const std::string& str() const
    {
        return _s;
    }

    friend bool operator<(const sentence& lhs, const sentence& rhs)
    {
        return lhs._diff < rhs._diff;
    }

private:
    std::string _s;
    size_t _diff;
};

sentence::sentence(const std::string& s) : _s(s), _diff(0)
{
    assert(s.size() == goal.size());

    for (size_t i = 0; i < s.size(); ++i)
    {
        if (s[i] != goal[i])
        {
            ++_diff;
        }
    }
}

int main()
{
    std::srand(std::time(NULL));

    const size_t count = 300;

    std::vector<sentence> v(count);

    for (size_t generation = 1; ; ++generation)
    {
        std::sort(v.begin(), v.end());

        v.erase(v.begin() + count, v.end());

        std::cout << std::setw(4) << generation << ": " << v.front().str() << std::endl;

        if (v.front().str() == goal)
        {
            break;
        }

        for (size_t i = 0; i < count; ++i)
        {
            std::string s = v[i].str();

            s[random(s.size())] = random_char();

            v.push_back(sentence(s));
        }
    }
}

本当にこれで高速化するか試してませんが・・・部分ソートというのがあるみたいなので、使ってみました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
--- main.cpp.old    Wed May 21 13:00:14 2008
+++ main.cpp.new    Wed May 21 19:04:41 2008
@@ -78,7 +78,7 @@
 
     for (size_t generation = 1; ; ++generation)
     {
-        std::sort(v.begin(), v.end());
+        std::partial_sort(v.begin(), v.begin() + count, v.end());
 
         v.erase(v.begin() + count, v.end());


全く余談ですが
METHINKS IT IS A WEASEL は

ハムレットの第三幕第二場のセリフで

ハムレットは彼に、雲を指しながら、「まるでラクダ」、「イタチにも思える」、 
「鯨にも見える」と統一性のない事を言うが、それにポローニアスも意見を合わせてくる。 
「みんなして俺をうまくあしらいやがって」とハムレットは呟き ... の部分のセリフみたいです。

どうも何を意味しているのか分からなかったので。

最終の文字列を"METHINKS IT IS A WEASEL"にして、 ２：のソートをシュウォーツ変換っぽく。 あとやっぱり、派生が3つだと収束しないので5つで。

see: Schwartzian transform 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <algorithm>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string>
#include <utility>
#include <vector>

const std::string GOAL("METHINKS IT IS A WEASEL");
const std::size_t MULTI_NUM = 5;
const std::size_t INIT_SIZE = 300;

typedef std::vector<std::string> strlist_t;
typedef std::pair<std::string, std::string> keyed_t;

char
gen_char()
{
  static const std::string CANDIDATES("ABCDEFGHIJKLMNOPQRSTUVWXYZ ");
  return CANDIDATES[std::rand()%CANDIDATES.size()];
}

std::string
gen_seed()
{
  std::string seed(GOAL.size(), '\0');
  std::generate(
      seed.begin(), seed.end(),
      gen_char);
  return seed;
}

char
diff_char(const char l, const char r)
{
  return l < r ? r - l : l - r;
}

keyed_t
make_diff(const std::string& seed)
{
  std::string diff(seed.size(), '\0');
  std::transform(
      seed.begin(), seed.end(),
      GOAL.begin(),
      diff.begin(),
      diff_char);
  return std::make_pair(diff, seed);
}

bool
diff_cmp(const keyed_t& lhs, const keyed_t& rhs)
{
  return lhs.first < rhs.first;
}

std::string
extract_seed(const keyed_t& dpair)
{
  return dpair.second;
}

void
sort_seeds(strlist_t& seeds)
{
  std::vector<keyed_t> difflist;
  difflist.reserve(seeds.size());

  std::transform(
      seeds.begin(), seeds.end(),
      std::back_inserter(difflist),
      make_diff);
  std::sort(
      difflist.begin(), difflist.end(),
      diff_cmp);
  std::transform(
      difflist.begin(), difflist.end(),
      seeds.begin(),
      extract_seed);
}

int main()
{
  strlist_t seeds;
  seeds.reserve(INIT_SIZE);
  // 1:
  std::generate_n(
      std::back_inserter(seeds),
      INIT_SIZE,
      gen_seed );
  // 2:
  sort_seeds(seeds);

  std::size_t generation = 0;
  while ( 1 )
  { // 3:
    strlist_t new_seeds;
    new_seeds.reserve(INIT_SIZE*MULTI_NUM);
    for ( strlist_t::const_iterator it = seeds.begin();
        it != seeds.end(); ++it )
      for ( int i = 0; i < MULTI_NUM; ++i )
        new_seeds.push_back(
            std::string(*it)
              .replace(std::rand()%it->size(), 1, 1, gen_char()));
    seeds.swap(new_seeds);
    // 4:
    sort_seeds(seeds);
    seeds.erase(seeds.begin()+INIT_SIZE, seeds.end());

    std::cout << std::setw(4) << ++generation <<
      " : \"" << seeds.front() << "\"\n";
    if ( seeds.front() == GOAL )
      break;
  }

  return 0;
}

変異数：５。変異の仕方が文字列のどこか一文字をほかの文字と置き換える操作なので、スコアは正しい文字が正しい位置に何文字あるかで計算しています。

乱数生成がIOな関係上、やたらとIOな関数がいっぱい出てくるコードになっちゃいました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
module Main where

import System.Random
import Data.Array.IArray
import Data.List
import Data.Function
import Data.Ord

goal    = "METHINKSITISAWEASEL"
score str = length $ filter (id) $ zipWith (==) str goal

updateRandom :: (Array Int Char) -> IO (Array Int Char)
updateRandom rg = do
    ch <- randChar
    i <- randPos
    return $ rg // [(i, ch)]

genRandStr :: IO (Array Int Char)
genRandStr = do
    str <- sequence $ replicate (length goal) (randChar)
    return $ listArray (0, length goal - 1) str

randChar= getStdRandom $ randomR ('A', 'Z')
randPos = getStdRandom $ randomR (0, (length goal) - 1)

sortIt :: [Array Int Char] -> [Array Int Char]
sortIt = sortBy (\x y -> inverse $ (comparing (score.elems) x y))
    where 
        inverse GT = LT
        inverse EQ = EQ
        inverse LT = GT

mutate :: [Array Int Char] -> IO [Array Int Char]
mutate strs = do
    strs' <- mapM (updateRandomN 5) strs
    return $ concat strs'
    where
        updateRandomN :: Int -> Array Int Char -> IO [Array Int Char]
        updateRandomN n str = mapM (updateRandom) $ replicate n str    

genMutation :: Int -> [Array Int Char] -> IO [Array Int Char]
genMutation i strs = do
    strs' <- mutate strs    
    return $ take 300 $ sortIt strs'

doCycle :: Int -> [Array Int Char] -> IO ()
doCycle i strs = do
    putStrLn $ (show i) ++ "th iteration:" ++ (elems $ head strs) ++ " : " 
        ++ (show $ score $ elems $ head strs)
    if (elems $ head strs) == goal then print "goal reached"
        else genMutation i strs >>= doCycle (i + 1)

main :: IO()
main = do
    strs <- sequence $ replicate 300 genRandStr
    doCycle 0 $ sortIt strs

PostScript で素直に実装してみたのですが、 なかなか収束しないので皆さんと同様、 5個のバリエーションを生成、元の文字列も 残す方向です。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
%!PS
% ---- Parameters ----------------------------------
/String (ABCDEFGHIJKLMNOPQRSTUVWXYZ) def
/Target (METHINKSITISAWEASEL) def
/NumStrings 300 def
/NumMutations 5 def
/Keep true def
% ---------------------------------------------------


/TargetLength Target length def
/StringLength String length def


/RandomLetter {
    String rand StringLength mod get
} bind def

/Diff { % (TargetString) (string) Diff  (TargetString) (string)  integer
    0
    0 1 TargetLength 1 sub {
    % (str) (tar) sum count
    dup 4 index exch get
    % (str) (tar) sum count  let
    exch 3 index exch get
    % (str) (tar) sum count  let let2
%    sub abs add   
%    sub dup mul add   
    sub 0 ne { 1 add } if
    } for
} bind def


/GenStrings { % NumStrings TargetLength GenStrings [(String1) ... (String N)]
    exch
    [ 3 1 roll
    % [ Len Num
    {
        % [ Len
        dup dup string exch
        % [ Len (Str) Len
        0 1 3 -1 roll 1 sub {
        % [ Len (Str) count
        1 index exch RandomLetter put
        } for
        exch
    } repeat
    pop
    ]
} bind def

/CalcDistance { % (TargetString) (String) CalcDistance (Target) [dist (str)]
    Diff exch 2 array astore
} bind def

/Sort { % [[x y] [x1 y1] Array Data ] Sort [ArrayData]
    [ exch
    aload length
    % func -mark- [] [] [] [] [] len
    -1 2 { % func -mark- [] [] [] [] [] len2
    -1 2 {
        3 1 roll
        2 copy 0 get exch 0 get sub
        0 gt { exch } if
        3 -1 roll
        1 roll
    } for
    counttomark 1 roll
    } for
    counttomark 1 roll
    ] 
} bind def

/Mutation { % (String)  Mutation  (String')
    dup dup length rand exch mod RandomLetter put
} bind def



NumStrings TargetLength GenStrings
[ exch Target exch {
    CalcDistance exch
} forall pop ]
Sort

{
[ exch {
    1 get
    % (str)
    NumMutations {
    % (str) (str') (str') 0
    dup length string dup 0 3 index putinterval
    Mutation
    } repeat
    Keep not { NumMutations 1 add -1 roll pop } if
} forall ]
[ exch Target exch {
    CalcDistance exch
} forall pop ]
Sort
0 NumStrings getinterval
dup 0 get dup == flush
0 get 0 eq {quit} if
} loop

　ちょっと遅いですが...。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#! /usr/bin/ruby
    
class Text
    
    GOAL        = 'METHINKSITISAWEASEL'
    CHARACTER_SET = ('A'..'Z').to_a
    
    attr_accessor :text
    
    def create
        self.text = (1..GOAL.length).map { |_| CHARACTER_SET[rand(CHARACTER_SET.length)] }.to_s
        self
    end
    
    def update
        self.text[rand(GOAL.length)] = CHARACTER_SET[rand(CHARACTER_SET.length)]
        self
    end
    
    def rank
        self.text.split('').zip(GOAL.split('')).inject(0) { |r,s| s[0] == s[1] ? r + 1 : r }
    end
    
    def complete?
        self.rank == GOAL.length
    end
    
    def clone
        copy = super
        copy.text = self.text.clone
        copy
    end
end

class Processor
    
    POOL_SIZE    = 300
    COPY_SIZE    = 3
    
    attr_accessor :text_list
    
    def initialize
        self.text_list = (1..POOL_SIZE).map { |_| Text.new.create }.sort { |a,b| b.rank <=> a.rank }
        self
    end
    
    def process
        self.text_list = self.text_list.map { |t| (1..COPY_SIZE).map { |_| t.clone.update } }.flatten.sort { |a,b| b.rank <=> a.rank }.first(POOL_SIZE)
        self
    end
    
    def complete?
        self.text_list.first.complete?
    end
end

i = 1
processor = Processor.new
until processor.complete? do
    puts "process(#{i}): #{processor.text_list.first.text}(#{processor.text_list.first.rank})"
    processor.process
    i = i + 1
end
puts "complete(#{i}): #{processor.text_list.first.text}"

　プロセスと乱数の相性が悪い様なのでちょっとべたですが。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
-module(methinks_it_is_a_weasel).
-import(io).
-import(lists).
-import(random).
-export([start/0]).

get_char(CS) -> lists:nth(random:uniform(length(CS)),CS).

create(T,_,TS) when TS == 0 -> T;
create(T,CS,TS) -> create([get_char(CS)|T],CS,TS-1).
create(CS,TS) -> create("",CS,TS).

create_text_list(TL,_,_,S) when S == 0 -> TL;
create_text_list(TL,CS,TS,S) -> create_text_list([create(CS,TS)|TL],CS,TS,S-1).
create_text_list(CS,TS,S) -> create_text_list([],CS,TS,S).

rank(T,G) ->
    lists:foldl(
        fun({CT,CG},A) ->
            A +
            if
                CT == CG -> 1;
                true -> 0
            end
        end,
        0,
        lists:zip(T,G)
    ).

sort_text_list(TL,G) -> lists:sort(fun(A,B) -> rank(A,G) > rank(B,G) end,TL).

update_text(T,CS) ->
    P = random:uniform(length(T)),
    lists:append(lists:sublist(T,P-1),[get_char(CS)|lists:sublist(T,P+1,length(T)-P)]).

update_text_list(TL,G,CS,S,N) ->
    lists:sublist(
        sort_text_list(
            lists:foldl(
                fun(T,A) ->
                    lists:append(
                        A,
                        lists:map(
                            fun(_) ->
                                update_text(T,CS)
                            end,
                            lists:seq(1,N,1)
                        )
                    )
                end,
                [],
                TL
            ),
            G
        ),
        S
    ).

process([T|TL],G,CS,S,N,I) ->
    R = rank(T,G),
    L = length(G),
    if
        R == L ->
            io:format("goal(~w):~p~n",[I,T]);
        true ->
            io:format("process(~w):~p(~w)~n",[I,T,rank(T,G)]),
            process(update_text_list([T|TL],G,CS,S,N),G, CS, S, N, I+1)
    end.

start() ->
    G = "METHINKSITISAWEASEL",
    CS = lists:seq($A,$Z,1),
    S = 300,
    N = 5,
    process(sort_text_list(create_text_list(CS,length(G),S),G),G,CS,S,N,1).


愚直に実装。収束させるために派生文字列を10個に増やしました。大体50-100世代辺りで目的の文字列が作れるようです。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
let target = [
  'M'; 'E'; 'T'; 'H'; 'I'; 'N'; 'K'; 'S';
  'I'; 'T'; 'I'; 'S'; 'A'; 'W'; 'E'; 'A'; 'S'; 'E'; 'L';
];;

let similarity str =
  List.fold_left2 (fun n target' str' ->
    n + abs ((Char.code target') - (Char.code str'))
  ) 0 target str
;;

let compare' a b = compare (similarity a) (similarity b);;

let random_char () = Char.chr (65 + (Random.int 26));;

let rec random_string list = function
  | 0 -> list
  | _ as n -> random_string (random_char () :: list) (n-1)
;;

let rec create_initial_list list = function
  | 0 -> list
  | _ as n -> create_initial_list ((random_string [] 19) :: list) (n-1)
;;

let change str =
  let i = Random.int 19 and c = random_char () in
  let _, res = List.fold_left (fun (i', res) c' ->
    if i = i' then i'+1, c::res else i'+1, c'::res
  ) (0, []) (List.rev str) in res
;;

let print_result n str =
  Printf.printf "G%d: " n;
  List.iter (fun c -> print_char c) str;
  Printf.printf " (%d)" (similarity str);
  print_newline ()
;;

let rec generation n list =
  let sorted =
    List.sort compare' (List.flatten (List.map (fun str ->
      [change str; change str; change str; change str; change str;
       change str; change str; change str; change str; change str;]
    ) list))
  in
  let _, res = List.fold_left (fun (i, res) str ->
    if i < 300 then i+1, res @ [str] else i, res
  ) (0, []) sorted in
  print_result n (List.hd res);
  if (similarity (List.hd res)) > 0 then
    generation (n+1) res
  else
    print_endline "Finished."

let main =
  Random.self_init ();
  let list = create_initial_list [] 300 in
  generation 0 list


派生文字列の生成方法を３パターン作ってみました。
これなら収束します。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
(use srfi-1)
(use srfi-27)

(define GOAL "METHINKSITISAWEASEL")

(random-source-randomize! default-random-source)

(define random-char (lambda ()
  (let ((str "ABCDEFGHIJKLMNOPQRSTUVWXYZ"))
    (string-ref str (random-integer (string-length str))))))

(define make-element (lambda ()
  (let loop ((n (string-length GOAL)) (ret '()))
    (if (<= n 0)
      (list->string ret)
      (loop (- n 1) (cons (random-char) ret))))))

(define make-element-list (lambda ()
  (let loop ((n 300) (ret '()))
    (if (<= n 0) ret
      (loop (- n 1) (cons (make-element) ret))))))

(define check-element (lambda (e)
  (fold + 0 (map
    (lambda (x y) (abs (- (char->integer x) (char->integer y))))
    (string->list e)
    (string->list GOAL)))))

(define sort-element-list (lambda (ls)
  (sort ls (lambda (x y) (< (check-element x) (check-element y))))))

(define make-mutant-1 (lambda (e)
  (let ((mutant (string-copy e)))
    (string-set! mutant (random-integer (string-length e)) (random-char)))))

(define make-mutant-2 (lambda (e)
  (let* ((mutant (string-copy e))
         (i (random-integer (string-length e)))
         (ci (- (char->integer (string-ref e i)) 1)))
    (string-set! mutant i
      (if (< ci (char->integer #\A)) #\Z (integer->char ci))))))

(define make-mutant-3 (lambda (e)
  (let* ((mutant (string-copy e))
         (i (random-integer (string-length e)))
         (ci (+ (char->integer (string-ref e i)) 1)))
    (string-set! mutant i
      (if (< (char->integer #\Z) ci) #\A (integer->char ci))))))

(define main (lambda (args)
  (let loop ((count 0) (ls (sort-element-list (make-element-list))))
    (print count ":" (car ls))
    (if (string=? (car ls) GOAL)
      (begin (display "OK!") (newline))
      (loop (+ count 1)
        (take (sort-element-list
          (fold
            (lambda (x ret)
              (cons (make-mutant-1 x)
              (cons (make-mutant-2 x)
              (cons (make-mutant-3 x)
                ret))))
            '() ls)) 300))))
  0))

Gauche で書きました。他の方も書いていらっしゃるように単純に変異を起こすだけでは n = 3 ではなかなか収束しません。上位のものを交叉するなどの工夫が必要でしょう。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
(use srfi-1)
(use srfi-27)
(use srfi-42)
(use srfi-43)

(define random-upper-alphabet
  (let* ((s "ABCDEFGHIJKLMNOPQRSTUVWXYZ")
         (n (string-length s)))
    (lambda ()
      (string-ref s (random-integer n)))))

(define (mutate v)
  (let ((v* (vector-copy v)))
    (vector-set! v* (random-integer (vector-length v)) (random-upper-alphabet))
    v*))

(define (similarity v1 v2)
  (vector-fold (lambda (_ knil c1 c2)
                 (+ knil (if (char=? c1 c2) 1 0)))
               0 v1 v2))

(define (sort-by xs f)
  (map car (sort (map (lambda (x) (cons x (f x))) xs)
                 (lambda (a b) (negative? (compare (cdr a) (cdr b)))))))

(define (main args)
  (random-source-randomize! default-random-source)
  (let ((goal (list->vector (string->list "METHINKSITISAWEASEL"))))
    (let search ((candidates
                  (list-tabulate 300
                                 (lambda (_) 
                                   (vector-ec (: _ (vector-length goal))
                                              (random-upper-alphabet))))))
      ;#?=(similarity (car candidates) goal)
      (if (equal? (car candidates) goal)
          0
          (search
           (take (sort-by
                  (append-map! (lambda (v)
                                 (list-ec (: _ 3) (mutate v)))
                               candidates)
                  (lambda (v)
                    (- (similarity v goal))))
                 300))))))

Rの投稿をしておきながら、実はこういうシミュレーションをRでやったことはなかったのですが・・・面白いですね！

Windows版Rでは、グラフィカルなコンソール(Rgui)はコンソール出力のオーバーヘッドがものすごく大きいので、テキストベースのコンソール(Rterm)の方で実行するのをお勧めします。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# initial value
target      <- "METHINKSITISAWEASEL"
target.char <- unlist(strsplit(target, ""))
target.len  <- nchar(target)
initial.population <- 300
mutation.number    <- 1
increase.number    <- 3

# make mutation
mutation <- function(s){
   l <- unlist(strsplit(s, ""))
   l[sample(target.len, mutation.number)] <- sample(LETTERS, mutation.number, replace=FALSE)
   paste(l, collapse="")
}

# calc distance between two strings
distance <- function(lhs, rhs=target.char){
   sum(!(unlist(strsplit(lhs, "")) == rhs))
}

# setup the first population
strings <- replicate(initial.population, paste(sample(LETTERS,target.len, replace=FALSE), collapse=""))

# main routine
while(strings[1] != target){
   strings <- sapply(rep(strings, increase.number), mutation)
   strings <- head(strings[sort.list(sapply(strings, distance))], initial.population)
   print(data.frame(str=head(strings), dist=sapply(head(strings), distance)))
}


やればできる子でした＜Vim
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
:function! s:Random(n)
: if has('win32')
:   let r = libcallnr("msvcrt", "rand", 0)
: else
:   let r = libcallnr("libc", "rand", 0)
: endif
: return r % a:n
:endfunction

:function! s:MakeRandom()
: let res = ''
: for i in range(strlen(s:goal))
:   let res = res . nr2char(char2nr('A')+s:Random(26))
: endfor
: return res
:endfunction

:function! s:CheckScore(line, goal)
: let score = 0
: for i in range(strlen(a:goal))
:   let a = char2nr(strpart(s:goal,i,1))
:   let b = char2nr(strpart(a:line,i,1))
:   let d = a < b ? b - a : a - b
:   let score = score + d
: endfor
: return score
:endfunction

:function! s:SortLines(num)
: for i in range(a:num)
:   let line = getline(i+1)
:   let score = s:CheckScore(line, s:goal)
:   let line = printf("%05d:%s", score, line)
:   call setline(i+1,line)
: endfor
": %!sort
: let lines = sort(getline(1,a:num))
: for i in range(a:num)
:   call setline(i+1,strpart(lines[i],6,strlen(s:goal)))
: endfor
:endfunction

:function! s:ChangeLine(line_num, idx_num, var_num)
: for i in range(a:line_num)
:   let line = getline(i+1)
:   for j in range(a:var_num)
:     let vline = line
:     for k in range(a:idx_num)
:       let split_idx = s:Random(strlen(s:goal))
:       let head = strpart(vline,0,split_idx)
:       let tail = strpart(vline,split_idx+1,strlen(s:goal))
:       let vline = head .nr2char(char2nr('A')+s:Random(26)) . tail
:     endfor
:     call setline(a:line_num*(j+1)+i,vline)
:   endfor
: endfor
:endfunction

:let s:initial_line_num = 300
:let s:change_idx_num = 1
:let s:variaty_num = 5
:let s:goal = "METHINKSITISAWEASEL"

:let s:start_time = localtime()
:new
:for s:i in range(s:initial_line_num)
: call setline(s:i+1, s:MakeRandom())
:endfor
:call s:SortLines(s:initial_line_num)

:let s:break_flag = 0
:while s:break_flag == 0
: call s:ChangeLine(s:initial_line_num,s:change_idx_num,s:variaty_num)
: call s:SortLines(s:initial_line_num * s:variaty_num)
: let s:line = getline(1)
: if s:line ==# s:goal
:   let s:break_flag = 1
: endif
: echo getline(1)
:endwhile
:1
:let s:end_time = localtime()
:call append(0, (s:end_time - s:start_time) . " seconds elapsed")


PHP練習中。
言語の練習にはいい問題だった。
配列周りのバグが出まくり。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
<?php
print <<< END_DOC
<HTML>
<HEAD><title>doukaku177</title>
</HEAD><BODY>
END_DOC;

$answer = str_split("METHINKS IT IS A WEASEL");
$alphabet_table = str_split(" ABCDEFGHIJKLMNOPQRSTUVWXYZ");

function getLength($targetString)
{
    $length = 0;
    global $answer;
    
    for($i = 0; $i < count($answer); $i++){
        $length += abs(ord($answer[$i]) - ord($targetString[$i]));
    }
    
    return $length;
}

function cmp($a, $b)
{
    return $a["length"] - $b["length"];
}

function doukaku177()
{

    global $answer;
    global $alphabet_table;
    
    #init        
    $string_pool = array();
    $string_pool_max = 900;
    
    for($i = 0; $i < $string_pool_max; $i++){
        $s = array();
        for($j = 0; $j < count($answer); $j++){
            array_push($s, $alphabet_table[mt_rand(0, count($alphabet_table)-1)]);
        }        

        $length = getLength($s);
        $s["length"] = $length;
        array_push($string_pool, $s);
    }    
    
    #evolve
    $i=0;
    do{        
        usort($string_pool, "cmp");
        
        #show top
            print "Generation = $i ";
            print "Str = ".join("",$string_pool[0])."<BR>";
        
        $string_pool = array_slice($string_pool, 0, $string_pool_max / 3);
        
        foreach($string_pool as $item){
            unset($item["length"]);
            $item[mt_rand(0, count($item)-1)] = $alphabet_table[mt_rand(0, count($alphabet_table)-1)];
            $length = getLength($item);
            $item["length"] = $length;
            array_push($string_pool, $item);
        }
        
        $i++;
    }while($string_pool[0]["length"]);
}

doukaku177();

print <<< END_DOC
</BODY>
</HTML>
END_DOC;
?>

素朴に書いてみました。

Ruby-1.8.x系だと滅茶苦茶遅いですが、Ruby-1.9.1だと阿呆みたいに速くなりますね……。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
TARGET = "METHINKSITISAWEASEL".split("")

class Array
  def choice
    self[rand(self.size)]
  end
end

def rand_char
  ('A'..'Z').to_a.choice
end

def gen
  (1..300).map{ (1..TARGET.size).inject(""){|r,s|r+=rand_char()} }
end

def weasel_sort(arr)
  arr.sort_by{|s| rank = 0;s.each_char.with_index{|c, i|;rank += 1 if c != TARGET[i]};rank}
end

def evolve(arr)
  arr.map{|word| (1..10).map{ t=word.dup;i = rand(word.size);t[i]=rand_char;t}}.flatten
end

def generate_passage
  rc = gen
  i = -1
  until rc[0].split("") == TARGET
    i += 1
    rc = evolve rc
    rc = weasel_sort rc
    rc = rc[0..299]
    puts "generation #{i}: ", "\t" + rc[0..5].join(" ")
  end
  return i
end

if $0 == __FILE__
  TARGET = ARGV.fetch(0, "METHINKSITISAWEASEL").upcase.split("")
  generate_passage()
end

作ってはみたものの、metaClassを多用したせいなのかロジックが悪いのか、遅い・・・

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#!/usr/bin/env groovy
final RANDOM = new Random()
final TARGET = "METHINKSITISAWEASEL"
final WORDS_COUNT = 300

final CHARS = "A".."Z"
CHARS.metaClass.random = {
    delegate[RANDOM.nextInt(delegate.size())]
}
String.metaClass.define{
    getDiff{
        def d = 0
        for( def i in 0..<delegate.size() ){
            d += Math.abs(TARGET[i] <=> delegate[i])
        }
        d
    }
    getNewWord{
        def clist = delegate.chars as List
        clist[RANDOM.nextInt(clist.size())] = CHARS.random()
        clist.join("")
    }
}
def words = []

WORDS_COUNT.times{
    def chars = []
    for( def i in 0..<TARGET.size() ){
        chars << CHARS.random()
    }
    words << chars.join("")
}

while( words[0] != TARGET ){
    words = (words * 3)*.newWord.sort{
        it.diff
    }[0..<WORDS_COUNT]
    println words[0]
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]