GENESISについて

GENESIS は John J. Grefenstette らにより開発されたC言語で作成した GAの実験用ソフトである.ソースコードが公開されており, 適合関数を利用者が任意にプログラムして各種の実験ができるようになって おり,オプションも豊富で種々の調査もできるなど便利に作られており,ソースコードも公開されている. 遺伝子表現がバイナリビットストリング及び実数のGAに適している. 以下,このソフトを使用してGAを実現する方法について述べる. なお,GENESISは圧縮したtarファイル genesis.tar.Z を入手できる.

概要

  1. 遺伝子の表現として次の2種のいずれかが選択できる

  2. 交叉には2点交叉を適用する.

  3. 選択方式としては次のいずれかを指定できる.

    適合値最小モードを標準とし,オプションで最大モードが可能. (適合値最小モードの表現は適当ではないが,GENESISの表現に従った.むしろ 目的関数最小モードと考えた方がよい) また最良の個体1つを常に次の世代に残すエリート選択(elitist selection)も 可能.

  4. 全個体の内,選択,交叉,突然変異を行なう範囲を指定出来る.  変数 Gapsize により制御し,最初の設定の際に Generation Gap 値で指定する. 全個体の内のこの値分が上記の処置を受け, 残りの個体はそのまま次世代に残される.

  5. 適合関数のみは利用者が作成できる.後述の利用上の注意を参照.

  6. 実行に際して20個のオプションが指定でき,各種のモードやデータ採取方法 などで実行できる.

  7. 対話モードがあり,対話的な使用ができる.

  8. 目的別の各種のファイルに出力が出され,それにより動作の解析が容易に できる.

トップに戻る

プログラム上の特徴

プログラム上も種々の配慮がなされており,ここではその内の代表的なものを挙げる.
  1. 遺伝子の表現にはつぎの3種が用いられている

  2. 複数の遺伝子が指定できる(実数型の場合) 実数型の場合,1つの実数を1つの遺伝子として表し,複数の遺伝子が使用できる. 遺伝子の個数はsetup時 に genes の値で指定する.
    なお,これに関連して次の値の間の関係に注意する必要がある.
    遺伝子の数(genes),各遺伝子の値(2の指数乗),ビット長の間に 遺伝子数と指数との積がビット数に等しくなければならない. これはプログラム内ではgenes個の実数が1つのビットストリングに変換されて 処理されるためである.

  3. 1世代の実行方法として次の方法が用いられている.
    「選択−突然変異−交叉−エリート選択−評価」のサイクルを全個体分実行して, つぎに移るようになっている. 突然変異の方法は従来のものと異なり,実行時間が短くなる方式を採用している. 従来の方式では全ビットを順次辿りながら,確率により突然変異を行なうか否かを 決めているが,今回の方式は確率で次に突然変異するビットを決め, そこに跳ぶようにしている.

トップに戻る

利用上の注意

主な事項のみを記す.
  1. 適合値計算プログラムの作成 : 利用者が作成するプログラムはGAの操作に関しては適合値の計算部分のみでよい. その他のプログラム,例えばグラフィック表示などは必要によって作成する. 以下ではこの適合値計算部分のプログラム方法を示す.
     適合値は以下に示す関数 eval(str,length,vect,genes) により指定する.

         double eval(str, length, vect, genes)
         char   str[];  /* string representation */
         int    length; /* length of bit string  */
         double vect[]; /* floating point representation */
         int    genes;  /* number of elements in vect */
    
    GENESISに当初より添付のサンプルプログラムファイル f1.c に実数の二乗の 最小値を求める場合の適合値の計算プログラムが添付されており, 参考になる.

  2. Makefile の作成}: 前述の適合値計算プログラムやグラフィック関係のプログラムなどを 記述したファイル名を当初のMakefile に追記,修正する.
  3. 実行:2段階で行なわれる.

  4. 実行結果:多数のファイルで出力される.内容は後述.

トップに戻る

プログラムの作成

