九州大学学術情報リポジトリ
Kyushu University Institutional Repository
推定収束点を用いた多目的最適化の高速化
裴, 岩
会津大学コンピュータサイエンス部門
高木, 英行
九州大学大学院芸術工学研究院
http://hdl.handle.net/2324/1905534
出版情報：2017-12-10 バージョン：
権利関係：
推定収束点を用いた多目的最適化の高速化
裴 岩
†, 高木英行††
会津大学コンピュータサイエンス部門† 九州大学大学院芸術工学研究院††
1 はじめに
単 目 的 最 適 化 と 多 目 的 最 適 化 の 違 い はfitness 関数の数である．単目的最適化では設計変数空 間上の唯一のfitness景観上での最適解を求め，多 目的最適化では同じ設計変数空間上の異なる複 数の目的景観上の最適解を求める．多目的は二 律 背 反 的 関 係 に あ り，通 常 一 つ に ま と め る こ と ができない．多単目的最適化のようにfitness値が 最高の唯一の設計解を求めることができない目 的最適化では，目的空間上のパレートフロント の非劣解を探索目標とすることが一般的である．
大 多 数 の 多 目 的 最 適 化 研 究 で は ，探 し 出 し た 非劣解の多様性と数を評価指標にしている．進 化的多目的最適化（EMO）はこの多目的最適化 問 題 を 効 率 的 か つ 効 果 的 に 扱 う こ と が で き る ． EMOは，決定論的プログラム手法のように多目 的を単目的に変換するスカラー化をするのでは な く，複 数 の 目 的 関 数 を 独 立 に 保 持 し ，パ レ ー ト・ランクを用いることで多目的解を直接扱う．
ほとんどのEMOは目的空間のパレート支配関係 を 扱 う の で ，パ レ ー ト・フ ロ ン ト を 形 成 す る 探 索解を得ることになる1) ．このEMOアプローチ の 問 題 点 は ，最 適 化 能 力 が 弱 く，パ レ ー ト 最 適 性の保証がないことで，EMOのパレート支配の アプローチをしている限り完全に解決すること は で き な い ．
決定論的手法をアルゴリズムに組み込むこと はこの問題の解決につながる．進化計算探索を 高速化する推定収束点の利用は，この考え方の 一つの実現方法である2, 3) ．世代間の個体移動 方 向 か ら 進 化 計 算 探 索 の 収 束 情 報 が 得 ら れ る ．
Acceleration of Multi-objective Optimization Using an Estimated Convergence Point
† Yan Pei ([email protected]) (http://web-ext.u-aizu.ac.jp/∼peiyan/)
†† Hideyuki Takagi
(http://www.design.kyushu-u.ac.jp/∼takagi/) Computer Science Division, University of Aizu (†) Faculty of Design, Kyushu University (††)
こ の 情 報 か ら 数 学 的 に 収 束 点 が 推 定 で き2, 3) ， 推定収束点をエリート個体として使うことで単 目的最適化の性能向上が図られ，多峰性問題に も 適 用 で き る4,5) ．
本 論 文 で は ，目 的 空 間 で の 非 劣 解 情 報 を 設 計 変数空間に写像して，設計変数空間での非劣解 の移動ベクトルを生成し，これらの移動ベクト ルから非劣解探索の収束点を推定するようEMO を拡張する．推定収束点をEMO探索に加え，劣 解を削除することで，EMOアルゴリズムがより 多くの非劣解を早く探し出すことができるよう になると考えられる．この仮説を確かめるため にNSGA-IIを 用 い 提 案 手 法 の 性 能 を 確 認 す る ． こ の 点 が オ リ ジ ナ リ ティの 一 つ で あ る ．
本節に続き，第2節で単峰性問題での個体収束 点の推定方法を簡単に述べ，第3節でこの推定法 をどのようにEMO探索高速化に用いるかを説明 する．この方法には三つのステップがあり，第1 に目的空間での移動ベクトルの対情報を得，第2 に探索の収束点を推定し，第3に劣解削除してこ の推定収束点を加える．第4節でNSGA-IIを使っ て多目的最適化ベンチマーク問題で提案手法の 評 価 を 行 う．最 後 に 全 体 の 結 論 を 述 べ る と と も に 今 後 の 研 究 課 題 を 述 べ る ．
a1
c1
a2
c2
a3
c3
an
cn
Fig. 1 移動ベクトルbi (=ci−ai) はd次元設計 変数空間上の親個体ai とその子個体 ciから求め られる．印はこれら移動ベクトルから推定する 個 体 群 の 収 束 点 で あ る ．
a1 c1
a2 c2
a3
c3
an
cn
x
㼐ḟඖタィኚᩘ✵㛫
┠ⓗ䠍
┠ⓗ䠎
➨G-1ୡ௦䛾first Pareto front
➨㻳ୡ௦䛾first Pareto front
Fig. 2 EMO探索性能向上を目的とした，目的空間の劣非劣情報を用いた設計変数空間でのパレート
解 領 域 の 推 定 法 ．
2 単峰性問題での収束点推定計算方法 親 個 体 か ら 子 個 体 へ の 移 動 ベ ク ト ル（ さ ら に 言えば親子個体に限らず，低fitness値個体から高
fitness個体へのすべての有向ベクトル）から個体
群 の 収 束 点 が 数 学 的 に 推 定 可 能 で あ る2, 3,4) ． 次 節 で 述 べ る 提 案 法 は こ の 方 法 を 用 い る ．
初 め に ，収 束 点 推 定 を 説 明 す る た め の 記 号 を 定義する．Fig. 1のai とciはi番目の親個体とそ の子個体である(ai,ci∈Rd). 次に，i番目の移動 ベクトルは有向ベクトルbi=ci−aiとして定義 される．biの単位有向ベクトルはb0i=bi/||bi||と な る ．す な わ ち ，bT0ib0i= 1で あ る ．
x∈Rdをn本の延長した有向線分ai+tibi (ti ∈R に最も近い点としよう．この最近傍点という意味 は，式(1)で示す，xからこれらn本の延長線分へ の距離の総和J(x,{ti})が最小になることである．
収束点xから延長線分への最小線分は，xから の垂線になるので，式(2)の直交条件を式(1)に代 入 し てtiを 消 去 す る ．
J(x,{ti}) =
n
i=1
ai+tibi−x2 (1)
bTi (ai+tibi−x) = 0 （ 直 交 条 件 ） (2) 式(1)の距離総和を最小にするxˆは，xの各要素 で偏微分して0とする式を解くことで得られる．
最 後 に ，収 束 点xˆは 式(3)得 ら れ る ．こ こ で ，Id
は 単 位 行 列 で あ る ．
xˆ =
n
i=1
Id−b0ibT0i−1 n
i=1
Id−b0ibT0i ai
(3)
3 収束推定点を用いたEMO探索の高速化 EMOアルゴリズム研究方向に，パレート解の 探索と解の多様性の二つがある．これらの多くの 研究は目的空間でいかに探索するかに目が向い ており，設計変数空間での探索条件に注意を払っ ていない．EMOアルゴリズムは多くの非劣解を 探そうとする．目的空間での世代間のパレート フロント解の動きから，設計変数空間での設計 変数解の動き情報が得られ，この情報からさら に 新 し い パ レ ー ト 解 を 得 る 情 報 が 得 ら れ る ．
Fig. 2は，目的空間での世代間のパレート非劣
解の移動情報から，対応する設計変数空間の非 劣解を求めて，対応する移動ベクトルを求める 様子を示している．この設計変数空間での移動 ベクトル群から推定収束点を求めて新しい非劣 解候補にすることでEMO探索の性能向上を図る ことが可能になる，という仮説に基づく研究が 本 論 文 の 提 案 で あ る ．
EMO性 能 向 上 の た め の こ の 方 法 は3段 階 か ら な る ．
第1 Step 目 的 空 間 上 の 移 動 ベ ク ト ル に 対 応 す る設計変数空間での移動ベクトルを見つけ る ．目 的 空 間 上 の 一 世 代 前 と 現 世 代 の 非 劣 解グループから近傍の個体を1個ずつ選択し て 非 劣 解 移 動 ベ ク ト ル と す る ．次 に ，こ れ ら2点 に 対 応 す る 設 計 変 数 空 間 上 の 探 索 点 (ai,ci)を求め選択した目的空間での世代間 の近傍2点を削除する．こうして設計変数空 間 上 の 移 動 ベ ク ト ルbi (=ci−ai)が 得 ら れ る の で ，以 上 の 操 作 を 繰 り 返 し ，目 的 空 間 で の 非 劣 解 が な く な る ま で ，設 計 変 数 空 間 で 移 動 ベ ク ト ル を 次々に 求 め る ．
第2 Step これらの移動ベクトルと第2節の推定 式を用い，設計変数空間上の非劣解群の推定 収 束 点 を 求 め る ．こ の 推 定 収 束 点 は パ レ ー トフロントにある可能性が高く，EMO探索 速 度 の 高 速 化 に 寄 与 し 得 る ．
第3 Step 第2 Stepで 得 た 推 定 収 束 点 をEMOア ルゴリズムの探索エリート解として追加し，
代 わ り に 現 世 代 の 劣 解 の 一 つ を 削 除 す る ．
4 評価実験と分析
提案手法の定性的評価のために，実験用EMO ア ル ゴ リ ズ ム と し てNSGA -IIと 五 つ の 多 目 的 ベ ン チ マ ー ク 関 数 (ZDT1, ZDT2, ZDT3, ZDT4,
and ZDT6)6) を用いる．これらの関数の次元数
を2〜30次元に変化させてパレート解の分布状況 を 調 べ る ．
Fig. 4は30次元問題で得られた各世代の，NSGA -IIによるパレート解（赤）と（NSGA -II＋提案 手法）によるパレート解（青）である．両者を重 ねた左端の列を見て分かるように，ZDT3の一部 領域を除いて提案手法の方がより良いパレート 解 を 探 し 出 せ て い る こ と が 分 か る ．す な わ ち ， 個体の推定収束点をエリート個体として利用す る 提 案 手 法 はNSGA-II探 索 を 高 速 化 し ，よ り 良 い 非 劣 解 を 探 し 出 せ る と い え る ．
さらに解析を進めるため，NSGA-IIと（NSGA-II＋ 推定収束点）の提案手法とでパレート解の検出能 力を調べる．両手法が見つけたパレート解数を30 次元問題で30試行平均した結果をFig. 3に示す．
ZDT3ベンチマーク関数を除き，提案手法は従 来 のNSGA-IIよ り も 多 く の 非 劣 解 を 探 し 出 せ て
いる．Wilcoxonの符号検定結果からはいくつか
の 世 代 で 有 意 な 差 で あ る こ と が 示 さ れ た ． ZDT1では40世代までは提案手法がより多くの 非劣解を探し出せているが，それ以降では探し 出 せ る 非 劣 解 が 少 な く なって い る ．こ れ は 生 成 個体が似たものになり多様性が失われてきたた め で は な い か と 思 わ れ る ．そ の た め ，提 案 手 法 を毎世代適用するのではなく数世代に1回適用す る な ど の 工 夫 で 改 善 策 を 考 え る 必 要 が あ ろ う．
今後の課題である．ZDT4は多くの非劣解を見つ けられているが，ZDT3では提案手法の効果が見 られない．このタスク依存性の原因を解析し改 善 す る た め に ，ZDT3とZDT4のfitness景 観 の 違 いや移動ベクトルの振舞いなどを解析し，この 性能の違いの理由を明らかにする必要があろう．
Table 1 評価に用いる多目的ベンチマーク関数．
パ レ ー ト・フ ロ ン ト は す べ てg(x) = 1で あ る ．
Functions Definition ZDT1
f1(x) = x1
f2(x) = g(x)[1−
x1 g(x)] g(x) = 1 + 9
n i=2xi n−1
ZDT2
f1(x) = x1
f2(x) = g(x)[1−(g(x)x1 )2] g(x) = 1 + 9
n i=2xi n−1
ZDT3
f1(x) = x1
f2(x) = g(x)[1−x
g(x)1
−g(x)x1 sin(10πx1)]
g(x) = 1 + 9
n i=2xi n−1
ZDT4
f1(x) = x1
f2(x) = g(x)[1−x
g(x)1 ] g(x) = 1 + 10(n−1)+
n
i=2[x2i−10 cos(4πxi)]
ZDT6
f1(x) = 1−exp(−4πx1) sin6(6πx1) f2(x) = g(x)[1−(g(x)x1 )2]
g(x) = 1 + 9[
n i=2xi n−1 ]0.25
こ の 点 も 今 後 の 課 題 で あ る ．
適 用 条 件 を 解 析 す る た め2次 元 問 題（Fig. 5） で有効性を確認したところ，多くの世代での推 定 収 束 点（ 図 中 の 緑 色 点 ）は 非 劣 解 で は な く 高 速化の寄与は認められなかった．このことから，
我々の 提 案 手 法 は ，高 次 元 の 複 雑 な 問 題 に 対 し て 有 効 に な る と 言 え る ．
5 考察と結論
目的空間の世代間パレート解から設計変数空 間の移動ベクトルを求め，移動ベクトルから設 計変数空間上の個体群の推定収束点を求めてエ リート個体とすることでEMO探索を高速化する 手法を提案した．推定収束点を進化計算の高速化 に利用するという考えは，これまで発表されて き た 単 目 的 最 適 化 だ け で は な く，本 論 文 で 示 し たように多目的最適化の高速化にも有用である．
NSGA-II vs. (NSGA-II＋ 提 案 手 法 ）の 比 較 を 多目的最適化ベンチマーク問題で評価したとこ ろ，複雑度が高い高次元問題で有効性を確認でき た．高次元問題で（NSGA-II＋提案手法）が探し 出す非劣解数はNSGA-IIが探し出す非劣解数より も有意に多く探し出せている（Wilcoxonの符号検 定結果）が，その性能度合はタスクに依存する．
特に低次元問題のように複雑度が少ないタスク で は 高 速 化 の 効 果 が 見 ら れ な かった ．移 動 ベ ク トルの生成方法が原因の一つであることを考え
0 10 20 30 40 50 60 70 80 90 100 Generations
15 20 25 30 35 40 45 50 55 60
Number of Pareto Frontier
NSGA II + Estimated Point NSGA II
0 10 20 30 40 50 60 70 80 90 100
Generations 4
5 6 7 8 9 10 11 12 13 14
Number of Pareto Frontier
NSGA II + Estimated Point NSGA II
(a) ZDT1 (b) ZDT2
0 10 20 30 40 50 60 70 80 90 100
Generations 10
20 30 40 50 60 70
Number of Pareto Frontier
NSGA II + Estimated Point NSGA II
0 10 20 30 40 50 60 70 80 90 100
Generations 0
2 4 6 8 10 12 14 16 18
Number of Pareto Frontier
NSGA II + Estimated Point NSGA II
(c) ZDT3 (d) ZDT4
0 10 20 30 40 50 60 70 80 90 100
Generations 5
10 15 20 25 30
Number of Pareto Frontier
NSGA II + Estimated Point NSGA II
(e) ZDT5
Fig. 3 NSGA-IIと提案手法の（NSGA-II＋推定収束点）が検出するPareto解数の30試行平均．タスク は30次 元ZDT ベ ン チ マ ー ク 関 数 ．
0 0.2 0.4 0.6 0.8 1 1
2 3 4 5 6
7 ZDT1Comparison Figure
0 0.2 0.4 0.6 0.8 1
1 2 3 4 5 6
7 ZDT1 NSGA-II+Estimation Point:Red
0 0.2 0.4 0.6 0.8 1
1 2 3 4 5 6
7 ZDT1NSGA-II:Blue
0 0.2 0.4 0.6 0.8 1
1 2 3 4 5 6
7 ZDT2Comparison Figure
0 0.2 0.4 0.6 0.8 1
1 2 3 4 5 6
7 ZDT2 NSGA-II+Estimation Point:Red
0 0.2 0.4 0.6 0.8 1
2.5 3 3.5 4 4.5 5 5.5 6 6.5
7 ZDT2NSGA-II:Blue
0 0.2 0.4 0.6 0.8 1
0 1 2 3 4 5 6
7 ZDT3Comparison Figure
0 0.2 0.4 0.6 0.8 1
0 1 2 3 4 5 6
7 ZDT3 NSGA-II+Estimation Point:Red
0 0.2 0.4 0.6 0.8 1
1 2 3 4 5 6
7 ZDT3NSGA-II:Blue
0 0.2 0.4 0.6 0.8 1
-200 -100 0 100 200 300 400 500
600 ZDT4Comparison Figure
0 0.2 0.4 0.6 0.8 1
-200 -100 0 100 200 300 400 500
600 ZDT4 NSGA-II+Estimation Point:Red
0 0.2 0.4 0.6 0.8 1
-100 0 100 200 300 400 500
600 ZDT4NSGA-II:Blue
0.2 0.4 0.6 0.8 1
6.5 7 7.5 8 8.5
9 ZDT5Comparison Figure
0.2 0.4 0.6 0.8 1
6.5 7 7.5 8 8.5
9 ZDT5 NSGA-II+Estimation Point:Red
0.2 0.4 0.6 0.8 1
6.5 7 7.5 8 8.5
9 ZDT5NSGA-II:Blue
Fig. 4 30次 元 問 題 で の 全 世 代 の パ レ ー ト 解 分 布 ．赤 と 青 の 個 体 は そ れ ぞ れ ，NSGA -IIと（NSGA -II＋ 提 案 手 法 ）に よ る パ レ ー ト 解 で あ る ．
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0
1 2 3 4 5 6 7 8 9
10 objective spaceZDT1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
1 search spaceZDT1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0 1 2 3 4 5 6 7 8 9
10 objective spaceZDT2
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
-0.2 0 0.2 0.4 0.6 0.8
1 search spaceZDT2
-0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
-2 0 2 4 6 8
10 objective spaceZDT3
-0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
1 search spaceZDT3
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
70 75 80 85 90 95 100 105 110 115
120 objective spaceZDT4
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
-5 -4 -3 -2 -1 0 1 2 3 4
5 search spaceZDT4
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0 1 2 3 4 5 6 7 8 9
10 objective spaceZDT5
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
1 search spaceZDT5
Fig. 5 2次元問題の2目的空間上のPareto解分布（左列）と2変数空間での解分布（右列）．赤と青の 個体はそれぞれ，NSGA -IIと（NSGA -II＋提案手法）によるパレート解である．緑色点は個体群の推 定 収 束 点 ．
ら れ る ．こ の 解 析 と 改 善 が 今 後 の 課 題 で あ る ． 結論として以下の点が挙げられる．(1)提案手 法でEMO探索を高速化することができる．しか し、その性能はタスクに依存する．(2) 推定収束 点が単目的最適化の高速化に有用であるとのこ れまでの研究と合わせて，少なくとも高次元の 複雑な問題では多目的最適化の高速化にも有用 である．(3)低次元の複雑度の少ないタスクで高 速化効果のためには，目的空間での移動ベクト ルとする世代間の対個体とするパレート非劣解 の 選 択 が 鍵 と な る ．
今後，色々な多目的問題に適用して評価を固め ていく必要がある．移動ベクトルの選定方法が今 後の研究のキーになると思われる．多峰性問題で の性能を向上させるために，局所解領域の分離 を導入する必要があろう．多目的fitness景観と推 定収束点を用いた探索条件も今後の課題となる．
謝辞
本研究はJSPS科学研究費（課題番号JP15K00340） の 助 成 を 受 け た も の で あ る ．
参考文献
1) Li, B., Li, J., Tang, K., and Yao, X., ”Many- objective evolutionary algorithms: A survey.
ACM Computing Surveys (CSUR),” 48(1), 13 (2015).
2) 村田昇，西井龍映，高木英行，裴岩「世代間 移動ベクトル群の収束点推定法」2014進化計 算シンポジウム，pp.210-215，廿日市市(2014 年12月20-21日).
3) Murata, N., Nishii, R., Takagi, H., and Pei, Y., ”Analytical Estimation of the Convergence Point of Populations,” 2015 IEEE Congress on Evolutionary Computation, Sendai, Japan, pp.2619-2624 (May 25-28, 2015).
4) Yu, J. Pei, Y., and Takagi, H., ”Accelerating Evolutionary Computation Using Estimated Convergence Point,” IEEE Congress on Evo- lutionary Computation, Vanvouver, Canada, pp.1438-1444 (July 24-29, 2016).
5) 余俊，高木英行「多峰性最適化問題での局所 最適解推定高度化のための補正法 – 局所最 適 解 が2個 の 場 合–」第9回 進 化 計 算 研 究 会 ， pp.92-97, 神 戸(2015年9月7-8日).
6) Zitzler, E., Deb, K., Thieler, L. Comparison of multiobjective evolutionary algorithms: Empir- ical results. IEEE Trans. on Evol. Computation 8 (2000) 173-195
