A New Meta-Heuristic for Improving General Multi-Start Procedures, With an Application to the Planar p-Median Location Problem

あなたは、広大で平坦な街の中に、5つの新しいピザ屋を建てるための最高の場所を見つけようとしていると想像してください。あなたは、人々が一切れを食べるために歩かなければならない合計距離を最小限に抑えたいと考えています。これが**平面p-メディアン問題（Planar p-Median Problem）**です。一見単純そうに聞こえますが、この街は罠の迷路です。もし単に場所を選んで、より良い場所を探して歩き回るだけなら、あなたは小さな丘の上に立ち止まり、「ここが一番高い」と思い込んでしまうかもしれません。しかし、すぐ隣の尾根の向こうには、巨大な山が隠れているかもしれないのです。数学用語では、これらの丘は「局所最適解（ローカル・オプティマ）」と呼ばれます。そして、この問題には、それが数百万個存在する可能性があります。

数十年にわたり、研究者たちは**マルチスタート（Multi-Start）**と呼ばれる戦略を使用してきました。これは、800,000人の異なる偵察兵（あるいは800,000通りの別々のピザ配達ルート）を雇い、ランダムな場所から街中を走り回らせるようなものです。各偵察兵は、ある地点で行き詰まるまで走り続け、その後、あなたはその中で最も優れた結果を選び出します。これは機能しますが、まるでボードに向かって100万本のダーツを投げ、そのうちの1本がブルに当たることを祈っているようなものです。

新しいトリック：「エリート部隊」と「ベビーステップ」

著者であるZvi DreznerとJack Brimbergは、RPT（Repeated POSTの略）と呼ばれる、巧妙な新しいメタヒューリスティック（賢い解法ルール）を提案しています。彼らは、800,000人の偵察兵から得られた単一の最高の結果を保持するのではなく、見つけたトップ5の優れた結果からなる小さな「エリート部隊（Elite Squad）」を保持すべきだと主張しています。

ここが魔法の部分です：

1. ミックス・アンド・マッチ（混ぜ合わせと組み合わせ）： 2つの異なる「エリート」解（2組の異なるピザ屋の所在地）を取り出します。これらを「親」だと想像してください。
2. 子孫の生成： 街の中に一本の線を引きます。親Aのショップのうち線の片側にあるものと、親Bのショップのうち反対側にあるものを組み合わせます。これで、両親の最良の部分を組み合わせた新しい「子供」の解、つまりハイブリッドな地図が誕生しました。
   3.お磨き上げ（ポリッシュ）： この新しい「子供」に対して、標準的な改善アルゴリズムを実行します。もしかすると、新しい丘で行き詰まるかもしれませんが、それは以前よりも「高い」丘かもしれません。
3. 反復： もしこの新しい「子供」が現在のベストよりも優れていれば、それをエリート部隊に加え、再び他の解との混合を試みます。より良い「子供」が見つからなくなるまで、このプロセスを繰り返します。

論文では、この初期の混合フェーズをPOST（ポスト・オプティマイジング・ステップ）と呼んでいます。完全なRPT戦略は、このプロセスを一歩進めています。800,000人の偵察兵を一度に走らせるのではなく、作業を小さなバッチに分割します。まずPOSTプロセスを小さなグループに対して実行してトップ5を見つけ、それらを混ぜ合わせ、そしてこのサイクル全体を何度も（具体的には、最高のテストでは700回）繰り返します。

彼らが発見したこと（および発見できなかったこと）

著者らは、48種類の異なる都市マップ（均一に広がった顧客がいる24ケースと、塊状で不均一なクラスターがある24ケース）を用いてテストを行いました。彼らは2つの異なる「偵察兵」アルゴリズムを使用しました。一つは古典的なALT（Cooperによる伝統的な手法）、もう一つはより新しく洗練されたCLUSTと呼ばれるものです。

