はじめに
普段あまり意識することはないが、世の中には多く最適化されたモノが溢れており、その多くが複雑に最適化されたモノである。
例えば海上物流において、輸送船の本数を増やすと、輸送時間の観点から荷主(荷物を送りたい人)の利便性が上がる一方で、輸送需要量(送りたい荷物の量)は変わらないため、輸送費用の観点から船主(荷物を運ぶ人)の利益は下がる。
このように1つの指標を追い求めると、もう１つの指標を毀損するようなモノも少なくない。
この記事では、このような問題(多目的最適化問題)を解決する手法の1例として、
NSGA-Ⅱ[1]という手法を取り上げる。
多目的最適化問題とは何か?
上でも簡単に説明したが、複数の目的関数に対し、同時に最適化を行う問題を多目的最適化問題と呼ぶ。
多目的最適化問題は一般に、n個の設計変数を伴うk個の目的関数f(x)を、m個の制約条件g(x)のもとで最小化あるいは最大化する問題として式(3-1)のように定式化される。
min f_i(x_1,x_2,...x_n) (i=1,2,...,k) (3-1)
subject to g_i(x_i,x_2,...,x_n) (j=1,2,...,m)
多目的最適化問題では、一般に複数の目的関数同士が互いに優劣に影響を及ぼす場合が多いので、全ての目的関数f_i (x)を同時に最適化することはできない。そこで、多目的最適化問題では１つの最適解を求める代わりに、パレート最適解集合を求める。
パレート最適解
パレート最適は、ある一つの目的関数の値を改善しようとすると、かならず他のいずれかの目的関数の値が悪化するような状態のことであり、以下に多目的最適化における解の優劣関係の定義を記す。
定義1 （パレート優越）
ベクトル関数値$f_i (X), X = (x_1,x_2,…,x_n ), X_1,X_2∈X$において、
f_i (X_1 )≤f_i (X_2 ) (∀i=1,2,…,k) (3-2)
f_i (X_1 )<f_i (X_2 ) (∃i=1,2,…,k) (3-3)
数式(3-2)、(3-3)が成立するとき、$X_1$は$X_2$をパレート優越するという。
定義2 (パレート最適・パレートフロント)
ベクトル関数値$f_i (X), X = (x_1,x_2,…,x_n )$, $Y∈X$において、$Y$をパレート優越する$X$の元が存在しないとき、$Y$はパレート最適であるという。
以下の図に目的関数が2つの場合におけるパレート最適解の例を示す。図中のプロットは、各々実行可能領域における解の一つを表しており、先に述べたパレート最適解(パレート最適である解)の集合によって形成される曲面をパレート最適フロントと呼び、図中の点線曲面にあたる。さらに、他のどの解と比較しても劣らない解を非劣解と呼び、パレートフロント上の解は互いにある目的関数値では優れるがもう一方の目的関数値で劣る非劣解である。
NSGA-Ⅱ
NSGA-Ⅱ(Elitist Non-dominated Sorting Genetic Algorithm)は、Debらによって2002年に提案された多目的遺伝的アルゴリズムである。
多目的遺伝的アルゴリズムでは単一目的遺伝的アルゴリズムとは異なり、それぞれの目的関数について独立に評価・選択を行うアプローチ(非パレート的アプローチ)と、解同士のパレート優越関係を用いて適応度を割り当てて評価・選択して次世代継承をするアプローチ(パレート的アプローチ)がある。
前者の代表的な例としては、ベクトル評価遺伝的アルゴリズム(Vector Evaluated Genetic Algorithms)[2]、後者の例としては、本節で紹介するNSGA-Ⅱや、ZitzlerらのSPEA2[3]がある。特に、NSGA-Ⅱは適合度の高い個体の保存方法や、多様性に優れた個体の抽出方法に優れているため、多目的最適化問題において数多くの適用例がある。
NSGA-Ⅱの主な特徴としては、「非優越ソート」によるランキング法、「混雑距離」の導入、「混雑度トーナメント選択」の導入が挙げられる。
アルゴリズム
NSGA-Ⅱでは、保存する母集団(アーカイブ母集団)$P_t$と交叉・突然変異といった遺伝子操作を用いた探索を行うための母集団$Q_t$の2つの独立した母集団を用いて解探索を行う。この手法では、非劣個体を保存する母集団$P_t$を親母集団とし、探索を行うための母集団$Q_t$を子母集団として用いることにより解探索を行っている。
具体的には、個体数$N$として、まず世代tにおける親母集団$P_t$から探索を行うための子母集団$Q_t$を選択する。そして、$Q_t$に対して各遺伝子操作を行って$Q_t$を更新する。次に$Q_t$と親母集団$P_t$を組み合わせた$R_t=P_t∪Q_t$を生成し、個体数$2N$の$R_t$から個体数$N$の$P_{t+1}$を新たに選択して探索を進める。具体的なアルゴリズムの流れは以下のようになる。
- $t=1$とする。探索母集団$Q_t$を初期化し、アーカイブ母集団$P_t=∅$とする。
- 探索母集団$Q_t$に対して、交叉・突然変異を適用し、$Q_t$の目的関数値を導出する。
- アーカイブ母集団$P_t$と探索母集団$Q_t$を組み合わせて$R_t=P_t∪Q_t$を生成する。$R_t$に対して非優越ソートを行い、全個体をランクごとに分類する。$Rank_i (i=1,2,…)$
- 新たなアーカイブ母集団$P_t=∅$を生成する。変数$i=1$として、
$|P_(t+1) |+|Rank_i |<N$を満たすまで、$P_{t+1}=P_{t+1}∪Rank_i$と$i=i+1$を実行する。 - 混雑距離を導出し、$Rank_i$の中で最も多様性に優れた(混雑距離の大きい)個体$N-|P_{t+1} |$個を$P_{t+1}$に加える。
- 終了条件を満たしていれば終了する。
- $Q_{t+1}=P_{t+1}$として、新たに探索母集団$Q_{t+1}$を生成する。$t=t+1$としてstep2.に戻る。
上記のように、NSGA-Ⅱでは、各世代で常にそれまでの世代における優良な個体を保存するアーカイブ母集団と探索を行う母集団を分けて保持することで、それまでの探索で発見した優れた解が欠落するのを防いでいる。Step 3からStep 5までの処理を以下の概念図に表す。
非優越ソート
非優越ソート(Non-Dominated Sort)は、1989年にGoldberg[4]により提案されたアルゴリズムで、NSGA-Ⅱにおいて適応度の高い個体を抽出するために用いられている個体のランク付け方法であり、これが上述のパレート的アプローチにおける適応度の割り当てにあたる。以下、非優越ソートのアルゴリズムを記す。
- ランクr=1とする。
- 個体群Pの中から非劣個体を求め、これらの個体をランクrとする。
- 得られた非劣個体群を個体群Pから除き、$r=r+1$とする。
- すべての個体がランク付けされるまで(個体群$P=∅$となるまで)、Step2およびStep3を繰り返す。
非優越ソートに基づくランク付けの例は下図のようになります。
混雑距離
混雑距離は、同一ランク内の個体同士において、そのパレート曲面上で各目的関数値が隣接する個体間の距離を評価するための手法である。以下、非優越ソートのアルゴリズムを記す。
- ランクRankに含まれる個体数を変数$l=|Rank|$として代入する。このランクに含まれる各個体$i$に対して混雑距離$d_i=0$ $( i=1,2,…,l)$として初期値設定を行う。
- 各目的関数$f_m$ $(m=1,2,…,k)$に対して、目的関数値が悪い順にソートを行う。$：I^m=sort(f_m,>)$
- 各目的関数$f_m$ $(m=1,2,…,k)$に対して、最初に境界個体に対して最大距離、もしくは無限距離を与える。$：d_{I_1^m} =d_{I_l^m }=∞$ そして、境界個体以外の全ての個体$( i= 2,…,l-1)$に対して式(3-4)に従い混雑距離を導出する。ここで、$I_j^m$は$m$番目の目的関数においてStep 2でソートした個体群の中で$j$番目の個体である。
d_j=\sum_{m=1}^{k} \frac{f_m^{I_{j+1}^m}-f_m^{I_{j-1}^m }}{f_m^{max}-f_m^{min}} j∈[2 ,l-1] (3-4)
混雑距離の導出過程の例は下図になります。
混雑度トーナメント選択
混雑度トーナメント選択は、ランクが高い個体を優先的に選択し(アルゴリズム Step 4)、さらに各ランクによって形成されるパレートフロントの中でも、特定フロントから限られた数の個体を抽出する場合(アルゴリズム Step 5における$N-|P_{t+1} |$個を$P_{t+1}$に加える過程)、そのフロントから一様に分布する(多様性に富む)ように個体を選択する方法である。個体$i$のランクを$i_{rank}$とし、個体の混雑距離を$i_{distance}$として個体$i$と$j$の優越関係を評価する際、具体的には以下のいずれかの基準を満たす際に$i$は$j$よりも優れていると評価し、アーカイブ母集団の個体として選択する候補を比較する方法である。
個体$i$のランクが個体$j$のランクよりも優れている。($i_{rank}<j_{rank}$)
個体$i$とはともに同じランクであり、$i$の混雑距離が$j$よりも優れている。
最後に
海上物流を題材にした研究論文のリンクも貼るので、もし仮に興味ある方がいらっしゃったら見てみてください。
https://drive.google.com/open?id=1FE8AMJ4diup6-Cqu8o_KlCvFA6_H7jXN
参考文献
[1] K.Deb et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ. IEEE Transactions on Evolutionary Computation, vol.6, Apr, 2002
[2] J.D.Schaffer. Some experiments in machine learning using vector evaluated genetic algorithms (artificial intelligence, optimization, adaptation, patter recognition). Vanderbilt University Nashville, TN, 1984
[3] E. Zitzler, M. Laumanns, L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Technical Report 103, Computer Engineering and Communication Networks Lab (TLK). Swiss Federal Institute of Technology (ETH) Zurich , 2001
[4] D.E.Goldberg. Genetic algorithms in search, optimization and machine learning. Addison-Wesly, 1989.