提供されるGENESISのプログラムはアーカイブの圧縮ファイルであるので, つぎのunixコマンドにより解凍し,アーカイブを展開する.
     uncompress  genesis.tar.Z
     tar xvf  genesis.tar
  1. 適合値計算プログラムの作成: 利用者が作成するプログラムはGAの操作に関しては適合値の計算部分のみでよいが, グラフィック表示などはこのプログラムには含まれていないので, 利用者が必要によって作成する必要がある. 以下ではこの適合値計算部分のプログラム作成方法を述べる.  適合値は以下に示す関数 eval(str,length,vect,genes) の戻り値として与える.

         double eval(str, length, vect, genes)
         char   str[];  /* string representation */
         int    length; /* length of bit string  */
         double vect[]; /* floating point representation */
         int    genes;  /* number of elements in vect */
      
    この関数の引数の使用方法は遺伝子表現がビットストリングか実数かにより, つぎのように変わってくる. GENESISに当初より添付のサンプルプログラムファイル f1.c に実数の二乗の 最小値を求める場合の適合値の計算プログラムが添付されているので, これを参考にするとよい. %
  2. その他,プログラムの変更: 多くの場合は前項の適合値計算プログラムの作成でよいが,グラフィック表示や複数遺伝子表現などを採用する場合は必要に応じて変更,追加を行なう.

  3. Makefile の修正作成: コンパイル用のMakefileを,前述の適合値計算プログラムやグラフィック関係の プログラムなどを記述したファイル名を追記,修正する.

トップに戻る

実行

つぎの2段階で行なわれる.
  1. セットアップ用ファイルの作成:各種パラメータを設定するファイルを 作成する.コマンド setup で開始し,以後はコンピュータ側の指示に従い, 入力する. 以下,例を示す.なおカッコ[]の中にはデフォルト値を示し,この値でよい場合はその ままCR(キャリッジリターン)でよい. また,各入力についてはこの後に説明している.

          File suffix []: ex1                 ファイル名を *.ex1 
          Floating point representation [y]:  以下は実数の場合を示す.
                                              n(ビットストリングの場合)はExperiment
                                              までとぶ
          genes: 3                            実数の場合の遺伝子の数 = 3
          gene 0:                             入力の要なし,遺伝子の順番を表示
          min: -5.12                          
          max: 5.11                           
          values (must be a power of 2):1024  2の10乗の1024
          format: %7.2f                       
          repetition: 3                       
          
          Experiment [1]:                     
          Trials [1000]:                      
          Pop Size [50]:                      
          Length [30]:                        
          Crossover Rate [0.6]:               
          Mutation Rate [0.001]:              
          Generation Gap [1.0]:               
          Windowsize [5]:                     
          Report Interval [100]: 200          
          Structures Saved [10]: 5            
          Max Gens w/o Eval [2]:              
          Dump Interval [0]:                  
          Dumps Saved [0]:                    
          Options [cefgl]: acefgL             
          Random Seed: [123456789]:           
          Rank Min :  [0.75]:                 
    
    入力に対する注意事項
  2. 実行:コマンドgo に以下のパラメータをつけて実行する. コンパイル後,実行される.

        go fun1 ex1
              fun1 : 適合関数のファイル名(fun1.c)の本体部分.
              ex1  : ケース番号を示す.入力を変えて実行するときに別の番号を取る.
    

トップに戻る

実行結果の出力

