進化型アルゴリズムによる多目的最適化

はじめに

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

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

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

多目的最適化問題の解法手段の一つとして,スカラー化手法があります.目的関数それぞれに重みを付け足し合わせることで一つの評価関数とする加重和法、あるいは一つの目的関数を除いて残りすべての目的関数を制約条件とすることで一つの評価関数とするε-制約法などが提案されています.ただし,これらの手法では一度の探索で一つのパレート最適解しか得ることが出来ません.つまり,目的関数間のトレードオフを把握するためには,探索を試行錯誤的に繰り返す必要があります.

一方,EAは解集団を用いた多点解探索法であるため,一度の探索で多数のパレート最適解を同時に求めることが可能である.また,スカラー化手法では導出が難しいとされる非凸や非連続のパレートフロントの探索にも頑健な探索性能を示し,MOPの有力な解法手段とされています.このようなEAの利点から,1985年,SchafferらによるVector Evaluated Genetic Algorithm(VEGA)の提案に始まり,今日までMOP の解法にEAを用いる多目的進化型アルゴリズム(Multi-objective Evolutionary Algorithm,以下MOEA) の研究が鋭意進められています*3*4.昨今では,進化型計算の選択の際に,パレート支配の概念を用いて解の優劣関係を決定するNSGA-II, SPEA2などのアルゴリズムのPOS探索性能の高さが示されています. 多目的EAでは得られたPOSの真のPOSへの収束性や,解の多様性を同時に実現することが重要となります.

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

進化型アルゴリズム(EA)

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

EAの種類としては遺伝的アルゴリズム,進化型戦略,遺伝的プログラミングがあげられます.遺伝的アルゴリズム(GA)は,Holland先生によって提案されたアルゴリズムです*5.GAは複数の個体を解集団として用意し,適応度を考慮して選択した親個体の遺伝子情報を組み替える交叉と呼ばれる遺伝的操作を主に探索を行い,局所解からの脱出とより良い解への誘導を図るために突然変異を行います.一方,Rechenberg先生とSchwefel先生は主に突然変異を用いた探索を行う進化型戦略(ES)を提唱しました*6*7.GAが解集団を用いるのに対し,最も単純なESでは親個体と子個体の2個体の中から, 優れている方を次世代の個体に選択する方法がとられます.また,Koza先生は遺伝子型に木構造やグラフ構造を扱えるようにGAを拡張した遺伝的プログラミング(GP)*8を提案しています.

これまで, EA による最適化問題の解法では,主に単一目的関数の最適化の検討が多数行われてきました.

多目的最適化問題(MOP)

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

#ref(): File not found: "01.gif" at page "進化型アルゴリズムによる多目的最適化"

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

#ref(): File not found: "02.gif" at page "進化型アルゴリズムによる多目的最適化"

が成立するとき,xyを支配するといいます.近年のMOEAは,解の支配を用いて解集団内での解の優劣を決めます.つまり多くの解を支配している解ほど,次の世代に自身の遺伝的情報を残すことができるわけです.また,この支配を用いてPOSを,

#ref(): File not found: "03.gif" at page "進化型アルゴリズムによる多目的最適化"

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

多目的進化型アルゴリズム(MOEA)

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

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

nsgaii.jpg

MOEAのシミュレーション実験

NSGA-IIを用いて多目的0/1ナップザック問題を解くJAVAアプレットを以下に掲載します.Zitzler先生のWEBページからテスト問題を採用させていただきました.のプロットが求めるべき真のPOS,のプロットが解集団になります.パラメータも変えられるように作られていますので,目的関数空間における解集団の進化を時系列的に見ることができて面白いと思います.

  • 多目的ナップザック問題のパラメータ
アイテム数 n100
ナップザック m2
実行可能率 φ0.5
  • 遺伝的パラメータ(初期設定)
集団サイズ N100
交叉法二点交叉
交叉率 Pc1.0
突然変異法ビット反転
突然変異率 Pm0.01
世代数 G50

まとめ

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


*1 J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.
*2 D. E. Goldberg, Genetic Algorithms in Search, Optimization & Machine Learning, Addision-wesley, Reading, 1989.
*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.
*5 J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.
*6 I. Rechenberg, Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution, Frommann-Holzboog, 1973
*7 H.P. Schwefel, Numerical Optimization of Computer Models, Wiley, Chichester, UK, 1981.
*8 J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, The MIT Press, 1992.
*9 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.
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS