[PR]当サイトはアフィリエイト広告を利用しています。
はじめに
このブログではエクセルソルバーとか、オペレーションズ・リサーチとかを扱ってきました。
ご訪問いただく方々の中には数理最適化にご興味のあるかたもいらっしゃるかと思います。
そこで最適化手法の中の「進化計算」、その中でも基本となる
「遺伝的アルゴリズム(GA)」
を対象に最適化手法に関して入門的な記事を書いてみることにしました。
遺伝的アルゴリズムって難しそう…
やってることがわかれば簡単…かも？ルーレット選択のところが難しいかな。
最適化って結局何をやっているのか、その感覚がつかめれば幸いです。
なお、今回は遺伝的アルゴリズムの概要で結構なボリュームになってしまったので、プログラミングは別記事で紹介しています。
遺伝的アルゴリズムの活用例は以下をご覧ください。
なぜ遺伝的アルゴリズムなのか
なぜ遺伝的アルゴリズム(GA)なのかというと、実装が簡単だからです。
微分して傾きを求める系の手法は、色々な条件と行列計算を駆使して最終的にこれまた微分系の値がこうなったら終了、みたいなことをします。
条件の理解にかなりの大学数学の知識が必要で、これを目で追っていくと、本が数冊書けてしまいます。
しかも前提条件として大学の数学の様々な科目が必要となり、ここから解説していくと数年かかってしまいます。
しかしながら遺伝的アルゴリズムなら、やっていることが単純で色々な問題が解けるので、入門の最適化手法にはちょうどいいと思います。
その分たくさん計算時間がかかりますが、入門でちょっとした問題を解くなら十分です。
他の手法よりは”まし”ってこと？
そうだね。コンピュータで微分を駆使するのは大変だからね。遺伝的アルゴリズムは微分とか使わないんだ。
それでは始めていきましょう。
問題設定
次の問題の、-5<=x1,x2,x3<=5のときの最小値とそのときの変数の値を求めよ。
y=x1×x1+x2×x2+x3×x3
いきなり式が出てきてびっくりだよ
最適化って基本的に何か式があって、それを最小にするパターンを見つけることだからね。
元の式y=x1×x1+x2×x2+x3×x3のことを目的関数というよ。
x1、x2、x3のことを変数というよ。目的関数が最適（最小）になる変数のパターンを見つけるんだ。
-5<=x1,x2,x3<=5のことを制約条件というよ。
この最適解（最小の値を取るときの変数の値）は
x1,x2,x3=0
y=0
となります。
単純な放物線が三次元になっただけの問題です。
y=x^2って中学校で出てくる式だね。
うん、今回はそれが3次元になった式だよ。答えは全部の変数が0になるときだよ。
遺伝的アルゴリズムの中身を体験
それでは早速遺伝的アルゴリズムをやってみましょう。
すごくザックリやりますので、厳密ではないですけどイメージをつかみましょう。
まず変数の箱（遺伝子）を探索する個体分だけ用意します。
個体数は適当に決めます。本来は10個体くらいほしいですが、簡単のため3個にしています。
3人がそれぞれ3個の遺伝子の箱を持っているんだね
この3人の遺伝子の値（変数の値）をある法則で更新し続けると最適解が求まるんだ。
初期化
遺伝子の箱にランダムに数を入れます。
ただし
-5<=x1,x2,x3<=5
です。
最初はとりあえず適当に値を入れちゃうんだね
うん、最初は手掛かりがないから、なるべく色々な場所の情報を手に入れるためだよ。
評価
各遺伝子の値を元に、yを計算します。
14と21が良い値ですね。
最小化したいから値は小さい方がいいんだね
そうだよ。より小さい値は良い値と考えて、良い値を取るときの変数の値を使って遺伝子を更新していくんだ。
交叉
成績の良い遺伝子から適当に箱の中身をコピーします。
これを個体数（3）個分やります。
遺伝子の値の選び方は適当でいいの？
実際は色々な方法があるよ。遺伝子を半分に分けて右と左でごっそり変えるとか。でもあんまりどう分けるかっていうのは関係ないんだ。AとBの遺伝子があったら、どちらから情報を取り込むかはランダムに決めてしまっても大丈夫なんだ。
再評価
再び各遺伝子の値を元に、yを計算します。
17と6が良い値ですね。
これさっきもやったね
そうだよ。こうやって見つかった良い値の情報を使って、遺伝子をどんどん更新していくんだ。
良い値からより良い値が生まれて、それを繰り返していくうちに一番良い値を見つける、というのが基本的な考え方だよ。
再交叉
再び交叉を行います。
成績の良い遺伝子から適当に箱の中身をコピーします。
これを個体数（3）個分やります。
だんだん0に近づいてきたけど、もう遺伝子には0の情報がないよ？
そうだね。最初にランダム生成した値に0がないから、このままだとどう頑張っても変数に0が出てこないね。
だから次の処理で突然変異という操作をするんだ。
突然変異
たまに遺伝子の箱にランダムな数を入れます。
ただし
-5<=x1,x2,x3<=5
です。
今回は都合よく-2に0が出ましたね。
今までにない値が出るようにガチャを引くんだね
そうだよ。良くない値が出るかもしれないけど、それは上の評価と交叉ではじかれていくから、良い値を引き当てればそれが残っていくんだ。
終了
この
評価→交叉→評価→交叉（たまに突然変異）
のループを数百回から数千回繰り返せば次のような遺伝子になります。
最良の遺伝子を記録しておけば、最終的にそれが最適解です。
何千回もかかるんだね
そうなんだ。これがGAは遅いと言われる理由なんだ。でも簡単な問題ならコンピュータの計算速度はすごいから、あっという間に計算できるし、GAにはGAの利点があるんだよ。
GAの利点は色々な問題が解けるということなんだ。微分を駆使する最適化手法は目的関数が微分できないと使えないんだよ。
変な条件が入ると、目的関数が微分できない複雑な計算をすることって結構あるんだ。
でもGAならとりあえず目的関数が何らかの手続きで計算できればいいから、使える目的関数の種類が多いんだ。もちろん微分できない目的関数にも使える。
だから目的関数の形を見極めて、どんな最適化手法を使うかが大事だったりするんだけど、入門の段階ならまず簡単なGAを覚えよう。
交叉の解説
上で交叉の時は優秀な個体の情報を元に交叉を行うと述べました。
一番単純な方法は各遺伝子のyの値を昇順に並べて、yが一番小さい遺伝子とその次に小さい遺伝子を選ぶ方法です。
しかしながらこれだと他の遺伝子に優秀な値があった場合取りこぼします。
この場合優秀な1番良い遺伝子、2番目に優秀な遺伝子のコピーばかり量産されて、いつまでも３番目のx3の値である1が取り込めません。
しかも３番目の個体を交叉するときに、今のx3の1が上書きされて、消滅するので非常にまずいです。
まあ突然変異でランダムにいい値が出るまで待てばいいんですけど、もう少しうまくいかないものか。
良い遺伝子はなるべく取り込むけれど、良くない遺伝子も少し取り込んでみたい。
そんな要求に応えるのが
「ルーレット選択」
です。
最初に難しいって言ってたやつだね
そうなんだ。これ結構面倒な計算するから難しいよ。でもよく使う方法だから勉強してみよう。
ルーレット選択
やり方はこうです。
まず各遺伝子のyを計算して、次の「F：適応度」という値を求めます。
多くの場合y=Iとして計算します。
とりあえずyの値を使ってFを求めるんだね
そう。yの値を使うってことは、良い値かどうかという情報でFという値を作るってこと。
上の図では
I1=y1=21
I2=y2=19=Imin
I3=y3=51=Imax
F(i)=(Imax-I(i))/(Imax-Imin)
Fの計算、複雑じゃない？
ここが難しいね。Fの式の分母は目的関数の最小値と最大値の差だよね。
そして分子は目的関数の最大値引くある遺伝子のyの値。
つまり分母は目的関数の値の散らばり度の最大幅、分子は対象の遺伝子の優秀度って感じかな。
分子は最大値からの差が小さいほど、つまりyが大きい値で優秀じゃないほど小さな値になるよ。
逆に最大値からの差が大きい、つまりyが小さい値で優秀であるほど大きい値になるんだ。
なんか複雑だね
まあFの式に遺伝子の値を当てはめると、優秀な遺伝子ほどFが大きくなって、優秀じゃないほどFが小さくなるってことだよ。
F1=(51-21)/(51-19)=0.9677
F2=(51-19)/(51-19)=1
F3=(51-51)/(51-19)=0
ほらね。yが小さいy=21とy=19はFが大きくなって、yが大きいy=51はFがゼロになったよ。
そしてFを合計させFsを求めます。
Fs=sum(F(i))=F1+F2+F3=1.9677
なんでFsを求めるの？
Fをルーレットにしたいからだね。Fの合計であるFsを100%にして、各Fの値を100%中の何%に対応させたいんだ。Fが大きければ%は大きくなるよね。それだけ的に当たりやすくなるから、選ばれやすくなる。Fが大きいなら優秀な遺伝子だから、優秀な遺伝子ほど的に当たりやすくなるってこと。
そして0から1の乱数rを発生させます。
ここではr=0.7が出たとします。
0～1なら0%～100%のことを表してるんだね
次の方法でrとtempの値を比較していきます。
●ステップ1
temp1=F1/Fs=0.9677/1.9677=0.4918
r>temp1なので継続。
●ステップ2
temp2=F2/Fs+temp1=1
r<temp2
なので終了、個体2の遺伝子を採用。
つまり
F(i)/Fs
を順番に足していって、rを超えたら、tempの添え字の数値を採用します。
ここではtemp2でrを超えたので、添え字2を採用します。
難しいよう…
そうだね。まあこのやり方で良い値が選ばれやすくなるってことがわかればいいかな。
一応説明すると、Fsが100%、F1が49.18%、F1+F2が100%。F1に割り当てられたのが49%でF2に割り当てられたのが49%から100%の間の51%ってことだね。
r=0.7だったから70%の部分を選んでるんだ。すると49%のF1の的を通り越して、F2の的の部分に当たっているってことだね。
つまり2番目の個体を交叉の元データに使用するということです。
おわかりかもしれませんが、yつまりIが小さいほうがFが大きくなり、Fが大きいほうがF(i)/Fsの値が大きくなるので、的が大きくなるので、より高い確率で選ばれます。
逆にIが大きければ、Fが小さくなり、F(i)/Fsの値が小さくなるので、的が小さくなり、より低い確率で選ばれます。でも0%ではないので、たまに選ばれます。
つまり
良い遺伝子はなるべく取り込むけれど、良くない遺伝子も少し取り込んでみたい。
この要求が実現できるのです。
ルーレット選択の注意点
ただしこの方法では3番目の個体は永久に採用できないので、Fの値にもし0が出たら、0.01などの小さい数値で置き換えます。
0%では絶対に選ばれないもんね
つまり本番では
If(F(i)=0) then
F(i)=0.01
つまり
F3=0.01にして計算します。
さらに遺伝子が収束してきて、すべてのIが同じ値になる場合も考えなければいけません。
そういう時は(Imax-Imin)が0になるのでFを0.01などの小さい数値で置き換えます。
If(Imax-Imin=0) then
F(i)=0.01
とします。
交叉時に適当に箱の中身を選ぶ
これは元のデータになる個体が２つ求まったら、各変数毎に乱数rを発生させて
r<0.5
なら片方のデータから
r>=0.5
ならもう片方のデータから箱の中身をコピーすればOKです。
各遺伝子の場所でコイントスしてるんだね
またこの後で再びr1、r2、r3を再発生させて、突然変異率mより小さかったら
-5<=x1,x2,x3<=5
の範囲でランダムな値を発生させて、その値を採用します。
mを大きくしすぎると、元の遺伝子の情報がすぐなくなっちゃうから小さめがいいよ
mは突然変異率ともいいます。突然変異は頻繁に行うと元の遺伝子が破壊されすぎて、良い値が後世に残っていきません。mは小さめにするのが無難です。
収束の判定
厳密にこの値を計算して求めたら最適解というのは難しいので、適当に1000回とかで計算して最良個体のyを記録しておいて、そこから計算を続けて100回連続で最良のyの値に変化が0.1%しかない、とかで判定します。
もちろん、満たすべき条件が存在するなら、その条件を満たしているかどうかで判定すればよいです。
この辺は適当なんだね
うん、というのも何を持って最適解かというのは判定が難しいんだ。微分できればその値が0になるとかで判定できるんだけど、GAは微分できない関数でも使うから、その方法は使えない。
かといって微分の値を見る以外に最適解かどうかという指標があるかというとないんだよね。
だから良い値が更新されないとかで判定するしかないんだ。
まとめ
遺伝的アルゴリズムのザックリとした説明でかなりの量になってしまいました。
プログラムは次の機会にします。
それでは次の記事で会いましょう。
お疲れ様。またね！
GAのことをさらに知りたい、あるいは他の最適化手法が気になるというときはこの本がおすすめです。
ただしプログラムをある程度読める、プログラミングスキルがそこそこあるのが前提に書かれています。
