称号及び氏名

博士（工学）

学位授与の日付

平成 31 年 3 月 31 日論

「実問題に即した進化型多目的最適化手法の開発と文

名谷垣勇輝

ベンチマーク問題の作成に関する研究」

論文審査委員

主査

本多克宏

副査

宇野裕之

副査

中島智晴

副査

能島裕介

論文要旨

日常的に行っている小さな意思決定から組織単位の複雑な計画策定に至るまで，現実世界には様々なレベルの意思決定が溢れている．意思決定における選択肢の評価は，評価指標，すなわち目的関数を最大化，あるいは最小化するような最適解を求める最適化問題として定式化することが可能である．このとき，個々の選択肢が複数の評価基準を持つことは珍しくない．多目的最適化は，このような複数の評価基準を同時に最適化することで，選択肢となりうる解を選別する強力なツールである．
多目的最適化では全ての目的関数を同時に最適化する唯一の最適解が存在することは非常に稀である．一般には，一方の目的関数を改善すると他方の目的関数は悪化するトレードオフの関係が存在する．例えば，製品開発において，開発コストの最小化と製品性能の最大化は互いに反する目的となる．部品設計においても，強度最大化と質量最小化は相反する．旅行プランの意思決定では，サービスや利便性と価格にはトレードオフが存在する．このような多目的最適化問題における複数の最適解のことを，パレート最適解と呼ぶ．特に，目的関数空間においてパレート最適解集合によって構成されるトレードオフ曲面はパレートフロン
トと呼ばれる．
意思決定者がパレート最適解集合から，目的関数間のトレードオフ情報など，問題に対する有益な知識を獲得可能であることは，多目的最適化の大きな利点である．そのため，多目的最適化ではパレート最適解，あるいはその近似解を多数獲得することが望ましい．メタヒューリスティクス手法の一つである進化型最適化手法は，複数の解による多点探索という特徴を活かすことで，多目的最適化問題においても複数のパレート最適解を１度の実行で獲得可能である．この手法は進化型多目的最適化（Evolutionary Multiobjective Optimization:EMO）と呼ばれ，アルゴリズムの開発が活発に行われている．

