書籍サポート / Support

Excelで学ぶ遺伝的アルゴリズム

GA-2D 解説

山登り法やGA を用いた1次元関数の最適化を実験できます。概観は以下のとおりです。

GA-2Dシミュレータの操作方法

押すと下のような関数入力用のフォームが表示されます。

関数名・関数・定義域を入力し「OK」ボタンを押すと、メイン画面のグラフが新しい関数に更新されます。なお，変数は小文字の x です。大文字の X は使えません。使える関数はsin(x), cos(x)など以外にもExcelで使用可能な関数であればすべて使用できます。

押すと関数保存用のフォームが表示されます。現在の関数・定義域を名前付きで保存することができます。保存した関数の呼び出しは下記の「Load」ボタンを使用します。

押すと下のような関数呼び出し用のフォームが表示されます。

リスト中の呼び出したい関数をクリックし「Load」ボタンを押すか、関数をダブルクリックすることで、メイン画面に関数がロードされます。リスト上部のラベルを押すと関数をソートすることができます。「Delete」ボタンを使えば保存してある関数を消去することもできます。

以下から探索方法を選択します。GAを選択した場合はGAパラメータを設定してください。山登り法を選択した場合は「#.Evaluation 」(評価回数)と「Gene Length」(歩幅に相当)を設定してください。

  • GA(Genetic Algorithm)--遺伝的アルゴリズム--

    • 遺伝的アルゴリズムとは、最適化を高速に行うための探索アルゴリズムの一種であります。GAは生物の進化、例えば選択、交叉突然変異といったものにヒントを得た比較的単純な手順を有し、ほとんどあらゆる最適化、探索の問題に適用可能な方法であります。GAでは遺伝子をもつ仮想的な生物の集団を計算機内に設定しあらかじめ定めた環境に適応している個体が、子孫を残す確率が高くなるよう世代交代シミュレーションを実行し遺伝子および生物集団を"進化"させます。

  • SAHC(Steepest-ascent hill climbing)--最急勾配山登り法--

    1. まず1つの遺伝子配列を選びます。そしてこれを「現頂上」を呼ぶこととします。
    2. この遺伝子配列を左から右に順に１ビットずつ反転させて、それぞれの適合度を記録します。
    3. もし反転した結果適合度が増加するなら現頂上を反転結果の中で最も優れた適合度の遺伝子配列に変更します。
    4. もし適合度の増加がない場合は現頂上を保存し１に戻ります。そうでなければ２に移動します。
    5. 設定した回数の関数評価が済んだならば見つかった最高の頂上を答えとして出力します。

  • NAHC(Next-ascent hill climbing)--逐次勾配山登り法--

    1. まず1つの遺伝子配列を選びます。そしてこれを「現頂上」を呼ぶこととします。
    2. SAHCと同様にビットを順順に変えていって適合度の増加が見られたら他の反転結果を見ることなく、それを現頂上とします。そしてこれを繰り返します。ただし反転するビット位置は先に適合度の見られたビット位置の隣から始めます。
    3. もし適合度の増加が見られない場合は現頂上を保存して１に戻ります。
    4. 設定した回数の関数評価が済んだならば見つかった最高の頂上を答えとして出力します。

  • RAHC(Random-ascent hill climbing)--ランダム勾配山登り法--

    1. まず1つの遺伝子配列を選びます。そしてこれを「最高評価解」を呼ぶこととします。
    2. この遺伝子配列からランダムに１ビット反転させて、現在の適合度より優れた結果が得られるならそれを最高評価解とします。
    3. 最適な遺伝子が見つかるか定められた回数の関数評価が済むまで２に戻り繰り返します。
    4. もし適合度の増加が見られない場合は現頂上を保存して１に戻ります。
    5. 設定した回数の関数評価が済んだならば見つかった最高の頂上を答えとして出力します。

    GAのコーディング法・オペレータおよび各パラメータを設定します。リストボックスを使えばメイン画面からでも代表的な値を選択できます。「GA Setting」ボタンを押すと以下のフォームが表示されます。より厳密な設定ができます。

  • Coding

    • 遺伝子型の表現方法を決定します。コーディング法は以下の3つから選択できます。

    1. Binary : バイナリ表現によるコーディング
    2. Gray : グレイ表現によるコーディング
    3. Real : 実数値によるコーディング

  • Genelation

    • 総世代数です。この世代まで世代交代を繰り返します。1〜1000の範囲で設定できます。

  • Population

    • 個体数です。1世代あたりの評価回数と等しいです。1〜1000の範囲で設定できます。

  • Gene Length

    • 遺伝子長です。遺伝子を最大何Bitで表現するかを決定します。1〜50の範囲で設定できます。

  • Elite

    • エリート個体数です。世代交代のときに設定した数だけエリートとして次世代に残します。0〜Populationの範囲で設定できます。

  • Crossover Rate

    • 交叉率です。この割合の固体が他の個体と交叉します。0〜1の範囲で設定できます。

  • Mutation Rate

    • 突然変異率です。この割合の個体の遺伝子が突然変異します。0〜1の範囲で設定できます。

  • Sharing

    • 棲み分け処理の有無の設定です。棲み分け処理は割り当て関数により集団の多様性を維持します。

  • Selection Method

    • 交叉する個体の選択方法を決定します。以下の3つより選択できます。

    1. Roulette : ルーレット方式による選択
    2. Tournament : トーナメント方式による選択
    3. Random : ランダムに選択

  • Crossover Method (RealGA)

    • 交叉方法を決定します。実数値コーディングの場合のときのみ関係します。以下の2つより選択できます。

    1. BLX-α : 一様乱数による交叉
    2. UNDX : 正規分布に基づく交叉

  • Mutation Method (RealGA)

    • 突然変異方法を決定します。実数値コーディングの場合のときのみ関係します。以下の2つより選択できます。

    1. UD : 一様乱数による突然変異
    2. ND : 正規分布に基づく突然変異

    GAもしくは山登り法による最大値探索を開始します。

    押すと下のようなステップ探索用のフォームが表示されます。

    指定した世代数だけ世代を進めることができます。探索過程を確認するのに便利です。「Continue」ボタンで探索を再開します。「Parameter」ボタンはGAパラメータ設定フォームを表示します。「Report」ボタンは押すと以下のようなレポートフォームが表示されます。

    現世代(子世代)の集団と前世代(親世代)の集団の構成を確認できます。また、子世代の個体がどの親個体からどのように発生したかも確認できます。リスト上部のラベルを押すと個体がソートされます。子世代リストの個体をダブルクリックすると、以下の詳細なレポートのフォームが表示されます。

    このフォームでは、親個体の遺伝子と子個体の遺伝子が確認できます。また、GAオペレータと作用した遺伝子位置(site)も確認できます。

    Copyright © 2002-2023 Iba Lab., University of Tokyo, All Rights Reserved.