The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 1 -
索
知識利用を自
調整
人工蜂
ニ
Artificial Bee Colony Algorithm that autonomously balances exploration and exploitation
澤
優太
*1佑
*1高橋
達
*2Ozawa Yuta Kohno Yu Takahashi Tatsuji
*1
東京電機大学大学院
*2
東京電機大学
Graduate School of Tokyo Denki University Tokyo Denki University
Artificial Bee Colony (ABC) Algorithm is an optimization algorithm that is inspired by the intelligent foraging behavior of honeybee swarms. It is a superior method for high-dimensional space. However, ABC depends on the uniform random number in some crucial points. We improve the search by ABC with introducing a causal value function inspired by human cognition that is known to treat the dilemma of exploration and exploitation that is inevitable in uncertain and/or huge environments. We propose a new ABC algorithm that autonomously balances exploration and exploitation with a kind of causal reasoning.
1.
じめに
人工蜂 ニ Artificial Bee Colony 以 ABC
[Karaboga 05] 蜜蜂 餌 索行動 業を 表現し
多点 索型関数最適化手法 1 ，群知能
類 ．群知能 ，粒子群最適化，蟻
ニ 最適化 い あ ， 中 ABC
非線形問題や多峰性問題 対し 高い 索性能を持 ，
特 高次元 問題 い 索性能 優 い いう報告
あ [宇谷 12]．ABC 索点 目的関数値
を 適合度 表現 索点 評価を 定 化し い ．
適合度 解改善行動 共 変動し，適合度を 用い 索点
試行 解生 成 回 数を 変 化 索空 間 有
望領域を短時間 詳細 索 ．し し ，改善行動
処理 要素 選択や 索 変動値 一様乱数
行 い ， 索点 状態を考慮し い い いう
改善 余地 あ 考え ．一様乱 数 各要素
選択割合を 同一 大域的 索を実現し い ，
要素 選択割合を 同一 し 索を 行う ，改善行動
得 情報を 用い ， 大 適合度 変化を 期待
要素を無視し し う を意味 ．
本研究 ABC 解改善行動 着目し，解
改善 密接 関係 あ 索点 適 合度 変化 を 考慮
し 要 素 選 択を 行う 手 法を 考 案し ． 際 生物 因
果関係 推論 傾向 情報 索 活用 ン ン 有
効 あ 知 い ， う 推論 傾 向を ABC
組 込 ， 繁 変化 環境 一様乱
数 処理 比較及び考察 ，従来 ABC
解 変動を比較し考察を行 ．
2. ABC
ア
ゴ
ズム
ABC 穫 蜂 Employed bees ， 追 従 蜂
Onlooker bees ，偵察蜂 Scout bees 3種類 人工蜂群 ，
蜜源 を 索点 呼ぶ を基本構成 し 索を行う． ニ
目 的 ，評 価 最 高 い蜜 源を 索 あ ．
章 ，ABC 処理 流 問 題点 い 説
明 ．次 与え 関数 f(x) 最 値 要素 x を 求
際 ABC 処理手順 い 説明 ．
2.1 ABC
ア
ゴ
ズム
流れ
Step0：初期化
1. 最大 プ回数Rを設定し， プ回数r = 1 し
N個 索点� を 索空間 ン 生成
． = { , , , . . . , N } 索点 番号 あ ．
索点 � 数 N 時， 穫蜂 数Ne 追従蜂
数No N=Ne=No ． 穫蜂 追従蜂 索
更新 回数を表 �iを�i = 0
． �i 偵察蜂 索 用い ． ，
偵察蜂を制御 値limitを設定 ．
2. 索点 � 適合度� � を計算 ．
� � = { + � � if � �
+ |� � | others
(1)
3. 初期段 最良解 関数値を保持 ．
�be = �
�be = �
， = argmax � �i あ ．
Step1： 穫蜂 索
N個全 索点 � い ，新しい 索点 候補�
を生成し，適合度 基 い 情報 更新を ．
1. 索点 � ン 選択 第 番目 次元を
2)式を用い 求 ．
� = � + � � − �
(2)
， N個 ン 選択 索点，
� = [− , ] 一様乱数 あ ．
2. 新 し い 索 点 候 補� 適 合 度� ��
�を 以 う
求 .
� ���= { + � �
if � �
+ |� � | others
(3)
3. 適合度 ， 索点 � ，適合度� � ，更新情報 �
を次 う 更新 ．
� = { � if � ���> � �
� others
(4)
� � = { � ��� if � ���> � �� � others
(5)
� = { if � ��� � �� + others
(6)
連絡先： 澤: e-mail: 10rd050[at]ms.dendai.ac.jpThe 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 2 -
Step2：追従蜂 索 相対確率 計算
適合度 � � 基 い ，各 索点 � 相対確率 � を求 ．
� = .9 ∗ (max � � ) + .� �
(7)
Step3：追従蜂 索
相対確率 � 基 ， ッ 選択 索点
� を選択し，step 1，2，3を適用 ．
Step4：最良 索点 更新
全 索点 ，� > �be を満 時，次 う
最良 索点を更新 ．
�be = �
fbe = �
， = argmax � �i あ ．
Step5：偵察蜂 索
指定回数更新 索点 � ， わ
� limit を満 番号 索点を，一様乱数 初期化し 索空間 再配置 ． ，� = し 適合度� � を求 ，保持 ．
Step6：終了条件 判定
プ回数r 最大 プ回数R 場合，
� = �を満 場合終了 ．満 し い い場合 � = � + し Step1 戻 ．
2.2 ABC
ア
ゴ
ズム
問題点
ABC 処理 ，適合度 いう 得 情報を
追 従 蜂 索 利 用 有望 領域 詳 細 索 を
実現し い ．し し ， 試行解 生成 用い 2 式 着
目 ， 索 次元 j ，差 用 索点 k ，差 変動値�
一様乱数 計算し い ． ，ABC
改善行動 得 結果， 知識を 利用し い 追
従蜂 索点 i 選択 あ ，試行解 生成 知識
を 利用し い い いう 確 ． ， 2 式 明
，試行解 生成を 際 ， 索点� 要素 あ
� 差 を 索点 � 要素 あ � 値 解 変動 大 変わ いう あ ．要素 � � 値
差 ば， 点 い 局所的 索を
， 解 変動 幅 い ． ， 変動 幅
局所的 最適 解を 多 含 多峰 性 強い
関数 場合，解及び 索 局所化を 生 原因 ． ，
ABC 索点生成 ，次元 j ，差 用 索点 k ，
� 一様乱数 選択 い ， 一様乱数 影
響 強 知識を利用し い い ， 索点 状態を考
慮し い い ，適合度 変動値 索点 状態 依存
， 大 適合度 変化を 期待 要素を 考
慮し い い いう 考え ．
3.
提案手法
ABC 問題点 し ，試行解 生成 処
理 ，要素 選択 一様乱数 あ 適合度 変化を 考
慮し い い い い ，大 改善を 見込 要素を
考慮し い い いう を 指摘し ． ， 解 改善行動
得 知識を 利用 方法 し ， 適合度 変化 を 改善
行動 結果 し 利用し， 索点 状態を考慮し 要素を選択
要素価値選択 以 EVS を 考案し ．
，解 改善行動 得 各次元 適 合度 変
化 を，選択し 行動 結果 し 用い 各要素
価値を 推定し， 大 改善を 見込 要素を 選択 を 目
的 ．
各要素 適 合度 変 化 を 算 出 あ ，各要 素 適
合度 変化 差 用 索点 k 変化し し う 一
意 定 い ． ， 各 要素 現在 変 化 ，現 在 得
変化 差 対し 索点 数 逆数 を用い
漸化的 新しい変化 値を更新し算出 ，複
数 差 索点を用い 際 適合度 変化 値を推定し ．
EVS 各 索点 要素 選択を行動 し
考え，適合度 変化 平均 あ 行動を改善結果
得 知識を 用い ， 大 変化 得 要
素を選択 を基本 ．
図1. ABC 要素 選択
図2. EVS 要素 選択
， 索点や差 索点 状態 変わ 度 索点 状
態 変化 ，改善行動 際 得 適合度 変化
要素 価値 大 変わ ． ，現在得 い 価値
要素 100%信 い を意味し， 要素を選択し
確実 変 化 得 限 い ． ， 最適化
処理 う 環境 ， 早 正確 適合度 大
変化を期待 要素を予測し ば い．
予 測 正確 判断 早 オ フ 関 係
あ ， 索 知識利用 調節 要 あ ． オフ
関し 最 基本 的 問 題設定 し ン ッ 問 題 存在
． ，本研究 提案手法 あ EVS ，
ン ッ 問題 用い い 価値関数を用い し ．し
し，通常 ン ッ 問題 用い い 行動 結果 ，当
， い う 離散的 情報 扱わ い ．今回，
EVS 価値関数を適用 あ 適合度 変化
連続 値 あ ，本研 究 結果 表現 方法 を ， 各要
素を更新し 際 適合度 変化 索点 各要素 適
合 度 変化 平 均 あ 場 合 ，平 均 あ
場合 離散的 情報 2 結果を 表現し ． 次 ，評価方
法 し 用い 表を表1 示 ．
表1. 2×n 割表 共変動情報
要素 結果
平均 平均
� �
⋮ ⋮ ⋮
�� � �
x1
x2
x3
x4
探索点i
? Bee
改善行動
?
? ?
要素 選択
Random
Bee
改善行動
価値関数
探索点i
0.004 0.003
0.016
0.15
x1
x2
x3
要素 選択
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 3 -
4.
用いた価値関数
章 ，用い 価値関数 い 説明 ．
4.1 CP(
条件付き確率
)
モデ
CP 最 単純 あ ，複数 評価対象を
独立 評価 評価方法 あ ．ABC を例
説明 ．選択 索点 i い ，平均 あ
合を選択し改善 いう 結果 得 時， 索点 i 平
均 合 評価 ． ，平均 合
評価 い 平均 合 評価 影響
を与え い．CP 表1 次 式 定義 .
CP(平均 あ |� ) =
+
(8)
4.2 LS-VR
モデ
LS-VR Loosely Symmetric model(以 LS)を改良
し あ [ 12][ 13]．LS 人 非論理的
を 記述 対称性 相互排他性 を 緩 満
あ ，意思決定課題 あ 2本腕 ン ッ 問題 対
し 優 成績を持 示 い [篠原 07]．通常 LS
選択肢 対 振 舞い 変化 境界線 あ 参照点
0.5 固定 可変 い． 対し LS-VR
参照点 R を 入 ，参照点
R を任意 変更しオン ン 更新 を可能 し
あ ． ，恵 環 境 早期 索を 辞 し う
や，貧 しい環 境 永遠 索し続 を 回 避 ． ，
割引率γを実装し情報を 適度 忘 ，定常，非定常
関わ 高い成績を示し い ．LS-VR 表1 次
式 定義 ．
LSVR(平均 あ |� ) = + � � �+ � + + � � � �+ �+ � � �+ �
�= argmax � + ,
�= argmax � + ,
�= argmin � + ,
�= argmin � + , � = � −
(9)
5.
数値実験
数値実験 し ，4 種類 代表的 ベン 関数
限制約条件付 最適化問題 を用い ABC 比
較をし，考察を 行う ．初期設定 し プ回数 R=10000 ，
索点 数 N=20 ，偵察蜂 制御 limit=100 設定し，
価値関数 関し CP を用い 際 LS-VR を
用い 際 ュ ョンを行 LS-VR 参照点R
1.0 固定し 理 し 今回 処理 問題
オ フ ， 付 索能力 要 あ
あ ． 変化 環境 満足 い 振 舞いを 要視
， 索効率 良 必要 ． ，4 種類 ベン
関数 要素数 次元 をD=10 ，50 し 実験し
． ， プ 回 数 10000 最 値 推 移を 求 ，
200回 平均を結果 し ．
図3. 10次元Sphere関数
図4. 50次元Sphere関数
図5. 10次元Rosenbrock関数
図6. 50次元Rosenbrock関数
図7. 10次元Griewank関数
1E-16 1E-14 1E-12 1E-10 1E-08 0.000001 0.0001 0.01 1 100 10000
1 101 201 301 401 501 601 701
F(
x
)
ープ回数r
D=10 Sphere関数 実験結果
10次元-ABC
10次元EVS-LSVR
10次元EVS_CP
1E-15 1E-13 1E-11 1E-09 0.0000001 0.00001 0.001 0.1 10 1000 100000
1 501 1001 1501 2001 2501 3001
F(
x
)
ープ回数r
D=50 Sphere関数 実験結果
50次元ABC
50次元EVS-LSVR
50次元EVS-CP
1.00E-01 1.00E+00 1.00E+01 1.00E+02 1.00E+03 1.00E+04 1.00E+05 1.00E+06 1.00E+07 1.00E+08 1 5 0 1 1 0 0 1 1 5 0 1 2 0 0 1 2 5 0 1 3 0 0 1 3 5 0 1 4 0 0 1 4 5 0 1 5 0 0 1 5 5 0 1 6 0 0 1 6 5 0 1 7 0 0 1 7 5 0 1 8 0 0 1 8 5 0 1 9 0 0 1 9 5 0 1 F( x )
ープ回数r
D=10 Rosenbrock関数 実験結果
10次元-ABC
10次元EVS-LSVR
10次元EVS_CP
1.00E-01 1.00E+00 1.00E+01 1.00E+02 1.00E+03 1.00E+04 1.00E+05 1.00E+06 1.00E+07 1.00E+08 1.00E+09 1 5 0 1 1 0 0 1 1 5 0 1 2 0 0 1 2 5 0 1 3 0 0 1 3 5 0 1 4 0 0 1 4 5 0 1 5 0 0 1 5 5 0 1 6 0 0 1 6 5 0 1 7 0 0 1 7 5 0 1 8 0 0 1 8 5 0 1 9 0 0 1 9 5 0 1 F( x )
ープ回数r
D=50 Rosenbrock関数 実験結果
50次元ABC
50次元EVS-LSVR
50次元EVS-CP
1.00E-16 1.00E-14 1.00E-12 1.00E-10 1.00E-08 1.00E-06 1.00E-04 1.00E-02 1.00E+00 1.00E+02
1 101 201 301 401 501 601 701 801 901
F(
x
)
ープ回数r
D=10 Griewank関数 実験結果
10次元-ABC
10次元EVS-LSVR
The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
- 4 -
図8. 50次元Griewank関数
図9. 10次元Rastrigin関数
図10. 50次元Rastrigin関数
6.
考察
Sphere関数 関し ，10次元，50次元 い 各 プ
回数 従来 ABC 良い最 値 索 成功し ，
最 値 変化 大 い を確 し ．
Rosenbrock 関 数 関 し ，大 変 化 を 期 待 要
素を選択し 改善を行う EVS-ABC 比較し 大
差を 現 ． ，ABC 目的関
数値 変数を独立的 改善し い あ 考え ．
Griewank関数 関し ，Sphere 関数 同様 結果 得
．
Rastrigin関数 関し ，従来 ABC 大域的 索
成功 い いう結果 得 ．6000 ップ 従来
ABC 早い段 局所化し し い
，価値関数 柔軟 局所化を 抜 出し い 確
． ，10次元，50次元 い 従来 ABC 解
局所化を防 ， 良い値を 索 成功し い
を確 し ．
CP 大域的 索 失敗し い を 確 し ．
CP 表 1 示 情報を独立的 評価し
い ， 今回 う 最適化 激しい環境 変化 対
応 い い 考え ． 対し LS-VR
フ ン を1.0 固定 ，変化 環
境 中 満足 効率的 索を 行い，環境 変化
対応し 索 成功し い を確 し ．今回 ABC
環境 ，動的 効率的 索 要 点
あ ． う 環境 ，適合度 変化 を 結果 し 用い
従来 一様乱数を 用い 選択 比 ，価値関数 し
LS-VR を用い EVS ほう ， 効率的
索を行え い を確 し ．
7.
結論
本研究 ， ABC い 処理 結果を経験
し 利用し い 追従蜂フェ 適合度 あ
，一様乱数 影響 大 い いう問題点 着目し ．
，一様乱数を用い 次元 選択 適合度 変化 を
考慮し い い部 ，適合度 変化 を行動 結果 し 得
大 変化 を 期待 要素を 選択 要素価値選
択 EVS を 提案し ．EVS ， 改 善 行動
得 離散的 結果を 用い ， 価値関数 索
点 要素 価値を予測 を 目的 し ． し ，従
来 ABC EVS を4種類 代表的 ベン
関数 比較し ． 結果，最 値 推移 ，
EVS 従来 ABC 大 変化
改 善を 行 え を 確 し ， 変化 落 い 部 従
来 性能 保 持 し い を 示 し ． 今 回 提案 手法 ，
改善処理 式 変更 一 い ． 解 更新
次元 選択 順序 価値 関数を 用 い 性能 向 を
得 ， ，一様乱数を 用い い 差異 選
択を 効率化 考え ．
本研究 ，連続値 あ 適合度 変化 を ，改善し ，改
善し いう離散値 変換 行動 結果 し ．
し し，連続値を 価値関数 映 ば，
正確 推論を行う 考え ．
今 ，一様乱数 対 知識利用を用い 処理 効率
的 判断を 行う 方法や， 価値 関数 を 計算 際 計 算 考
察 を行う必要 あ 考え ．
参考文献
[Karaboga 05]Karaboga D.(2005):n Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR-6, Erciyes University, Engineering Faculty, Computer Engineering Department.
[宇谷 12]宇谷明秀, 西本 明, 山本尚生:高次元工学設計問題
最適化手法, 知能 情報 日本知能情報フ 学
会 Vol24,No3,pp.791-802(2012)
[ 12] 佑高橋達 :緩い対称性推論を用い 強化学習
,日 本 知 科 学 会 第 29 回 大 会 発 表 論 文
,2012 313-320.
[ 13] 佑, 高橋達 :価値推論 ュ し
規準学習 忘却，日本 知科学会第 30 回大会発表論文
，74-79，2013
[篠原 07]篠原修 , 口亮, 桂 浩一, 新 恒 . 因果性 基
信 念形 成 N本 腕 ン ッ 問題 適用,
人工知能学会論文 , Vol.22, No.1, pp.58-68, 2007.
[Kohno 12]Kohno Y., Takahashi, T. (2012): Loosely symmetric reasoning to cope with the speed-accuracy trade-off, In Proceedings of SCIS-ISIS 2012, Kobe, Japan, November 20--24, 2012, 1166-71.
[並木 13]並木尚也, 大用庫智, 高橋達 :知識利用 索 対
因果的直感 相対評価 処方箋的効果,JSAI 2013 予
稿 ,1L4-OS-24b-6in.
[西 11]西 健:時変関数 適応 ABC
修 正, 電 気 学 会 論 文 C 電 子 情 報 部 門
,Vol.132,No.4,pp.584-591
1.00E-15 1.00E-13 1.00E-11 1.00E-09 1.00E-07 1.00E-05 1.00E-03 1.00E-01 1.00E+01 1.00E+03
1 501 1001 1501 2001 2501 3001
F(
x
)
ープ回数r
D=50 Griewank関数 実験結果
50次元ABC
50次元EVS-LSVR
50次元EVS-CP
1E-18 1E-16 1E-14 1E-12 1E-10 1E-08 1E-06 0.0001 0.01 1 100
1 1001 2001 3001 4001
F(
x
)
ープ回数r
D=10 Rastrigin関数 実験結果
10次元-ABC
10次元EVS-LSVR
10次元EVS_CP
1E-09 1E-08 0.0000001 0.000001 0.00001 0.0001 0.001 0.01 0.1 1 10 100 1000
1
5
0
1
1
0
0
1
1
5
0
1
2
0
0
1
2
5
0
1
3
0
0
1
3
5
0
1
4
0
0
1
4
5
0
1
5
0
0
1
5
5
0
1
6
0
0
1
6
5
0
1
7
0
0
1
7
5
0
1
8
0
0
1
8
5
0
1
9
0
0
1
9
5
0
1
F(
x
)
ープ回数r
D=50 Rastrigin関数 実験結果
50次元ABC
50次元EVS-LSVR
