進化計算による多目的最適化

はじめに

生物の遺伝と進化の過程をモデル化して構築された進化型アルゴリズム(Evolutionary Algorithms，以下EA) は，探索，学習，最適化，分類などの手段として，幅広い分野で有用性が示されています．EA による最適化問題の解法では，これまで，主に単一目的関数の最適化の検討が多数行われてきました．しかし，意思決定などの現実問題では，最適化すべき目的関数が1つだけであることは稀で，複数の目的関数が互いにトレードオフの関係となって存在する多目的最適化問題(Multi-objective Optimization Problem，以下MOP) となることが多くなります．

例えば，自動車の設計においては，走行性能と価格の間にはトレードオフの関係があり，走行性能の高い自動車は高価格に，低価格な自動車は走行性能を落とさざるを得ません．このように一方を追求すれば他方を犠牲にせざるを得ない背反の状態・関係にある目的を同時に最適化する問題が多目的最適化問題になります．

単一目的最適化との違いは，複数の目的関数を同時に最適化するところにあります．多目的最適化問題では，それぞれの目的関数の間にトレードオフの関係が存在することが多いため，すべての目的関数を同時に最大化(もしくは最小化)する単一の解は一般的に存在せず，目的関数空間でトレードオフの関係を示すパレート最適解集合(Pareto-Optimal Solutions，以下POS)を求めることになります．パレート最適解集合の分布によって，その目的関数間のトレードオフを把握することが多目的最適化のゴールになります．

EAは，解集団を用いた多点解探索法であるため一度の探索で多数のパレート最適解集合を同時に求めることが可能な点で多目的最適化問題の有用な解法手段とされています．1985年，SchafferらによるVector Evaluated Genetic Algorithm(VEGA)の提案に始まり，今日までMOP の解法にEAを用いる多目的進化型アルゴリズム(Multi-objective Evolutionary Algorithm，以下MOEA) の研究が鋭意進められてきました．昨今では，進化型計算の選択の際に，パレート支配の概念を用いて解の優劣関係を決定するNSGA-II, SPEA2などのアルゴリズムのPOS探索性能の高さが示されています．

こちらのページではEA，MOP，MOEAについて簡単に紹介し，最後にコンピュータ・シミュレーションを行います．

進化計算

生物は環境に対する適応度の高い個体ほど，その個体が持つ遺伝子を後の世代に受け継がれるように増殖と淘汰を繰り返し，進化していくと考えられています．この生物の進化の過程における，自然淘汰，遺伝的操作の仕組みを模倣して解探索を行う計算アルゴリズムがEAになります．EAでは，最適化問題の解を個体の遺伝子として表現し，評価関数を用いてすべての個体に評価値を与えます．評価値に基づいて次世代の親となる個体が選択され，親個体の持つ遺伝子情報を，遺伝的操作によって組み換ます．これらを繰り返すことにより，高い評価値を示した個体の遺伝子情報(解)を手がかりに，個体集団を用いてさらに高い評価値を示す個体の探索を実現します．これまで， EA による最適化問題の解法では，主に単一目的関数の最適化の検討が多数行われてきました．

多目的最適化問題

意思決定などの実世界の問題では，最適化すべき目的関数が1つだけであることは稀で，複数の目的関数が互いにトレードオフの関係となって存在する多目的最適化問題(MOP)となります．MOPは以下のように定義されます．ここでは最大化を考慮することにします．

