【2026年10月版】

索引と探す技術（第6回）― 局所探索と生物着想の手法

公開日: 2026/10/02
読了時間: 約 22分

第5回では、最適性や完全性を保証する探索を扱った。第6回は、その保証を手放し、使える解が早く見つかればよい場合の探索を扱う。

1. 古典的な局所探索

配達の順番を決める問題なら、いまの順番から二か所を入れ替えた順番のように、現在の解を少しだけ変えた候補がいくつも作れる。局所探索は、こうした候補(近傍)を作って評価し、そこへ移るかどうかを決めることを繰り返す手法で、手法ごとの違いは、近傍の作り方と受理の規則に現れる。良くなる候補だけを受け入れていると、近傍のどれに移っても悪くなる解(局所解)に行き着いたところで止まってしまう。焼きなまし法は、1983年にカークパトリック、ゲラット、ヴェッキが Science に発表した手法で、悪くなる候補も温度に応じた確率で受理し、温度を下げるにつれてその確率を小さくしていくことで、局所解から抜け出す。タブー探索はグローバーが1980年代に考案し、直近の解への再訪を短期の記憶で禁じる。遺伝的アルゴリズムはホランドが提案し、解の集団に選択、交叉、突然変異を繰り返す。

連続空間の問題では CMA-ES が代表的である。現在の中心の周りに候補をばらまいて評価し、成績の良かった候補がどの向きにどれだけ広がっていたかを覚えておき、次にばらまく範囲をその向きに伸ばしたり縮めたりする。解説では、探索の分布の共分散行列を逐次推定して分布を更新する手法と説明されている。伸ばす向きを問題から学ぶので、地形を斜めに傾けても評価値の目盛りを付け替えても振る舞いが変わりにくく、目的関数の単調な変換や空間の回転に影響されにくい。単純な二次関数では BFGS のほうがはるかに速い一方、CMA-ES は不連続、ノイズ、多峰性のある荒い問題に強い。

手法の優劣は、問題ごとに入れ替わる。書類棚から一枚を探す場面で、書類が置き場所と関係なくでたらめに散らばっていれば、どの順番で引き出しを開けても平均の手間は同じになる。ありうる問題をすべて同じ重みで並べて平均すると、ある問題で速い手法は別の問題で遅くなり、差が打ち消し合う。ウォルパートはノーフリーランチ定理を、問題が一様に分布するという前提の下で全アルゴリズムが等しく振る舞うことを示す定理だと整理している。Igel と Toussaint は、この結果が成り立つのは、関数の集合が定義域の置換で閉じている場合に限ると論じた。これは、ある問題の評価値を候補どうしの間でどう入れ替えても、入れ替えた後の問題がまた同じ集合に含まれているという条件である。たとえば道路網では近い交差点どうしの所要時間も近く、評価値を入れ替えるとこの性質が崩れてしまうので、道路網の問題の集合はこの条件から外れる。Igel と Toussaint も、実問題のクラスがこの条件を満たす可能性は低いと論じている。実問題には構造がある。手法をその構造に合わせて選び、調整することに意味が生まれるのは、そのためだ。

次章以降の手法は、アリやミツバチ、鳥の群れ、細菌、粘菌といった生物の行動に着想を得て名づけられている。生物の行動は発想のきっかけであり、手法の更新則は生物学の知見から導かれたものではない。手法の性能を支える根拠は、ベンチマークと実データでの評価にある。

2. 蟻コロニー最適化 ― 二重橋実験からの着想

蟻コロニー最適化(ACO)は、アリの採餌の実験とその数理モデルに着想を得ている。Goss らの二重橋実験では、巣と餌場を長さの違う二本の橋でつなぐ。たまたま短い橋を選んだアリが先に餌に着いて戻るため、短い橋にフェロモンが多く残り、選ばれやすくなる。第一の橋を選ぶ確率は、橋を通ったアリの数 m1、m2 を使って (m1+k)^h / ((m1+k)^h + (m2+k)^h) と表され、k≒20、h≒2 が実験によく合った。この式が、ACO の遷移確率の着想になった。

