遺伝的アルゴリズム

移転しました。

GAを実際に最適化問題に適用する場合

  • 個体の表現方法 どのように解を個体として表現するか
  • 個体の評価方法 どのように個体を評価するか
  • 解探索のための操作の設計 どのように個体を進化させるか

についてまず考える必要がある。

遺伝子の配列を遺伝子型(genotype)
遺伝子型に基づいて発現した個体を表現型(phenotype)

適応度

ナップサック問題の例では、ナップサックに入れた荷物の価値の総和、つまり目的関数値そのものを適応度することができる。

しかし、TSPの場合には、より短い順回路を求める必要があるため、目的関数値である巡回路長そのものを適応度とすることができない。そのため、巡回路長の逆数を適応度とするなどの変換が必要になってくる。

適応度の変換、スケーリング

スケーリング(scaling)とは?
良好に探索が進むように選択圧を調節すること。ここでの選択圧とは、選択の強さを表す指標で、選択圧が高いと劣った解はすぐに淘汰され死滅する。