Chapter 5

集団と大規模近傍 — 現代の主役 ALNS

あなたは古民家のリフォームを依頼された。
小さな修繕では限界がある。
ある日、思い切って一階の壁を全部ぶち抜いて、間取りから組み直した。
結果は ——劇的に良い空間になった。

これが現代の組合せ最適化の主役、大規模近傍探索 (LNS) の発想だ。
「ちまちま swap」じゃない。「壊して作り直す」。

この章では、まず集団型 (GA、ACO など) を軽く眺めて、本命の LNS と ALNS に着地する。本書を実プロジェクトで活かしたいなら、ALNS は絶対に知っておくべき道具だ。

5.1 集団型: 解をいっぱい持つ

これまでの章は「現在解 x ひとつを動かす」だった。
集団型は「解の群れを保持して、群れごと進化させる」発想。

代表は 遺伝的アルゴリズム (GA)。生物の進化からの類推で、四つの要素を持つ:

👨‍👩‍👧 集団: 解 (=「染色体」) の集合
💑 交叉: 2 解を混ぜて子を作る
🎲 突然変異: 解の一部をランダムに変える
🏆 選択: 良い解を残し、悪いのを捨てる

def GA(pop_size, max_gen):
    pop = [random_solution() for _ in range(pop_size)]
    for _ in range(max_gen):
        parents = select(pop)
        offspring = []
        while len(offspring) < pop_size:
            p1, p2 = pick_two(parents)
            child = crossover(p1, p2)
            if random() < p_mut: child = mutate(child)
            offspring.append(child)
        pop = replace(pop, offspring)
    return best(pop)

GA は強いのか?

ここは率直に書く。1990 年代までは GA が花形だった。
だが現代では、純粋な GA は組合せ最適化のベンチマークで ALNS や LKH に普通に負ける。
「GA」と銘打った現代の優秀手法は、たいてい memetic algorithm —— 「GA の各個体に局所探索を適用」したハイブリッド —— のことだ。
だから本書では GA を中心にしない。

他の集団型 (ACO, PSO)

1990 年代に流行した「自然界の集団行動」系もある。

ACO (蟻コロニー最適化): アリがフェロモンを残して最短経路を学習する仕組み。「解の構成要素にフェロモン濃度を持たせる」アイデアは美しいし、ハイブリッドの素材として今でも使われる。
PSO (粒子群最適化): 鳥の群れの動きから着想された連続最適化手法。組合せ問題には工夫が必要で、本書では深入りしない。

警鐘: 動物名アルゴリズムバブル
過去 20 年で、Whale、Firefly、Bat、Cuckoo、Grey Wolf、Salp Swarm… など数十の「動物名アルゴリズム」が大量発表された。
研究者の Sörensen は 2013 年に “No more nature-inspired metaheuristics” という論文を書き、これらが本質的に PSO や SA の表面的な変種だと指摘した。
名前に騙されず、古典のベースライン (SA, Tabu, ALNS, LKH) と比較する習慣をつけよう。

5.2 ここから本題: 大規模近傍探索 (LNS)

さて本題。
これまでの局所探索の近傍は小さかった: swap、2-opt、Or-opt。
LNS は逆。近傍を桁違いに大きくする。

LNS のアイデア:
「現解の 30% を破壊して、残りから再構築する」
これを 1 反復とする。

なぜこれが強いかというと —— 近傍サイズが指数的に大きいからだ。配送計画で 100 顧客のうち 30 顧客を抜くと、それを再配置する組み合わせは もう一つの中規模 VRP を解くことに等しい。

図 5.1 — LNS の destroy-repair サイクル。「壊して作り直す」が 1 反復。re-build の質次第で世界が変わる。

destroy の戦略

Random: ランダムに k 個抜く
Worst: コスト寄与が大きい (= 高い場所にいる) 要素を抜く
Related (Shaw): 互いに関連する要素群をまとめて抜く (例: 近い顧客)
Cluster: 同じ機械 / 同じ日をまとめて抜く

repair の戦略

Greedy insertion: コスト最小の位置に順次挿入
Regret-k: 「後回しにすると最大の損」を先に
厳密最適化: 抜いた部分を CP-SAT で完璧に解く ⭐

