【FA】ホタルアルゴリズム(Firefly algorithm)とは？

かんたんな例

分かりやすく理解するために、ナップサック問題（Knapsack problem）という問題をホタルアルゴリズムで解いてみます。

ナップサック問題とは、ある一つのカバンがあって、その中に入れる荷物の組み合わせを探す問題です。

例えば、あるナップサックには100kgまで荷物が入るとします。

そして、荷物の種類はA、B、Cの３つあって、それぞれ10㎏、20kg、30kgだとします。

それぞれの荷物には得点があって、1つ運ぶごとに、Aは5点、Bは20点、Cは45点もらえるとします。

ABCそれぞれ何個入れてもいいとき、どの組み合わせでナップサックに入れれば、得点が一番高いでしょう。というのがナップサック問題となります。

一応同じ荷物は1つしか入れないといったバージョンもありますが、今回は何個でもokとします。

ホタルアルゴリズムの流れ

では、上のナップサック問題をホタルアルゴリズムで解いていきます。

ホタルアルゴリズムの流れとしては、次のような流れで進んでいきます。

初期化（initialization）

最初に、①ランダムに最初のホタルたちを作ります。そのホタル達はそれぞれ、ABCの荷物をそれぞれ何個入れるかという情報を持っています。

例えば3匹ホタルを作るとします。

今回は、上の3匹を作りました。

評価（evaluation）

次に②ホタルたちを評価していきます。ABCそれぞれ得点がわかっているので、ホタルそれぞれの合計得点を計算します。

このようになります。この点数をホタルの光の強さとします。

修正（modification）

そして③光の強いホタルに弱いホタルを近づけます。

ホタル3が一番光が強いので、ホタル１とホタル2をホタル3に近づけます。ホタル1のAを2つ減らして、Bを1つ増やします。

ホタル２はBを1つ増やしてAを2つ減らしましょう。

一番光が強いホタル３はランダムに動かします。今回はCを1つ増やして、Bを2つ減らしましょう。

一応ホタル1と2を比べると、1のほうが光が強いので、さらにホタル2のAを1つ減らして、Cを1つ増やします。

注意しなければいけないのは、修正するときに合計の重さが100kgを超えないようにするということです。

再評価（Re-evaluation）

そしてまた②ホタルたちを評価していきます。

さらに③ホタルの修正と続いていきます。大体50回くらいこれを繰り返します。

この例ではうまく全体の点数が上がっていることがわかります。

最終的には④一番良かった結果を表示すると続きます。

この例では、荷物の数も3つとすくなかったので、人間が考えたほうがすぐに答えが出ますが、これが荷物の数が100個などとなってくると、パソコンを使わないと計算することが難しいです。

そういった場合、ホタルの数も増やして、30匹程度にするのが多いです。

光の強いホタルにどれだけ近づけるか、一番光の強いホタルをどれだけランダムに変化させるかはいろいろ異なりますが、あまり変化させすぎないのが一般的です。

何に使える？

ナップサック問題のような組み合わせで答えが変わるような問題によく使用されます。かなり有名な方法でよく論文などでも使われます。

コンビニでどの商品をどれだけ仕入れるかも、組み合わせで利益が変わってくるので使うことができます。

どの商品をどの順番で運ぶかという配送問題というのもあるのですが、そういった順序を決めるような問題も利用することができ、かなり汎用性が高いです。

まとめ

簡単に内容をまとめると、ホタルアルゴリズムはホタルの光に引き付けられる習性を利用して問題を解く仕組みです。

最初にランダムに組み合わせを決めて、その組み合わせの点数を出します。点数に基づいて組み合わせを変えていき、もっといい答えを探していくのでした。

組み合わせや順序を決める問題に有効なアルゴリズムとなっています。似ているアルゴリズムに遺伝的アルゴリズムもあるので、気になる方はぜひ記事ご覧ください!

【GA】遺伝的アルゴリズム(Genetic algorithm)とは？

ぜひsnsフォローお願いします!記事更新の際すぐに見ることができます!