• 結果： 48件のテストケースすべてにおいて、RPT(CLUST) メソッドは、標準的なマルチスタート法よりも優れた解を見つけ出しました。（注：標準的なRPT(ALT)法は結果を大幅に改善しましたが、48件すべてのインスタンスで新しいベスト既知解を見つけたわけではありません。この特定の成果は、CLUSTアルゴリズムと組み合わされたRPTメソッドによるものです）。
• スピード： ここが重要な点ですが、この混ぜ合わせと組み合わせに要した追加時間は、ほとんど無視できるものでした。24の均一なインスタンスにおいて、標準的なALTメソッドを実行する平均時間は約257.68分でした。RPTメソッドは約257.45分でした。彼らは、ほぼ同等の時間で、より優れた結果を得たのです。
• 改善度： 標準的なALT法による解は、平均してベスト既知の結果より0.80%劣っていました。RPTはこれを0.53%まで削り込みました。特定のケースでは、その改善は劇的であり、誤差を60%以上、あるいは70%以上削減しました。

より低速で新しいCLUSTアルゴリズムを使用した場合、結果はさらに印象的なものとなりました。標準的なCLUST法はすでに非常に優れた解を見つけていましたが、RPTはすべての均一な24インスタンスおよびすべての非均一な24インスタンスにおいて、新しいベスト既知解を見つけ出しました。実際、均一なテストにおいて、特定のセッティング（I = 1,000）を用いたRPT法は、単独で24ケース中14ケースでベスト既知解を見つけました。もし異なる設定（I = 1,000 と I = 10,000）の結果を組み合わせれば、24ケース中21ケースで新しいベスト既知解が見つかりました。非均一なテストについては、RPT法は単独で24ケース中13ケースでベスト既知解を見つけ、設定を組み合わせれば、全24ケースでベスト既知解を見つけ出しました。

彼らが否定していること

この論文は、この手法ができないことについても明確に述べています。

• これは、毎回完璧なグローバル最適解を保証する「魔法の杖」ではありません。著者らは、「もしマルチスタート・ヒューリスティックが最適解を見つけたのであれば、当然ながらRPTはそれを改善することはできない」と明言しています。すでに絶対的な最善の答えを見つけているなら、RPTでもそれを良くすることはできません。
• これは、コンピュータを何日も長く動かし続けることを要求する手法でもありません。著者らは、追加時間は「無視できる（negligible）」程度であると主張しています。
• また、彼らは（何人の偵察兵を使うかといった）完璧なパラメータを見つけることに執着する必要はないとも示唆しています。彼らは異なるグループサイズ（1,000 vs 10,000など）をテストしましたが、どちらも同様に良好に機能したため、「合理的なパラメータの選択であれば、どれも同様にうまく機能する」としています。

彼らの確信度

著者らは、Intel i7プロセッサを搭載したデスクトップコンピュータ上で実際のシミュレーションを実行したため、その数字に非常に自信を持っています。彼らは単に推測したのではなく、測定を行いました。

• 彼らは、統計テスト（ペアードt検定）を用い、改善が統計的に有意であることを確認しました（p値は $6.7 \times 10^{-5}$ まで下がりました）。
• 彼らは、この手法が「一般的なマルチスタート改善アルゴリズム」に適用可能であると主張していますが、今回実証したのは平面p-メディアン問題のみです。彼らは、これが他の問題（クラスタリングなど）にも機能する可能性を示唆していますが、まだ証明はしていません。

まとめ

これらの問題を解く古い方法を、100万本のダーツを投げて、そのうちの1本がブルに当たることへの期待に例えるなら、新しいRPTメソッドは、これまでに投げた5本のベストなダーツを取り出し、それらを半分に切り、最も良い部分同士を接着して、新しい「スーパーダーツ」を作るようなものです。そして、その新しいダーツを投げるのです。もしそれが以前より良く当たれば、それを保持して再び試します。

この論文は、この「ミックス・アンド・マッチ」のアプローチが、コンピュータの処理を何日も待つことなく、既存のアルゴリズムからより優れた解を絞り出すための、強力かつ低コストな方法であることを示唆しています。それは「十分な検索」を、ほぼ無料に近いコストで「素晴らしい検索」へと変えるのです。