第三回 面白アルゴリズム紹介(コウモリアルゴリズム編)
面白アルゴリズム第3弾。コウモリの超音波（エコーロケーション）に着想を得たBat AlgorithmをPythonで実装。Wordleを題材に、遺伝的アルゴリズムやABCとの違いを踏まえて解説。
- 技術
みなさん こんにちは！ せしょうです！
「面白アルゴリズム」シリーズも、いよいよ第三弾になりました。
今回ご紹介するのは、夜空を飛び回るコウモリの 超音波（エコーロケーション） をヒントに作られた、コウモリアルゴリズム（Bat Algorithm: BA）です！ 第一回の遺伝的アルゴリズム(GA)編、第二回の人工蜂コロニーアルゴリズム(ABC)編をまだ見ていないよ、という方はぜひそちらの記事もご覧になってください。今回も前回同様、 Wordle を題材として実コードと一緒に解いていきます。
コウモリアルゴリズム (Bat Algorithm) とは？
コウモリアルゴリズム（Bat Algorithm: BA）は、2010年に Xin-She Yang 氏によって提案された比較的新しいメタヒューリスティックです。コウモリは目があまり見えない代わりに、口や鼻から超音波を発して、その反響（エコー）で獲物までの距離や方向を見極めます。
これを「エコーロケーション」と呼びます。
BAでは、群れの各コウモリが「飛びながら超音波を発する」という挙動を、以下の5つの値で表します。
- 位置 xi：そのコウモリが今いる場所（＝今の解候補）
- 速度 vi：次にどっちに、どれくらい動くか
- 周波数 fi：エコーロケーションのパルスの音域。速度更新時の「ベスト解への引力の強さ」を決める係数として使われます
- パルス発射率 ri：単位時間あたりの超音波の発射回数。獲物に近づくほど大きくなる
- 音量 Ai：超音波の音量。獲物に近づくほど小さくなる（こっそり近づく）
「遠くにいるうちは大きな声で広くサーチして、獲物に近づいてきたら音を小さく・回数を多くしてピンポイント探索する」という、コウモリの賢い狩りの戦略をそのままアルゴリズム化したのが Bat Algorithm です。
GAやABCと何が違うの？
ここまで紹介してきた3つのアルゴリズムは、どれも「生物にヒントを得た最適化手法」ですが、得意とする戦略がそれぞれ違います。違いを表にすると、次のような感じです。
|
観点 |
GA |
ABC |
Bat Algorithm |
|
発想の元 |
生物の進化（自然淘汰） |
ミツバチの採餌行動 |
コウモリのエコーロケーション |
|
世代の進め方 |
交叉と突然変異で次世代を作る |
働き蜂・傍観蜂・偵察蜂の分業 |
各コウモリが自分の音量・パルス率を動的に調整しながら飛ぶ |
|
多様性の確保 |
突然変異（確率で常時発生） |
偵察蜂（停滞検知で発動） |
周波数を毎ステップランダム化＋音量で受理確率を制御 |
|
探索 ⇔ 活用 |
交叉率・突然変異率で人為的に調整 |
正と負のフィードバックで自己組織化 |
パルス発射率が上がり音量が下がることで自動的に「活用寄り」へ移行 |
|
個体の記憶 |
遺伝子のみ（直近の経験は持たない） |
trials（停滞カウンタ）を持つ |
速度・音量・パルス率という「内部状態」を持つ |
特に Bat Algorithm の特徴的なところは、コウモリ一匹一匹が「自分の音量とパルス発射率」という内部状態を持っていて、その値が探索の進捗に応じて自動的に書き換わっていく、という点です。
GAは「集団としてゆっくり進化していく」、ABCは「コロニーで役割分担する」、Bat Algorithmは「個体それぞれが学習しながら集団で攻めていく」——という感じで、同じ群知能でも世代観・時間感覚がけっこう違うのが面白いところです。
今回使用する題材「Wordle」の簡単な説明
今回も前回までと同じく、Wordleのような単語推測ゲームを題材にします。
- お題となる単語は8文字
- 制限ターンは2000世代
- 解はアルファベットの大小文字・記号（ASCII印字可能文字）で構成
今回の目的：「Wordleっぽいもの」の最良解を導出するぞ
今回のBat Algorithmで解かせたいお題は、おなじみの「Gluegent」です。条件は以下の通りです。
- お題となる単語：Gluegent（8文字）
- コウモリの数：30匹
- 世代交代：2000回
- 周波数 fi ∈ [0.0, 2.0]
- 初期パルス発射率 r0 = 0.5
- 初期音量 A0 = 1.0
- 音量減衰係数 α = 0.9
- パルス発射率収束係数 γ = 0.9
評価関数（適合度）は前回のABC編と揃えて、
- 正しい文字が正しい位置：パーフェクトマッチ ＋2点
- 正しい文字だが位置が違う：部分一致 ＋1点
Fitness = (パーフェクトマッチ数 × 2) + (部分一致数 × 1) を最大化することが目標です。「Gluegent」が完成すると 2×8 = 16点 が得られます。
BAのアルゴリズム（もっと詳しく！）
BAの1ステップは、ざっくり次の流れで進みます。
- ① 周波数 fi をランダムに決める
- ② 速度 vi と位置 xi を更新する（大域探索）
- ③ パルス発射率 ri に応じて、ベスト解の近傍をランダムウォーク（局所探索）
- ④ 新しい位置の評価値が良くて、かつ「音量 Ai に比例する確率」を満たしたら採用
- ⑤ 採用されたら、その個体の音量を下げ、パルス発射率を上げる
① 周波数と速度・位置の更新（大域探索）
まず、各コウモリの周波数 fi を [fmin, fmax] の範囲でランダムに決め直します。
β を一様乱数 ∈ [0, 1] として、
fi = fmin + (fmax − fmin) × β
続いて速度と位置を、現在のベスト位置 x* を引きつけ先として更新します。
vi(t+1) = vi(t) + (xi(t) − x*) × fi
xi(t+1) = xi(t) + vi(t+1)
ポイントは「fi が大きいコウモリほど、ベスト解に向かう力が強い」「fi はステップごとに振り直される」ことです。これによって、集団のなかにベストに突進する個体とじわっと動く個体が混在し、自然に多様性が保たれます。
各コウモリの速度ベクトル：周波数fiが大きいほどベスト解への引力が強い
図: 周波数fiが大きいコウモリほど、ベスト解x*への引き寄せが強い。fiはステップごとに振り直されるため、群れの中に派手に動く個体と慎重に動く個体が常に存在する
実装コードはこちらです。
# 周波数を毎世代ランダムに決め直す
beta = np.random.rand()
bat.frequency = self.freq_min + (self.freq_max - self.freq_min) * beta
# 速度更新：ベスト解 self.best_position に引き寄せられる
bat.velocity = bat.velocity + (bat.position - self.best_position) * bat.frequency
# 位置更新：文字コード空間を移動する
new_position = bat.position + bat.velocity
new_position = np.clip(new_position, 32, 126)【補足】原典 Yang (2010) の擬似コードでは、このあとに「ランダムに飛び回ってもう一度新しい解を生成する」というステップ（Generate a new solution by flying randomly）が入りますが、後続の局所探索とほぼ役割が重複するため、今回の実装では省略しています。
② パルス発射率による局所探索
ここがBAらしさのキモの一つです。各コウモリは「乱数 > pulse_rate」のときだけ、ベスト解の近傍を細かく探りに行きます。
現実のコウモリは、獲物にロックオンするとパルス発射率を上げて精度を高めます。アルゴリズム上もそれを真似て、後半になるほど局所探索の発動確率が高くなるよう pulse_rate を増加させていきます。
原典の Yang (2010) では、局所探索は次のような連続的なランダムウォークで定義されています。
x_new = x_best + ε × A^t
ε は一様乱数 ∈ [-1, 1] のベクトル、A^t は現時点での全コウモリの平均音量。「ベスト解のすべての座標に、平均音量に比例した小さなノイズを加える」というイメージで、本来は連続最適化向けの式です。
【補足】今回はWordleが離散な文字列問題なので、上の式をそのまま使うと「文字コードがうろうろするだけで意味のある単語にならない」状態に陥ります（実際、最初に試した連続版では停滞しました）。そこで以下のように離散版に書き換えています。
- ベース位置を「ベスト解」にコピーする
- 音量 A が大きいうちは、複数文字をランダムに置き換える（大胆に探す）
- 音量 A が小さくなるほど、置き換える文字数が少なくなる（細かく詰める）
これによって、「最初は派手に攻めて、終盤はピンポイントで仕上げる」という挙動が自然に生まれます。連続版の「歩幅」が、離散版では「書き換える文字数」に置き換わっているイメージです。
if np.random.rand() > bat.pulse_rate:
new_position = self.best_position.copy()
# 音量に比例した文字数だけランダム置換
num_changes = max(1, int(round(avg_loudness * self.target_len * 0.4)))
indices = np.random.choice(self.target_len, num_changes, replace=False)
for idx in indices:
new_position[idx] = np.random.randint(32, 127)③ 音量による受理判定 ＆ 内部状態の自己更新
Bat Algorithmでは、新しい位置候補が見つかってもいきなり採用するわけではありません。「より良い解で、かつ確率 Ai を超えたら採用」という二重条件を通ります。
if new_fitness > bat.fitness and np.random.rand() < bat.loudness:
bat.position = new_position
bat.fitness = new_fitness
# 獲物に近づいたので、音量を下げ、パルス発射率を上げる
bat.loudness = self.alpha * bat.loudness
bat.pulse_rate = self.initial_pulse_rate * (1 - np.exp(-self.gamma * t))採用条件に「確率 Ai」が入っているのがミソです。序盤は Ai が大きいのでほとんど採用されますが、終盤になると Ai が小さくなり、「よっぽど良い改善でないと採用されない」ようになります。
【補足】受理判定の比較対象には2つの流派があります。原典 Yang (2010) の擬似コードでは「新解 vs グローバルベスト x*（f(x_new) < f(x*)）」と比較しますが、Fisterら (2014) 以降の解説では「新解 vs そのコウモリ自身の現在解」と比較する方が個体ベースの群れアルゴリズムとして自然、とされています。今回の実装は後者の流派を採用しています。
そして採用される度に、
- Ai ← α × Ai （音量を少しずつ下げて、慎重モードへ）
- ri ← r0 × (1 − exp(−γ・t)) （パルス発射率を上げて、局所探索の頻度を増やす）
という更新が走るため、コウモリは経験を積むほど「派手な探索 → 精密な活用」へ自動的にシフトしていきます。これがBAの一番ユニークなところで、人為的に「世代の何%で交叉率を下げる」みたいな調整をしなくても、勝手にスケジューリングされるイメージです。
GAの突然変異・ABCの偵察蜂との比較
「ベスト解の周りをランダムに探る」「内部状態に応じて挙動が変わる」というだけを聞くと、第一弾の突然変異や、第二弾の偵察蜂と似ているように感じるかもしれません。ただ、よく見比べると役割の哲学が違います。
- GAの突然変異：低確率で常に発生する予防的な多様性確保（個体の内部状態には依存しない）
- ABCの偵察蜂：「stagnation（停滞）が limit 回続いた」という治療的なトリガで起動
- BAの局所探索＋音量受理：「個体ごとの音量・パルス発射率」という連続値が、探索→活用の比率を自己組織的に滑らかに切り替える
ざっくり言うと、GAは「集団全体に常に少しの揺らぎを撒く」、ABCは「行き詰まったコにのみリセットをかける」、BAは「個体それぞれが連続的に集中力を上げ下げする」という対比です。同じ探索と活用のバランスという課題でも、設計思想が全然違っていて面白いですよね。
実装コードと結果
上記のBat Algorithmを「Gluegent」問題で実行したところ、おおよそ 数百〜1000世代 で正解にたどり着きました。 5回試行した一例は以下の通りです。
- 試行1：2000世代まで到達できず（解：Glueegnt / 適合度 14点）
- 試行2：761世代で正解
- 試行3：1017世代で正解
- 試行4：404世代で正解
- 試行5：681世代で正解
5回中4回で「Gluegent」を発見、収束した試行の平均は約 715世代 でした。
一回だけ局所解（Gueglent：文字の中身は正解だが順番が一部入れ替わっている）に捕まってしまっています。BAは音量 A が小さくなるほど受理確率も下がるため、「正解直前の停滞」から脱出しづらいケースもあります。GA編・ABC編でも触れた局所解の脱出は、BAでも依然として工夫しがいのあるテーマです。
コウモリたちの動きを見てみよう！（2次元での可視化）
アルゴリズムの動きをより直感的に理解するために、Wordleではなく簡単な2次元の宝探し問題に切り替えて、コウモリたちの飛び方を観察してみましょう。マップ上にぼんやり広がる黄色いエリアは「適合度の地形」で、明るいほどスコアが高い場所です。中央の★が獲物（最適解）。25匹のコウモリ（紫）と、現時点でのグローバルベスト（緑）が、世代を追うごとにどう動くかを見ていきます。
「点の大きさ」=「そのコウモリの音量 Ai」を表しています。音量が大きいほど派手に動き、小さくなるほどピンポイント探索になっていきます。また、その世代で「局所探索を行ったコウモリ」はオレンジで描かれています。
図1：BAの3つのフェーズ。 初期はランダムに散らばり、徐々にベスト解に引き寄せられ、最終的に獲物周辺で音量が下がって収束する。
3枚並べてみると、
- 初期状態：群れがランダムに散らばっており、音量も最大（点が大きい）。各コウモリの適合度はバラバラ。
- 中盤：オレンジ色（局所探索中）のコウモリが増え、ベスト解 ／ 獲物 のまわりに集まりはじめる。
- 終盤：ほぼ全員が獲物（★）のすぐ近くに集まり、音量が小さく（点が小さく）なる＝慎重モード。
この「最初は派手に攻めて、終盤はピンポイントで仕上げる」という挙動は、人為的に外からスケジュールしたものではなく、各コウモリが自分の音量 A とパルス発射率 r を採用ごとに勝手に更新した結果として生まれます。これがBAの 自己組織化 の面白いところです。
図2：内部状態の推移。 平均音量 A は単調に減り、平均パルス率 r は徐々に上がる。これにより自動的に「探索 → 活用」のシフトが起きる。
数字で追ってみましょう。平均音量 A は世代を追うごとに 1.0 → 0.7 まで滑らかに減少し、平均パルス発射率 r は 0 から徐々に上がって 0.5 に漸近します。一方、最良適合度はおよそ50世代で 1.0 にほぼ到達。「A が落ちながら r が上がる時間帯に、ちょうど適合度が一気に伸びる」のがポイントで、BAの 音量による受理確率の制御 がうまく効いているのが見て取れます。
補足：今回の実装と原典BAとの違いまとめ
ここまでの説明で都度ふれてきましたが、今回の実装は「Yang (2010) の原典BAそのもの」ではなく、Wordle（離散文字列問題）に合わせて一部書き換えた離散版BAになっています。読者のみなさんが誤解しないように、原典との差分をまとめておきます。
|
項目 |
原典 Yang (2010) |
今回の実装 |
|
周波数・速度・大域位置の更新 |
fi = fmin + (fmax−fmin)·β / vi+= (xi−x*)·fi / xi+= vi |
原典と同じ（変更なし） |
|
局所探索の式 |
x_new = x_best + ε × A^t （連続的なランダムウォーク） |
ベスト解の k 文字をランダムに置換（k は平均音量に比例） |
|
受理判定の比較対象 |
グローバルベスト x* と比較 |
そのコウモリ自身の現在解と比較（Fisterら2014流派） |
|
ランダム飛行ステップ |
擬似コードに記載あり（Generate a new solution by flying randomly） |
局所探索と役割が重複するため省略 |
|
音量・パルス発射率の更新 |
Ai+1 = α·Ai / ri+1 = ri(0)·(1−exp(−γt)) |
原典と同じ（変更なし） |
要点としては、「大域探索（周波数・速度・位置の式）と内部状態の自己更新（音量・パルス発射率）は原典通り。一方で、「離散文字列問題に合わせて局所探索と受理判定の比較対象だけ書き換えている」と理解いただけるとピッタリです。
もし原典通りの連続最適化問題（たとえば Rastrigin関数や Sphere関数の最小化）で BA を試したい場合は、局所探索を上の x_new = x_best + ε × A^t の式に戻し、受理判定を f(x_new) < f(x*) に変更すればOKです。
考察と補足
今回の実装で意識したポイントは、大きく次の3つです。
- ① 問題に合わせた局所探索：もともとBAは連続最適化向けのアルゴリズムなので、文字列問題で素直に xi = xi + vi をやるとなんかぼんやり数字が動くだけになりがちです。今回は局所探索で「ベスト解を雛形にして音量に応じた数の文字だけ置き換える」と離散化することで、現実的な探索を可能にしました。
- ② 音量を歩幅として使う：BAでは音量 A はもともと受理確率の役割ですが、「音量が大きい＝まだ獲物まで遠い＝大胆に探す」という発想で、局所探索の置換文字数にも反映させています。これにより、序盤は派手に、終盤は慎重に、という挙動が自然になります。
- ③ パルス発射率の動的更新：t（世代）が進むほど ri が上がる仕組みを入れているので、終盤になるほど局所探索が頻発し、ピンポイントで仕上げに行く流れが生まれます。
ちなみに、BAは α・γ・fmin・fmax といったパラメータが多いので、「α を小さくしすぎると音量が一気に消えて停滞」「fmax を大きくしすぎると速度が暴れる」など、ハマりどころも多いアルゴリズムです。パラメータをちょっと変えるだけで挙動が様変わりするので、いじっていて飽きません。
発展形として、以下のような亜種も研究されています。
- Discrete Bat Algorithm：シグモイドで速度を確率に変換して、離散変数を扱う
- Chaotic Bat Algorithm：周波数や音量の更新にカオス写像を組み込み、停滞を防ぐ
- Binary Bat Algorithm：0/1の組合せ最適化問題（特徴選択など）に応用
「コウモリ × カオス」って字面だけでもう面白くないですか？
まとめ
今回は「面白アルゴリズム」第三弾として、コウモリアルゴリズム（Bat Algorithm）を紹介させていただきました。
GAが「世代を超えた進化」、ABCが「コロニーでの分業」だとすると、BAは「個体それぞれが、自分の音量とパルス発射率を成長させながら獲物を狙う」という、また少し違った世界観のアルゴリズムです。
周波数で大域探索の歩幅を変え、ベスト解に引き寄せられながらも、進捗に合わせて自動で慎重モードにシフトしていく——この自己組織化のしくみは、シンプルなコードで実現できる割にとても奥深いので、ぜひ手元の環境で動かしてみてほしいです。
Bat Algorithmも、GA・ABCと同じく実問題への応用例が多く、配送計画・スケジューリング・機械学習のハイパーパラメータ調整・ニューラルネットの最適化などで利用されています。アルゴリズムごとの「性格の違い」を知っておくと、解きたい問題に合わせて道具を選べるようになるので、ぜひ他のメタヒューリスティックにも興味を広げてみてください。
それでは、また次回の記事でお会いしましょう！
おまけ（BA実装部分の全体コード）
今回ブログ中で紹介したBat AlgorithmのフルコードをPythonで掲載します。numpyだけあれば動きます。
import numpy as np
from collections import Counter
class Bat:
"""
コウモリ1匹（探索エージェント）を表すクラス
- position : 現在の位置 (候補解：文字コードの配列)
- velocity : 速度ベクトル
- frequency: 周波数 fi (パルスの音域)
- pulse_rate: パルス発射率 ri ∈ [0, 1]
- loudness : 音量 Ai (獲物に近づくほど小さくなる)
"""
def __init__(self, dim):
self.position = np.random.randint(32, 127, dim).astype(float)
self.velocity = np.zeros(dim)
self.frequency = 0.0
self.pulse_rate = 0.5
self.loudness = 1.0
self.fitness = 0
class BatAlgorithm:
def __init__(self, target_word, num_bats=30, max_iterations=2000,
freq_min=0.0, freq_max=2.0,
alpha=0.9, gamma=0.9,
initial_pulse_rate=0.5, initial_loudness=1.0):
self.target_word = target_word
self.target_len = len(target_word)
self.num_bats = num_bats
self.max_iter = max_iterations
self.freq_min = freq_min
self.freq_max = freq_max
self.alpha = alpha
self.gamma = gamma
self.initial_pulse_rate = initial_pulse_rate
self.initial_loudness = initial_loudness
self.bats = [Bat(self.target_len) for _ in range(num_bats)]
for bat in self.bats:
bat.pulse_rate = initial_pulse_rate
bat.loudness = initial_loudness
bat.fitness = self._fitness(bat.position)
best = max(self.bats, key=lambda b: b.fitness)
self.best_position = best.position.copy()
self.best_fitness = best.fitness
def _fitness(self, position):
candidate = self._decode(position)
target = self.target_word
perfect = 0
unmatched_t = list(target)
unmatched_c = list(candidate)
for i in range(len(target) - 1, -1, -1):
if candidate[i] == target[i]:
perfect += 1
unmatched_t.pop(i)
unmatched_c.pop(i)
partial = sum((Counter(unmatched_t) & Counter(unmatched_c)).values())
return perfect * 2 + partial
def _decode(self, position):
return "".join(chr(int(np.clip(c, 32, 126))) for c in position)
def run(self, verbose=True):
max_fitness = self.target_len * 2
for t in range(self.max_iter):
avg_loudness = max(np.mean([b.loudness for b in self.bats]), 0.05)
for bat in self.bats:
# 1) 周波数を更新
beta = np.random.rand()
bat.frequency = self.freq_min + (self.freq_max - self.freq_min) * beta
# 2) 速度・位置を更新（大域探索）
bat.velocity = bat.velocity + (bat.position - self.best_position) * bat.frequency
new_position = np.clip(bat.position + bat.velocity, 32, 126)
# 3) パルス発射率を超えたら局所探索
if np.random.rand() > bat.pulse_rate:
new_position = self.best_position.copy()
num_changes = max(1, int(round(avg_loudness * self.target_len * 0.4)))
indices = np.random.choice(self.target_len, num_changes, replace=False)
for idx in indices:
new_position[idx] = np.random.randint(32, 127)
# 4) 評価
new_fitness = self._fitness(new_position)
# 5) 受理：良くなって、かつ音量に比例した確率で
if new_fitness > bat.fitness and np.random.rand() < bat.loudness:
bat.position = new_position
bat.fitness = new_fitness
bat.loudness = self.alpha * bat.loudness
bat.pulse_rate = self.initial_pulse_rate * (1 - np.exp(-self.gamma * t))
# 6) 群れ全体のベスト更新
if new_fitness > self.best_fitness:
self.best_position = new_position.copy()
self.best_fitness = new_fitness
if verbose and (t % 50 == 0 or self.best_fitness == max_fitness):
print(f"Gen {t+1:4d}: Best Fitness = {self.best_fitness}/{max_fitness}, "
f"Best Word = {self._decode(self.best_position)}")
if self._decode(self.best_position) == self.target_word:
if verbose:
print(f"\nTarget found at generation {t+1}!")
return t + 1
return self.max_iter
if __name__ == '__main__':
TARGET = "Gluegent"
bat_algo = BatAlgorithm(target_word=TARGET, num_bats=30, max_iterations=2000)
bat_algo.run(verbose=True)
print("Final:", bat_algo._decode(bat_algo.best_position),
"fitness=", bat_algo.best_fitness)
