遊び tokidoki 仕事

数学と音楽と教育と遊び

Top | おしごと | ゼミ | がくせい | すうがく | かがく | きょういく | おんがく | おきにー | Tips | Photo | イベント | ものもう | あれこれ | About

素朴なGA

今年のゼミ生の卒論の一つで遺伝的アルゴリズム(GA)についての
素朴な考察を行った。
その際、実際にどれほど有効なものなのか見ようと、
BASICアルゴリズムを組んでみた。
遺伝子長は4で長さ2に固定した2点交叉
(つまり連続した2遺伝子を両親の間で交換する)
のみで、突然変異などはない。
各染色体が親として選ばれる確率は適合度関数に比例させてある。
下の図は区間[0,1]を16等分して各区間を長さ4の染色体で対応させ
[0,1]区間上の正値関数をそのまま適合度関数にとった。
例えば

f(x)=30x(x-0.3)(x-0.6)(x-0.8)(1-x)+0.5

は染色体が対応している座標7/16=[0111]と15/16=[1111]で
きわめて近い値で極大値となっているが
僅かにf(7/16)>f(15/16)となっている。
(f(7/16)/f(15/16)=1.01412...)
実行結果の以下の図を見ると初めは染色体[1111]も
それなりの確率を持っているが、
400代ほど世代交代をさせると[0111]に確率が集中してくる。


う〜ん、面白い。
どうやら、引き伸ばしと折りたたみの仕組みが
働いているようだ。






10進BASICプログラム→[ga00.bas]


REM [GA00.bas]
REM Genetic Argorithm
REM 遺伝子長=4, 交叉長=2

!DEF f(x)=4*x*(1-x) ! 適合度関数
!DEF f(x)=30*x*(x-.5)*(x-.5202314098)*(1-x)+.2 ! 適合度関数
DEF f(x)=30*x*(x-.3)*(x-.6)*(x-.8)*(1-x)+.5 ! 適合度関数
!DEF f(x)=EXP(-(x-.5)^2/.002) ! 適合度関数
LET win=.02 ! windowの余白
LET L=4 ! 遺伝子長
LET pt=2^L ! 遺伝子パターン数
LET dx=1/pt
OPTION BASE 0
DIM g$(pt) ! 遺伝子名(Binary)
DIM p(pt),q(pt),a(pt),aaoo(pt),ooaa(pt),aooa(pt),oaao(pt)

REM 【初期確率、適合度値】
FOR k=0 TO 15
LET q(k)=1/pt
LET p(k)=0
LET a(k)=f(k*dx)
NEXT k

REM 【交叉パターンの設定】

DIM g1(4,4),g2(4,4),g3(4,4),g4(4,4)
FOR j=0 TO 3
FOR i=0 TO 3
LET g1(j,i)=j*4+i
LET g2(j,i)=j+i*4
LET g3(j,i)=INT(j/2)*8+MOD(j,2)+i*2
LET g4(j,i)=j*2+INT(i/2)*8+MOD(i,2)
NEXT i
NEXT j
FOR k=0 TO 15
LET aaoo(k)=INT(k/4)
LET ooaa(k)=MOD(k,4)
LET aooa(k)=INT(k/8)*2+MOD(k,2)
LET oaao(k)=INT(MOD(k,8)/2)
NEXT k

REM 【適合度関数の表示】

SET VIEWPORT win, 1-win, .5+win, 1-win
SET WINDOW -.05,1.05,-.1,1.1
SET TEXT COLOR 8
PLOT TEXT ,AT 0,1:"適合度関数"
SET TEXT font "Times New Roman Italic",7
DRAW grid0(dx,.5)

SET LINE COLOR 2
SET LINE width 2
FOR x=0 TO 1 STEP dx
PLOT LINES : x,f(x);
NEXT x
FOR k=0 TO pt-1
FOR i=L TO 1 STEP -1
LET g$(k)=g$(k)&STR$(INT(MOD(k,2^i)/2^(i-1)))
NEXT i
PLOT TEXT ,AT k*dx,-.05*(MOD(k,2)+1):g$(k)
NEXT k

REM 【遺伝子存在率のヒストグラム

SET VIEWPORT win, 1-win, win, .5-win
SET WINDOW -.05,1.05,-.1,1.1
SET LINE width 1
SET TEXT font "MS ゴシック",11
PLOT TEXT ,AT 0,1:"各遺伝子パターンの存在確率"
SET TEXT font "Times New Roman Italic",7
DRAW grid0(dx,.5)
PLOT TEXT ,AT -.03,1:"1.0"
PLOT TEXT ,AT -.03,.5:"0.5"
FOR k=0 TO pt-1
PLOT TEXT ,AT k*dx,-.05*(MOD(k,2)+1):g$(k)
NEXT k

INPUT PROMPT "世代数=":gen
LET gstep=INT(gen/10)

REM 【交叉計算とヒストグラム表示】

SET LINE COLOR 10

FOR t=1 TO gen
LET S=0
FOR k=0 TO 15
LET S=S+a(k)*q(k)
NEXT k
FOR k=0 TO 15
LET p(k)=a(k)*q(k)/S
NEXT k
LET p1=0
LET p2=0
LET p3=0
LET p4=0
FOR k=0 TO 15
LET p1=p(g1(aaoo(k),0))+p(g1(aaoo(k),1))+p(g1(aaoo(k),2))+p(g1(aaoo(k),3))
LET p2=p(g2(ooaa(k),0))+p(g2(ooaa(k),1))+p(g2(ooaa(k),2))+p(g2(ooaa(k),3))
LET p3=p(g3(aooa(k),0))+p(g3(aooa(k),1))+p(g3(aooa(k),2))+p(g3(aooa(k),3))
LET p4=p(g4(oaao(k),0))+p(g4(oaao(k),1))+p(g4(oaao(k),2))+p(g4(oaao(k),3))
LET q(k)=(p1*p2+p3*p4)/2
NEXT k

IF MOD(t,gstep)=0 OR t=gen THEN
SET COLOR MIX(10) (1-t/gen)/2,(1-t/gen)/2+.5,t/gen
FOR k=0 TO 15
PLOT LINES : k*dx,q(k);
NEXT k
PLOT lines
END IF

NEXT t
END