読者です 読者をやめる 読者になる 読者になる

遺伝的アルゴリズムのメモ

最適化

基本

  • 1975にHollandが提案.
  • 最適化対象の関数の微分可能性や単峰性を要求しない(SAも同様).
  • 但し,評価関数の順序性と,探索空間が位相を持っていることが要請される.
  • 解の遺伝子表現方法を決めるということは,表現型と遺伝子型の符号化方法(コーディング)を決めていると言える.
  • コーディング方法としては,バイナリコーディング(ナップザック問題のように,あるアイテムのあるなし,または個数を符号とする),順列コーディング(TSPやタスクスケジューリングなどのような,何かしらの並びを求める場合),実数値コーディング(実数を文字列としてコーディングする),また遺伝的プログラミングでは木(またはグラフ)としてコーディングする.
  • 探索の集中化(良い解の周辺を探索したい)と多様化(局所解からの脱出)をどう塩梅を取るか,という観点でSAやPSOなどと比べて見ると良い.
  • 集中化の前提としては,良い解は類似の構造を持つ,という近接最適性原理を仮定している.これが成り立たないような問題は,結局全探索するよりほか無いということを意味していて,工学の対象としては成立しない部類何だと思う.
  • 近傍解というもののしっかりとした定義は無い.そして,近傍解というものを適切に決めることは実は難しい.但し,近傍解の生成ルールを複数用意しておき,適用するルールを変化させることで局所構造への捕捉を回避することがよく行われる.
  • GAは理論的根拠が弱いとされているが,スキーマ定理と呼ばれる定理が一定の条件下では拠り所となる.スキーマとは部分構造のことであり,スキーマ定理はある部分構造の存在確率に関する定理であり,適応度の高い,ある一定の大きさの部分構造が残りやすい,ということを述べている.つまり,GAは交叉によりバンバンジャンプするけど,その進化は最適解が持っているであろう良い部分構造を内包するものが生き残り,最終的な解にたどり着く,と考えるんだ.だから,GAの適用が向く問題というのは,とても広い範囲をくまなく探索する必要な問題で,かつ,探索範囲は広いものの,部分構造としては最適解は准最適解類似の構造を内包している,というような仮定が成り立つ問題に向くんだと思う.

他の集団最適化アルゴリズムとの違い

  • DE(差分進化)は全体で最適解の情報を共有して,その全体の最適解に収束するような操作が入っており,探索序盤は広く,探索終盤には自然と最適解の周囲を集中的に探索したい,という目的を実現する意図が入っている.そして,それぞれは自分の周りをある程度しっかりと調べる.
  • 対してGAは大域的ジャンプをし続けてしまうというのが欠点と言える.本当に大域的な情報を調べたい,というときがGAの出番なのかな.DEは基本的には局所探索をバラバラにやっているイメージで,バンバンジャンプしていこう,ってイメージではないな.じんわりじんわりみんなで,って感じかな.

フロー

  1. 評価集団の生成
  2. 適応度計算
  3. 交叉候補の選択

 適応度に応じて交叉させる.交叉候補の選択方法は適応度に重みづけてルーレット選択する,もしくはN個をランダムに取ってきてトーナメントして強いものを残す,などが行われる.また,エリート保存と言い,最も良い上位何個かを必ず選択する,などもある. 4. 交叉     ある1点で切って,そこをスワップする1点交叉が基本.多点交叉もあるが,わざわざそうする理由があまり無いのか(1点交叉を何回も回すのと何が違う)?と思う.一様交叉というのは,どこかから後ろを全部入れ替えるとかではなく,マスクビットのようなもので,マスクしたビットを全部入れ替える,みたいなもの.これはマスクに知識を入れるなどである程度意味がありそうだ. 5. 突然変異    交叉を大域ジャンプだとすると,突然変異は近傍解生成と言える.一般的には変数ごとに,今の変数の値を平均とするガウス分布に従うように乱数で変化させることが行われる.これをガウス突然変異というが,ガウス突然変異は裾の減速が激しいのでそれを緩めるためにコーシー分布に従う乱数で変化させるものもある.それがコーシー突然変異.