ABC アルゴリズムを用いた関数最適化問題の難易度推定の検証〇原田航 片田喜章(摂南大学)  Estimation of Problem Difficulty on Function Optimization by Using ABC Algorithm*W. Harada and Y. Katada (Setsunan University)
Abstract－ Since the early works of the theoretical GA community, problem difficulties for a GA have beendiscussed. In the GA community, a major attempt to characterize difficulty has been done by measuring thefeature of a fitness landscape (objective function), i.e., ruggedness. In this study, we proposed the approach estimating problem difficulties by using the ABC algorithm and investigated the validity of the proposed method onbenchmarks for function optimization problems. The obtained results in this study are consistent with those in
the previous work.
Key Words: ABC Algorithm, Function optimization, Problem difficulty

1. 研究背景及び目的

3.

身近に存在する問題でも，解が多すぎて，全探索を試みても実時間で最適解を見つけ出すのが困難な問題が存在する．このような “多数の解の中から，ある制約条件の下で最も適した解を求める”問題は最適化問題とよばれる．これに対し，最適化問題の最適解を導くアルゴリズムは最適化アルゴリズムとよばれる．実問題を取り扱う場合，最適化問題の難易度を定量的に表す指標があれば，それに基づいた最適化アルゴリズ
ムの選定，パラメータのチューニングが可能になると期待される．よって，本研究では，関数最適化問題における関数の難しさを, ABC アルゴリズムを用いて定量化する指標を提案し，テスト関数において検証することを目的とする．ABC アルゴリズムの採用理由は次節以降で述べる．

3.1 ABC アルゴリズムを用いる提案手法
偵察蜂のフェーズに注目する．ある個体が探索を連続して失敗する状況とは，周辺の優良な解を探索し終え，その個体の持つ解より優良な解が見つからない状
況であると言える(局所解における滞留)．局所解は最適化問題を難しくする代表的な要因であり，局所解が多く存在する場合，働き蜂と見物蜂のフェーズで生じる Trial がより多くカウントされ，ABC アルゴリズム
では偵察蜂フェーズがより多く実行されると考えられる．よって，ABC アルゴリズムにおける探索において，探索中にカウントした Trial の総数は問題の難しさを定量的に表現していると考えられる．これらを用いて問題の難易度の推定を試みる．

2.

難易度の指標3.2 景観の凹凸の特徴量
目的関数の景観における山や谷といった凹凸の度合いが激しい関数は，そうではない関数と比較して，最適値を求めることが困難であることが考えられる．つまり，問題の難しさと凹凸の特徴量は直結していると予想される．これに関して，凹凸の特徴量の指標として Smith ら[2]によって提案された手法 Eb がある．評価
値 k の個体を変化させて作られた個体の平均評価値は以下のように定義される．

ABC アルゴリズム

本研究では，蜜蜂の採餌行動にもとづいて最適解を探索する Artificial Bee Colony (ABC) アルゴリズム[1]を採用する．この最適化アルゴリズムは，働き蜂・見物蜂・偵察蜂の 3 種のフェーズによって探索が行われる．以下に概要を記す．

① 働き蜂
全蜂個体 N匹が各々持つ設計変数の一つをランダムに変更する．変更後の目的関数値が優良であった場合はその変数を更新する．優良でなかった場合は変数値を更新せず，探索失敗回数(Trial)をカウントする．

𝐸𝑏 (𝑘) =② 見物蜂∑𝑔∈𝐺(𝑘) 𝑉 (𝑔)|𝐺 (𝑘)|(1)

ここで，G(k)は評価値 k の個体から作られた個体の設計変数集合で，g は作られた個体の設計変数，V(g)は作られた個体の評価値である．最適化アルゴリズムの中で，評価値が改良されることを期待してある個体を変化させる工程があるとする．そこで変化前の評価値を x 軸，変化後の評価値を y 軸として散布図に Eb (k)をプロットし，最小二乗法を用いて Eb (k)の傾き Eb を求める．凹凸の特徴量が大きければ大きいほど，Eb の傾きは減少することが知られている[3].

