称号及び氏名

博士（工学） 塚本 実孝

学位授与の日付

平成 22 年 3 月 31 日論

「進化型多数目的最適化およびIndicator に基づく進化型多目的最適化アルゴリズムに関する研究」

文

名

論文審査委員

主査

石渕 久生

副査

市橋 秀友

副査

松本 啓之亮

論文要旨

多目的最適化問題とは，互いに競合する複数の目的を同時に最適化する問題である．多目的最適化問題
では，全ての目的に関して最適となる絶対的な解が存在することは非常に稀である．一般に各目的間には，一方を良くすれば一方が悪くなるトレードオフの関係が存在する．例えば製品開発では，製品機能の最大化と開発費用の最小化は互いに相反する目的であり，両方の目的を考慮する必要がある．材料開発や部品設計では，強度最大化と重量最小化は相反する．また，日常的に購入する多くの商品やサービスにおいても，商品の機能と価格あるいはサービスの質と価格の間にトレードオフの関係が存在する．多目的最適化
では，個々の解は優越関係を用いて評価される．しかし，複数の目的の間にトレードオフの関係が存在するため，優越関係が成立しない多数の解が存在する．したがって，優越関係を用いた比較では，どの解が良い解であるか判断することが出来ない．このような他の解に優越されないような解をパレート最適解と呼ぶ．多目的最適化問題には，多数のパレート最適解が存在し，パレート最適解の集合は目的関数空間上においてパレートフロントと呼ばれるトレードオフ曲面を形成する．
進化型多目的最適化（EMO: Evolutionary Multiobjective Optimization）は，進化計算において最も活発な研究分野の一つであり，様々な問題に適用されている．EMO アルゴリズムの目的は，１回の実行で出来るだけ多くのパレート最適解またはパレート最適解集合を近似する非劣解を効率よく獲得することである．効率的な解の探索を行うため，パレート優越関係に基づくランキング，過疎度に基づく多様性維持，エリート保存戦略を持つ EMO アルゴリズムが多数提案されている．このような特徴を持つ EMO アルゴリズムの中でも，NSGA-II や SPEA2 が幅広く用いられており，その有効性が示されている．また，パレート優越関係だけでなく，スカラー化関数を用いた EMO アルゴリズムも提案されている．一方，EMO アルゴリズムと局所探索を組合せたハイブリッドアルゴリズムも提案されており，これらの有効性も示されている．

近年，EMOアルゴリズムを目的数が４以上の多目的最適化問題である多数目的最適化問題に適用した進化型多数目的最適化と呼ばれる研究が盛んに行われるようになり，注目を集めている．多数目的最適化問
題に対しては，パレート優越関係を用いたEMOアルゴリズムの探索性能が低下することが示されている．
そこで，EMOアルゴリズムの探索性能の低下を防ぐための手法が提案されている．
一方，多数目的最適化問題に対する有効なEMOアルゴリズムとして，Indicator functionと呼ばれる個体群全体を評価する関数を用いたEMOアルゴリズム（Indicator-Based EMO Algorithm）が提案されている．
Indicatorに基づくEMOアルゴリズムでは，HypervolumeがIndicator functionとして用いられることが多い．つまり，Indicatorに基づくEMOアルゴリズムは個体群全体を評価するIndicator functionであるHypervolumeの最大化を行う単一目的最適化手法となる．Indicatorに基づくEMOアルゴリズムの問題点は，目的数の増加と共にHypervolumeの計算量が指数関数的に増加することである．したがって，Indicatorに基づくEMOアルゴリズムを多数目的最適化問題に対して適用することは困難となる．
本論文では，進化型多数目的最適化および Indicator に基づく EMO アルゴリズムに関して論述した．第２章以降の各章の内容は以下の通りである．
本論文では，進化型多目的最適化を用いて，ルールに基づく識別器，および，相関ルールの獲得について論述した．第２章以降の各章の内容は以下の通りである．
第２章「Hypervolume に基づく繰り返し型進化型多目的最適化アルゴリズムの提案」では，１回の実行で１つの解を獲得する繰り返し型 EMO アルゴリズムを提案した．繰り返し解を探索する際には，個体群全体の Hypervolume が最大となるような解が獲得される．しかし，繰り返し解を探索する際に，Hypervolumeを最大化する領域に探索が進まなくなる可能性がある．そのため，繰り返し型 EMO アルゴリズムでは，初めに各目的に対して，単一目的最適化を行うことにより，各目的に対して基準となる解を獲得する．その後，決められた終了基準に達するまで，基準となる解と個体群全体の Hypervolume が最大となる解を繰り返し探索する．
数値実験では，提案手法の有効性を示すため，代表的な EMO アルゴリズムである NSGA-II
および Hypervolume に基づく EMO アルゴリズムである IBEA との比較を行った．数値実験より，提案手法によって，多様性に優れた解集合が獲得されることを示した．目的数が増加した場合でも，良好な結果が獲得されることを示した．また，パレートフロントに対して，均一に解を獲得することが出来ることを示した．さらに，繰り返し回数が少ない場合には，NSGA-II や IBEA と比べて，提案手法の計算時間が短くなることを示した．一方，繰り返し回数が多い場合には，１つの解を探索するための計算量が少なくなるため，繰り返し回数が少ない場合よりも探索性能が低下することを示した．さらに，繰り返し回数が少ない場合よりも計算時間が長くなることを示した．
第３章「多数目的最適化問題への進化型多目的最適化アルゴリズムの適用と問題点」では，多数目的最適化問題に対して EMO アルゴリズムを適用した際の問題点に関して述べた．まず，多数目的最適化問題を用いた数値実験において，パレート優越関係に基づく EMO アルゴリズムの探索性能が低下することを示した．探索性能の低下を示すために，パレート優越関係に基づく EMO アルゴリズムである NSGA-II を多数目的最適化問題に適用し，探索挙動の解析を行った．数値実験より，目的数が増加するにつれて非劣解の数が増加することを示した．また，非劣解の数が増加することによって，パレート優越関係に基づく解の評価が困難になり，パレートフロントに対する収束性が低下することを示した．さらに，パレート優越関係に基づく評価が困難になることによって，多様性基準に基づいた進化が行われることを示した．次に，多数目的最適化問題において，パレート優越関係に基づく EMO アルゴリズムの探索性能の低下を防ぐために提案されている手法の説明を行った．多数目的最適化問題に対して提案されている手法の比較実験を行い，各手法の有効性を検討した．数値実験より，各手法によって，EMO アルゴリズムの性能が改善されることを示した．また，第２章で提案した繰り返し型 EMO アルゴリズムと他の改善手法との比較を行い，多数目的最適化問題に対する有効性の検討を行った．
第４章「進化型多数目的最適化における Hypervolume 近似手法の提案」では，スカラー化関数を用いたHypervolume の近似手法を提案した．提案手法では，均一に分布した重みベクトルを用いる．そして，その重みベクトルに対して参照点から獲得された解によって形成される Attainment Surface と呼ばれる境界線までの距離を計算する．その距離を各重みベクトルに対して計算し，平均することによって，Hypervolumeを近似する．数値実験では，提案手法の Hypervolume の近似性能および Indicator に基づく EMO アルゴリ

