学習したローカル検索ヒューリスティックスの限界を明らかにする: あなたは最も強い弱者ですか?

リンク一覧

概要と序論

関連作業

Max-Cutの評価

SATの評価

要約と展望、参考文献

補足資料

抽象的な

近年、ニューラル ネットワークとローカル検索ヒューリスティックを組み合わせることが、組み合わせ最適化の分野で人気になっています。かなりの計算量を必要とするにもかかわらず、このアプローチは最小限の手動エンジニアリングで有望な結果を示しています。ただし、これらの統合の試みの実証的評価では、3 つの重大な制限が特定されています。まず、中程度の複雑さと弱いベースラインを持つインスタンスは、学習ベースのアプローチの有効性を正確に評価する上で課題となります。次に、アブレーション スタディがないため、改善を定量化してディープラーニング アーキテクチャに正確に帰属させることが困難です。最後に、さまざまな分布にわたる学習ヒューリスティックの一般化は、まだ十分に調査されていません。この研究では、これらの特定された制限について包括的な調査を行います。驚くべきことに、Tabu Search に基づく単純な学習ヒューリスティックは、パフォーマンスと一般化の点で最先端の (SOTA) 学習ヒューリスティックを上回ることを実証しています。私たちの研究結果は、一般的な仮定に挑戦し、組み合わせ最適化における将来の研究と革新への刺激的な道を開きます。

1 はじめに

NP困難な組み合わせ最適化（CO）問題に効果的なヒューリスティックまたは近似アルゴリズムを設計することは困難な作業であり、多くの場合、ドメイン知識と広範な試行錯誤が必要です。そのため、問題の固有の構造を活用するアルゴリズムを学習する機械学習を通じて、この要求の厳しい退屈な設計プロセスを自動化するというアイデアは、研究者の間で大きな関心を集めています（Bello et al., 2016; Khalil et al., 2017; Bengio et al., 2021; Dong et al., 2021）。特に、これらの研究のかなりの部分（Khalil et al., 2017; Barrett et al., 2020; Yolcu and P´oczos, 2019）は、CO問題にグラフニューラルネットワーク（GNN）を採用することに集中しています。計算要件にもかかわらず、これらのGNNベースのアプローチは、特定の問題に合わせて調整されたSOTAヒューリスティックと比較して競争力のあるパフォーマンスを示しています。

これらの潜在的な進歩は大きな期待を抱かせますが、いくつかの懸念も残っています。学習されたヒューリスティックの優れたパフォーマンスは、特定のインスタンスとベースラインの選択に起因します。具体的には、ベースラインが弱い場合、学習されたヒューリスティックは簡単にそれらを上回るパフォーマンスを発揮します。ハードインスタンスと適切なベースラインの選択がなければ、学習されたヒューリスティックは簡単に SOTA ヒューリスティックと同等のパフォーマンスを示し、学習されたヒューリスティックの実際の機能を過大評価する可能性があります。さらに、ディープラーニング アーキテクチャのスケーラビリティの課題により、SOTA ヒューリスティックとの比較が省略されることがあります。

学習ベースのアプローチのサブセット (Khalil et al., 2017; Yolcu and P´oczos, 2019; Barrett et al., 2020, 2022) は、従来のヒューリスティックの機能または動作を組み込んでおり、ヒューリスティックの原理を機械学習コンポーネントと統合することで、パフォーマンスの向上または強化が期待できます。統合されたヒューリスティックとの包括的な比較とディープラーニング アーキテクチャのアブレーション スタディが不足している場合、ディープラーニング アーキテクチャの具体的な貢献を判断することは困難になります。その結果、統合されたヒューリスティックが堅牢であれば、学習されたヒューリスティックはベースライン ヒューリスティックをシームレスに上回ることができますが、ディープラーニング アーキテクチャの役割はほとんどありません。

学習済みヒューリスティックスのもう一つの大きな成果 (Khalil et al., 2017; Barrett et al., 2020; Toenshof et al., 2019) は、最初は特定の分布からのより小さく特定のインスタンスでトレーニングされ、異なる分布からのより大きなインスタンスでテストされたときに印象的なパフォーマンスを示します。この成果は、学習ベースのアプローチを採用する中核的な目的、つまりヒューリスティックスでしばしば必要とされる広範なカスタマイズとドメイン固有の知識の必要性を軽減することと一致し、重要な成果として位置付けられています。ハイパーパラメータを使用した古典的なヒューリスティックスも、特定の分布に合わせて微調整すると課題に直面する可能性がありますが、異なる分布にわたって一般化することもできます。主な調査は、学習済みヒューリスティックスが古典的なヒューリスティックスと比較して優れた一般化可能性を実際に示すかどうかを中心に展開されます。学習済みヒューリスティックスと古典的なヒューリスティックスを徹底的かつ洞察力に富んだ比較することで、学習済みヒューリスティックスの一般化可能性に関する貴重な洞察が得られます。

学習されたヒューリスティックには理論的な保証が欠けていることが多く、提案された方法論の長所と限界を理解するには経験的評価が唯一の方法となります。これらの研究の実験的評価では、いくつかの基本的かつ極めて重要な疑問が未解決のままであると私たちは考えています。これらの疑問は学習されたヒューリスティックのすべてのタイプに関係しますが、私たちはローカル検索ヒューリスティックの学習に焦点を当てた、引用数が多く最近の査読済み出版物を分析することで、これらの疑問を問い、答えます。私たちの目標は、私たちの研究で議論された CO 問題に対する包括的なベンチマークを提供することではなく、将来の研究者が研究を評価するのを支援することです。

具体的には、次のような質問をし、答えます。

1. 学習したヒューリスティックを過剰にパラメータ化できますか? もちろんです。ECO -DQN の GNN を線形回帰に置き換え、Tabu Search (Glover、1990) にリンクする ECO-DQN (Barrett ら、2020) の機能のサブセットを利用して、SoftTabu と呼ばれる ECO-DQN のプルーニング バージョンを導入します。私たちの研究では、NPhard 最大カット (Max-Cut) 問題に対して、SoftTabu が ECO-DQN と比較して優れたパフォーマンスと一般化性を発揮することが実証されています。

2. ベースライン バイアスは、学習済みヒューリスティックの優れたパフォーマンスに起因するのでしょうか?はい、バニラ学習済みヒューリスティックである SoftTabu が、Max-Cut 問題では S2V-DQN (Khalil ら、2017 年) よりも、ブール満足度 (SAT) では GNNSAT (Yolcu および P´oczos、2019 年) よりも優れていることを実証しています。

*3. 学習したヒューリスティックは、インスタンス選択バイアスにより優れた一般化可能性を示すことができますか? *はい、ECO-DQN はより難しいインスタンスでは一般化が不十分であり、検索空間に簡単に閉じ込められることを示しています。