これまで，工学，医療，経済など多くの実問題において EMO アルゴリズムが優れた性能を示すことが報告されている．一方で，目的数が 4 以上の多数目的最適化問題，膨大な決定変数を扱う大規模最適化問題，複雑な多数の制約を持つ最適化問題といった従来の EMO アルゴリズムが苦手とする問題が存在することも報告されている．そのため，近年の進化計算の分野では，このような困難な特徴を含む実問題を想定した EMO アルゴリズムの開発が高い関心を集めており，多数目的最適化問題を指向した NSGA-III や大規模最適化問題を指向した WOF のように，特定の問題領域において高い性能を発揮するアルゴリズムが提案されている．
これらの EMO アルゴリズムの性能評価で主に用いられるのがベンチマーク問題である．
特に，近年の激しい EMO アルゴリズムの開発競争では，DTLZ や WFG といった一部の有名なベンチマーク問題群による EMO アルゴリズムの評価が繰り返し行われている．しかし，現実世界には多様な多目的最適化問題が存在するにも拘らず，これらのベンチマーク問題自体の特徴調査はあまり行われていない．
そこで本論文では，まず第 2 章「ベンチマーク問題とアルゴリズムの共進化」において，幅広い既存のベンチマーク問題を年代別に分類することで，既存のベンチマーク問題が年代ごとに類似する傾向を持つことを示す．また，同年代に提案された EMO アルゴリズムとの比較から，ベンチマーク問題の持つ特徴が EMO アルゴリズムに与えた影響について論述し，ベンチマーク問題とアルゴリズムの開発が共進化的に行われていることを示す．
具体的には，1990 年代から 2010 年代までに提案された既存のベンチマーク問題に対して，目的関数空間においてパレートフロントとランダムに生成した解集合の分布を比較する．
パレートフロントと解集合の分布には，年代ごとに類似する傾向があることを視覚的に示すと共に，同年代に提案された EMO アルゴリズムがこの傾向に適した探索メカニズムを持つことを示す．また，ひとたびベンチマーク問題に適した EMO アルゴリズムが開発されると，それらが苦手とする特徴を持った次なるベンチマーク問題が提案されてきたことを示す．
さらに，目的の数が 4 以上となる多数目的最適化を指向した EMO アルゴリズムである
NSGA-III を例として，近年の代表的なベンチマーク問題で高い探索性能を示す最新の EMO
アルゴリズムは，2000 年代に提案された多目的ナップサック問題において探索性能が低下することを示す．これは，2010 年代に提案された多数目的ベンチマーク問題が類似した性質を持っているため，特定の性質を利用することで探索を効率化する，汎用性に乏しい EMOアルゴリズムが開発されたためである．すなわち，近年提案された EMO アルゴリズムは，一部の頻繁に用いられるベンチマーク問題に過剰に適合していると言える．
EMO アルゴリズムが現実世界の多様な多目的最適化問題に対して高い汎用性を持っていることを確かめるためには，多様な特徴を持つテスト問題を用いた性能評価を行う必要がある．しかし，膨大な種類のテスト問題に対して逐一性能調査を実行するのは困難である．すなわち，多様なテスト問題を開発する必要性があると同時に，効率よく問題の多様な特徴について比較する性能評価環境の実現が重要な課題である．
一方，多数目的最適化では，目的数の増加に伴い，トレードオフ関係の全体像を表現するために必要な解の数が指数関数的に増加する．既存の EMO アルゴリズムの多くは，100 から 1,000 個程度の限られた数の個体を用いてパレートフロント全体を近似することを想定して設計されている．しかし，多数目的問題のパレートフロント全体を限られた数の解集合で近似するのは容易でなく，一部の頻繁に用いられるベンチマーク問題にのみ高性能なアルゴリズムが開発されている．現実世界における意思決定のプロセスを考慮すると，意思決定者に膨大な数の候補解を提示し，最も好ましい解を選択させることも現実的ではない．すな
わち，意思決定者に有益な少数の解集合を獲得するアルゴリズムの開発は，今後の EMO アルゴリズム開発における大きな課題と言える．上記の議論から，以下の 2 点を本研究の課題として設定する．

課題 1: 既存のベンチマーク問題とは異なる特徴を持った，多様なテスト問題による効率的な性能評価環境の実現
課題 2: 多数目的最適化問題においても，意思決定者にとって有益な解集合を獲得することを目的としたアルゴリズムの開発
第 3 章「既存のベンチマーク問題と異なる特徴を持つテスト問題の作成」では，課題 1 を解決するために，既存のベンチマーク問題とは異なる特徴を持つテスト問題を作成し，EMOアルゴリズムの探索性能を再評価する．ここでは，以下の三つの特徴に注目して調査を行う．
(a) 目的関数の性質(b) 探索領域の形状(c) 制約条件付き問題(a)では勾配の非線形性，多峰性，不連続性，変数の非分離性といった，決定変数空間においてパレート最適解を探索する障害となる目的関数の性質に注目する．また，多目的最適化
では高次元の目的関数空間を探索するため，パレートフロントに向けて多方向に探索圧力をかける必要性がある．(b)ではこのような目的関数空間における探索領域の形状についての特徴に注目する．さらに，現実世界には自動車デザインにおける製品の安全性，エネルギープラント運用計画における機器の運用制約のように複雑な制約を持つ最適化問題が多く存在する．(c)ではこのような制約付き多目的最適化問題における，制約数や制約間の関係性といった特徴に注目する．
既存のベンチマーク問題を用いた EMO アルゴリズムの評価では，これらの特徴について網羅的に評価することは難しい．本論文では，特徴(a), (b)に関して EMO アルゴリズムの実行結果をフィードバックとしてテスト問題をメタ最適化することで EMO アルゴリズムの探索性能に強い影響を及ぼす特徴を含んだテスト問題を自動生成する．つまり，テスト問題の最適化では二重構造の最適化が行われる．下位レイヤーの最適化は，通常の EMO アルゴリズムの実行である．一方，上位レイヤーではテスト問題が個体として表現され，下位レイヤーで得られた EMO アルゴリズムの実行結果を基にテスト問題の最適化が行われる．テスト問題の最適化により得られた問題から，代表的な EMO アルゴリズムの探索性能に大きな影響を与える特徴について考察する．
また，特徴(c)について制約数や制約間の関係性を自由に変更可能な多目的最適化テスト問題を提案し，既存の EMO アルゴリズムにおける制約取扱い手法の性能が制約数及び制約間の関係性に強く影響を受けることを示す．
第 4 章「効率的な意思決定のための EMO アルゴリズム開発」では，課題 2 を解決するために意思決定者の選好情報を用いることで，多数目的最適化問題に対しても意思決定者にとって有益な解集合を提供する EMO アルゴリズムを提案する．提案手法において，意思決定者から得られた選好情報は，現個体群を基に構築した超平面上にガウス関数を用いて表現される．このときガウス関数の中心は選好する領域の中心，ガウス関数の分散は選好する領域周辺に対する関心度合いに対応する．ガウス関数に従う解分布を得ることで，選好領域の中心だけでなく関心のある領域に分布した解集合を獲得することで，局所的なトレードオフ情報を保有した，意思決定に有益な候補解を提供する．数値実験ではベンチマーク問題を通して，多様性に優れた解集合が選好領域に獲得されることを示す．また，目的数が増加しても選好情報を用いた探索を行うことで，選好領域に対する高い収束性が維持されることを示す．
第 5 章「結論」では本論文で得られた結果についての総括を行う．