ドリゴらの Ant Systemでは、アリ k が都市 i から j へ移る確率が、フェロモン τ と問題固有の情報 η(距離の逆数)を使って τ^α · η^β に比例する。フェロモンは τ ← (1−ρ)τ + Σ Δτ で更新し、アリ k の巡回路の長さを L_k として、通った辺に 1/L_k を足す。1996年の論文の実験(Oliver30)では α=1、β=5、持続率0.5、Q=100 と設定しており、これらはその論文のテスト問題に合わせて決めた値である。論文自身も、問題に特化したアルゴリズムに負ける場合があると認めている。

Ant Colony Systemは、確率 q0 で最良の辺を貪欲に選び、通るたびにフェロモンを少し減らして同じ反復内の多様性を保ち、最良の巡回路の辺だけを大域的に更新する。Ant System との違いは、どの部品を変え、どの問題に合わせたかにある。

ACO は、二重橋実験の仕組みを着想にして作られた最適化の枠組みで、経路の長さを直接計算してフェロモンの量に反映し、蒸発も探索を制御するパラメータとして使う。Scholarpedia の解説も、ACO が実アリと関係のない要素を多く含む枠組みに育ったと述べている。

3. 粒子群最適化と人工蜂コロニー ― 群れの簡略化

粒子群最適化(PSO)は、ケネディとエバーハートが1995年に提案した。鳥や魚の群れのシミュレーションが出発点で、レイノルズの boids は、分離、整列、結合の三つの規則で群れの動きを作る。PSO の更新は、これを個体の過去最良 p と近傍の最良 l に引き寄せられる形へ簡略化したものである。標準的な形では、位置 x と速度 v を v ← ωv + φ1 a⊙(p − x) + φ2 b⊙(l − x)、x ← x + v と更新する(Camacho-Villalón らの定式化)。各粒子は、直前に進んでいた向きをいくらか保ちながら、自分がこれまでに見つけた最良の位置と、近くの仲間が見つけた最良の位置の両方へ引っぱられて動く。a、b は乱数のベクトルで、調整するのは慣性 ω と引力の係数 φ1、φ2、近傍の取り方になる。

人工蜂コロニー(ABC)は、カラボガが2005年に提案した。ミツバチの採餌を、雇用蜂、傍観蜂、偵察蜂の役割分担として模した手法である。雇用蜂が餌源の周りを探し、傍観蜂は品質に比例した確率で餌源を選ぶ。改善が一定の回数続けて止まった餌源は放棄され、偵察蜂が乱択で新しい解を作る。放棄の回数 limit が、探索と活用の釣り合いを決める。論文の評価に使われたのは Sphere、Rosenbrock、Rastrigin の三つの関数で、著者自身もテスト問題が非常に限られると書いている。

4. 個体の動き ― 走化性とレヴィフライト

大腸菌は、泳ぎながら感じる濃度の変化を手がかりに誘引物質へ近づく。Macnab と Koshlandは1972年に、誘引物質の濃度が急に下がると方向転換(タンブル)が増え、上がると協調した遊泳が増えることを示した。細菌は空間の勾配を、移動に伴う時間変化として感知している。これを探索の手続きに置き換えると、評価値を逐次比べて、良くなっていれば同じ向きに進み、悪くなれば向きを変えることになり、山登り法の生物版として読める。

ランダム探索のステップ長の分布として、レヴィフライトがある。Viswanathan らの1999年の論文は、標的がまばらな場合、近くを短い移動で調べる動きにときどき非常に長い移動を混ぜる探し方が有利になることを示した。一回の移動の長さで見ると、長い移動ほど長さの二乗に反比例して少なくなる形、つまり飛行長の逆二乗のべき分布が最適なランダム探索になり、動物の採餌のデータがこれを支持するとした。探索アルゴリズムでは、カッコウ探索が、更新にレヴィフライトのステップを使う。

動物が実際にレヴィフライトで動いているかについては、生物学の側で、否定する再解析(Edwards らの2007年の研究)と、環境によって動き方が変わるという報告(Humphries らの2010年の研究)がある。探索アルゴリズムの部品としては、レヴィフライトはステップ長の分布の選択肢の一つとして扱える。

5. 粘菌 ― 局所フィードバックによる最短路への収束

粘菌は、管の太さが流量に応じて変わる局所のフィードバックだけで、ネットワークを作る。中垣らは2000年に迷路を解く粘菌を報告し、手老らは2010年に、粘菌が作るネットワークが東京の鉄道網に匹敵する効率、耐故障性、コストを示すことを報告した。

