信学技報
IEICE Technical Report
NLP2019-42(2019-09)

一般社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATIONAND COMMUNICATION ENGINEERS
社団法人 電子情報通信学会

信学技報
TECHNICAL REPORT OF IEICE.

THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

時変解に追従する人工蜂コロニーアルゴリズム
上四元 謙†

上手 洋子†

トーマス オット††

西尾 芳文†† 徳島大学 〒 770–8506 徳島県南常三島 2–1† チューリッヒ応用科学大学 Einsiedlerstrasse 31a， 8820 Waedenswil， Switzerland
E-mail: †{kamiyotsumoto,uwate,nishio}@ee.tokushima-u.ac.jp, ††thomas.ott@zhaw.ch
あらまし

本研究では， 時変解への高い性能が期待できる新たな人工蜂コロニー (ABC) アルゴリズムとして予測値を用いた ABC アルゴリズムを提案する. 標準の ABC では最適解の時間変化に即時対応できない. この問題点を解決するために繰り返しの度に再評価を行う手法が提案されている. 今回の研究ではそれに加えて予測値を付加させることでさらに高精度なアルゴリズムを提案する. 3 つの手法 (提案手法， 前手法， 標準の ABC) を比較し， 提案手法の性能が優れていることを示す.
キーワード

人工蜂コロニー最適化，最適化問題，群知能

Artificial Bee Colony Algorithm Following Time-Varying Solutions
Ken KAMIYOTSUMOTO† , Yoko UWATE† , Thomas OTT†† ,and Yoshifumi NISHIO†† Dept. of Electrical and Electronic Engineering， Tokushima University
2-1 Minami-Josanjima， Tokushima 770–8506， Japan† Zurich University of Applied Sciences
Einsiedlerstrasse 31a， 8820 Waedenswil， Switzerland
E-mail: †{kamiyotsumoto,uwate,nishio}@ee.tokushima-u.ac.jp, ††thomas.ott@zhaw.ch
Abstract Recently， nature-inspired metaheuristic optimization algorithms such as Artificial Bee Colony Algorithm (ABC) is developed. ABC is based on the feeding behavior of bee herds. ABC can not solve for time-varying
function. In this study， we oﬀer a new ABC for time-varying function. We propose ABC in which the scout
bee is improved probability by normal distribution. We compare the best solution with ABC， previous method
and the proposed method. Object function which optimal solution moves circle of shape is used. We investigate
characteristic of proposed method according to variance of normal distribution. Best value and orbit of solutions
for proposed method are better than those of other method.
Key words Artificial Bee Colony Algorithm， Optimization， Swarm Intelligence
ズムは，ランダム要素を持つためにそのような局所解から抜け1. ま え が き出すことができる.

近年，最適化問題を解くことが非常に重要になってきている.

確率的アルゴリズムの代表的なものとして群知能アルゴリ

最適化とは， 条件の中で最も目的に沿った解や計画を見つけるズムが挙げられる．群知能アルゴリズムは，動物や昆虫の特ことであり， 高い効率で設計，計画できることが利点である.

徴的な行動から考えられたアルゴリズムで，蟻コロニー最適最適化問題の例としては， 巡回セールスマン問題やナップサッ

化 (ACO)，粒子群最適化 (PSO)，人工蜂コロニーアルゴリズ

ク問題などが挙げられる. 確率的アルゴリズムは，最適化問題

ム (ABC)，ホタルアルゴリズム (FA)，カッコウ探索 (CS)[1]を解く上で非常に有用なアルゴリズムと考えられており，決定などが代表例として挙げられる. 群知能アルゴリズムは制御機論的要素とランダム要素で構成される. 決定論的要素しか持た構を小さくできることや複数の制御を単純に行えることが利点

ないアルゴリズムは，ほとんどの場合，局所探索アルゴリズムとして挙げられる. 蜂は 3 種類の蜂がそれぞれ探索を行うことであり局所解に陥る可能性がある. しかし，確率論的アルゴリで効率的に採餌行動を行うことができる. これを模倣したもの- 37 -—1—
This article is a technical report without peer review, and its polished and/or extended version may be published elsewhere.
Copyright ©2019 by IEICE

