47 lines
1.0 KiB
Plaintext
47 lines
1.0 KiB
Plaintext
target="METHINKS IT IS LIKE A WEASEL";
|
|
fitness(s)=-dist(Vec(s),Vec(target));
|
|
dist(u,v)=sum(i=1,min(#u,#v),u[i]!=v[i])+abs(#u-#v);
|
|
letter()=my(r=random(27)); if(r==26, " ", Strchr(r+65));
|
|
insert(v,x=letter())=
|
|
{
|
|
my(r=random(#v+1));
|
|
if(r==0, return(concat([x],v)));
|
|
if(r==#v, return(concat(v,[x])));
|
|
concat(concat(v[1..r],[x]),v[r+1..#v]);
|
|
}
|
|
delete(v)=
|
|
{
|
|
if(#v<2, return([]));
|
|
my(r=random(#v)+1);
|
|
if(r==1, return(v[2..#v]));
|
|
if(r==#v, return(v[1..#v-1]));
|
|
concat(v[1..r-1],v[r+1..#v]);
|
|
}
|
|
mutate(s,rateM,rateI,rateD)=
|
|
{
|
|
my(v=Vec(s));
|
|
if(random(1.)<rateI, v=insert(v));
|
|
if(random(1.)<rateD, v=delete(v));
|
|
for(i=1,#v,
|
|
if(random(1.)<rateM, v[i]=letter())
|
|
);
|
|
concat(v);
|
|
}
|
|
evolve(C,rate)=
|
|
{
|
|
my(parent=concat(vector(#target,i,letter())),ct=0);
|
|
while(parent != target,
|
|
print(parent" "fitness(parent));
|
|
my(v=vector(C,i,mutate(parent,rate,0,0)),best,t);
|
|
best=fitness(parent=v[1]);
|
|
for(i=2,C,
|
|
t=fitness(v[i]);
|
|
if(t>best, best=t; parent=v[i])
|
|
);
|
|
ct++
|
|
);
|
|
print(parent" "fitness(parent));
|
|
ct;
|
|
}
|
|
evolve(35,.05)
|