より優良な目的関数値を持つ個体に高い確率が与えられるよう全蜂個体に対し相対確率を算出する．この確率に基づき個体の選択を N 回行い，設計変数を働き蜂のフェーズと同様に更新する．

③ 偵察蜂
働き蜂と見物蜂の探索によってカウントされた探索失敗回数(Trial)が一定数に達した個体の設計変数を初期化し，再度，探索を開始する．

第 56 回システム工学部会研究会（2017 年 3 月 9 日・大阪）

17PG0003/17/0000-0001 © 2017 SICE1

4.

探索の終了判定

すべての個体が収束した場合，その探索は十分に行われた，もしくは，それ以上の探索は期待できないと判断できる．よって，蜂個体の位置(設計変数)情報から分散を計算し，分散があるしきい値以下になった場合，探索を終了させることとする．一方，最適化アルゴリ
ズムや問題によっては各個体がある 1 点に収束しない関数も多く存在する．そのような関数では分散によって終了判定を行うことが難しい．そこで，探索によって得られた最良解が，ある一定サイクル間で更新されなかった場合に探索を終了させることも同時に実行する．つまり，未更新の連続回数による判定または分散による判定を用いて終了判定を行う．

5.

計算機実験

5.1 設定計算機実験の設定を表 1 に示す．本実験では 9 種類のテスト関数を用いた(附録参照)．D=10，30，50，70，90 次元で計算機実験を行い，Trial を記録した．このTrial は式(2)で正規化している．これらの値は 1 に近ければ近いほど，関数は難しいと考えられる．なお，分母で 2 をかけている理由は働き蜂・見物蜂の両フェーズを考慮しているためである．

Trial⁄(Trial の最大数) =Trial
全蜂個体数×2×サイクル数(2)

表 1 計算機実験設定
生成する蜂個体N探索する次元D
変数xの定義域
最大Trial
終了判定
試行回数

20
10，30，50，70，90[-100,100]100
位置の分散:100
未更新の連続回数:5000

5.2 結果
実験結果を表 2 に示す．Sphere 関数と Rastrigin 関数を比較したとき，単峰性である Sphere 関数に比べて多峰性である Rastrigin 関数の方が難しいと予想できる．
結果は Rastrigin 関数の方が Trial/(Trial の最大数)が大きな値を示していた．Rosenbrock 関数は変数依存性を有するため，Trial/(Trial の最大数)は Sphere 関数よりも大きな値を示すことが予想できる．結果は Rosenbrock関数のほうが大きな値を示した．また，多峰性を持つ
Rastrigin 関数と Trial/(Trial の最大数)を比較して，Rosenbrock 関数の方が大きな値を示していることから，多峰性より変数依存性の方が関数の最適化の探索を困難に す る 性 質 で あ る こ と いう こ と が 考 え られ る ．
Griewank 関数は多峰性を持つが，Trial/(Trial の最大数)が Sphere 関数よりも小さい値を示している．これは，Griewank 関数の計算式中で Sphere 関数を 1/4000 倍にしており，Sphere 関数に比べ該当する項の評価値が大幅に小さい値を示すため，Sphere 関数よりも優良とされる最適値が求めやすくなったことが原因であると推測される．Griewank+Rosenbrock 関数は Trial/(Trial の最大数)が Griewank 関数や Rosenbrock 関数単独の場合よりも大きい値を示している．これは，Griewank 関数の局所解を多く有する性質と Rosenbrock 関数の変数間依存性が複合されたことによって高い値を示したと考えられる．Ackley 関数は Trial/(Trial の最大数)が比較的高い値を示している．ここで，Ackley 関数の最適値に注目すると，30～90 次元で一定の値を示している．これは，Ackley 関数の持つ最適値付近で急激に適応度が下がる範囲を探索中に発見できていないことが，高い値を示す要因となっていると考えられる．Happycat 関数や HGbat 関数は多峰性を持つが，同じく多峰性を持つ Rastrigin 関数よりも，Trial/(Trial の最大数)が低い値を示した．これは，Happycat 関数や HGbat 関数の持つ局所解は，Rastrigin 関数のように規則的に表れるのではなく，変則的に表れるよう設計されていることが影響していると考えられる．Weierstrass 関数は比較的高い値を示している．これは Weierstrass 関数の持つ微分不可能な性質が影響していると考えられる．