特に最後の**「抜いた部分だけ CP-SAT で完璧に解く」**のがエレガント。
全体は重すぎて厳密に解けない。でも 30 個程度なら CP-SAT が一瞬で解く。
「ヒューリスティクス × 厳密ソルバー」の現代的な姿だ。

5.3 ALNS — オペレータが「自分で進化する」

LNS の destroy / repair オペレータには色々ある。じゃあ問題ごとにどれを選ぶ?
Ropke と Pisinger は 2006 年、その選び方を学習させればよいと気付いた。

これが ALNS (Adaptive Large Neighborhood Search)。
オペレータの「過去の成績」に基づいて、選ばれる確率が動的に変わる。

def ALNS():
    x = initial
    best = x
    weights = uniform()
    T = T0
    while time_left:
        d = sample_op(destroy_ops, weights)
        r = sample_op(repair_ops, weights)
        x_new = r(d(x))
        score = classify(x_new, x, best)   # global-best更新 / 改善 / 受入 / 棄却
        update_weights(d, r, score)
        if accept(x, x_new, T): x = x_new
        if f(x_new) < f(best): best = x_new
        T *= alpha
    return best

図 5.2 — ALNS の自己適応: 「効く」オペレータが自然に重みを伸ばし、効かないオペレータは静かにフェードアウトする。

ALNS の素晴らしさは「正解を最初から選ばなくていい」こと。
オペレータを 10 個並べて雑に放り込めば、勝手にチームの主役と脇役が決まる。
人間が手作業でチューニングするより、よっぽど信頼できる。

5.4 ALNS が支配する現代

2010 年代以降、生産計画・物流・スケジューリング系の論文を読むと、ベースライン手法として ALNS が常連だ。すべての SOTA を保証するわけではないが、ものすごく広い問題で SOTA に近づける。

分野	ALNS の適用例 (近年)
VRP, VRPTW, PDP	古典かつ研究の宝庫
並列機械スケジューリング	段取り時間付き、最近の論文多数
AGV スケジューリング	製造業の自動搬送車
ベース割当て・港湾	船の停泊計画
クラウドリソース割当て	VM 配置
無線基地局配置	通信ネットワーク

5.5 もう一つの大規模近傍 — Path Relinking

最後に簡単に触れておく。
集団型と局所探索の中間にある面白い手法、Path Relinking。

2 つの良い解 x と y があるとき、「x を y に向かって少しずつ変える中間解の列」を作り、その列の中で新しい良い解を探す。
集団全体を持たずに「解同士の知恵を統合」できる、エレガントな技だ。

5.6 機械学習と最適化のいま (2025〜2026)

ここ数年で「ML × 組合せ最適化」がホットだ。
本書は ML を中心にしないけど、地図だけ描いておく。

パターン1: ML が解を直接作る

グラフニューラルネット + 強化学習で、解を一手ずつ構築するモデル。 2025 年の FJSP 系では、多エージェント PPO + GNN がディスパッチ規則を超える結果が出ている。
分布シフトと説明可能性が課題。

パターン2: ML が探索を導く

ALNS のオペレータ選択を Q-learning で置き換える、LNS の destroy 範囲を予測モデルで決める、など。
古典ベースラインを下回らない範囲で、安全に組み込める。

パターン3: ML がパラメータを予測する

処理時間予測、納期予測、不良率予測。最適化の前段を ML で上げる。
投資対効果が最も高いとされる。地味だが強い。

5.7 この章の振り返り

集団型 (GA, ACO, PSO) は「解の群れを進化させる」。純粋形は現代では弱い。
動物名アルゴリズムバブルには騙されない。古典との比較を必ず見る。
**LNS は「壊して作り直す」**大規模近傍。指数的に大きな近傍を達成する。
ALNS は LNS にオペレータ重みの自己学習を載せた、現代の主役。新規プロジェクトの第一候補にすべき。
repair に CP-SAT を使うハイブリッドが、2020 年代の生産スケジューリングの王道。

これでメタヒューリスティクスの主要部分は終わり。
次の章では正反対の世界、厳密解法を覗きに行く。そこで CP-SAT という最強の道具と仲良くなったあと、第7章からスケジューリングの本丸に入る。