伊庭研究室

書籍サポート / Support

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

TSP シミュレータ 解説

GA を用いて巡回セールスマン問題(Travelling Salesman Problem, TSP)を解くことができます。概観は以下のとおりです。

TSPシミュレータの操作方法

  • Coding
  •     遺伝子方の表現方法を決定します。コーディング法は以下の2つから選択できます。
          1.Normal : バイナリ表現によるコーディング
         2.Ordinal representaion : 巡回表現によるコーディング
  • Report
  •    チェックを入れると交叉状況をReportします。

  • Parameter
  •     Number of city町の数
        Interval of Generation :探索を行う世代数を決定します。
        Population Size :個体数です。1世代あたりの評価回数と等しいです。
        Crossover Rate :交叉率です。
    こ の割合の個体が他の個体と交叉します。
        Mutation Rate :突然変異率です。この割合の個体の遺伝子が突然変異します。

        ※Reportにチェックを入れると探索速度は非常に遅くなります。
        このときはNumber of City,Population size を小さくして下さい。

  • Selection Method
  •     交叉時の親の選択方法を以下の3つから決定します。
         1.Roulette :ルーレット方式による選択
         2.Tournament :トーナメント方式による選択
         3.Random :ランダムに選択
     
      Tournament Size : Tournament方式を採用した場合に設定するサイズです.
       Elite Strategy : チェックを入れるとエリート戦略を行います。

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