Polaris.AIテックブログPublicationへの投稿
🚀

視覚的に学ぶヒューリスティック最適化入門 —— 焼きなまし・ビームサーチ・遺伝的アルゴリズム

binap
に公開
AtCoder
アルゴリズム
最適化
ヒューリスティック
tech

0. 挨拶

Polaris.AI株式会社でエンジニアをしておりますbinapと申します。
競技プログラミングを趣味としており、ほぼ毎週AtCoderというサイトでコンテストに参加しております。

1. 趣旨

AI のコーディング力が高まっている昨今、適切な手法を選ぶ直観力がいっそう重要になってきています。AI が選んだ方針の良し悪しを素早く見極め、より良い方向へ導くことで、生産性は何倍にも伸ばせるはずです。

本稿はヒューリスティックプログラミングの未経験者や初心者の方を主な対象としており、ビジュアライザーを通して解が改善していく様子を眺めながら、ヒューリスティックの直観を養っていきます。

すでに経験豊富な読者の方に向けては、第6項に著者からの挑戦課題を用意しています。ぜひ腕試しに取り組んでみてください。

2. ヒューリスティックな最適化とは

本稿では最適化問題のためのヒューリスティック手法をいくつかご紹介します。最適化問題とは、スコア関数 f:X \rightarrow \mathbb{R} に対し、f(x) ができるだけ大きくなるようなx \in X を見つける問題のことです。このときのxを最適解と呼びます。

理想的には全パターン試せば厳密な最適解が求まりますが、実務で求められるプログラミングでは、厳密な最適解を見つけるのに途方もない時間がかかる場合が少なくありません。計算資源には限りがあり、スコアの算出回数にも現実的な上限があります。とくに組合せ爆発で候補数が指数的・階乗的に増える問題では全パターン試すことは現実的に不可能です。そのため、効率よく解を探索していく必要があります。

そうした場合の最適化に用いられるのがヒューリスティックな手法です。ヒューリスティックな手法とは、厳密な最適解そのものではなく、現実的な計算時間で「十分に良い解」を見つけるための手法を指します。本稿では「焼きなまし法・ビームサーチ・遺伝的アルゴリズム」という代表的な3つの手法を取り上げ、それぞれビジュアライザーによる可視化を見ながら学んでいきます。

それぞれのアルゴリズムについて、解の変遷の様子を視覚的に確認できる「ビジュアライザー」を用意しました。適宜参照しながら学習に役立ててください。

※補足したい情報はたくさんありますが、初学者の第一歩として「ざっくり理解できる」ことを目標に、極力しぼって書いています。ツッコミどころも多いかもしれませんが、ご容赦ください。

https://binap-t.github.io/TSP-visualizer/

3. 山登り法・焼きなまし法

山登り法

ヒューリスティックな手法で最も一般的なアプローチは、いまの解の「近く」(近傍)を少しずつ試し、良くなる方向へ改善を重ねるというものです。ここでは、その代表として山登り法と焼きなまし法を紹介します。

  1. 初期解 x \in X を用意します。
  2. 近傍 x+Δx を 1 つ生成します。
  3. Δf = f(x+Δx)-f(x) を計算します。
  4. もし Δf \geq 0 なら x \leftarrow x+Δx に更新します。そうでなければ x を保持します。
  5. 上記の2.から4.を繰り返します。
近傍の例

・実数 (X = R) なら微小量変化（例：(x = 10.00 \rightarrow x + Δx = 9.98)）
・bit列 (X = \{0, 1\}^N) なら1点FLIP（例：(x = 10110_{(2)} \rightarrow x + Δx = 10010_{(2)})）
・順列 (X = \mathfrak{S}_N) なら 2点SWAP（例：(x = (6,5,1,3,2,4) \rightarrow x + Δx = (6,5,2,3,1,4))）
いずれも「あまり大きく変化しない範囲でランダムな変更」が定番です。
（加法が定義できない空間では x + Δx は不自然な記法ですが、微小変化を強調する意図でこの表記を採用しています）

スコア関数 f が山型であれば、この操作を繰り返すことでいずれ山頂付近までたどり着けます。

山登り法疑似コード
function hill_climbing(initial_solution):
    current = initial_solution
    while True:
        neighbor = random_neighbor(current)
        if score(neighbor) <= score(current):
            return current  # 改善できなければ終了
        current = neighbor

