5 遺伝アルゴリズム(GA)の拡張



  • 内容
    • 並列化
    • ハイブリッド化
    • 可変長染色体
    • ニッチ(一定環境における生態系(複数種の混在定常状態)モデル
    • 多目的最適化
    • 免疫システムモデル
  • 並列化

単純並列アプローチとして、個体ごとの処理である発生個体の適応度評価と、それらをあわせて世代単位で処理する遺伝プロセスとに分解する方法がある。また、分解型アプローチとして、集団を区分けして処理する方法がある。集団の区分けとしては集団が互いにある程度隔離された亜集団の集まりとし、亜集団ごとに処理をし、亜集団間で情報のやりとりをする方法と、個体同士の空間的位置関係になぞらえて個体間の遠近関係を導入し、個体ごとに処理し個体間処理の情報をやりとりする方法がある

  • ハイブリッド化

GAを最適化探索の1部品として他の探索アルゴリズムと組み合わせる方法。Heuristicsと組み合わせるのもそのひとつ。また、GAは局所での最適解到達には不向きなアルゴリズムなのでGAによって得られた解から局所探索をする方法も知られ、遺伝的局所探索(Genetic Local Search)と呼ばれている。遺伝的局所探索は生物学的な意味合いで、次のように説明される。遺伝子がGAで作られたのち、環境適応できるものは、適応し、その環境適応の部分を局所探索による改善がもたらしていると考える。その環境適応度の多寡が子孫数に反映するというもので、この後天性の適応が遺伝子変化として次世代に伝わるとする立場(遺伝のラマルク主義)と、後天性の適応は遺伝子変化をもたらさないが、子孫数に影響を与えることによって、結果として選択個体の遺伝型(解)に影響を与えるという立場(ボールドウィン主義)とがある。また、局所探索路を複数化する方法(多スタート局所探索法)と呼ばれるものも知られる。さらには、確率的に解の改善を試みる方法である、シミュレーテッド・アニーリング法がある。この方法は熱力学的平衡状態を模している。非常に多くの分子の集合は、平衡状態において温度という値を有する。個々の分子はそれぞれ、運動エネルギーを持つが、そのエネルギーは確率的に分子間で交換され定常分布に達する。温度は、この定常分布を決めるパラメタである。温度が高いときには、分子集合中の分子の中には、局所解から近隣の別の局所解(最適解の可能性がある)に遷移しうる分子エネルギーを持つものが含まれる可能性が高く、温度が低くなるにつれ、遷移のために乗り越えるエネルギー閾値が低くなる。したがって、温度を高温から低温に下げるという1パラメタを制御することによって、演算の初めには大域的探索を行い、処理を進めるにしたがって、局所のみの探索に限定していくことが可能となる

  • 可変長染色体

その名のとおり、遺伝子情報の総長を可変にすることで探索の改善を目指す方法

  • ニッチ(一定環境における生態系(複数種の混在定常状態)モデル

生物界ではある環境は有限な広さを持ち、有限な資源を持つ。そこには生態系と呼ばれる生物−生物間の食物連鎖や共生関係が存在し、固定的な定常状態や周期性を持つ定常推移状態にある。この考え方を援用し、複数の目的関数が作る組み合わせ最適解を演算対象とする方法もある

  • 多目的最適化

多目的最適化においては、パレート最適解という概念がある。x,yは自然数でありx^2+y^2¥le 25を満たすときに、x+yを最大にするx,yは(x,y)={(3,4),(4,3)}であり、最適解が2つ存在する。このようなとき、この2つの解をパレート最適解とよび、両者をパレート最適解群とかパレート最適解集合と呼ぶ。多目的最適化問題においては、パレート最適解集合の中の1つを求めるのではなくパレート最適解をすべて求めることが通常である。探索にあたっては、パレート最適解の1つを探索し、パレート最適解集合に属する他の解を明示的に扱う方法と、それらの明示的に扱わない方法とに分けられる

  • 免疫システムモデル

遺伝において遺伝子情報を交換(交叉)するのは、生物が多様性構築を通して達成している最適化戦略の一つ(目的論的にか結果論的にかは問題にしないとして)であるが、同様に生物が多様性を通じて機能を発揮しているシステムに免疫系の抗体多様性がある。この原理を最適化に援用したのが免疫システムによる最適化計算法である