グレイウルフ最適化アルゴリズムに基づく経路計画問題を解くためのハイブリッド最適化アルゴリズム

混雑した都市で賢いルートを

毎日、ドライバーや配送車、ロボットは同じ課題に直面します：A地点からB地点へ、いかに速く、安全に、燃料や時間を無駄にせず到達するか。本稿は、障害物や渋滞で複雑に入り組んだ道路網を通して、より短く滑らかな経路を計画する新しい計算手法を提示します。 グレイウルフ（ハイイログマではなくオオカミ）の群れの狩り方や、金鉱探しの探索法から着想を得ることで、混雑する都市環境で車両やロボットをより効率的に誘導する方法を示します。

なぜより良い経路が重要か

都市が拡大し交通が増えるにつれ、ルーティングのわずかな改善でも時間、エネルギー、汚染の大幅な削減につながります。従来の経路探索法は地図が単純ならうまく機能しますが、分岐や障害が多い環境では遅くなったり局所解に陥ったりしがちです。現代の「知能的」探索手法は、鳥やアリの群れのような自然現象を模倣して多くの選択肢を同時に探索し、良好な解に収束しようとします。代表的な手法の一つであるグレイウルフ最適化（GWO）は簡便で柔軟なため人気がありますが、なお三つの主な問題を抱えます：二次的に良い経路に捕らわれやすい、早期収束しやすい、全域を十分に探索できないことがある、という点です。

ウルフとカオスと金鉱探しの融合

これらの弱点を克服するために、著者らはCGGWOと呼ぶ改良版を設計しました。基本的な考え方である仮想のグレイウルフ群が最良経路を探索する枠組みは保ちながら、群れの広がり方や学習法を変更しています。まず、ウルフを乱数で配置する代わりに、カオス写像と呼ばれる数学的トリックを使って探索領域により均等に散らします。これにより、少なくとも一部のウルフが有望な領域を発見する確率が高まります。次に、金鉱探しに着想を得たルールを取り入れます。ここでは主導する“アルファ”ウルフが探索空間の特に有益な領域へ徐々に偏らせられ、鉱夫が金脈のある方向へ移動するように群れに制御されたランダム性と多様性を注入し、局所的に悪い選択から抜け出す助けとなります。

巧妙な交差と穏やかな揺らぎ

CGGWOはさらに、ウルフ間で情報を入れ替える二種類の「クロス」動作を追加します。水平交差では、異なる候補経路が経路の一部を交換し、死角を縮小して探索が地図全体に広がることを促します。垂直交差では、単一の経路内の異なる区間が混合され、解の停滞部分を活性化し、群れが早期に誤った経路に固着するのを防ぎます。最後に、各ウルフの適合度に応じて小さなランダム変動を与えるガウス変異を穏やかに加えます。あるウルフの経路が平均より悪ければ、より強い揺さぶりを受け、それがグループ全体を解空間の一角に閉じ込められるのを避ける助けになります。

新手法の検証

研究者らはまず、探索アルゴリズムの評価で広く用いられる23件の標準的な数値最適化問題でCGGWOを試験しました。これらの問題は、単一の最良解を持つ滑らかな地形から、多数の局所的な凹地がある荒れた地形まで多様です。多数のテストにおいて、CGGWOは既存の有名手法（元のグレイウルフ法、粒子群最適化、遺伝的アルゴリズムなど）に比べ、より良い解を見つけ、収束が速く、挙動が安定していることを示しました。次に研究チームは、ラサの商業地域付近の簡略化した道路格子を基にした現実的な経路計画問題に取り組みました。障害は通行止めや渋滞区間を表し、スタートとゴールを短く滑らかな経路で結ぶことが目標です。

より短く、より滑らかな移動

交通スタイルのテストでは、CGGWOは他手法より一貫して短い経路を、急な曲がりが少ない形で生成し、必要な計算時間も控えめでした。元のグレイウルフ法や他の競合手法と比較して、計画された経路はより直線的で追従しやすく、場合によっては距離を約25％程度短縮しました。一般読者へのポイントは明快です：カオス、群れでの狩り、金鉱探しの考えを巧みに組み合わせることで、新手法は地図をより徹底的に探索し、十分に良い解に留まるのを防ぎます。これにより、将来のナビゲーションシステム、配送ロボット、その他のスマート機械が、現代都市の混雑し変化する迷路の中で安全かつ効率的な経路を迅速に見つけるための有望な道具となります。

引用: Cheng, G., Liu, Y. Hybrid optimization algorithm for solving path planning problems based on grey wolf optimization algorithm. Sci Rep 16, 8479 (2026). https://doi.org/10.1038/s41598-026-35037-z

キーワード: 経路計画, 最適化アルゴリズム, 知能交通, 群知能, ロボット航行