■Pre ■Up ■Next
■3.5.5 NSGA(非優越ソートGA)


1.NSGA(Non-dominated Sorting Genetic A lgorithms

Srinivasらによって提案された手法.
まず非優越ソート(Goldbergの考え出したランキング法)に基づいて個体をランク付けし,同じランク内でシェアリングを行う.ランクレベルのみでシェアリングを行うことによって全個体でシェアリングを行うよりも計算負荷を軽減できる.

また,上位ランク個体の適応度は必ず低いランクの個体よりも高くなるように設定する.つまりランク2内の適応度はランク1内の最低適応度よりも下回る.こうしてランク上位の個体が優先される.

上記のように割り当てられた適応度に基づき,ルーレット選択(適応度分布を基準にした確率的な復元抽出操作)かトーナメント選択(ランダムにトーナメントを作り、各組ごとに大きいほうを残し、この作業を繰り返すことで必要な個体数だけ確保する)のように確率的な選択演算をおこなう.





2.NSGAの利点
  • どんな目的関数の数にでも対応できる
  • 最小化と最大化の両方の問題においてもこのアルゴリズムは対応できる 


3.NSGAの問題点
  • 非優越ソートの高い計算負荷
    用いる個体数が多い場合において非優越ソートアルゴリズムは高負荷である.とりわけ,毎世代ごと個体をソートする必要があるため,無視できない.

  • エリート保存の欠如
    近年の結果より,エリート保存がGAの性能にかなり利いてくることが分かっている.

  • 特別なシェアリングパラメータ ρ_shareの必要性
    同等の解の幅広い多様性を得るといった,個体における多様性を保持しようとする伝統的なメカニズムは,シェアリングの概念に基づいている.シェアリングにおける主な問題は,シェアリングパラメータρ_shareの設計を必要とすることである.動的なシェアリングパラメーターの変化を行うという研究はあるものの,パラメータのない多様性保持のメカニズムが望ましい.