306.

考察

D=50 次元における Eb (k)の実験結果を図 1～9 に示す．また，D=50 次元での Trial と Eb を比較した結果を表 3 に示す．3 節で述べたように Trial の値は大きいほど難しい問題と考えられ，Eb の値は小さいほど凹凸の特徴量は大きく，難しい問題とされている．
表 3 の結果より，Trial と Eb を関数ごとに比較したとき，多くの関数で整合性のある結果が得られていることがわかった．

2表 2 実験結果

次元10Sphere30-6203

673

1232

1764

2247

Trial5498

18197

33292

47666

60789

Happycat0.675690-50.675647-2

4.47×10 -5

サイクル数

396

1519

3376

6028

9119

Trial12414

47483

106316

1908392908070.781574

0.787360

0.791429

0.797262

1.43

1.47

2.68

1.57

-1

3.32×10

5.72×10

4.89×10最適値

6.35×10

サイクル数

7247

10468

9935

11216

12606

Trial

2539243539243281783645554043200.845227-70.825774-70.812556-70.801869-7

4.76×10 -7

最適値

6.58×10

サイクル数

158

536

964

1392

1818

Trial

4091

13939

25114

36319

47432

0.649989

0.651583

0.652290

0.652311

3.07×10

4.02×10

2.71×10

最適値

1.01×102.00×102.00×102.00×102.00×10

サイクル数

9587

7306

8564

9201

10002

Trial

352907261162302363322205348106

0.893713
20.882678
30.87541850.870049
51.45×10 5最適値

8.72×10

サイクル数

12510

17661

20049

24042

28823

Trial

440585615749694739832118995676

Trial/(Trialの最大数) 0.880447-2

1.47×100.871609-1

1.90×100.866290-1

1.01×100.865260-10.863604
2.98×10 -1

最適値

9.84×10

サイクル数

7964

8808

8775

9467

9199

Trial

256238258806250784267133257341-1

1.70×100.734570-1

2.24×100.714456-1

2.55×100.705401-10.699342
3.92×10 -1

最適値

1.77×10

サイクル数

8793

9243

99919003

9368

Trial282253

270794285553254122262632

Trial/(Trialの最大数) 0.802472

0.732441

0.714496

0.705629

0.700907

最適値

Weierstrass

0.675993-2

6.24×10

1.36×10

Trial/(Trialの最大数) 0.804383

HGbat

9.84×10

最適値

Trial/(Trialの最大数) 0.920307

Griewank+
Rosenbrock1.27×100.675993-5

Trial/(Trialの最大数) 0.649016

Ackley5.14×10 -7

サイクル数

Trial/(Trialの最大数) 0.875921

Griewank

90-7

1.49×10

Trial/(Trialの最大数) 0.784228

Rosenbrock

70-7

最適値

Trial/(Trialの最大数) 0.677968

Rastrigin

50-62.90×10

3.49×10

3.78×10

1.42×10 -14 1.42×10 -14 1.60×10 -1 9.62×10 -1

1.93

サイクル数

5059

5619

9090

9720

10289

Trial

186279201018321152340562358187

Trial/(Trialの最大数) 0.920616

0.894346

0.883275

0.875921

0.8703163

図1Sphere 関数における Eb 値

