Re: 遺伝的アルゴリズムで関数の最大値を求める投稿者：山中和義 投稿日：2013年 6月 1日(土)06時10分40秒 |
|
> No.3069[元記事へ] 島村1243さんへのお返事です。 チムセーさんが不在のようなので、代わりに回答します。 > 珍しい方法ですが、方法の名称は有るのでしょうか？ ●遺伝的アルゴリズム（Genetic Algorithm、GA）で関数の最大値を求める問題 複雑な関数、特に山がいくつもあるような関数y=f(x)の最大値を数値的に求める。 適応度は関数f(x)の値、染色体（個体）の表現型は実数xとなる。 染色体の遺伝子型は、実数xをビット配列で表したものとなる。 最大値が入っていそうな区間0≦x＜aを定める。 解の精度を定め、染色体の長さNを決める。a/2^Nの精度で解が求まることになる。 > 最大値を求めたい関数を指定する箇所は下記「DEF f(x)」でしょうか？ そうですね。 y=f(x)のグラフを描いてみました。 DEF f(x)=SIN(3*x)+0.5*SIN(9*x)+SIN(15*x+50) SET WINDOW -1,3,-2,2 DRAW grid(0.5,0.5) FOR x=-1 TO 3 STEP 1/2^8 PLOT LINES: x,f(x); NEXT x PLOT LINES END > また、最大値が得られるXの値を知るにはどこで「print x」を記述すれば良いでしょうか？ xはIN(,)より、P1番目が候補で10ビットなので、 END文の前に、 LET m=0 FOR n=1 TO 10 LET T=IN(P1,n) LET m=m+T*2^(n-1) NEXT n PRINT "x="; m/1024 END または、 LET m=0 FOR n=10 TO 1 STEP -1 LET m=m*2+IN(P1,n) NEXT n PRINT "x="; m/1024 END とすればよいと思います。 補足 本プログラムの解析 非負整数のみの処理なので、0≦x＜1の範囲ですね。 染色体の長さは10ビットなので、1024分割になります。 次の世代の10個体について ・選択淘汰は、エリート選択による適応度がベスト1,2の2個体 ・上記の2個体を親として、染色体の各々の遺伝子について0.1の確率で交叉させた8個体 ・突然変異は、染色体の各々の遺伝子について0.05の確率でビットの0,1を反転させる。 私もサンプルをつくってみました。 交叉は、Aaに対して（2進法で見ると）Ab,Acは近傍を表すので、山登り法に相当します。 また、突然変異は、特に上位ビットが変わればDb,Dcなので、焼きなまし法に相当します。 !遺伝的アルゴリズム（Genetic Algorithm、GA）で関数の最大値を求める問題 RANDOMIZE DEF F(x)=SIN(3*x)+0.5*SIN(9*x)+SIN(15*x+50) !適応度 LET N=10 !染色体の長さ LET M=9 !個体数 ※Mは3以上 DIM X(M) !個体 FOR i=1 TO M !第0世代 LET X(i)=INT(RND*2^N) !x=[0,1)を2^N分割 NEXT i MAT PRINT x; !debug DIM NX(M) !次の世代 FOR t=1 TO 2000 !世代交代を進めて進化させる !選択淘汰（Selection） !※エリート選択による適応度がベスト1,2,3（一番大きな数から順に3つ）の3個体 LET A=-99999 !1番目 値は-∞ LET B=A !2番目 LET C=A !3番目 FOR i=1 TO M LET W=F(X(i)/2^N) !関数f(x)の値 IF W>A THEN LET C=B !降格 LET XC=XB LET B=A LET XB=XA LET A=W !ベスト1 LET XA=i ELSE IF W>B THEN LET C=B !降格 LET XC=XB LET B=W !ベスト2 LET XB=i ELSE IF W>C THEN LET C=W !ベスト3 LET XC=i END IF END IF END IF NEXT i !!!PRINT XA;A; XB;B XC;C !debug LET NX(1)=X(XA) LET NX(2)=X(XB) LET NX(3)=X(XC) !上記の3個体を親として、各々の染色体について交叉（Cross Over）させた6個体 !※親Aa,Bb → 子Ab,Ba 親Aa,Cc → 子Ac,Ca 親Bb,Cc → 子Bc,Cb LET p=2^INT(N/2) !1点交叉法（上位と下位） LET NX(4)=INT(NX(1)/p)*p+MOD(NX(2),p) !Ab LET NX(5)=INT(NX(2)/p)*p+MOD(NX(1),p) !Ba LET NX(6)=INT(NX(1)/p)*p+MOD(NX(3),p) !Ac LET NX(7)=INT(NX(3)/p)*p+MOD(NX(1),p) !Ca LET NX(8)=INT(NX(2)/p)*p+MOD(NX(3),p) !Bc LET NX(9)=INT(NX(3)/p)*p+MOD(NX(2),p) !Cb FOR i=1 TO M !次の世代へ LET X(i)=NX(i) !各々の染色体について0.01の確率で遺伝子を変異させる !※1つのビットの0,1を反転させる IF RND<0.01 THEN LET X(i)=bitreverse(INT(RND*N),X(i)) !突然変異（Mutation） NEXT i NEXT t MAT PRINT x; !debug LET x0=X(1)/2^N !進化の結果 PRINT "x=";x0; " f(x)=";f(x0) !検算 x=.140792279664446 f(x)=1.84931356430434 END !UBASIC ビット演算関連より EXTERNAL FUNCTION bitreverse(n,x) !n番目のビットを反転する ※n,xは非負整数 LET d=2^n !n桁 LET a=INT(x/d) LET bitreverse=(INT(a/2)*4-a+1)*d+MOD(x,d) !大きい桁＋NOT＋小さい桁 END FUNCTION 
|