$$\left\{\begin{array}{l} \text{Maximize} & \boldsymbol{f}( \boldsymbol{x})=(f_1( \boldsymbol{x}),f_2( \boldsymbol{x}),\cdots, f_m(\boldsymbol{x})) \\ \text{subject to} & \boldsymbol{x} \in \mathcal{F} \end{array}\right.$$

すなわち，多目的最適化とは。\(m\)種類の目的関数 \( f_{i}(i=1,2,\cdots,m) \)からなるベクトル評価関数 \(\boldsymbol{f}\)について，解空間\(\mathcal{S}\)の実行可能領域 \( \mathcal{F}\) \((\mathcal{F}\subseteq\mathcal{S})\)内の決定変数ベクトル \(\boldsymbol{x}\)を用いて\(f_{i}\)の値を最大にすることと言えます．次に解の支配について定義します．\(\boldsymbol{x},\boldsymbol{y}\in\mathcal{F}\)に対して，

$${\forall} i \in {1, 2,\cdots , m} : f_i(\boldsymbol{x}) \ge f_i( \boldsymbol{ y}) \quad \wedge \quad {\exists} i \in {1,2,\cdots,m}:f_{i}( \boldsymbol{ x})>f_{i}( \boldsymbol{y})$$

が成立するとき，\(\boldsymbol{x}\)は \(\boldsymbol{y}\) を支配する(\({\boldsymbol{f}(\boldsymbol{x})\succeq \boldsymbol{f}(\boldsymbol{y})}\))といいます．近年のMOEAは，解の支配を用いて解集団内での解の優劣を決めます．つまり多くの解を支配している解ほど，次の世代に自身の遺伝的情報を残すことができるわけです．また，この支配を用いてPOSを，

$$\mathcal{P} = \{ \boldsymbol{x}\in \mathcal F {\rm~} | {\rm~} { \neg \exists} { \boldsymbol{ y} \in \mathcal F: f( \boldsymbol{ y}) \succeq f( \boldsymbol{ x}) }\}$$

の様に定義します．つまり，POSはどの解にも支配されない解集合であるといえます．MOEAでは解集団内の支配されない解集合を最終的に解として導出します．

進化計算による多目的最適化

EAは解集団を用いる多点探索であるため，一度の探索でトレードオフをなすパレート最適解集合(Pareto Optimal Solutions: POS) を求めることができます．このためMOPの解法にEAを用いる多目的進化型アルゴリズム(Multi-objective Evolutionary Algorithm: MOEA)は，効率良くMOPを解法する有力な手段として注目され，様々な応用例が報告されています．近年，POS探索性能が高いとされるNSGA-II(Nondominated Sorting Genetic Algorithm II)と呼ばれるアルゴリズムについて紹介します．

NSGA-IIでは，\(t\)世代の親集団\(P_t\)と子集団\(Q_t\)を合わせた\(P_t \cup Q_t\)について，集団内の各個体を支配されないレベルで個体をランク付けし，フロントと呼ばれるいくつかの階層に分類して親個体の選択に反映させます．上位フロントから順に半数の個体を選び，次世代の親集団\(P_{t+1}\)とする．この際，同一フロントに存在する解の優劣は，Crowding Distance (CD)と呼ばれる目的関数空間における解の混雑度を考慮して決定します．CDによる解の取捨選択では，各目的関数の最大値と最小値を評価値として持つ個体を絶対的に優遇する仕組みがあり，解集団に多様性を生み出すことが可能になります．支配ランクと解の混雑度に基づくバイナリートーナメント選択によって\(P_{t+1}\)から親個体を選び，これらに交叉，突然変異を施して子個体を生成します．

実験

0/1多目的ナップザック問題

NSGA-IIを用いて多目的0/1ナップザック問題を解くデモ動画を以下に掲載します．Zitzler先生のWEBページからテスト問題を採用させていただきました．赤のプロットが求めるべき真のPOS，黒のプロットが解集団になります．目的関数空間における解集団の進化を時系列的に見ることができて面白いと思います．

多目的連続関数最適化 DTLZ1

多目的連続関数最適化 DTLZ2

まとめ

研究紹介程度ではありましたが，進化型アルゴリズムを用いた多目的最適化について簡単に説明，コンピュータ・シミュレーションのためのデモ動画を掲載させていただきました．少しでも興味を持っていただけたら幸いです．

1. J. H. Holland, ”’Adaptation in Natural and Artificial Systems”’, University of Michigan Press, 1975.))((D. E. Goldberg, ”’Genetic Algorithms in Search, Optimization & Machine Learning”’, Addision-wesley, Reading, 1989.
2. K. Deb, S. Agrawal, A. Pratap and T. Meyarivan, “A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II”, ”’KanGAL report 200001”’, 2000.
3. K. Deb, ”’Multi-Objective Optimization using Evolutionary Algorithms”’, Jhon Wiley & Sons, 2001.
4. C. A. C. Coello, D. A. V. Veldhuizen, and G. Lamont, ”’Evolutionary Algorithms for Solving Multi-Objective Problems”’, Boston, Kluwer Academic Publishers, 2002.