が ABC アルゴリズムである. ABC は時変環境に弱いという問

ここで，g(xi ) は目的関数を表す. ABC アルゴリズムのフロー題点がある. 私達は時変環境において従来の ABC と比べて精チャートを図 1 に示す.

度の高い解を求めるために予測値によって蜂が探索候補位置を決定する ABC アルゴリズムを提案する。本報告では，時変の目的関数において最小値を従来の ABC，前手法と比較する. シ
ミュレーション結果より， 提案手法が最も良い探索能力を持つことを確認する. また， 不時変環境においても探索能力があることを確認する.
本報告は，2. で従来の人工蜂コロニーアルゴリズムを説明した後，3. で提案されている前手法を説明し， 4. で提案手法について説明する. その後，5. でシミュレーション結果を示し，最後に 6. で結論を述べる.

2. 人工蜂コロニーアルゴリズム (ABC)

図 1 ABC アルゴリズムのフローチャート.

人工蜂コロニーアルゴリズム (ABC) は，蜂の採餌行動を元に 2005 年に Karaboga Dervis によって作製されたアルゴリズ

3. 前 手 法 [5]ムである [2] [3]. ABC アルゴリズムは高次元の目的関数の場合高い探索能力を持つ.[4] ABC は，3 種類の人工蜂 (働き蜂，傍従来の ABC には時間変化する環境では対応できない問題点観蜂および偵察蜂) によって探索を行う. ABC の探索手順を以がある. 適応度の計算がその時刻一回にしか行われず，その適下に示す.

応度でそれ以降の時刻も計算を続けることになる. したがって，Step0.

時間が進んだ際，アルゴリズムで使用している適応度と実際に働き蜂の総数 ne ，傍観蜂の総数 no ，コロニーのサイズ N =その時刻での本当の適応度に差が生じてしまう. しかし，現実

ne + no および最大繰り返し回数 tmax を初期化.

において目的値や前提の環境は未知であるため，どんな環境にStep1.

おいても最適解を求めることができることが望ましい. そこで(1) i 番目の蜂の位置 xi をランダムに配置.

西田らは，時間変化に対応する人工蜂コロニー最適化アルゴリ(2) それぞれの蜂の位置における適応度 fi を式 (1) によって計ズム (ABCTV) を提案している. ABCTV のフローチャートを算し最も高い適応度 fi とその位置を記憶.

図 2 に示す.

Step2.
(1) 新たな探索候補位置 vi を式 (2) によって求めその位置の適応度を計算.

(2) 適応度をもとに最も良い位置を更新.
step3.
(1) step2 で求めた適応度をもとに確率 pi を式 (3) によって計算.

(2) 確率 pi をもとに xi を選択しつつ，Step1 と同じように探索.
step4.
最良の適応度を持つ蜂の位置と適応度を更新.

step5.
適応度の低い位置にいる働き蜂を再配置.

Step6.

図 2 ABCTV のフローチャート.

step 1 から step5 を繰り返し解を出力.
適応度 fi ，蜂の移動および確率を計算する式を以下に示す.


fi =