ズムへの適用可能性の検討を行った．数値実験より，目的数が少ない場合では，提案手法によってHypervolume が近似されていることを示した．一方，目的数が多い問題に対しては，提案手法の Hypervolumeの近似性能が低下するが，重みベクトルの数を増加させることによって，提案手法の近似性能が改善されることを示した．
また，目的数が多い問題に対して重みベクトルを多数用いた場合でも，通常のHypervolume計算よりも計算時間が短くなることを示した．
さらに，計算量を比較することによって，既存のHypervolume計算は目的数に対して指数関数的に計算量が増加するが，提案手法では目的数に対して線形的に計算量が増加することを示した．
第５章「Hypervolume近似手法を適用したIndicatorに基づく進化型多目的最適化アルゴリズムの性能調査」
では，第４章で提案したHypervolume近似手法をIndicatorに基づくEMOアルゴリズムに適用し，その性能調査を行った．Hypervolumeの近似手法をIndicatorに基づくEMOアルゴリズムにおけるHypervolumeの貢献度計算に対して適用した．貢献度計算を行う解の周辺に集中的に重みベクトルを生成する手法を提案し，生成された重みベクトルを近似手法に適用することにより，各々の解の貢献度を近似した．実数値表現を用いた多目的関数最適化問題による数値実験を用いて，近似手法を用いたIndicatorに基づくEMOアルゴリズ
ムと他のEMOアルゴリズムとの比較を行った．数値実験より，目的数が少ない場合では，近似手法を用いることによって，良好な結果が得られ，さらに計算時間が短縮されることを示した．また，重みベクトルの数を増加させることによって，探索性能が改善されることを示した．一方，多数目的最適化問題においては，探索性能が低下するものの，近似手法を用いることによって，Indicatorに基づくEMOアルゴリズムの計算時間が最大で5000分の１程度に大幅に短縮されることを示した．
第６章「結論」では，本研究で得られた結果について，総括を行った．

審査結果の要旨
本論文は，進化型多目的最適化アルゴリズムの多数目的最適化問題への適用およびIndicatorに基づく進化型多目的最適化アルゴリズムに関して提案，調査したものである．ベンチマーク問題を用いた実験的解析により，以下の成果を得ている．
(1) １回の実行で１個の解を獲得する繰り返し型進化型多目的最適化（EMO）アルゴリズムを提案した．提案手法では，個体群の Hypervolume が最大となるような解の探索を繰り返し行った．
数値実験より，提案手法によって，多様性の優れた解集合を獲得出来ることを示した．また，繰り返し回数が少ないときには，既存の EMO アルゴリズムと比べて，提案手法の計算時間が短くなることを示した．一方，繰り返し回数が多い場合には，探索性能が低下し，計算時間が長くなることを示した．
(2) EMO アルゴリズムを多数目的最適化問題に適用し，その際に生じる問題点を調査した．数値実験より，目的数が増加したとき，EMO アルゴリズムの探索性能が低下することを示した．さらに，多数目的最適化問題における進化型多目的最適化アルゴリズムの探索性能の低下を防ぐための手法に関して述べた．これらの手法の比較実験を行い，各手法の性能調査を行った．
(3) スカラー化関数を用いた Hypervolume の近似手法を提案した．提案手法では，一様に分布した重みベクトルを用い，参照点から獲得された解集合によって形成された境界線までの距離を計算することによって，Hypervolume を近似する．数値実験より，重みベクトルの数を増加させることによって，近似性能が改善されることを示した．また，提案手法の計算量は線形的に増加するが，既存の Hypervolume 計算手法の計算量は指数関数的に増加することを示した．
(4) スカラー化関数を用いた Hypervolume の近似手法を Indicator に基づく EMO アルゴリズムに適用し，その性能を調査した．数値実験より，目的数が少ない場合には，近似手法を用いても良好な結果が得られることを示した．目的数が多い場合には，探索性能が低下するが計算時間を最大で 5000 分の１程度に短縮できることを示した．
以上の研究成果は，知能情報工学分野における進化型多目的最適化の発展に貢献するところ大である．
また，申請者が自立して研究活動を行うに必要な能力と学識を有することを証したものである．学位
論文審査委員会は、本論文の審査ならびに学力確認試験の結果から、博士（工学）の学位を授与することを適当と認める．