変数間の従属関係情報を利用する遺伝的アルゴリズム

⃝ 加藤 真也，

大崎 美穂，

大西 圭

⃝ Masaya Kato,

Miho Ohsaki,

Kei Ohnishi

九州工業大学

同志社大学

九州工業大学

Kyushu Institute of Technology

Doshisha University

Kyushu Institute of Technology

Abstract: In this paper, we propose real-coded genetic algorithms that utilize a method for detecting

dependency relationships between variables. The method consists of neural network regression and group lasso. The proposed genetic algorithms select an appropriate crossover operator based on the dependency information between the variables, which are obtained from past solution candidates. Simulation results using the CEC’13 benchmark functions show that the proposed algorithms outperform conventional real-coded genetic algorithms.

1

はじめに

近年，様々な分野で大量に蓄積されるデータから未知 の有用な知識の発見が期待されている．そのような知識 発見を実現するために，まずは汎用的な分析手法で従属 関係にある変数集合を発見することが必要である．大崎 ら [1] は，そのための汎用手法として，ニューラルネット ワーク回帰 (NNR) とグループラッソ (GL) を用いた手法 を提案している． 一方，ブラックボックス最適化手法である進化計算の 解探索においては，探索の進行とともに，性質が未知の 問題の知識 (良い解領域) 発見につながるデータ，つまり 個体群 (解候補群) データが蓄積されていく．蓄積される 個体群データに，上述の変数間の従属関係を分析する手 法を適用すれば，良い解領域発見につながる情報が得ら れる可能性がある． そこで本研究では，上述の大崎らの手法を利用する実 数値遺伝的アルゴリズム (実数値 GA) を提案し，評価す る．提案手法は，実数値 GA が解探索過程で得る個体群 データに変数間の従属関係を検出する手法を適用し，そ の結果をもとに解探索中に問題に合う適切な交 演算を 選択・使用するものである． 続く第 2 節では，NNR と GL による変数間従属関係 検出手法について説明する．第 3 節では，提案アルゴリ ズムで使用する実数値 GA の交 演算について説明する． 第 4 節では，提案アルゴリズムについて説明する．第 5 節では，シミュレーション設定やその結果について説明， 考察する．第 6 節は，本論文のまとめである．

2

NNR と GL による変数間従属関係検出手法

NNR と GL を用いた変数間従属関係検出手法 [1](以下 [NNR+GL]) は，ニューラルネットワーク回帰 (NNR) に グループラッソ (GL) を組み込み，変数間の従属関係を 検出する手法である．従属関係を調べたい変数群のうち， 1 つを回帰対象とし，その他の変数を用いて NNR を行 う．i 番目の変数 xi (i∈ {1, 2, ..., N}) とその他の変数と の間の従属関係を調べるとき，ニューラルネットワーク への入力は xiを除いた x1, x2, ..., xi−1, xi+1, ..., xN であ り，回帰対象は xiである．そして，入力層のノードごと に第 1 層の結合重みをグループ化し，GL を適用する．入 力層の j 番目のユニットと第 1 層の k 番目のユニットの 間の結合重みを wjkとすると，GL 正則化項は以下のよ うになる (λ は正則化パラメータ)． λ N ∑ j=1,j_̸=i √∑ k w2 jk この式から第 1 層の結合重みが j ごとにグループ化され ていることが分かる．学習の過程で回帰に寄与しない変 数に対応する結合重みはグループでまとめて 0 に近づい ていく．GL 正則化のもとで十分に学習したモデルの第 1 層結合重みを調べることで回帰対象変数とその他の変数 の従属関係の有無を調べることができる．

3

実数値 GA における交 手法

本論文で提案するアルゴリズムは，実数値 GA の交 演 算を使い分ける．使い分け対象の交 演算は，BLX-α[2] と Simplex 交 (以下 SPX)[3] である．以下でこれらの 交 演算について説明する． 3.1 BLX-α BLX-α は，親個体を 2 個体用いて行う交 法である． 親個体の実数値ベクトルを基準とし，子個体をパラメータ α を用いて生成する．2 つの親個体を x = (x1, x2, ..., xn)， y = (y1, y2, ..., yn) としたとき，その実数値ベクトルを構 成する変数それぞれの区間 Ii= [xi, yi] (i = 1, 2, ..., n) の 両端を α 倍した領域からランダムに子個体を生成する． xi< yiとなる場合の子の第 i 番目の変数は図 1 の太線の 領域から生成される．

