GENITORについて

• 概要
• プログラムの構成
• 利用上の注意
• プログラムの作成
• 実行
• コマンドラインオプション
• ファイル関係

1. 遺伝子の表現として次の３種のいずれかが選択できるとなっているが， 整数の順序表現以外は使用したことがないので，状況は分からない．

   • ビット表現
   • 実数表現
   • 整数の順序表現
   　以下では整数の順序表現のみについて説明する．

2. 遺伝的操作方式が以下のようにシンプルGAと少し異なる． 最初に集団の全個体を適合値に従ってソートして，最良の個体がトップに来て， 最悪のものが最後になるように適合値の順に並べた後，以下の操作を 所定の回数だけ実行する．

   • ランク方式で2個体を選択する．
   • 交叉，突然変異などの遺伝的操作を行う．
   • その結果，得られた新個体の内の1個体に対して適合値を計算する．
   • その個体を集団に戻す．その際，集団の最悪のものより悪い場合は捨て， そうでない場合は適した位置に挿入する（適合値の順に並べる)．
   このように1個体単位に進化させている．

3. 選択操作はランク方式で行なわれる．

4. TSPを対象に以下に示すように順序問題に特有な交叉のソフトが豊富に 準備されていて，この種の問題に使用するには最適である． しかし，これらを使用する際はmain関数ファイル main_tsp.c 及び Makefileを 書き換える必要がある． なお当初のソフトは辺再組合せ交叉の適用で作成されている．

   • Cycle：循環交叉(Cycle crossover) Oliverらによる.
   • Order1：順序による交叉１(Order-based crossover) Devisによる．
   • Order2：順序による交叉２(Order-based crossover) Syswerdaによる．
   • Pmx ：部分写像交叉(Partially-mapped crossover) Goldbergによる．
   • Recomb：辺再組合せ交叉(Edge recombination crossover) Whitleyらに よる．

5. プログラムは各種用途への使用を考慮し，コンパクトにつくられ，かつ大域変数 も少ないので，ソフトの追加も容易である．

6. 利用者が新たにソフトを追加あるいは変更して使用できる． 利用者は下記を作ればよい．

   • main関数　
   • 評価関数，即ち，適合値計算用関数
   • Makefile：コンパイル用ファイル

  Genitor/src/ga    ga の基本的な操作のプログラムのソースコード
  Genitor/src/op    TSP 用のオペレータ，即ち，交叉用各種プログラムのソースコード
  Genitor/include/ga  上記用ヘッダーファイル
  Genitor/include/op  同上
  Genitor/Examples/TSP/Recomb/Original ソフトに添付されていた 辺再組合せ交叉の
                                     　関係プログラム
  Genitor/Examples/TSP/SampleConfigs/15city 15都市の位置データ
  Genitor/Examples/TSP/SampleConfigs/30city 30都市の位置データ
  Genitor/Examples/TSP/Cycle,Order2,Position,Recomb,Order1,Pmx それぞれの
                    ディレクトリーに各種交叉方式のプログラムが入っている。
                    それぞれには次のものが収納されている  
      main_tsp.c   メインプログラム（方式ごとに異なる）
      eval_tsp.c   評価関数 距離の計算（すべての方式で同じ）
      Makefile     make 用（方式ごとに異なる）
      GenitorINT   コンパイルした結果の実行用プログラム（各方式とも同じ名前)

1. プログラムの作成．

   • main関数：オリジナルはTSPを対象に作成されているので，取り扱う問題に 応じて修正して利用する．
   • 評価関数：適合値の計算用．TSPの場合は組み込みのものが使用できるが， TSP 以外に使用する場合は使用者が作る必要がある．
   • 交叉：TSP に対しては前述のように各種方式のものが用意されているので， その中から選択すればよい．その他の用途では使用者が作成する必要がある．
   • 突然変異：突然変異のプログラムは含まれていないので，使用者が作る必要が ある．しかし，すでに作ったものがあるので，それを利用すればよい．
   • その他：グラフィック表示などのプログラムを必要に応じて作成する．

2. コンパイル：まずMakefile を作る必要があるが，これは TSP用を参考に すればよい．つぎにコンパイルは コマンド make で行なわれる．

