読者です 読者をやめる 読者になる 読者になる

ほろ酔い開発日誌

有意義な技術的Tipsを共有出来たら嬉しいです。Ruby、Railsが好きです。Web開発全般(Rails多め、フロント、サーバー、インフラ)、データ分析、機械学習あたりの記事が中心になる予定です。

群知能(Swarm Intelligence)の実装 (Java) - PSO・ABC-

大学の課題で群知能(Swarm Intelligence)の実装が課題に出て、PSO(Particle Swarm Intelligence) と ABC(Artificial Bee Colony) のアルゴリズムを実装することになりました。

そこで、コードの紹介(github)と参考になったものを載せておきます。

群知能(ぐんちのう、むれちのう、Swarm Intelligence, SI)は、分権化し自己組織化されたシステムの集合的ふるまいの研究に基づいた人工知能技術である。( 群知能 -Wikipedia- )

群知能はたくさんのエージェントを用意してそれぞれが各々相互作用を起こしながら最適解を探し出す人工知能技術です。それぞれのエージェントを中央管理するわけではなく、それぞれが自発的に行動し、結果的に全体としての創発をもたらすところが特徴にあります。

群知能のアルゴリズムは自然界からヒントを得たものが多く、PSOは動物の群れをヒントにしたアルゴリズムですし、ABCは蜂の採餌行動をヒントにしたアルゴリズムになります。

アルゴリズム

まず実装したコードは以下です。PSOとABCの2つを実装してあります。

github.com

以下の関数の最小化問題を解けるようになっています。 (もちろん、自分で定義すれば他の関数でも可)

  • shpere関数 定義域 [-5.0, 5.0]
  • rastrigin関数 定義域 [-5.0, 5.0]
  • rosenbrock関数 定義域 [-5.0, 5.0]
  • griewank関数 定義域 [-600.0, 600.0]
  • alpine関数 定義域 [-10.0, 10.0]
  • 2n-minima関数 定義域 [-5.0, 5.0]

Javaの実装になっています。本当はPythonでやりたかったのですが(それがダメでもRubyがいい)、JavaC言語C++のどれかの制限があったので、Javaにしました。C言語はあまりちゃんとしたコードは書いてこなかったのでやめました。(勉強しておきます。)

PSO

粒子群最適化(りゅうしぐんさいてきか、Particle Swarm Optimization、PSO)とは、群知能の一種。 昆虫の大群や魚群において、一匹がよさそうな経路を発見すると(すなわち、食料を発見したとか安全であるという場合)、群れの残りはどこにいても素早くそれに倣うことができる。( 粒子群最適化 -Wikipedia- )

まず、アルゴリズムなのですがWikipediaで十分わかりました。

粒子群最適化 - Wikipedia

具体的なコードとしてPythonで実装してある下記もわかりやすく参考になりました。Wikipeiaのアルゴリズムを見たあとにこちらを見るとすっきりします。

qiita.com

下記はN-Queens問題をPSOで解いたコードです。アルゴリズム自体は上記の2つを参考にしたのですが、Javaの書き方として参考になりました。

github.com

ABC

In computer science and operations research, the artificial bee colony algorithm (ABC) is an optimization algorithm based on the intelligent foraging behaviour of honey bee swarm, proposed by Karaboga in 2005. ( Artificial bee colony algorithm -Wikipedia- )

↑ ABCアルゴリズムは蜂の採餌行為をもとにした最適化アルゴリズムです、ということですね。(英語版しかなかった)

アルゴリズムはまずWikipediaを参考にしました。

Artificial bee colony algorithm - Wikipedia

Wikipediaだけではちょっと分かりづらかったのですが下記の2つが分かりやすかったです。

Step by Step Procedure of ABC

研究/2012-03-09 - Kondo's Page

下記はN-Queens問題をABCで解いたコードです。Javaの書き方も参考になりましたし、アルゴリズムも分かりやすかったです。

github.com

終わりに

他の講義の課題でカッコウアルゴリズムやホタルアルゴリズムなども調べたのですが、たくさんのアルゴリズムがあるのですね。自然界から発想を得てアルゴリズムにおこすところはディープラーニングも同じで面白さを感じます。 アルゴリズムの発想が詰まったら生命に戻って考える必要があると教授がおっしゃっていたのを思い出しました。