図 5 Ackley 関数における Eb 値

図 2 Rastrigin 関数における Eb 値

図 6 Griewank+Rosenbrock 関数における Eb 値

図 3 Rosenbrock 関数における Eb 値

図 7 Happycat 関数における Eb 値

図 4 Griewank 関数における Eb 値

図 8 HGbat 関数における Eb 値47.

まとめ

本研究では，関数最適化問題における関数の難しさを，ABC アルゴリズムを用いて定量化する指標を提案し，テスト関数において検証を行った．ABC アルゴリズムを用いて求めた探索失敗回数(Trial)は文献[2]で提案されている指標 Eb と多くのテスト関数で整合性のある結果を得た．提案する指標は Eb よりも簡易に求めることができ，実数値関数最適化問題における判断材料として有効に活用できると期待される．
図 9 Weierstrass 関数における Eb 値

参考文献
表 3 提案指標と Smith らの指標の比較
テスト関数名[1] D. Karaboga, B. Basturk: A powerful and Efficient Algorithm
for Numerical Function Optimization: Artificial Bee Colony

Trial/Trialの最大数

EbGriewank

0.65189

1.00002

Sphere0.67574

0.98955

Rastrigin

0.783210.87495

scapes and evolvability, Evolutionary Computation, Vol. 10,Rosenbrock0.820190.85011

No. 1, pp. 1-34, (2002)

Griewank + Rosenbrock0.86665

0.40520[3] 片田，大倉：根井の標準遺伝距離を用いた適応度景観にHappycat0.71446

0.68207含まれる neutrality の推定，システテム制御情報学会論Hgbat

0.71450

0.50805

Ackley0.88261

0.98319

Weierstrass

0.883180.85240(ABC) Algorithm, Journal of Global Optimization,Volume:39,
Issue:3, pp.459-471, (2007)[2] T. Smith, P. Husbands, P. Layzell and M. O'Shea: Fitness land-

文誌，Vol.18 No.8，pp.284-291,(2005)[4] J. J. Liang，B. Y. Qu，P. N. Suganthan：Problem Definitions
and Evaluation Criteria for the CEC 2014 Special Session
and Competition on Single Objective Real-Parameter Numerical Optimization，http://web.mysites.ntu.edu.sg/epnsugan/PublicSite/Shared%20Documents/CEC-2014/Definitions%20of%20%20CEC2014%20benchmark%20suite%20Part%20A.pdf (2014)

5

Griewank+Rosenbrock 関数

附録

𝑓𝑔𝑟𝑖𝑒𝑤𝑎𝑛𝑘+𝑟𝑜𝑠𝑒𝑛𝑏𝑟𝑜𝑐𝑘 (x)実験に用いる最適化問題の目的関数として採用したテスト関数[4]の式とその最適値を(3)～(20)に示す．

= 𝑓𝑔𝑟𝑖𝑒𝑤𝑎𝑛𝑘 (𝑓𝑟𝑜𝑠𝑒𝑛𝑏𝑟𝑜𝑐𝑘 (𝑥1 ∙ 𝑥2 ))+ 𝑓𝑔𝑟𝑖𝑒𝑤𝑎𝑛𝑘 (𝑓𝑟𝑜𝑠𝑒𝑛𝑏𝑟𝑜𝑐𝑘 (𝑥2 ∙ 𝑥3 ))Sphere 関数2𝑓𝑠𝑝ℎ𝑒𝑟𝑒 (x) = ∑𝐷𝑖=1 𝑥𝑖𝑓𝑠𝑝ℎ𝑒𝑟𝑒 (0) = 0+ ⋯ 𝑓𝑔𝑟𝑖𝑒𝑤𝑎𝑛𝑘 (𝑓𝑟𝑜𝑠𝑒𝑛𝑏𝑟𝑜𝑐𝑘 (𝑥𝐷−1 ∙ 𝑥𝐷 ))(3)+ 𝑓𝑔𝑟𝑖𝑒𝑤𝑎𝑛𝑘 (𝑓𝑟𝑜𝑠𝑒𝑛𝑏𝑟𝑜𝑐𝑘 (𝑥𝐷 ∙ 𝑥1 ))