3. 実行方法：configuration file を作成して実行する． コマンドラインでオプションを指定できる． コマンドラインオプションとしては20個指定できる． 実行のための入力ファイルは４つ（TSPの場合）， 実行結果の出力ファイルは２つある．

     uncompress  GENITOR.tar.Z　（圧縮ファイルの場合）
     tar xvf  GENITOR.tar

1. main関数の変更：オリジナルはセールスマン巡回問題（TSP）を対象に 作成されているので，取り扱う問題に応じて修正を必要とする．

2. 評価関数の作成：適合値の計算用．TSPの場合は組み込みのものが 使用できるが，TSP 以外に使用する場合は使用者が作る必要がある．

3. 交叉関係の選択，作成：TSP に対しては前述のように各種方式のものが 用意されているので，その中から選択すればよい． その他の用途では使用者が作成する必要がある．

4. 突然変異の作成：突然変異のプログラムは含まれていないので， 使用者が作る必要がある．

5. その他の作成：グラフィック表示などのプログラムを必要に応じて 作成する．

6. Makefile の修正：現在のディレクトリーに対応して変更する．

7. コンパイル：以上が終わればmakeコマンドによりコンパイルを行い， 実行用ファイルを作成する． まずMakefile を作る必要があるが，これは TSP用を参考にすればよい．
   つぎにコンパイルは コマンド make で行なわれる．

1. configuration fileの作成：実行に際してプログラムに与えるパラメータ値を 記載したファイルである． パラメータ値はコマンドラインのオプションで与えることもできるが， 少なくとも以下の３つのパラメータ値はこのファイルで指定する必要がある．

   • String Length ：ストリングの長さ
   • Population Size ： 集団の個体の数
   • Number Trial ： 実行の回数
   なお，ファイル名は コマンドラインオプション -c で指定する． その他のパラメータ値はあらかじめデフォルト値として与えられているが， それから変える場合はこのファイルか後述のコマンドラインオプションで指定する．

2. コマンドラインでのパラメータ指定：configuration file よりも コマンドラインのパラメータオプションの方が優先する。

3. 実行：つぎのコマンドで実行する．

      GenitorINT -c tsp30.config 
      configulation file 名をオプション -c で与えた場合．
    

-c file       Config File    オプション設定用ファイル． 
-b 2.0  (2.0) Selection Bias 選択の際のバイアスであり，2のとき最良の個体の
　　　　　　　　　　　　　　 選ばれる確率は平均のものの２倍となる． 
-d 4500 (0)   Dump Interval  ファイルをダンプする間隔．
-e            Experiments    実験の数．
-f file       Final Populatoin file 最終結果の出力するファイル名．
-g 124  (0)   Current Generation 再スタート時に設定する世代の値．
-i file       Initial Population File  集団の初期化用データ，遺伝子の値と
　　　　　　　　　　　　　　　　　　　 その評価値．
-l 25       * String Length  遺伝子の長さ．
-m 0.0        Mutation  Rate 突然変異の確率．
-n file       Node File      TSPのみ必要ファイル．都市の位置情報 X-Y．
-o file       Dump File      ダンプファイル名．ファイル名には拡張子は不用．
                             dump\_pool,dump\_config の両ファイルを出力．
-p 100      * Pool Size      集団の個体数．
-r 8765       Random Seed    乱数の種，Long Integer．
-s 750        Status Interval 簡単な出力を画面に出す間隔（実行回数）．
-t 9000     * Number Trials  実行回数の指定．この値を個体数で割った値が世代数．
 　　--- 以下は殆んど考慮の必要なし ---
-u Float N    Cut Off
-w Int        NumPOP         sub-population の数．
-x Int        Swap Interval  スワップ間隔．
-y Int        Swap Numbers   スワップするストリングの数．
-z reset/check               reset : 値がすべてゼロとなる．
                             check : デフォルト値に設定する．

1. 入力関係

   • configuration file ：各種パラメータの入力 (-c option)
   • node file ：位置データ，TSPのみに必要(-n option)
   • initial population file ：集団の初期化用で，これがない場合は乱数で設定す る．

2. 出力関係

   • final population file ：最終の集団のデータ、-i option による再開に 使用できる(-f option)
   • output dump file ：ダンプ用 (-o option)．つぎの２つのファイルを出力
     • .config ：設定パラメータ関係．print_param()参照
     • .pool ：１個体のデータ．print_pool()参照