以下のファイルに実行結果が出力される.
  1. rep.ex1: 実行結果をまとめたファイルであり,以下にその内容の例を示す.

    rep.ex1 for ga.fun1
    1995年02月28日(火) 18時04分09秒 JST
    
          Experiments = 1
         Total Trials = 1000
      Population Size = 50
     Structure Length = 30
       Crossover Rate = 0.600
        Mutation Rate = 0.001
       Generation Gap = 1.000
       Scaling Window = 5
      Report Interval = 200
     Structures Saved = 5
    Max Gens w/o Eval = 2
        Dump Interval = 0
          Dumps Saved = 0
              Options = acefgL
          Random Seed = 123456789
             Rank Min = 0.750
    
    MEAN
    Gens  Trials  Lost  Conv   Bias    Online    Offline      Best     Average
       0      50     0     0  0.569  2.622e+01  5.271e+00  2.795e+00  2.622e+01
       3     200     0     0  0.617  1.951e+01  2.859e+00  7.049e-01  1.518e+01
       7     400     0     0  0.690  1.467e+01  1.633e+00  3.097e-01  7.546e+00
      11     600     1     2  0.723  1.146e+01  1.185e+00  2.485e-01  3.514e+00
     注
      Lost:集団の全個体の遺伝子のビットが1または0となっているビットの位置の数の
            合計.このビット位置の値は交叉で変化しないので,交叉の効果を失っている
            程度を示す.多様性の程度を表し,この値が多いと多様性を失っている.
      Conv:集団の全個体の遺伝子のビットで,1の数が FEW より少ないか,あるいは
            Popsize - FEW の数より多いビットの位置の数.
            FEW は Popsize/20 に設定している.Popsize は集団の個体の数.
            この数は収束したビットの数を示し,収束の程度を示す.
      Bias:集団の全個体の遺伝子の各ビット位置で1の数が Popsize/2 より多い場合
            は1の数の合計、少ない場合は (Popsize - <1の数の合計>)を求め,それ
            らを累計したものを(Popsize * Length) で割ったもの.
            この値は1または0の偏りの程度を示す.従っ0.5 の時は1と0が同数ある
            ことを表す.
      Offline:Offsum / Trials : 各トライアルまでの最良の適合値の平均(各世代ごと)
          OffSumはそのトライアルまでの最良(最小または最大)の適合値の累計
      Online: Onsum / Trials  : 全トライアルの適合値の平均(各世代ごと) 
          Onsumはそのトライアルまでの適合値の累計
      Best  :そのトライアルまでの最良(最小または最大)の適合値
      Average:各世代の平均適合値
    

  2. ckpt.ex1: 実行結果のさらに詳細な内容であり,以下にその内容の例を示す. なお,右側にコメントを追加して置く.

      Experiment 0                   1回目の実験であることを示す。
      Totonline 0.000000e+00         Online の合計値
      Totoffline 0.000000e+00        Offlineの合計値
      Gen 19                         世代数
      Onsum  7.859897e+03            rep.ex1 ファイル参照           
      Offsum 7.836706e+02            rep.ex1 ファイル参照
      Trials 1000                    トライアル数
      Plateau 1200                   次のプリントアウトのトライアル
      Best 1.202000e-01              最良の適合値
      Worst  3.007321e+01            最悪の適合値
      Spin 0                         評価開始後の世代数
      Curr_dump 0                    ダンプ出力の周期番号
      Mu_next 159                    次に交叉を行なう位置
      Random Seed 1453178189         乱数のシード
      Initialization Seed 239974671  乱数の初期化のシード
    
      Window                         最悪の適合値のデータ5回分。Worst を決めるため
      2.360986e+01
      1.213971e+01
      3.007321e+01
      6.173917e+00
      6.173917e+00
                                                      
      110010000111111011011101110001 4.58040000e+00 0   ビット と 適合値
      110010010011000111011100101000 5.92400000e-01 0    (各個体の値)
      110011110101110111011100101000 2.67860000e+00 0
      (以下省略)
    
      110011001011000110011100111000 3.72300000e-01 0
      110010010101111111011111111010 6.17330000e+00 0
      110000010011000100011100110010 2.17400000e-01 0
      010011001011000101110100011001 2.29600000e-01 0
      010001001011000100011100000000 1.74100000e-01 0
                                             
       0.62    1.82    0.94      4.5804      左から順に 各遺伝子(今回は3)の
       0.56    0.22    0.48      0.5924     浮動小数点値及びそれから求めた値
       0.41   -1.51    0.48      2.6786     今回は3個の値の二乗和
       0.35    0.30    1.08      1.3789     (各個体の値)
      -0.35    2.25    0.32      5.2874
      (以下省略)
    

トップに戻る

プログラム上の特徴

