制約付き多目的最適化問題のための異種交叉の適用 法

制約付き多目的最適化問題のための異種交叉の適用 法

著者 比留間 渉

出版者 法政大学大学院情報科学研究科

雑誌名 法政大学大学院紀要. 情報科学研究科編

巻 15

ページ 1‑6

発行年 2020‑03‑24

URL http://doi.org/10.15002/00022731

Supervisor: Prof. Yuji Sato

制約付き多目的最適化問題のための異種交叉の適用法 Heterogeneous Crossovers for Constrained Multi-Objective

Continuous Optimization

比留間 渉 Hiruma Wataru

法政大学大学院情報科学研究科情報科学専攻 E-mail: [email protected] Abstract

This paper proposes a method to utilize multiple crossovers to deal with directive mating using effective impossible solution to approximate Pareto-front more accurately in solving the constrained multi objective optimization problem. We focus on Two-Stage Non- dominated Sorting and Directed Mating (TNSDM) algorithm to solve the Constrained Multi-Objective Optimization Problems (CMOP). The crossovers used in this study are the Simulated Binary Crossover (SBX) which is a wide area search and good at solving problems with strong correlation between objective function and variable and Polynomial Mean-Centric Crossover (PMCX) which is a local search and superior to solve problems with weak correlation between objective function and variable. In the experiment, we will switch the crossover for a fixed generation targeting the search TNK, switching the crossovers for each constant generation, switching the number of generations and the order of crossover I changed it. In conclusion, SBX assists the search of PMCX. Efficient search is based on adjusting the generation that switches from SBX to PMCX based on the rise amount of HV.

1.

まえがき

実世界での最適化問題の多くは，複数の要素をトレー ドオフの関係性や制約条件に違反しないように，同時に 最適化することを要求する．このような問題を制約付き 多目的最適化問題 (Constrained Multi-Objective Optimization Problem， CMOP) [1]という．CMOPの解法として，進化 型アルゴリズムを用いた多目的進化型アルゴリズムの開 発の研究が活発である．本研究では，二段階の非支配ソ ートによる，制約違反量と目的関数値を同時に扱う解の ランク付けと，有用な実行不可能解を用いる指向性交配 を導入した Two-Stage Non-dominated Sorting and Directed Mating (TNSDM) アルゴリズム [2] に注目する．TNSDM アルゴリズムに適応例のある，後述する二つの交叉法 Simulated Binary Crossover (SBX) [3], Polynomial Mean- Centric Crossover (PMCX) [3]には親同士の距離が近いほど，

親に対する分布は変わらず，子が生成される範囲が狭く なるという性質がある．しかし，SBXとPMCXの得意と する問題は異なっている．探索中にSBXとPMCXを切り

替え，交叉法により子が生成される分布を変更し，より 精緻なパレート最適解が得られることを期待する．その ために，どのように切り替えることが最善であるか検証 する．

2. TNSDM

アルゴリズムで適応例のある交叉法

2.1 Simulated Binary Crossover (SBX)

SBXは上述した方法で選択した2つの親から次世代の探索 に用いる解となる子を以下の手順に従って生成する．まず，

[0,1]の乱数𝑢_𝑖を生成し，子の分布係数𝛽_𝑖を算出する．

𝛽

_𝑖