審査結果の要旨
本論文は，多目的最適化問題において，目的関数間のトレードオフ情報など，問題に対する有益な知識を与えるパレート最適解集合を効率的に探索することで，意思決定支援を目指す研究であり，以下の成果を確認した．
(1) 複 数 の パ レ ー ト 最 適 解 を 1 度 の 実 行 で 効 率 的 に 獲 得 可 能 な 進 化 型 多 目 的 最 適 化（Evolutionary Multiobjective Optimization: EMO）手法の開発において，幅広い既存のベンチマーク問題を年代別に分類することで，既存のベンチマーク問題が年代ごとに類似する傾向を持つことを示した．また，同年代に提案された EMO アルゴリズムとの比較から，ベンチマーク問題の持つ特徴が EMO アルゴリズムに与えた影響について論述し，ベンチマーク問題とアルゴリズムの開発が共進化的に行われたことを明らかにした．
(2) 実問題に即した EMO アルゴリズムの開発を可能とするために，(a)目的関数の性質，(b)探索領域の形状，(c)制約条件付き問題の三つの特徴に注目し，EMO アルゴリズムの実行結果をフィードバックとしてテスト問題をメタ最適化することで，EMO アルゴリズムの探索性能に強い影響を及ぼす特徴を含んだテスト問題を自動生成する手法を提案した．また，制約数や制約間の関係性を自由に変更可能な多目的最適化テスト問題を提案し，既存の EMO アルゴリズムにおける制約取扱い手法の性能が制約数及び制約間の関係性に強く影響を受けることを明らかにした．
(3) 意思決定者にとって有益な解集合を獲得することを目的として，現個体群の情報を基に構築した超平面上に意思決定者の選好情報を表現する，選好ベースの EMO アルゴリズムを提案した．
選好領域の中心だけでなく関心のある領域に分布した解集合を獲得することで，局所的なトレードオフ情報を保有した，意思決定に有益な候補解が提供可能であることを明らかにした．また，目的数が増加しても選好情報を用いた探索を行うことで，選好領域に対する高い収束性が維持されることを示した．
以上の諸成果は，進化型多目的最適化手法の実問題における有用性の向上に大いに貢献すると期待され，本分野の学術的・産業的な発展に貢献するところ大である．また，申請者が自立して研究活動を行うのに必要な能力と学識を有することを証したものである．学位論文審査委員会は，本論文の審査ならびに最終試験の結果から，博士（工学）の学位を授与することを適当と認める．