I

_i

x

_i

y

_i

α

I

_i

α

I

_i

図 1: BLX-α における子個体生成の領域 3.2 Simplex 交 (SPX) SPX は，以下の手順によって子個体を生成する交 法 である．ただし，変数サイズを n とする． (i) 個体群から (n + 1) 個の親個体 p0, ..., pnをランダム に選ぶ． (ii) 親個体の重心 g を求める． g = 1 n + 1 n ∑ i=0 pi (iii) 以下のようにして xk，ckを k = 0, ..., n について求 める． xk= g + ε(pk− g) ck =    0 (k = 0) rk−1(xk−1− xk+ ck−1) (k = 1, ..., n) ε は拡張率と呼ばれる正のパラメータである．rkは 区間 [0, 1] の一様乱数 u(0, 1) を以下のように変換し て得る乱数である． rk = (u(0, 1)) 1 k+1 _{(k = 0, ..., n}− 1) (iv) 子個体 C を，以下のように計算する． C = xn+ cn (v) 手順 (iii), (iv) を，目標の子個体数の分だけ繰り返す． 図 2 は，n = 2 のときに親個体 p0, p1, p2が張る子個体 生成領域を図示したものである．

4

提案アルゴリズム

提案するアルゴリズムは，はじめに BLX-α または SPX を交 演算とする実数値 GA を実行し，得られた個体群 データをもとに変数間の従属関係を検出し，その後の交 を使い分けようとするものである．一般に，BLX-α は 変数間に従属関係を持たない問題を得意とし，SPX は変 数間に従属関係を持つ問題を得意とする． 提案アルゴリズムは，以下の通りである．

g

p

₁

p

₀

p

₂ 図 2: SPX における子個体生成領域 (i) BLX-α または SPX を交 演算に用いる実数値 GA を，はじめの G 世代実行する． (ii) G 世代までに得た個体群データを元に，[NNR+GL] を実行し，変数間従属関係を調べる． (iii) 変数間の従属関係に応じて，(G + 1) 世代以降の交 を以下のように変更する． • 従属関係が検出されなかった変数群には BLX-α を適用する． • 従属関係が検出された変数群には SPX を適用 する． (iv) 手順 (iii) で設定した交 演算を用いる実数値 GA を， E 世代 (E > G) まで実行する．

5

シミュレーション

5.1 使用する問題 提案手法の性能評価のために用いる問題は，CEC 2013 のコンペティションで用いられた 28 種類の実数値パラ メータ最適化問題 [5] で，目的変数の数はすべてで 10 で ある． 5.2 シミュレーション設定 前述した 28 種類の問題に対し，それぞれ 30 試行ずつ 最適化を行う． 提案手法の世代交代モデルには Minimal Generation Gap(MGG)[4] を用いるが，G + 1 世代以降では必要とす る親個体の数が異なる BLX-α と SPX を用いるため，以 下のように変更する． (a) 個体群から D + 1 個の親個体をランダムに選ぶ (D は従属関係が検出された変数の数)． (b) 従属関係が検出された部分列に対して SPX を適用 し，2 個の子の部分列を生成する． (c) D + 1 個の親個体からランダムに 2 個体を抽出する． (d) 抽出された親個体の従属関係を持たない部分列に対