焼きなまし法

  1. 初期解 x \in X と初期温度 T_{\text{init}}、終端温度 T_{\text{final}} を用意します。温度 T=T_{init} として初期化します。
  2. 近傍 x+Δx を 1 つ生成します。
  3. Δf = f(x+Δx)-f(x) を計算します。
    1. Δf \ge 0 のときは更新（x \leftarrow x+Δx）します。
    2. Δf < 0 のときは確率 \exp(Δf/T) で更新します。
  4. 温度 T を低下させます（T_{\text{final}} に近づけます）。
  5. 上記の2.から4.を繰り返します。
解釈

・ f(x+Δx) - f(x) \geq 0 は必ず採用。
・ f(x+Δx) - f(x) \simeq -T はときどき採用。確率 \frac{1}{e}。
・ f(x+Δx) - f(x) \simeq -2T くらいになるとなかなか採用されなくなる。確率 \frac{1}{e^2}。
この T が徐々に減少していく。
つまり、始めスコアが悪くなるような遷移もある程度採用するが、徐々に良くなる遷移のみしか採用しなくなっていくイメージ。

スコア関数が多峰性を持つ山脈のような形でも、かなり良い解にたどり着きやすいです。直感ではうまくいかないように感じられるかもしれませんが、焼きなまし法で大きく改善する場面は少なくありません。

焼きなまし法疑似コード
function simulated_annealing(initial_solution):
    current = initial_solution
    best = current
    
    for cnt in range(steps):
        T = T_init + (T_final - T_init) * (cnt / steps)
        neighbor = random_neighbor(current)
        delta = score(neighbor) - score(current)

        if delta > 0:
            current = neighbor
        else if random() < exp(delta / T):
            current = neighbor

        if score(current) > score(best):
            best = current

    return best
高温でのイメージ 低温でのイメージ

イメージ図を用意しました。 8 方向それぞれについて、その方向が近傍として選ばれたときに移動する確率を p 、移動せずその場に留まる確率を 1-p とします。
左下に山があります。高温状態（序盤）は他のより良い山を探してある程度自由に動き回りますが、低温状態（終盤）では近くの山の山頂めがけて登っていく様子を大雑把に表しています。

山登り法にたとえると「ときどき下りながら登る」イメージです。広いプラトーや、近傍間でスコア相関が弱い状況では、ランダムウォークのようになりやすいです。

ビジュアライザーを見てみよう！

シンプルな巡回セールスマン問題（TSP）のビジュアライザー（ https://binap-t.github.io/TSP-visualizer/ ）を用意しました。初期シード Seed と頂点数 N を設定して「Generate Cities」ボタンを押すと、2 次元平面上に点がランダムに配置されます。これらの点をすべて通って 1 周する経路のうち、距離の総和ができるだけ小さいものを選ぶ問題です。解は全部で (N-1)!/2 通り（初期値では (40-1)!/2 = 10^{46} 通り）あり、全探索は現実的ではありません。より高速なアプローチもありますが、それでも最適解の厳密探索にはかなりの時間がかかります。
※TSP では score = (-1) \times tour\_length とし、距離の最小化を目的とします。

「Run SA」ボタンで焼きなまし法の解を生成し、ステップごとに結果を確認できます。シークバーを動かして、序盤は解が悪化する遷移が多いこと、終盤はほとんど変化しなくなることを観察してみてください。

また、steps = 500, 5000, 50000, \dots とステップ数を増やすと、最終スコアが大きく改善する様子も見て取れます。N=25 程度にして、手作業で焼きなまし法より強い解を作れないか挑戦してみるのも面白いと思います。

4. ビームサーチ

ありうるすべての解を全探索することを考えると、多くの場合、探索経路は木構造で表せます。いったん全探索のつもりで考え、木上の各頂点（途中状態）にスコア関数を定めます。途中までの時点でスコアが低い頂点は、そこからの逆転が見込みにくいと判断して棄却することで、探索空間を絞ります。

  1. ビーム（各深さでのスコア上位の頂点の集合）を初期状態のみで開始します。
  2. ビーム内の各ノードを展開して子ノード候補を列挙します。
  3. 候補からスコア上位 Width 個だけを新しいビームとして残します。
  4. 2.から3.を繰り返します。

途中経過で評価を入れる性質上、「短期的に見て良い手が長期的にも良い手である」場面に非常に強い一方、序盤で損をして布石を打ち終盤で大きく回収するタイプの問題は苦手になりがちです。