手老らの数理モデルは、流れの多い管ほど太くなり、流れの少ない管は細って消えていくという仕組みを、適応的なネットワークとして定式化したもので、フィードバックの強さを決めるパラメータが最短経路を見つけられるかどうかを左右する。Bonifaci らは、粘菌のモデルが、ネットワークの複雑さや初期の質量の分布がどうであっても、最短の経路に収束することを数学的に示した。

実装には、反復ごとに連立一次方程式を解くコストがある。Gao らの高速化の論文は、収束が連立一次方程式の反復に基づくため計算性能が低くなりがちだと述べ、不要な節点と辺の枝刈りと早期終了を提案した。最短経路を求めるだけなら、計算量の面ではダイクストラ法が有利である。そのため粘菌モデルの使いどころは、局所の規則だけでネットワークを作る発想を借りる場面や教材としての利用になる。

6. 部品の構成と調整

ここまでの手法は、評価関数のほかに、候補の作り方、候補を受け入れたり選んだりする規則、解を更新する規則、パラメータという部品の組み合わせとして見ることができる。次の表は、それぞれの手法をこれらの部品に分け、主に何を調整するかをまとめたものである。

手法	候補の生成	受理・選択・更新	主なパラメータ
山登り法	現在の解の近傍	良くなる候補へ移る	近傍の取り方
焼きなまし法	現在の解の近傍	悪くなる候補も確率的に受理する	温度とその下げ方
蟻コロニー最適化	フェロモンと問題固有の情報で経路を構築	フェロモンの蒸発と付加	α、β、ρ、q0、蟻の数
粒子群最適化	位置と速度の更新	個体最良と近傍最良への引力	ω、φ1、φ2
人工蜂コロニー	餌源の近傍	品質比例の選択、改善が止まった餌源の放棄	個体数、放棄の回数 limit

論文の手法は、こうした部品の組み合わせを、評価に使ったデータセットに向けて調整した形で発表されているので、現場では論文の設定を出発点にして、自分のデータでパラメータを調整し直して使う。動物の名前がついた手法は数が多いが、名前より部品の構成で見ると、既存の手法の知見を使える場面が増える。灰色オオカミ最適化(GWO)は、各反復の最良の3解の周りで候補を作り、その平均へ動き、ばらつきを決める係数を2から0へ線形に減らす。Camacho-Villalón らの分解では、これは PSO の標準的な形の一つの特殊な場合にあたるため、PSO の調整の知見をそのまま使える。

手法の定数は、作者が使ったベンチマークに合わせた値である。Aquila Optimizerは反復の2/3を境に探索の局面と活用の局面を切り替え、この2/3は設計者が置いた定数になっている。Bald Eagle Searchのように、極座標の螺旋で空間を動く局面を持つ手法もある。螺旋の式や局面を切り替える定数も、自分のデータに合わせて調整する部品として扱える。

調整の際に確認しておく項目は二つある。一つは、最適解の位置をずらしたベンチマークでの成績である。ベンチマークの関数で最適解が探索域の中心にあると、候補を中心へ寄せる癖を持つ手法は、問題を解く力とは別にその癖だけで好成績を出せてしまう。Kůdela の検査は、13の関数で最適解を原点から動かした場合と原点に置いた場合の成績の比の幾何平均を、この癖の強さを表す中心バイアスの指標にした。中心に置いたときだけ成績が良い手法ほど比が大きくなり、1E+01 を超えると、探索域の中心に最適解がある関数で有利になる性質を持つとみなす。GWO は 8.89E+05、Aquila Optimizer は 2.26E+05、Bald Eagle Search は 2.62E+08、Harris Hawks Optimization は 1.62E+05、PSO は 0.97 だった。PSO の値は、最適解を動かしても成績がほとんど変わらないことを表している。最適解の位置が探索域の中心から外れうる自分の問題に使う場合は、最適解の位置を動かして成績を測っておくと、この性質の影響を確かめられる。

もう一つは、実装の違いである。Vermetten らの294実装の比較では、同じ名前のアルゴリズムでも、実装によって性能が大きく違った。そのため、採用する実装そのものも自分のデータで測ることになる。採否を決めるのは、論文の順位でも手法の新しさでもなく、自分のデータで調整した後の成績である。パラメータの調整そのものを自動化する方法は、第8回で扱う。

第7回では、探索が目指す先を決める評価関数に進む。ヒューリスティック関数、ゲームの評価関数、検証器の作り方を扱う。