して BLX-α を適用し，2 個の子の部分列を生成する． (e) 手順 (b) と手順 (d) の部分列を組み合わせ，突然変 異を適用し，2 個の子個体を生成する． (f) 手順 (c) で選んだ 2 個の親個体と手順 (e) で生成した 2 個の子個体の中から，エリート 1 個体とルーレット 選択で選んだ 1 個体を，手順 (c) で選んだ親個体と 入れ替える． 実数値 GA で用いるパラメータ，[NNR+GL] で用いる パラメータ等の設定をそれぞれ表 1，表 2 に示す．突然変 異は，変数の定義域内で一様分布に従う乱数によって変 数の値を書き換えるものとする．提案アルゴリズムのパ ラメータは G = 20，E = 100 とする． 表 1: GA の設定 問題サイズ 10 集団サイズ 100 突然変異確率 0.01 BLX-α における α 0.36 各変数の定義域 [−100, 100] 表 2: [NNR+GL] の設定 層数 8 隠れ層のノード数 40 重みの初期化 正規乱数 N (0, 12₎ 初期化数 10 学習係数 η 0.01 正則化パラメータ λ 0.10 最大 epoch 数 15000 5.3 シミュレーション結果 手順 (i) で BLX-α を用い，21 世代以降の交 を切り替 える提案手法 (以下提案手法 B) と，21 世代以降も BLX-α を用いる GA(以下従来手法 B) とのシミュレーション結 果の比較を表 3 に示す．手順 (i) で SPX を用い，21 世代 以降の交 を切り替える提案手法 (以下提案手法 S) と， 21 世代以降も SPX を用いる GA(以下従来手法 S) とのシ ミュレーション結果の比較を表 4 に示す．これらの表は， 各試行において，一方の手法が他方に対してより良い最終 解を得た回数をまとめたもので，有意差は有意水準 0.05 の符号検定により判定した．また，提案手法 B と提案手 法 S について，21 世代以降に適用された交 の回数をま とめたものを表 5 に示す．各問題に対して，試行ごとに 提案手法 B と提案手法 S が (G + 1) 世代以降に BLX-α， SPX，またはそれらの混合による交 を適用した回数を 示している．さらに，考察のために，従来手法 B と従来 手法 S の性能比較を表 6 に示す． はじめに提案手法 B の結果について見ていく．提案手 法 B のシミュレーションの結果，14 個の問題において有 意差があった．そのうち 11 個の問題において提案手法 B が従来手法 B に対して有意に優れ，3 個の問題において 有意に劣る結果となった． 提案手法 B が従来手法 B に対して有意に優れる結果と なった 11 個の問題は，いずれも変数間従属関係を持つ問 題であった．問題の変数間従属関係を適切に検出したこ とで，ベースである BLX-α よりも効率良く解くことが できたと考えられる．一方で，提案手法 B が有意に劣る 結果となった 3 個の問題のうち F11，F22 は変数間従属 関係を持たない問題であった．変数間従属関係を誤って 検出してしまったことで，変数間従属関係のない問題を 得意とする従来手法 B に劣る結果になったと考えられる． F14 は，変数間従属関係を持つ問題であり，提案手法 B も多くの試行で SPX を適用しているが，従来手法 B に 劣る結果になっている．表 6 を見ると，F14 の最適化に 関して BLX-α が SPX よりも優れていることが分かる． 提案手法 B が SPX を選択して従来手法 B に劣る結果に なったのはこのためであると考えられる． 次に提案手法 S の結果について見ていく．提案手法 S のシミュレーションの結果，5 個の問題において有意差が あった．そのうち 4 個の問題において提案手法 S が従来 手法 S に対して有意に優れ，1 個の問題において有意に 劣る結果となった． 提案手法 S が従来手法 S に対して有意に優れる結果と なった 4 つの問題のうち F01，F05，F11 は，変数間従属 関係を持たない問題であった．問題の変数間従属関係が 無いことを適切に検出したことで，ベースである SPX よ りも効率よく解くことができたと考えられる．F21 は，変 数間従属関係を持つ問題であるが，提案手法 S は多くの 試行で BLX-α を適用している．表 6 を見ると，F21 の 最適化に関して BLX-α が SPX よりも優れていることが 分かり，提案手法 S が従来手法 S に対して優れる結果に なったことが理解できる．一方で，F06 に関して提案手法 S は従来手法 S に劣る結果となっていた．提案手法 S は BLX-α を多くの試行で適用していた．表 6 より，F06 に 関しては BLX-α の方が SPX よりも性能が劣るため，こ のような結果になったと考えられる．

表 3: 提案手法 B と従来手法 B の比較結果．○は提案手 法 B が従来手法 B に対して有意に優れており，×は有意 に劣っていることを示す． 問題 提案手法B 従来手法B 有意差(P<0.05) F01 8 7 F02 26 4 ○ F03 19 11 F04 29 1 ○ F05 18 12 F06 23 7 ○ F07 17 13 F08 25 5 ○ F09 27 3 ○ F10 18 12 F11 3 27 × F12 18 12 F13 16 13 F14 1 29 × F15 30 0 ○ F16 28 2 ○ F17 12 18 F18 28 2 ○ F19 15 15 F20 18 12 F21 16 14 F22 3 27 × F23 23 7 ○ F24 16 14 F25 22 8 ○ F26 23 7 ○ F27 15 15 F28 16 14

6

おわりに

本研究では，NNR と GL による変数間従属関係検出手 法によって得た変数間の従属関係情報を利用して交 演算 を切り替える実数値 GA を提案し，従来の実数値 GA と CEC’13 ベンチマーク関数を用いて性能を比較した．その 結果，ほとんどの問題において，提案アルゴリズムが従来 の実数値 GA よりも優れた性能を持つことを示した．今 後は，NNR と GL による変数間従属関係検出手法を直接 的に個体生成に使用する GA を検討していく予定である．

参考文献

[1] M.Ohsaki et al: ”Discovery of Sets and Repre-sentatives of Variables in Co-nonlinear Relation-ships by Neural Network Regression and Group Lasso,” IEEE Int’l Conf. on Bioinformatics and Biomedicine BIBM-2018, pp.2287-2294, 2018. [2] L.J.Eshelman et al: ”Real Coded Genetic

Algo-rithms and Interval-Schemata,” Foundations of

Ge-表 4: 提案手法 S と従来手法 S の比較結果．○は提案手 法 S が従来手法 S に対して有意に優れており，×は有意 に劣っていることを示す． 問題 提案手法S 従来手法S 有意差(P<0.05) F01 30 0 ⃝ F02 15 15 F03 18 12 F04 12 18 F05 30 0 ⃝ F06 2 28 × F07 16 14 F08 17 12 F09 18 12 F10 11 19 F11 30 0 ⃝ F12 14 16 F13 15 15 F14 18 12 F15 17 13 F16 13 17 F17 17 13 F18 15 15 F19 18 12 F20 14 16 F21 24 6 ⃝ F22 17 13 F23 12 18 F24 12 18 F25 15 15 F26 15 15 F27 10 20 F28 20 10 netic Algorithms 2, pp. 187-202, 1993.

[3] S.Tsutsui et al: ”Multi-parent Recombination with Simplex Crossover in Real Coded Genetic Algo-rithms,” Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation-Volume 1, 1999.

[4] H.Satoh et al: ”Minimal generation gap model for GAs considering both exploration and exploita-tion,” Proceedings of the 4th International Con-ference on Soft Computing, Iizuka, Japan, pp. 494–497, 1996.

[5] J.J.Liang et al: ”Problem Definitions and Evalu-ation Criteria for the CEC 2013 Special Session on Real-Parameter Optimization, ” IEEE CEC 2013.

表 5: 提案手法の交 使い分け 問題 提案手法B 提案手法S BLX SPX 混合 BLX SPX 混合 F01 30 0 0 29 1 0 F02 0 30 0 0 30 0 F03 28 0 2 25 3 2 F04 0 30 0 0 30 0 F05 26 1 3 28 0 2 F06 9 12 9 23 4 3 F07 15 11 4 12 11 7 F08 0 30 0 0 30 0 F09 0 30 0 0 30 0 F10 7 16 7 5 18 7 F11 13 15 2 25 2 3 F12 11 13 6 19 8 3 F13 7 17 6 23 2 5 F14 0 28 2 0 30 0 F15 0 30 0 0 30 0 F16 0 30 0 0 30 0 F17 0 30 0 0 29 1 F18 0 30 0 0 30 0 F19 26 4 0 28 1 1 F20 0 29 1 1 27 2 F21 27 0 3 27 2 1 F22 0 30 0 0 30 0 F23 0 29 1 0 30 0 F24 1 26 3 3 23 4 F25 0 26 4 0 28 2 F26 1 27 2 1 23 6 F27 16 10 4 3 22 5 F28 18 6 6 25 3 2 連絡先 大西 圭 九州工業大学 大学院情報工学研究院情報・通信工学研究系 〒 820-8502 福岡県飯塚市川津 680-4 TEL&FAX: 0948-29-7660 E-mail: [email protected] 表 6: 従来手法 B と従来手法 S の性能比較．○は従来手 法 B が従来手法 S に対して有意に優れ，×は従来手法 S が従来手法 B に対して有意に優れていることを示す． 問題 従来手法B 従来手法S 有意差(P<0.05) F01 30 0 ○ F02 14 16 F03 24 6 ○ F04 14 16 F05 30 0 ○ F06 7 23 × F07 9 21 × F08 7 23 × F09 15 15 F10 11 19 F11 27 3 ○ F12 17 13 F13 26 4 ○ F14 29 1 ○ F15 9 21 × F16 3 27 × F17 28 2 ○ F18 2 28 × F19 19 11 F20 21 9 ○ F21 27 3 ○ F22 25 5 ○ F23 11 19 F24 22 8 ○ F25 17 13 F26 23 7 ○ F27 29 1 ○ F28 22 8 ○