(4)

(13)
𝑓𝑔𝑟𝑖𝑒𝑤𝑎𝑛𝑘+𝑟𝑜𝑠𝑒𝑛𝑏𝑟𝑜𝑐𝑘 (1)＝0Rastrigin 関数(14)2𝑓𝑟𝑎𝑡𝑟𝑖𝑔𝑖𝑛 (x) = ∑𝐷𝑖=1(𝑥𝑖 − 10 cos(2𝜋𝑥𝑖 ) + 10)

Happycat 関数(5)𝑓𝑟𝑎𝑡𝑟𝑖𝑔𝑖𝑛 (0) = 0 (6)14

𝐷𝑓ℎ𝑎𝑝𝑝𝑦𝑐𝑎𝑡 (x) = | ∑ 𝑥𝑖2 − 𝐷|𝑖=1Rosenbrock 関数

2𝐷+(0．5 ∑𝐷
𝑖=1 𝑥𝑖 + ∑𝑖=1 𝑥𝑖 )/𝐷 + 0．5

𝐷

𝑓𝑟𝑜𝑠𝑒𝑛𝑏𝑟𝑜𝑐𝑘 (x) = ∑(100(𝑥𝑖 + 1 − 𝑥𝑖2 )

2(15)

𝑖=1

𝑓ℎ𝑎𝑝𝑝𝑦𝑐𝑎𝑡 (−1) = 0 (16)+(𝑥𝑖 − 1)2 ) (7)HGbat 関数𝑓𝑟𝑜𝑠𝑒𝑛𝑏𝑟𝑜𝑐𝑘 (1) = 0 (8)2𝐷𝐷

12 2𝑓ℎ𝑔𝑏𝑎𝑡 (x) = | (∑ 𝑥𝑖2 ) − (∑ 𝑥𝑖 ) |Griewank 関数
𝐷𝑖=1

𝐷𝑥𝑖2
𝑥𝑖(x)
𝑓𝑔𝑟𝑖𝑒𝑤𝑎𝑛𝑘=∑− ∏ cos ( ) + 1
4000
√𝑖𝑖=1

𝐷

𝐷
2+ (0．5 ∑ 𝑥𝑖 + ∑ 𝑥𝑖 ) /𝐷 + 0．5
𝑖=1
𝑖=1

𝑖=1(9)
𝑓𝑔𝑟𝑖𝑒𝑤𝑎𝑛𝑘 (0) = 0

𝑖=1(17)(10)𝑓ℎ𝑔𝑏𝑎𝑡 (−1) = 0 (18)Ackley 関数
Weierstrass 関数

𝐷1𝑓𝐴𝑐𝑘𝑙𝑒𝑦 (x) = −20 exp − 0．2√ ∑ 𝑥𝑖2
𝐷𝑖=1()

𝐷𝑘𝑚𝑎𝑥

𝑓weiestrass (x) = ∑( ∑ [𝑎𝑘 𝑐𝑜𝑠 (2𝜋𝑏𝑘 (𝑥𝑖 + 0．5))]𝑖=1𝑖=1𝑘𝑚𝑎𝑥
1𝐷+ ( √∑𝐷
𝑖=1 cos(2𝜋𝑥𝑖 )) + 20 + 𝑒−D ∑ [𝑎𝑘 𝑐𝑜𝑠(2𝜋𝑏 𝑘 ∙ 0．5)])𝑖=1(11)
𝑓𝐴𝑐𝑘𝑙𝑒𝑦 (0) =0(19)a = 0．5，b = 3，kmax = 20

(12)𝑓wiestrass (0) = 06(20)