各種のファイルがあるので、既出のものも含めて整理しておく. なお,サフィックスは '*'で示している.
  1. rep.* : 実行結果の出力.プログラム report.c にて作成する.

  2. ckpt.* : 各個体のデータなど.

  3. in.* : 入力ファイル.プログラム setup.c にて作成する.

  4. init.* : 個体の初期化データ.オプション-i の時はビットの初期値を乱数 ではなく,このファイルの値に設定する.

  5. template.* : 各遺伝子の浮動小数点表示への変換のためのデータ(入力値).

  6. schema.* : 1つの schema の状況を示す.schema の世代間の向上など. オプション - s で出力する.最初にこのファイルに schema を入力して置く.schema は 1,0,\# で表す. \# は don't care を表す.

  7. min.* : 最良のもののデータを出力する.データ数は setup で指定する.

    データの中身は各遺伝子の浮動小数点値,適合値,その世代数,トライアル数.

  8. out.* : setup で指定したトライアルの採取間隔で結果の表示を行なう. データの内容は世代数,トライアル数,Lost,Conv,Online,Offline,Best, Ave\_currrent\_perf.

  9. dump.0,dump.1,... : setup で指定したダンプ間隔で採取したデータを ファイルサフィックス を順次 0,1,2,... と変えて別々のファイルにセーブする.

  10. log.* : 起動及び再起動の時のログ用ファイル.オプション'l'で動作.

  11. log.error : エラーログ用.エラー発生時にはまずこのファイルを見ること.

トップに戻る

オプション

このプログラムでは多数のオプションが用意されている.以下,各々 について簡単に説明する.
  1. a : すべての構造を各世代に評価する.

  2. b : 実験の最後に平均の最良値を出力する.(標準出力に出す)

  3. c : 収束状況に関するデータを採取する.

  4. C : 特性に関するデータをファイル out.* に書きだす.周期はレポート間隔 でかつ世代の終り.オプション 'D','I' ではスクリーンに出力する.

  5. d : 現在の集団のデータを ファイル ckpt.* に出力する.しかし, このモードでは実行速度が遅くなるので,必要な時のみ使用するのがよい.

  6. D : ディスプレーモード.各世代の終りにスクリーンに特性値を表示する.

  7. e : 選択にエリート方式を採用する.最良の個体は常に次の世代に残すようにする.

  8. f : ファイル template.* に規定されている浮動小数点表示を採用する. この場合は setup において浮動小数点モードを指定すること.

  9. g : Gray code を使用する.

  10. i : 集団の初期値をファイル init.* に記載のものに設定する.このファイルの 個体の数が必要とするものより少ない場合は、残りは乱数で設定する.

  11. I : 対話モード.各世代ごとにスクリーンに各種データを出力する. さらに操作を制御するコマンドを入力できる.

  12. l : ログファイル log.* の作成指示用.

  13. L : 最後の世代で ckpt.* ファイルにダンプすることの指示用.これにより オプション 'r' で実験を続行できる.

  14. M : 適合値を最大にするモード.デフォルトは最小モード.

  15. o : 実験の最後で平均特性を標準出力に表示するモード.

  16. O : 実験の最後で Offline 特性を出力する.Offline 特性とは現在の最良値の 平均.

  17. r : 中断後の再開が可能なモード.ckpt.* ファイルのデータを読み込んで 再開する.

  18. R : ランクによる選択を行なうモード.

  19. s : 1つの schema のトレースモード.ファイル schema.* には予め schema を 1,0,\#を用いて記載しておく.

  20. t : トレースモード.トレースの表示は標準出力に出す.

トップに戻る

プログラム作成上の注意

GENESIS を使用するに際してユーザが作成する必要のあるプログラムは以下に示す 適合値を計算する関数 eval() である.
   double eval(str,length,vect,genes)
サンプルとして二乗関数の最小値を求める例がファイル f1.c として GENESIS に当初 から添付されているので,これを参照するとよい.
  1. ファイル名について:適合値を求める関数を記述するファイル名が f1.c と 異なる場合は makefile の下記の個所を変更する必要がある. 例はファイル名を f5.c とする場合を示している.

       f=f1 を  f=f5 に変更する
    

  2. eval関数の定義法: 遺伝子表現としてGENESIS では 実数表現とビット表現の2種が可能であるので、 各々について記す.なおいずれを使用するかはsetup において指定する.

トップに戻る

小野 俊彦 (Toshihiko Ono)