最適化問題と局所探索の基本：病院配置問題の例から学ぶ
これまでにAIが知識ベースの問題（論理と推論を使って結論を導く）や確率モデル（不確実性を扱う）を用いる方法を学びました。この記事では、最適化問題に焦点を当て、特に**局所探索（Local Search）**アルゴリズムとその応用例をわかりやすく解説します。例として、病院の最適配置問題を扱います。
1. 最適化問題とは？
最適化問題とは、多くの選択肢の中から最適な選択肢を見つけることを目的とした問題のことです。例えば、ゲームAIでは、最良の手を選ぶのが最適化問題の一例です。
一般的に最適化問題は次のように分類されます：
- 最大化問題: 目的関数（Objective Function）の値を可能な限り最大化する。
- 最小化問題: コスト関数（Cost Function）の値を可能な限り最小化する。
例：病院配置問題
- 目標: 地図上の病院を最適に配置し、すべての家から最も近い病院までの距離の合計（コスト）を最小化する。
- 制約: 病院を配置できる場所は格子状の地図内で決まっている。
2. 局所探索とは？
局所探索アルゴリズムは、現在の状態（配置）を基に、隣接する状態（配置）を探索し、解を改善していく手法です。
従来の探索アルゴリズムとの違い
- 幅優先探索やA*探索: 複数の経路を同時に追跡してゴールを目指す。
- 局所探索: 現在の状態を保持し、1つの隣接状態を基に探索を進める。
局所探索の特徴
-
経路ではなく解そのものに焦点を当てる
解（病院配置）が最適であることが重要であり、経路は考慮しない。 -
初期状態から開始し、逐次的に改善する
初期状態をランダムに生成し、そこから改善を図る。
3. 病院配置問題を局所探索で解く
問題設定
- 格子状の地図に家と病院を配置。
- コスト関数: 各家から最も近い病院までの距離の合計。
- 目標: コストを最小化する病院の配置を見つける。
隣接状態の定義
隣接状態は、病院の1つを上下左右に1マス移動した配置。
4. ヒルクライミングアルゴリズム
ヒルクライミング（Hill Climbing）は、最適化問題を解くための単純な局所探索アルゴリズムです。
アルゴリズムの流れ
- 初期状態を設定: 病院の位置をランダムに決定。
- 隣接状態を生成: 現在の配置から可能な隣接状態を全て列挙。
- 最良の隣接状態を選択: コストを最小化する隣接状態を選ぶ。
- 状態の更新: 最良の隣接状態に移動。
- 停止条件: 現在の状態がすべての隣接状態よりも良い場合、終了。
擬似コード
def hill_climb(problem):
current = problem.initial_state()
while True:
neighbors = problem.get_neighbors(current)
best_neighbor = min(neighbors, key=lambda state: problem.cost(state))
if problem.cost(best_neighbor) >= problem.cost(current):
return current
current = best_neighbor
5. ヒルクライミングの実行例
初期状態
初期配置では、家と病院の位置がランダムに決定されます。
- 病院の初期配置: コスト72
状態の更新
以下のようにコストを削減します：
- 病院1を左に移動 → コスト69
- 病院2を下に移動 → コスト63
- 病院1をさらに左に移動 → コスト53
最終状態
最終配置では、病院の位置が最適化され、コストが53に削減されました。
6. ヒルクライミングの限界
局所最適解に陥る可能性
- 局所最適解: 隣接状態の中で最良だが、全体で見ると最適解ではない。
- 大域的最適解: 全ての可能な解の中で最良の解。
ヒルクライミングは、局所最適解に陥りやすいという問題があります。
7. 改良版アルゴリズム
ヒルクライミングの弱点を補うための手法があります。
改良版
- 確率的ヒルクライミング: 最良ではなく、ランダムに隣接状態を選ぶ。
- ランダム再スタート: 複数回ランダムに初期状態を生成して試行。
- ビーム探索: 複数の状態を同時に追跡し、最良のk個を選ぶ。
8. 実装例: 病院配置問題
Pythonコード
以下のコードは、病院配置問題をヒルクライミングで解く実装例です。
import random
class HospitalProblem:
def __init__(self, width, height, num_hospitals, num_houses):
self.width = width
self.height = height
self.hospitals = []
self.houses = [(random.randint(0, width - 1), random.randint(0, height - 1)) for _ in range(num_houses)]
def initial_state(self):
return [(random.randint(0, self.width - 1), random.randint(0, self.height - 1)) for _ in range(len(self.houses))]
def get_neighbors(self, state):
neighbors = []
for i, (x, y) in enumerate(state):
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
new_state = state[:]
new_state[i] = (x + dx, y + dy)
neighbors.append(new_state)
return neighbors
def cost(self, state):
total_distance = 0
for house in self.houses:
total_distance += min(abs(house[0] - hx) + abs(house[1] - hy) for hx, hy in state)
return total_distance
9. まとめ
局所探索は、最適化問題を効率的に解くための有力なアプローチです。ヒルクライミングはその基本ですが、改良手法を活用することで、より良い結果を得られます。この記事の内容を基に、自分の問題に適した最適化アルゴリズムを設計してみてください。