スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ABCとかPSOとか:群知能タイプの最適化アルゴリズム

 最初のうちはちょっとはりきって書いてみるわけで。

 昨年ちょっと面倒な非線形のフィッティングをする必要があって、計算理論とかよく知らないから初歩的な最少二乗アルゴリズムでごり押しして解決しようとしていたときに採用してみたのがABC (Artificial Bee Colony) アルゴリズムでした。蜂が巣の前でダンスして蜜の場所を伝達する行動を基に作られたらしい?実装してみたら蜂関係なくね?って思ったけど。
 アルゴリズムの詳細などは mf.erciyes.edu.tr/abc/ あたりに投げますが、昔使ったPSO (Particle Swarm Optimization) も同時に実装して使ってみるとABCの方がかなり性能が高いと感じました(検証はしていないのであくまでも心証です)。まあ元々、高次元の探索空間においてPSOよりも優れているという評判を聞いて使ってみたものなので、評判通りだったわけです。
 もう一つ良かったのはPSOよりもかなり実装が楽だったこと。どちらのアルゴリズムも基本的な動作は同じで、
  1. 探索空間にいくつかの個体をランダムにバラまく(初期化)
  2. 各個体が、自分自身の移動履歴と、全個体の移動履歴の2つの情報を基に探索空間を移動する
  3. ランダム性を含みつつ、全体としてはスコアの高いところを目指して移動する
という感じの動作になっています。ポイントとなるのは3. の部分で、ここに各アルゴリズムの特色が出る感じでしょうか。移動にランダム要素を含ませるのは局所最適解にハマりにくくするのと、広域探索性能を上げるためだと思います。いかに少ない個体で効率よくかつ満遍なく探索できるかがキモですね。
 さて、PSOでは個体の移動方法として、各個体が速度(慣性もある)を持っているという設定になっています。この速度があるせいで探索空間の端にぶつかったときの処理をコードするのが面倒だった記憶があります(私は趣味程度のスクリプティングがほとんどであまりかっちりしたプログラミングは経験が浅いのです)。あと初期化処理で速度ベクトルをランダムに生成するためにN次元球体内一様乱数の生成アルゴリズムを使ったりとか。
一方ABCアルゴリズムでは各個体には速度のようなものはなく、ある個体の移動は、別の一個体の座標ベクトルのどれか1つの要素を取り込んだ新しい座標に飛ぶという方式です。イメージとしてはある個体がランダムに選んだ別の個体の方に、これまたランダムに選んだある座標軸と平行に移動する感じでしょうか。これだと座標ベクトルを1個更新するだけなのでものすご簡単です。簡単なのに高性能とはすばらしいアルゴリズムだ。
 ABCの方が高次元で優れているのは感覚的になんとなく理解できます。探索空間の次元が上がると、ランダム性を持たせたとしても速度ベクトルがハイスコアな座標に向きやすくなってしまうのでしょう(この辺私も漠然としたイメージしかなくて分かるような説明ができません)。ABCアルゴリズムは、参照先の個体はハイスコアの個体が選ばれやすくなってはいるものの、素直にその個体の方に向かうわけではなくある座標に平行にしか動きません。複雑になるので書きませんでしたが他にもランダム性を高めている仕組みがあり、コードを書いてみると乱数生成の回数がABCの方がずっと多いです。やはり高次元ではランダムな動きを増やしていくことが探索のポイントということなのでしょうか。

とりとめもなく書き殴ってしまいましたが、ABCアルゴリズムはなかなか良いと思ったよ、というお話です。
スポンサーサイト

テーマ : ひとりごとのようなもの
ジャンル : 日記

コメントの投稿

管理者にだけ表示を許可する

プロフィール

前世

Author:前世
Tipsとかてきとうに
趣味スクリプト書きだよ。
リグルが大好きだよ。
(元の生息地はここ)

Rユーザー
・Python/Javascript
・Applescriptもたまに書く

りぐる数
最新記事
月別アーカイブ
最新コメント
最新トラックバック
カテゴリ
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。