= { (2𝑢

_𝑖

)

1

𝜂_𝑐+1

𝑖𝑓 𝑢

_𝑖

≤ 0.5

( 1

2(1 − 𝑢

_𝑖

) )

1 𝜂_𝑐+1

𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

(1) 次に𝛽_𝑖を用いて 2 つの親𝑝_𝑎, 𝑝_𝑏の𝑖番目の遺伝子座の要素 𝑥_𝑖^𝑝𝑎, 𝑥_𝑖^𝑝𝑏に変化を与える

𝑥

_𝑖^′𝑝𝑎

= 0.5{(1 + 𝛽

_𝑖

)𝑥

_𝑖^𝑝𝑎

+ (1 − 𝛽

_𝑖

)𝑥

_𝑖^𝑝𝑏

} 𝑥

_𝑖^′𝑝𝑏

= 0.5{(1 − 𝛽

𝑖

)𝑥

_𝑖^𝑝𝑎

+ (1 + 𝛽

𝑖

)𝑥

_𝑖^𝑝𝑏

}

(2) 変異を加えた𝒙^′𝑝𝑎, 𝒙^′𝑝𝑏の各遺伝子を，0.5 の確率で入れ替え て子𝒐を生成する．SBXでは，親同士の変数の値が近いほど 変化量は小さくなり，親の変数に近い値で子が生成される確 率が高まる．また，(1)中のパラメータ𝜂_𝑐は非負の値を持ち，値 が大きいほど変化量が小さくなり，親の変数に近い値で子が 生成される確率が高まる．SBXは後述するPMCXよりも変数 領域と目的関数領域の相関が弱い問題に対して高い探索性 能を示す．

2.2 Polynomial Mean-Centric Crossover (PMCX)

PMCXもSBXと同様には乱数を用いて親の中点の周辺に 子を生成する交叉法であり，まず，[0,1]の乱数𝑢𝑖を生成し，子 の分布係数𝛿_𝑖を算出する．

𝛿

_𝑖

= { (2𝑢

_𝑖

)

1

𝜂_𝑐+1

− 1 𝑖𝑓 𝑢

_𝑖

> 0.5 1 − {2(1 − 𝑢

_𝑖

)}

1

𝜂_𝑐+1

𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

(3)

次に，子𝒐の𝑖番目の遺伝子座の要素𝑥_𝑖^𝒐を 2つの親𝑝𝑎, 𝑝𝑏の𝑖 番目の遺伝子座の要素𝑥_𝑖^𝑝𝑎, 𝑥_𝑖^𝑝𝑏と𝛿_𝑖を用いて算出する．

𝑥

_𝑖^𝑜

= (𝑥

_𝑖^𝑝𝑎

+ 𝑥

_𝑖^𝑝𝑏

)

2 + 𝛿

_𝑖

(|𝑥

_𝑖^𝑝𝑎

− 𝑥

_𝑖^𝑝𝑏

|)

(5) PMCXは親同士の距離が近いほど親の中点に近い距離に発 生しやすくなる．(3)中のパラメータ𝜼_𝒄は非負の値を持ち，の値 が大きいほど，親の中点に近い値に子が発生する確率が高く なる．PMCX は SBXに比べて，目的関数領域と変数領域の 相関が強い問題に対して，高い探索性能を示す.

3. 異種交配の逐次適応法の提案

従来手法の異種トーナメント選択や異種グループ統合再編 成では複数のスレッドを用意し，各スレッドごとに交叉法や，

分布パラメータ𝜂_𝑐を設定し，一定世代ごとに強調処理を行うこ とで，複数の分布を用いた効率的な探索を実現した．しかし，

従来手法ではメモリ，実行時間の面のコストが多大きい．そこ で，本論文は制約付き多目的最適化問題を解くにあたって，

単一の探索上で，より精度よくパレートフロントを近似するため に有効な実行不可能解を用いた指向性交配で探索中に交叉 法により生成される子の分布確率を逐次的に変更することに ついて検討する.

3.1. SBX

と

PMCX

のハイブリッド型並列化

得意な問題の異なるSBX，PMCXの2つの交叉法を並列 化させ一定世代ごとに探索する解集団の最適化する協調 処理を行うことで解探索性能の向上を図ることである．

それぞれの交叉法はパラメータを変化させると，子の生 成範囲が変わる．一定回数，解探索を行うたびに各スレ ッドの解集団に対し以下に示す 2つの処理の内 1つを行 い，解の探索状況を共有化する．一定世代ごとに行う処 理とパラメータは探索が終了するまで変更しない．

3.1.1.

異種グループ間トーナメント選択

各スレッドの解集団の HV を求め，最も高い値を示し た解集団を次の探索集団として各スレッドに共有する．

HV の値が大きいほど，パレート最適解の探索が進んで いることを示す．

3.1.2.

異種グループ統合再編成

異種グループ統合再編成処理は探索する解集団に含ま れる解をパレート最適解と有用な実行不可能解に絞るこ とによって，指向性交配の性能の向上を図る処理である．

図1に個体数10，スレッド数2の場合の異種グループ

統合再編成処理の流れを示す．異種グループ統合再編成 処理は各スレッドの解集団の全てを 1つの集団にまとめ，

集団内の解同士での制約違反量，目的関数値に関しての 支配関係を再定義する．他の実行可能解から支配されな い実行可能解をパレート最適解という．次に一つにまと めた集団からパレート最適解とパレート最適解を支配す る実行不可能解を取り出し，次の探索に用いる解集団を

生成する．図 1 の場合では，ランクの再定義後のパレー ト最適解とパレート最適解を支配する実行不可能解の数 の合計が9であり，個体数10に満たないためパレート最 適解に支配されている実行可能解を1つ追加している．

Fig.1 異種グループ統合再編成の動き

3.2.

提案手法：異種交配の逐次適応法

TNSDM ア ル ゴ リ ズ ム に 適 応 例 の あ る 2 つ の 交 叉 法

SBX,PMCXを探索中に切り替えることで，逐次的に子の生成

分布を変化させ適応し，より効率的な探索を実現する.

Fig.2 異種交配のフローチャート

Fig. 1はTNSDMアルゴリズム内でHeterogeneous crossover を実装した場合のフローチャートである．図中の|Q|は交叉法 によって生成された子の集団サイズ，|R|は解集団のサイズを 示す．交叉法の切り替え条件は，一定探索世代を基準に一 度だけ，または，次式(4)の条件のどちらかを予め設定してお き，条件を満たしたとき切り替える．

Thread1 Thread2

統合

再編成

Next search group

ランクの再定義 パレート最適解

実行可能解（被支配）

実行不可能解

𝐻𝑉

_𝐴

< 𝐻𝑉

_𝐹

or 𝐻𝑉

_𝐿

< 𝐻𝑉

_𝐹

(4)

(4)中の

𝐻𝑉

_𝐴は探索世代をの一定世代ごとに区切ったとき

の HVを区間ごとのHVの平均値である．

𝐻𝑉

_𝐹

, 𝐻𝑉

_𝐿は区間 の最初と最後の世代のHVを示している．どちらの条件でも区 間の最初の世代の HV が大きくなったときに切り替えるように 設定する．

4. 評価実験

検証実験では，まず1つ目の実験ではどのような順番で交 叉法を適応させることで効率的な探索を行えるかどうかを検証 する．切替条件は，一定世代数に到達したときに変更する．

次に 1つ目の実験結果をもとに交叉法を切り替えるタイミング や条件に対して一定世代の区間の区切り方を変えることで検 証を行う．

4.1. 評価手法

より高い探索性能を示すためのSBX，PMCXの推移手法を 検証するために，テスト問題の TNK [5]を対象に比較実験を 行った．2つの実験に用いたパラメータはそれぞれ SBX， PMCX の分布パラメータ𝜂_𝑐= 15とした．交叉率𝑃_𝑐= 0.8，集 団サイズ|𝑅| = 400 (親集団|𝑃| = 200，子集団|𝑄| = 200)，

探 索 に よ っ て 得 た パ レ ー ト 最 適 解 集 合 は 解 探 索 精 度 Hypervolume(HV) [6]を用いて評価する．HV は，得られたパ レート最適解集合と参照点𝒓で構成される目的関数空間にお ける𝑚次元体積である．HV が高いほど，パレートフロントに対 して，パレート最適解が収束性と多様性の二つの観点で良好 であると判断する．HVの算出に用いる参照点𝒓は， TNKでは 𝒓 = (1.2,1.2)とする．

4.1.1. TNK

TNKは 2目的2制約の最小化問題で，パレートフロントは 非連続である．TNKは次項の式によって定義される．

{

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒

𝑓₁(𝒙) = 𝑥1

𝑓2(𝒙) = 𝑥2

𝑆𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑔1(𝒙) = 𝑥12+ 𝑥22− 1 − 0.1 cos (16 arctan𝑥1

𝑥2

) ≥ 0 𝑔2(𝒙) = (x1− 0.5)²+ (x2− 0.5)²≤ 0.5

(6)

変数ベクトル𝒙は2個の変数{𝑥₁, 𝑥₂}からなり，それぞれ[0, 𝜋]の 範囲で実数値をとる．目的関数が変数の値であるので，目的 関数空間と，変数空間は全く同じであり，解集団の進化の過 程が読み取りやすいという点で優れている．

4.1.2. Hypervolume (HV)

Hypervolumeは，得られたパレート最適解集合と参照点𝒓で 構成される目的関数空間における𝑚次元体積であり，多目的 再起化問題に対する探索精度を評価する基準として扱われ る．HV が高いほど，パレートフロントに対して，パレート最適 解が収束性と多様性の二つの観点で良好であると判断する．

4.2. 交叉法の逐次適応順序の評価

探索終了の世代数𝐺 = 20000とする．交叉法を切り替える 世代は1000，2500，5000，10000，15000，175000，19000と し，SBXからPMCXとPMCXからSBXに切り替える場合を 検証する．

4.2.1. SBX

から

PMCX

への切り替え

Fig.3 TNKの世代数とHVの関係(0.6529 ≤ HV ≤ 0.6533)

Fig.4 TNKの世代数とHVの関係(0.6529 ≤ HV ≤ 0.6533)

Fig.5 TNKの世代数と実行可能解の数の関係 Fig.3 には，SBX，PMCX のみで探索を行った場合と，SBX から PMCX に 1000, 2500, 5000, 10000, 15000, 17500,

19000 世代目で切り替えた場合の HV の推移を示してい

る.Fig.4には，SBX，PMCXのみで探索を行った場合と，SBX からPMCXに10000, 15000, 17500, 19000世代目で切り替 えた場合の HV の推移を示している．全体的な傾向として SBXからPMCXに切り替えた世代で，PMCXのみの探索に よるHVの増加ペースと増加量よりも，遥かに短い世代数で大 きく増加している．SBXから PMCX に切り替えた世代の違い による最終世代のHVは大きくは変わらない． Fig.5では，各 世代での個体集団内に含まれる実行可能解の数の推移を示 している．SBXからPMCXに切り替えた世代で解集団に含ま れる実行可能解の数は減少していることが読み取れる．

4.2.2. PMCX

から

SBX

への切り替え

Fig.6 TNKの世代数とHVの関係(0.6529 ≤ HV ≤ 0.6533)

Fig.7 TNKの世代数とHVの関係(0.6529 ≤ HV ≤ 0.6533)

Fig.8 TNKの世代数と実行可能解の数の関係 Fig.6 に は ，PMCX，SBX の み で 探 索 を 行 っ た 場 合 と ， PMCX か ら SBX に 1000, 2500, 5000, 10000, 15000, 17500, 19000世代目で切り替えた場合の HV の推移を示し ている.Fig.7には，PMCX，SBXのみで探索を行った場合と，

PMCXからSBXに10000, 15000, 17500, 19000世代目で 切り替えた場合のHVの推移を示している．全体的な傾向とし てPMCXからSBXに切り替えた世代で，SBXの探索のHV の近くまでHVは低下している．PMCXからSBXに切り替え

た世代の違いによる最終世代の HV は大きくは変わらない．

Fig.8 では，各世代での個体集団内に含まれる実行可能解の

数の推移を示している．PMCXからSBXに切り替えた世代で 解集団に含まれる実行可能解の数は減少している．

4.3 HV

による切り替え世代の調整手法の評価

4.2節の実験結果により，SBXから PMCXに切り替え ることによってSBXのみまたはPMCXのみの場合よりも 短い世代数で高い HV が得られるパレート最適解群が得 られる結果が観測された．実験 1では交叉法を切り替え る世代を予め設定し，切り替える世代によって最終世代 の HV が変化するかどうかを試したが大きな変化は見ら れなかった．そこで，HV の上昇量が少なくなる時点で 交叉法を切り替えることによって，より効率的な探索が 行えるかどうかを確かめる.

4.3.1.

検証手法

HV を基準に交叉法を切り替えるにあたって，探索世 代を一定世代ごとの区間に区切る．区間の最初の世代の HVと区間内の各世代のHVの平均値との差を取り正規化 した値が，実験前に設定した一定割合を超えていない場 合に交叉法を切り替える．

4.3.2. パラメータ

探索終了の世代数𝐺 = 100000とする．区間の世代数を 10,50 世代の 2 つの場合に対して検証を行う．また，1000，

10000世代目でSBXからPMCXに切り替える探索とも比較を 行う．

4.3.3. 実験結果 2

Fig.9 TNKの世代数とHVの関係(0.6529 ≤ HV ≤ 0.6533)

Fig.10 TNKの世代数とHVの関係(0.6529 ≤ HV ≤ 0.6533，20000世代まで)

Fig.11 TNKの世代数とHVの関係(0.6523 ≤ HV ≤ 0.6533，2000世代まで)

Fig.9は,100000世代，Fig.10は20000世代，Fig.11は2000 世代までの HVの推移を示している． HVの区間ごとに区切 って最後または平均値の HV を用いた両方の場合に推移の 大きな変化は見られなかった．区間の大きさの観点では，10 世代ごとに区切った場合では SBX による探索の収束が感知 できず立ち上がりが遅くなり，50世代ごとに区切った場合では HVの立ち上がりがよく1000世代目でSBXからPMCXに切 り替える場合よりもスムーズに HV が増加している．さらには，

100000世代目まで着実に探索が進んでいる．しかし，1000世 代目にSBXからPMCXに切り替えた場合は切り替えた直後 の増加のペースが大きく，一番高い HV のパレート最適解集 合を得ている．10000世代目でも同様に，10000 世代目で SBXから PMCXに切り替えた場合の切り替え直後の HVの 伸びは大きく，1000世代目で切り替えた場合と同じ水準まで 上昇している．

5.

考察

4.2節の検証実験1 の実験結果によるとSBXはPMCX よりも探索初期段階での収束性がすぐれている．一方，

2.1節で述べたように探索が進み，親同士の距離が近くな ると変化量が小さくなり，親のより近くに子が生成され やすくなる性質によって，パレート最適解集合をより緻 密に均等な割合で補完するようにはパレート最適解を生 成することはできず，HV の上昇は止まっていた．そこ で，親同士の中間点の周辺に子を生成するPMCXへ移行 することによって，パレート最適解同士の間を埋めるよ うに進化が促され HV は上昇した．また，解集団中に含 まれる実行可能解の数は交叉法を切り替えた世代で変化 している．SBXからPMCXに切り替えた場合では，実行 可能解の数が減っているのにも関わらず，HV は上昇し ている．逆に，PMCXからSBXに切り替えた場合では，

実行可能解の数が増えているのにも関わらず，HV は減 少している．一方，PMCX のみで探索を行った場合では，

SBX のみで探索を行った場合よりも実行可能解の数が少 ないままで HVは上昇し続けている． TNSDMアルゴリ ズムは個体集団のランク付けをする際に，同一パレート 間での基準として，混雑度距離[7]を用いている．これら のことより，PMCXは次世代に残りやすい解を生成し続 けパレート最適解集合をパレートフロント上に均一にな るように探索することで更新し続けていると考える．

そこで，4.3節では4.2節で得られたSBXからPMCXに 切り替えるタイミングを HV を用いて調節することを検 討し，SBXの探索の収束を待たずともPMCXに切り替え ることによって，より早く高い HVを持つパレート最適 解を得られるかを検証した．一定世代に区切ることり世 代の区間の最初の値と，最後もしくは平均値と比較する ことで SBXの探索の収束を判断することで，HVの上昇 を留めることなく探索を進めること目的とした．しかし，

SBX の探索の収束前に PMCX に切り替えた場合には，

SBXの探索で HVの上昇が停滞した段階での切り替えは 成功したものの，PMCXによる上昇も緩やかになってし まい，4.2節で検証した1000世代目にSBXからPMCXに 切り替える手法よりも効率が下がってしまった．SBX に よる，PMCXの探索の補助効果を最大限に得るにはSBX

によるパレート最適解群がある程度，整理されている必 要があり，その整理の処理にはHVの上昇は伴わず，HV の上昇が終了した後に探索を繰り返す必要があると考え られる．加えて，SBX の初期世代数での探索効率の良さ を活かしつつ，PMCX の局所探索によるパレート最適解 をパレートフロント上に均等に探索，配置する処理を可 能な限り短い世代数で行うには，HV とは別の評価軸を 用いてSBXによるパレート最適解群の整理の終了を判断 する必要があると考える．

6. むすび

本論文では，制約付き多目的最適化問題を実行不可能 解を用いた指向性交配による探索中に，交叉法によって 子が生成される分布を逐次的に変化させ，パレートフロ ントをより精緻に近似するパレート最適解集合を獲得す る方法について実験を行った．

結論として，制約付き多目的最適化問題の連続問題で は，SBXからPMCXに移行する探索方法がより高い精度 のパレートフロントを獲得することがわかった．そこで，

連続関数による制約付き多目的最適化問題のパレートフ ロントを最も短い探索世代でより，精密に近似したパレ ート最適解集合を得るために，SBXで探索を行い HVの 収束が見られた段階で，PMCXに交叉法を切り替える手 法を検証したところ HV の停滞なく探索が行われた．一 方，HVの収束では SBXによるパレート最適解軍の整理 の終了を判断することができず，SBX による整理が終了 したあとのPMCXによる探索よりも効率が下がる結果と なった．

文 献

[1] E. M. Montes, Constraint-Handling in Evolutionary Optimization, Springer, 2009.

[2] M. Miyakawa, K. Takadama, and H. Sato, “Two-Stage Non-Dominated Sorting and Direct Mating for Solving Problems with Multi-Objectives and Constrains, ”Proc. of 2013 Genetic and Evolutionary Computation Conference (GECCO 2013), pp.647-655, 2013.

[3] K. Deb and M. Goyal, A Combined Genetic Adaptive Search (GeneAS) for Engineering Design, Computer Science and Informatics, Vol.26 (4), pp.30-45, 1996.

[4] M. Miyakawa, H. Sato, and Y. Sato, Polynomial Mean- Centric Crossover for Directed Mating in Evolutionary Constrained Multi-Objective Continuous Optimization, 10th EAI International Conference on Bio-inspired Information and Communications Technologies (BICT), 2017 in USB memory, 8 pages, 2017.

[5] M. Tanaka, H. Watanabe, Y. Furukawa, and T. Tanino,

“GA-Based Decision Support System for Multicriteria Optimization,” Proc of the Int’l Conf. on Systems, Man, and Cybernetics, Vol. 2, pp. 1556–1561, 1995.

[6] E. Zitzler, Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications, PhD thesis, Swiss Federal Institute of Technology, Zurich, 1999.

[7] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A Fast Elitist Multi-Objective Genetic Algorithm: NSGA-II,”

IEEE Trans. on Evolutionary Computation, Vol. 6, pp.

182–197, 2002.