局所探索法

局所探索法とは

局所探索法（local search）は、別名、逐次改善法（iterative improvement）や近傍探索法とも呼ばれる、最適解やそれに近い解を探索するためのアルゴリズムの一種です。特に、近似アルゴリズムの中でも最も単純な枠組みの一つとして知られています。広義には、特定の枠組みを持つアルゴリズムの総称として用いられ、狭義には山登り法を指すこともあります。今日のメタヒューリスティクスの多くの手法が、この局所探索法の枠組みを基盤としています。

数値解析における反復法との違い

探索アルゴリズムの分野では「局所探索法」という言葉が使われる一方で、数値解析の分野では類似の概念として「反復法」という言葉が用いられます。両者の主な違いは、反復法が対象関数の連続性や微分可能性を前提とするのに対し、局所探索法は関数が離散的であったり、その内容が不明な場合でも、可能な限り良質な近似解を求めることを目的としている点にあります。また、反復法は厳密な最適解を求めることを目指すことが多いのに対し、局所探索法は近似解で十分な場合にも適用されます。

局所探索法のアルゴリズム

局所探索法の基本的なアルゴリズムは、以下の手順で構成されます。

1. 初期解の生成: まず、ランダムに一つの解を生成します。
2. 近傍解の選択: 現在の解の近傍にある解の中から、特定の条件に基づいて一つを選択します。この近傍解は、現在の解と少しだけ異なる解です。
3. 解の更新: 定義された条件を満たす場合、近傍解を現在の解と入れ替えます。これにより、解が少しずつ改善されていきます。
4. 終了条件: 上記のステップ2と3を、あらかじめ設定した終了条件を満たすまで繰り返します。

局所探索法のパラメータ

局所探索法を実装する際には、以下のパラメータを定義する必要があります。

近傍の定義: 現在の解とどれくらい異なる解を近傍とするかを定義します。ハミング距離が近いものや、グラフ表現で近い状態などが用いられます。
近傍解を選択する条件: 複数の近傍解がある場合に、どれを選択するかを決定する条件です。
解を入れ替える条件: 近傍解が現在の解よりも優れている場合に、解を入れ替えるかどうかを決定する条件です。
終了条件: 探索を終了する条件です。繰り返しの回数や、解が改善されなくなった場合などが用いられます。

局所探索法の具体的な手法

局所探索法には、さまざまな手法が存在します。以下に代表的なものを紹介します。

山登り法（Hill Climbing）

山登り法は、局所探索法の最も基本的な手法の一つです。すべての近傍解の中で最も評価が高い解を選択し、それが現在の解よりも優れていれば入れ替えます。この操作を繰り返すことで、解を徐々に改善していきます。しかし、局所的な最適解に陥りやすいという欠点があります。

焼きなまし法（Simulated Annealing）

焼きなまし法は、山登り法の欠点を補うために開発された手法です。近傍解をランダムに一つ選択し、現在の解よりも評価が低い場合でも、ある確率で解を入れ替えます。この確率は温度と呼ばれるパラメータによって制御され、探索の初期段階では広い範囲を探索し、徐々に探索範囲を狭めていくことで、局所解に陥るのを防ぎます。

タブーサーチ（Tabu Search）

タブーサーチは、過去に探索した解を一定期間「タブー」とすることで、同じ解に繰り返し戻るのを防ぐ手法です。複数の近傍解を探索し、最も評価の高い解を選択しますが、タブーリストにある解は選択しません。これにより、より広範囲な探索が可能になります。

注意点

遺伝的アルゴリズムを局所探索法に含める意見もありますが、遺伝的アルゴリズムは近傍の定義が曖昧なため、厳密には局所探索法とは異なります。

まとめ

局所探索法は、問題の性質や規模に応じて様々な手法を組み合わせることができ、幅広い問題に対して有効なアルゴリズムです。これらの手法を理解し、適切に使い分けることで、より効率的な問題解決が可能になります。

もう一度検索