1
1 + g(xi ) 1 + |g(xi )|{vij =pi = f i /if g(xi ) ≧ 0

if j = hxij

otherwisene∑

きる. 1 つ目は現在，蜂がいる位置の適応度を毎回改めて計算(1)

otherwise

xih + ϕ(xih − xmh )ABCTV は 2 つの改良によって時間変化に対応することがでする点である. この改良によって適応度のズレを正すことができる. 2 つ目は，全時刻を通じてではなく，各時刻ごとの最大の(2)適合度を求める点である. この改良で目的関数の変化に伴う適合度の変化に適応することが可能になる. またこの改良だけでも一定時間で大域解が発見され，多くの働き蜂がその周辺に集

fn ，(3)

まり大域解が移動した後は時間経過によって偵察蜂に再配置さ

i=1- 38 -—2—

れることで大局解の移動に対して適応できる可能性がある. この 2 つの改良によって ABCTV は目的関数の時間変化に対応することができた.

4. 提 案 手 法
ABCTV は時間変化する環境に対応できたが解は大まかな近図 3 式 (6) の形状.

似解であった.[6] 実際に医療や災害の現場に使用されるロボッ
トに実装する場合，即時性と解の精密性が必要である. また大域解の移動に追従するものの最適解への収束力は弱まった傾向が見て取れた. したがって，今回は最適解の動きに追従しつついる.今回使用したアルゴリズムの共通のパラメータを以下に示す.

より精度の高い ABC への改良を行う. ABCTV に予測値を付

ne = no = 50，tmax = 100，000(7)加させることで精度を高める. 予測値は大域解が等速運動であると仮定することで，現在と前回の最良値の差を計算すること

各シミュレーションは 25 回行い，その最小値を比較する.

で次の最適解の位置を予測する. 次に予測値を蜂の移動式に付

表 1 に従来の ABC，ABCTV，および 5 種類 C それぞれの場加するために粒子群最適化 (PSO) を参考にした. PSO の移動合の提案手法の最小値を示す. この表 1 では 7 種類の α(0.01，0.05， 0.10， 0.15， 0.20， 0.25， 0.30) において探索能力を式を式 (4) に示す.

比較した. 表 1 より，提案手法が ABCTV を上回るより良い最vij = xij + ϕ(xij − xk j ) + ψ(yj − xij )，(4)

適解を導けることがわかる．特に，C = 3.0 の時が最も良い解

yj は全個体の中の最良値， xk j はその個体の最良値を表す.PSO
では選択した個体の最良値，現在の値および群れ全体の最良値の 3 つを組み合わせることで最適な値に近づく. 蜂では現在の値とランダムに選んだ他の個体の 2 つの値によって最適解を探索する. したがって提案手法では従来の ABC と PSO を組みが求められている. しかし一方で，α が大きくなればなるほど多くの提案手法で探索能力が低下した. これは α が大きくなればなるほど最適解の動きは離散的になり探索が困難になる事と離散的な問題には等速運動の仮定での予測値には限界があることが分かる.

5. 2 シミュレーション 2合わせることで以下の式で蜂の移動を行う.

{vij =xih + ϕ(xih − xmh ) + ψ(xp − xih )xij

時変関数のみにしか適応できないのではなくどちらの環境にj=hも適応できることが望ましい. したがって次に，不時変関数で(5)その他の探索性能を確認する. 今回のシミュレーションでは 3 つのベψ は [0，C] の一様乱数であり， C は正の整数である. 今回のシンチマーク関数における探索性能を確認する. 今回使用したベミュレーションでは 5 種類の C(0.5， 1.0， 2.0， 3.0， 4.0) をンチマーク関数を以下の表 2 にまとめる. また，表 2 で表され設定した.

る 3 つのベンチマーク関数の形状を以下の図 4，5，6 で示す.

5. シミュレーション
最初に乱数の幅 5 種類の提案手法と従来の ABC，ABCTVの比較を行い，その後提案手法の不時変な環境への性能についても確認する.

5. 1 シミュレーション 1
はじめに時変環境の性能を評価するために私達は，ビジュア
ルトラッキング問題を模倣した以下の式 (6) を適用し，その解の最小値を比較する. 式 (6) の形状を図 3 に示す.

(x1 − 250 − 125 sin αk)22 · 402(x2 − 250 + 125 sin αk)2].
−2 · 402g(x1 ，x2 ，k) = 1 − exp[−

図 4 Sphere function.

(6)

この式 (6) で表される関数は単峰性の時変関数であり図 3 のようなガウス関数で表現される特徴が連続的に移動しこれを追跡する問題である. 最小値は 0 であり， その位置は (x1 ，x2 )= (250，250) を中心とした半径 125 の円周上を移動し，およそ(2π/α) ステップで元の位置に戻る. k は離散時間を表し，今回のシミュレーションではアルゴリズムの繰り返し回数と同じに設定する. αは最適解が 1 ステップで移動する変化量を表して- 39 -

図 5 Rastrigin fuction.

—3—

表1α

時変環境におけるシミュレーション結果

0.01

0.05

0.10

0.15

0.20

0.25

0.30

ABC

1.08e-08 1.11e-06 4.11e-06 4.51e-06 3.12e-06 4.55e-06 6.08e-06

ABCTV

4.12e-07 3.34e-06 9.96e-05 7.33e-05 2.96e-04 1.43e-04 2.77e-05

提案手法 (C=0.5) 2.26e-07 6.47e-06 6.75e-06 3.33e-05 2.62e-06 6.53e-06 1.56e-05
提案手法 (C=1.0) 9.21e-08 3.84e-07 3.90e-07 6.39e-06 5.94e-06 1.07e-05 5.96e-05
提案手法 (C=2.0) 1.55e-08 4.35e-07 8.59e-06 7.12e-06 2.92e-05 1.33e-05 6.71e-06
提案手法 (C=3.0) 4.28e-09 4.28e-09 3.52e-06 1.05e-05 9.34e-07 4.01e-07 7.16e-06
提案手法 (C=4.0) 4.31e-08 1.18e-06 1.99e-06 1.06e-05 3.16e-05 3.88e-06 1.56e-05

表2

ベンチマーク関数あることを示した.

function∑DNamex2n=1 n∑D(x2n − 10cos(2πxn ) + 10)√ n=1∑∑20 − 20exp(−0.21/nDx2 + e − exp(1/nn=1 nDcos(2πxn ))n=1

Sphere Function

今後の研究は，提案手法の詳細の調査が考えられる. また，予Rastrigin Function

測値を導く際に等加速度など他の仮定による改良も挙げられる.

Ackley Function

文

図 6 Ackey fuction.

図から分かるように単峰性と多峰性の関数において提案手法の探索能力を確認する. すべての最適解は 0 であり，使用したパラメータはシミュレーション 1 と同じである. シミュレーション 1 から C = 3.0 の時が最も良い解を導くことが出来たことより C = 3.0 の場合の探索能力を表 3 に示す.

献[1] X. S. Yang， “Nature-Inspired Metaheuristic Algorithms
Second Edition，” Luniver Press， 2010.
[2] D. Karaboga， “An idea based on honeybee swarm for numerical optimization，” Technical Report TR06， 2005.
[3] I. Iimura and S. Nakayama， “Search Performance Evaluation of Artificial Bee Colony Algorithm on HighDimensional Function Optimization，” Transactions of theInstitute of Systems， Control and Information Engineers，vol. 24， pp. 97-99， 2011.
[4] W. Y. Szeto and Y. Wu and S. C. Ho， “An artificial bee
colony algorithm for the capacitated vehicle routing problem，” European Journal of Operational Research，vol. 215，
pp. 126-135， 2011.
[5] T. Nishida， “Modification of ABC Algorithm for Adaptation to Time-Varying Functions，” Electronics and Communications in Japan， vol. 96， 2013.
[6] K. Kamiyotsumoto， T. Ott， Y. Uwate and Y. Nishio，“Artificial Bee Colony Algorithm for Time-Varying Optimization，” Proceedings of RISP International Workshop
on Nonlinear Circuits， Communications and Signal Processing (NCSP’19)， pp. 382-385， 2019.

表 3 不時変環境におけるシミュレーション結果
dimention

10Sphere

030

50

Rastrigin

17.39

92.80

189.34

Ackley

12.11

19.23

19.94

6.44e-243 6.11e-48

表 3 から不時変関数においても高い探索能力を持っていることが分かる.

6. 結論

私達は，多様な環境に対応するために予測値を付加した人工蜂コロニー最適化アルゴリズムを提案した. 従来の ABC では選択した個体とランダムな選択で選ばれた個体の 2 つの個体から次の状態に移動する. しかし今回の提案手法ではそれに等速運動と仮定することで計算された予測値を付加させた. この予測値を粒子群最適化の移動式を参考に ABC アルゴリズムに組み込んだ. 時変関数の最小値を ABC，前手法，および提案手法で比較した. 最小値は従来の ABC を上回り提案手法の優位性を示した. さらに提案手法が不時変関数においても探索性能が- 40 -—4—