ビームサーチ疑似コード
function beam_search(initial_state, beam_width):
    beam = [initial_state]
    
    for step in range(max_steps):
        candidates = []
        for state in beam:
            neighbors = expand(state)
            candidates += neighbors

        # 候補からスコア上位 beam_width 個を選択
        beam = top_k(candidates, beam_width)

    return best_solution_in(beam)
ビジュアライザーを見てみよう！

「Run BS」ボタンを押すとビームサーチの解を生成し、各ステップで採用される上位 Width 個の解を表示します。各ステップにおける上位 Width 個が、直前のどの解から派生したのかをたどってみると理解が深まります。

各ノードでの評価関数を「今までの距離の総和」で定義しています。そのため現在注目している頂点の近くだけが選ばれやすく、端の頂点を取りこぼすことが多々あります。その結果、終盤に端の頂点を無理に通ろうとしてスコアが悪化する様子が観察できるはずです。

取らずに残っている頂点たちの距離を上手に近似して、この寄与も反映した評価関数を設計すれば、改善するはずですが筆者はできていません。試されたし。

5. 遺伝的アルゴリズム

解の集団を1世代として、解の組み合わせで次世代を生み出します。

  1. PopSize 個の解をランダムに生成し、これを第1世代とします。
  2. 親個体の組み合わせで子個体を生成します。（交叉）
  3. 低確率で子に近傍の微小変更を加えます。（突然変異）
  4. 生成した子のスコアを計算します。
  5. スコアの低い個体を捨てて上位から PopSize 個だけ残します。
  6. 上記の2.から5.を繰り返します。

焼きなまし法では近傍のみを探索しますが、遺伝的アルゴリズムは解の組み合わせ（交叉）によって新たな解を作るため、大きく離れた領域へ跳べる可能性があります。一方で各世代を生み出す計算量が重い場合が多く、回せる改善サイクル数が少なくなりがちです。

遺伝的アルゴリズム疑似コード
function genetic_algorithm():
    population = [random_solution() for _ in range(POP_SIZE)]
    
    for gen in range(MAX_GENERATION):
        scored = [(sol, score(sol)) for sol in population]
        selected = selection(scored)

        children = []
        while len(children) < POP_SIZE:
            parent1, parent2 = select_parents(selected)
            child1, child2 = crossover(parent1, parent2)
            mutate(child1)
            mutate(child2)
            children.append(child1)
            children.append(child2)

        population = children

    return best_solution(population)
ビジュアライザーを見てみよう！

「Run GA」ボタンを押すと遺伝的アルゴリズムの解を生成します。各ステップで生き残った上位 PopSize 個の解を世代ごとに表示しています。PopSize は 1 世代あたりの個体数です。

実用上は以下の工夫を加えることが多いです。
・エリート（親世代の最上位解）をそのまま次世代に引き継ぐ
・解の多様性を保つため、同一解の重複を避ける
また「遺伝的アルゴリズム図解：交叉」の図はわかりやすい交叉を採用していますが、TSPでは少し複雑な交叉をすることになります。また良い交叉を構成しづらく遺伝的アルゴリズムを適用しにくい問題も多いです。

6. 実践

例題を作ってきました。どのアルゴリズムが良さそうか考えてみてください！

https://github.com/binap-t/bit-sequence

7. AHCのすすめと末文

競技プログラミングサイト AtCoder では、AHC（AtCoder Heuristic Contest）という名前でヒューリスティック問題のコンテストが開催されています。最近は月2回ほどのペースです。上位陣の解法やビジュアライザーを見ると、自分では思いつかないアプローチに触れられ、大きな学びがあります。本稿で紹介した手法は知っているだけでも武器になりますが、経験を重ねることで、複雑な条件下でも自在に使いこなせるようになっていきます。

過去コンテストの URL を貼っておきます。毎回とても楽しいので、よろしければぜひご参加ください！

弊社Polaris.AIはAI受託開発を中心に行っておりますが、

  • 積荷の最適化
  • 商品の棚割りの最適化
  • 生産計画の最適化
  • 輸送経路最適化
  • シフト最適化

など最適化の案件も増えてきています。実際に上述のヒューリスティック手法を使っています。是非興味がある人は応募してください！(https://www.wantedly.com/projects/2114557)

Polaris.AIテックブログ
Polaris.AIテックブログPublication

Polaris.AIの公式テックブログです。 AIに関する情報を発信していきます。

Discussion