第二回 面白アルゴリズム紹介(人工蜂コロニーアルゴリズム)
- グルージェントフロー
みなさん こんにちは！ 今回は「面白アルゴリズム」シリーズ第二弾を紹介していきます。
今回ご紹介するのは、生物の知恵をアルゴリズムにした、人工蜂コロニーアルゴリズム（ABC）です！ 前回の「第一回 面白アルゴリズム紹介 (遺伝的アルゴリズム編)」をまだ見てないよという方はぜひ、こちらの記事もご覧になってください。 前回同様に、Wordleを題材として解いていきます。
人工蜂コロニーアルゴリズム (ABC) とは？
人工蜂コロニーアルゴリズム（ABC: Artificial Bee Colony）は、2005年にDerviş Karaboğa氏によって提案された、ミツバチの賢い採餌行動を模倣した探索・最適化アルゴリズムです 。GAが生物の進化をヒントにしたように、ABCはミツバチのコロニー全体が協力して、最も効率良く蜜を集める習性をアルゴリズムに応用しています。
ABCの世界では、「蜜源の位置」が問題の「解候補」を、「蜜の量」がその解の「良さ（適合度）」を表します 。そして、コロニーは主に3種類の蜂で構成され、それぞれが重要な役割を担っています 。
- 働き蜂 (Employed Bees): 担当の蜜源を持っていて、その周辺を探索する蜂。
- 傍観蜂 (Onlooker Bees): 巣で待機し、働き蜂のダンス（情報）を見て、より良さそうな蜜源を手伝いに行く蜂。
- 偵察蜂 (Scout Bees): 担当していた蜜源が枯渇（解が改善しない）した場合、その場所を捨てて全く新しい蜜源を探しに行く蜂。
この3種類の蜂たちが、それぞれの役割をこなしながら情報を共有し、協力することで、コロニー全体として最適な蜜源（問題の最適解）を見つけ出すのです。
ABCの何が面白いの？何が凄いの？
私がABCを面白いと感じるのは、GAと同じく生物の習性をアルゴリズム化した点です。GAが世代を超えた「進化」を模倣したのに対し、ABCは一つのコロニー内での「情報共有」と「分業」による自己組織化を模倣しています 。
特に凄いのが、正のフィードバックと負のフィードバックの絶妙なバランスです 。
- 正のフィードバック: 傍観蜂が良い蜜源（良い解）に集まることで、有望なエリアの探索が加速します。これは「もっと掘り下げよう！（活用）」という動きです。
- 負のフィードバック: 偵察蜂が行き詰まった蜜源（局所解）を放棄することで、探索が停滞するのを防ぎます。これは「別の場所も探そう！（探索）」という動きです。
この2つの仕組みが自動的に働くことで、アルゴリズム全体が「活用」と「探索」のバランスを巧みにとりながら、賢く最適解に近づいていくのです。これぞまさに「集合知」ですね！
今回使用する題材「Wordle」の簡単な説明
今回の題材は、前回と同じく「Wordle」のような単語推測ゲームです。
- お題となる単語は8文字
- 制限ターンは500世代
- 解はアルファベットの大小文字で構成
今回の目的：「Wordleっぽいもの」の最良解を導出するぞ
今回のABCに解かせたいお題は「Gluegent」です。
より細かい条件は以下の通りです。
- お題となる単語: Gluegent
- 蜂の数: 30匹 (働き蜂15匹、傍観蜂15匹)
- 世代交代: 500回
- 評価 (適合度の算出): アルゴリズムに適切なヒントを与えるため、以下のような複合的な評価関数を設計します。
- 正しい文字が正しい位置にある場合（パーフェクトマッチ）：2点
- 正しい文字だが位置が違う場合（部分一致）：1点
この評価関数
Fitness = (パーフェクトマッチ数 × 2) + (部分一致数 × 1)
のスコアを最大化することが、今回の目的です。
ABCの３つの役割（もっと詳しく！）
さて、ここからが本題です。3種類の蜂たちが、具体的にどのように賢く振る舞っているのか、コードを交えて詳しく見ていきましょう！
働き蜂 (Employed Bees)
働き蜂 (Employed Bees)
働き蜂は、担当する蜜源（現在の解）の周辺を探索します。今回は、文字列問題に適したSwap（交換）演算子を使います。これは、現在の解の文字列からランダムに2文字を選んで、その位置を入れ替えることで新しい解候補を生成する方法です。これにより、意味のある近傍探索が可能になります。
傍観蜂 (Onlooker Bees)
傍観蜂は、働き蜂のダンスを見て有望な蜜源を選ぶまでは同じです。しかし、その後の探索方法を強化します。ただランダムに近傍を探すのではなく、コロニー全体で発見された最も良い解（g-best）を参考に、現在の解をg-best解に近づけるような探索を行います 。これにより、アルゴリズムの「活用」能力が大幅に向上し、局所解からの脱出が期待できます。
偵察蜂 (Scout Bees)
ある蜜源の改良が一定回数（limit）以上停滞すると、その蜜源は放棄されます 。担当していた働き蜂は偵察蜂となり、全く新しい場所をランダムに探しに行きます。この大胆なジャンプが、局所解からの脱出を可能にします。
偵察蜂 vs GAの突然変異：似ているようで、実は違う！
偵察蜂の役割は、GAの「突然変異」と似ていると感じるかもしれません。しかし、そのアプローチには哲学的な違いがあります。
- GAの突然変異: 低い確率で常に発生し続ける、いわば「予防的」な措置です 。
- ABCの偵察蜂: 「解が limit 回改善しなかった」という明確な停滞を検知してから発動する、「治療的」な措置です 。
この違いを理解すると、アルゴリズムの挙動がもっと面白く感じられると思います。
結果と考察
さて、このABCアルゴリズムを「Gluegent」問題で実行したところ、数回から数十回の試行で正解にたどり着くことができました。ABC君もGA君と同様、とても優秀です！
Gluegentが作成されるまでの流れ
動画: https://drive.google.com/file/d/1qA-OcsEQUYxTeu59cexGgaPSYLLSQu04/view?usp=sharing
今回の改良のポイントは2つです。
- 問題への適応: Swap演算子を導入したことで、蜂たちは無駄な探索をせず、意味のある文字列の組み合わせを探せるようになりました。これは、アルゴリズムを解きたい問題の性質に合わせることの重要性を示しています。
- 活用能力の強化: g-best解を傍観蜂の探索に組み込んだことで、コロニーは「ただ良い場所」に集まるだけでなく、「一番良い場所」を目指して協力できるようになりました。これにより、早期収束のリスクが減り、局所解から脱出する力が格段に上がりました 。
また、limitパラメータを少し下げることで、停滞した解をより早く見切り、新しい可能性を探す「探索」を促すことも、局所解脱出の一助となります。
補足：蜂たちの動きを見てみよう！（2次元での可視化）
アルゴリズムの動きをより直感的に理解するために、蜂たちに簡単な2次元の宝探し問題を解いてもらい、その様子をアニメーションで観察してみましょう。
以下のコードは、なだらかな山（ガウス関数）の頂上（一番蜜が濃い場所）を蜂たちが探す様子を描画します。
- 黄色い×が、目的地です。
- 青い点が、蜜源を探す探索蜂（働き蜂・追従蜂）です。
- 黄色い星が、今見つかっている中で一番良い場所です。
- ピンクの点が、新しい場所を探しに行った偵察蜂です。
世代が進むにつれて、青い点が山の頂上（黄色い×印）に集まっていく様子や、時々ピンクの偵察蜂が全く違う場所に出現する様子が見られるはずです。
最初の状態: 探索蜂が色んなところにいる
動画: https://drive.google.com/file/d/1PYZ8GH6GIffWSQQymFGB4kgt9gbM3WCJ/view?usp=sharing
まとめ
今回は「面白アルゴリズム」第二弾として、人工蜂コロニーアルゴリズム（ABC）を紹介させていただきました。
働き蜂と傍観蜂による「近傍探索」と、偵察蜂による「局所解の脱出」。この二つのバランスを自己組織的に取りながら最適解を探すABCの姿は、まさに自然界の叡智そのものです。
この記事で、ABCの奥深さに少しでも触れていただけたら嬉しいです。最適化問題は、配送計画からAIの学習まで、様々な分野で応用されています 。興味があれば、ぜひ他のアルゴリズムも調べてみてください。
それでは、また次回の記事でお会いしましょう！
おまけ(ABC実装部分のコード)
記事中で紹介した各フェーズを統合した、全体のPythonコードのサンプルです。
import numpy as np
from collections import Counter
class Individual:
"""
個体（解）を表すクラス
"""
def __init__(self, gene):
self.gene = gene
self.fitness = 0
def calculate_fitness(self, target_word_unicode):
"""
適合度を計算する。
- 正しい文字が正しい位置にある場合（パーフェクトマッチ）：+2点
- 正しい文字だが位置が違う場合（部分一致）：+1点
"""
target_word = "".join([chr(c) for c in target_word_unicode])
candidate_word = "".join([chr(int(c)) for c in self.gene])
perfect_matches = 0
# カウント用にコピーを作成
unmatched_target = list(target_word)
unmatched_candidate = list(candidate_word)
# 1. パーフェクトマッチを探し、部分一致の対象から除外する
# 後ろからループすることで、popによるインデックスのズレを防ぐ
for i in range(len(target_word) - 1, -1, -1):
if candidate_word[i] == target_word[i]:
perfect_matches += 1
unmatched_target.pop(i)
unmatched_candidate.pop(i)
# 2. 残りの文字で部分一致を探す
target_counts = Counter(unmatched_target)
candidate_counts = Counter(unmatched_candidate)
partial_matches = sum((target_counts & candidate_counts).values())
self.fitness = (perfect_matches * 2) + partial_matches
class ArtificialBeeColony:
"""
人工蜂コロニーアルゴリズムの本体
"""
def __init__(self, target_word, num_bees, limit, max_iterations):
self.target_word = target_word
self.target_len = len(target_word)
self.target_word_unicode = np.array([ord(c) for c in target_word])
self.num_employed_bees = num_bees // 2
self.num_onlooker_bees = num_bees // 2
self.limit = limit
self.max_iterations = max_iterations
self.solutions = []
self.trials = np.zeros(self.num_employed_bees)
self.best_solution = None
def _initialize(self):
"""
初期個体群を生成する
"""
for _ in range(self.num_employed_bees):
genes = np.random.randint(32, 127, self.target_len) # ASCII印字可能文字
solution = Individual(genes)
solution.calculate_fitness(self.target_word_unicode)
self.solutions.append(solution)
self.best_solution = max(self.solutions, key=lambda s: s.fitness)
def _create_neighbor_solution(self, current_solution):
"""
近傍解を生成する。新しい文字を導入する「突然変異」を追加。
- 80%の確率で、遺伝子の一つをランダムな文字に変化させる（突然変異）
- 20%の確率で、遺伝子内の2つの文字を入れ替える（スワップ）
"""
new_solution_genes = current_solution.gene.copy()
if np.random.rand() < 0.8: # 80%の確率で突然変異
idx_to_mutate = np.random.randint(0, self.target_len)
new_solution_genes[idx_to_mutate] = np.random.randint(32, 127)
else: # 20%の確率でスワップ
idx1, idx2 = np.random.choice(self.target_len, 2, replace=False)
new_solution_genes[idx1], new_solution_genes[idx2] = new_solution_genes[idx2], new_solution_genes[idx1]
new_solution = Individual(new_solution_genes)
new_solution.calculate_fitness(self.target_word_unicode)
return new_solution
def _create_gbest_guided_solution(self, current_solution, gbest_solution):
"""
g-best解の情報を利用して、より有望な近傍解を生成する。
- best解と異なる文字を、best解の文字に置き換えることで収束を促す。
"""
new_solution_genes = current_solution.gene.copy()
diff_indices = [i for i, (c1, c2) in enumerate(zip(new_solution_genes, gbest_solution.gene)) if c1 != c2]
if diff_indices:
idx_to_change = np.random.choice(diff_indices)
# best解の優れた遺伝子を直接コピーする
new_solution_genes[idx_to_change] = gbest_solution.gene[idx_to_change]
else:
# 稀に、完全に一致している場合でも突然変異を起こし、局所解からの脱出を試みる
idx_to_mutate = np.random.randint(0, self.target_len)
new_solution_genes[idx_to_mutate] = np.random.randint(32, 127)
new_solution = Individual(new_solution_genes)
new_solution.calculate_fitness(self.target_word_unicode)
return new_solution
def employed_bee_phase(self):
for i in range(self.num_employed_bees):
new_solution = self._create_neighbor_solution(self.solutions[i])
if new_solution.fitness > self.solutions[i].fitness:
self.solutions[i] = new_solution
self.trials[i] = 0
else:
self.trials[i] += 1
def onlooker_bee_phase(self):
fitness_values = np.array([s.fitness for s in self.solutions])
fitness_sum = np.sum(fitness_values)
if fitness_sum == 0:
selection_prob = np.ones(self.num_employed_bees) / self.num_employed_bees
else:
selection_prob = fitness_values / fitness_sum
for _ in range(self.num_onlooker_bees):
if np.isnan(selection_prob).any() or np.isinf(selection_prob).any() or selection_prob.sum() <= 0:
selected_index = np.random.choice(range(self.num_employed_bees))
else:
selection_prob /= selection_prob.sum()
selected_index = np.random.choice(range(self.num_employed_bees), p=selection_prob)
new_solution = self._create_gbest_guided_solution(self.solutions[selected_index], self.best_solution)
if new_solution.fitness > self.solutions[selected_index].fitness:
self.solutions[selected_index] = new_solution
self.trials[selected_index] = 0
else:
self.trials[selected_index] += 1
def scout_bee_phase(self):
for i in range(self.num_employed_bees):
if self.trials[i] > self.limit:
new_genes = np.random.randint(32, 127, self.target_len)
new_solution = Individual(new_genes)
new_solution.calculate_fitness(self.target_word_unicode)
self.solutions[i] = new_solution
self.trials[i] = 0
def run(self):
self._initialize()
max_possible_fitness = self.target_len * 2
for i in range(self.max_iterations):
self.employed_bee_phase()
self.onlooker_bee_phase()
self.scout_bee_phase()
current_best_in_population = max(self.solutions, key=lambda s: s.fitness)
if self.best_solution is None or current_best_in_population.fitness > self.best_solution.fitness:
self.best_solution = current_best_in_population
current_best_word = "".join([chr(int(c)) for c in self.best_solution.gene])
print(f"Generation {i+1}: Best Fitness = {self.best_solution.fitness}/{max_possible_fitness}, Best Word = {current_best_word}")
if self.best_solution.fitness == max_possible_fitness and "".join([chr(int(c)) for c in self.best_solution.gene]) == self.target_word:
print("\nTarget found!")
break
final_word = "".join([chr(int(c)) for c in self.best_solution.gene])
print(f"\nFinished. Best solution: {final_word} with fitness {self.best_solution.fitness}")
if __name__ == '__main__':
TARGET = "Gluegent"
BEE_COUNT = 100
LIMIT = 20
MAX_ITERATIONS = 2000 # 探索により多くの時間を与える
abc = ArtificialBeeColony(TARGET, BEE_COUNT, LIMIT, MAX_ITERATIONS)
abc.run()
ついでのおまけです。
ぼくたち開発者が、グルージェントフローの歴史を語っている記事を紹介します、よろしければご覧ください。
