論文の概要: Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems

• arxiv url: http://arxiv.org/abs/2010.11523v2
• Date: Fri, 13 Nov 2020 08:54:29 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-04 07:52:49.078644
• Title: Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems
• Title（参考訳）: 組合せ最適化問題に対するモンテカルロ木探索の適応版を用いた探索空間木探索
• Authors: Jorik Jooken, Pieter Leyman, Patrick De Causmaecker, Tony Wauters
• Abstract要約: このアプローチでは,問題インスタンスの探索空間木を探索するアルゴリズムを用いる。 このアルゴリズムはモンテカルロ木探索(Monte Carlo tree search)をベースとしている。
• 参考スコア（独自算出の注目度）: 0.6882042556551609
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this article, a novel approach to solve combinatorial optimization problems is proposed. This approach makes use of a heuristic algorithm to explore the search space tree of a problem instance. The algorithm is based on Monte Carlo tree search, a popular algorithm in game playing that is used to explore game trees. By leveraging the combinatorial structure of a problem, several enhancements to the algorithm are proposed. These enhancements aim to efficiently explore the search space tree by pruning subtrees, using a heuristic simulation policy, reducing the domains of variables by eliminating dominated value assignments and using a beam width. They are demonstrated for two specific combinatorial optimization problems: the quay crane scheduling problem with non-crossing constraints and the 0-1 knapsack problem. Computational results show that the algorithm achieves promising results for both problems and eight new best solutions for a benchmark set of instances are found for the former problem. These results indicate that the algorithm is competitive with the state-of-the-art. Apart from this, the results also show evidence that the algorithm is able to learn to correct the incorrect choices made by constructive heuristics.
• Abstract（参考訳）: 本稿では,組合せ最適化問題を解くための新しい手法を提案する。 このアプローチでは、ヒューリスティックアルゴリズムを使用して問題インスタンスの探索空間ツリーを探索する。 このアルゴリズムはモンテカルロ木探索(Monte Carlo tree search)をベースとしている。 問題の組合せ構造を活用することにより,アルゴリズムのいくつかの拡張が提案される。 これらの拡張は、サブツリーを刈り上げ、ヒューリスティックなシミュレーションポリシーを用いて探索空間木を効率的に探索し、支配的な値代入を排除し、ビーム幅を用いることで変数の領域を縮小することを目的としている。 これらは、非交差制約を持つクロイクレーンスケジューリング問題と0-1knapsack問題という2つの特定の組合せ最適化問題に対して実証される。 計算結果から,このアルゴリズムは両問題に対して有望な結果が得られ,従来の問題に対して,ベンチマークセットの8つの最適解が発見された。 これらの結果は,アルゴリズムが最先端技術と競合していることを示している。 これとは別に、この結果は、アルゴリズムが構成的ヒューリスティックスによってなされた不正確な選択を正すことができるという証拠も示している。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection [9.175779296469194]
  本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。 鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。 このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
  論文  参考訳（メタデータ） (2022-11-22T10:18:33Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Combining K-means type algorithms with Hill Climbing for Joint Stratification and Sample Allocation Designs [0.0]
  これは、基本層のすべての可能な成層集合から最適成層を探索するサンプル問題である。 それぞれのソリューションのコストを評価するのに 費用がかかります 上記のアルゴリズムと最近の3つのアルゴリズムの多段階組み合わせを比較し、ソリューションコスト、評価時間、トレーニング時間を報告する。
  論文  参考訳（メタデータ） (2021-08-18T08:41:58Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Evolutionary Algorithm and Multifactorial Evolutionary Algorithm on Clustered Shortest-Path Tree problem [2.578242050187029]
  CluSPT(Clustered Shortest-Path Tree Problem)はNPハード問題である。 探索処理の性能を向上させるために,2つの手法を提案する。
  論文  参考訳（メタデータ） (2020-10-19T08:37:18Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem [2.099922236065961]
  本稿では, RGA とショート・パス・ツリー・アルゴリズム (SPTA) の主な特徴を組み合わせたクラスタ・ショート・パス・ツリー問題 (CluSPT) を扱うアルゴリズムを提案する。 提案アルゴリズムの性能を評価するため,ユークリッドベンチマークが選択される。
  論文  参考訳（メタデータ） (2020-05-05T08:34:58Z)
• Parameterized Complexity Analysis of Randomized Search Heuristics [16.759797540118665]
  この章では、ランダム化アルゴリズムのパラメータ化実行時間解析の理論を適用した多数の結果をまとめた。 NP-hard最適化問題の解法を課題とするランダム化検索の集合に対する主な結果と証明手法について概説する。
  論文  参考訳（メタデータ） (2020-01-15T03:43:56Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。