論文の概要: Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming
- arxiv url: http://arxiv.org/abs/2405.11305v1
- Date: Sat, 18 May 2024 14:37:43 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-21 18:18:48.643057
- Title: Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming
- Title（参考訳）: 解集合プログラミングによる組合せ最適化のための大規模近傍優先探索
- Authors: Irumi Sugimori, Katsumi Inoue, Hidetomo Nabeshima, Torsten Schaub, Takehide Soh, Naoyuki Tamura, Mutsunori Banbara,
- Abstract要約: ASP(Answer Set Programming)における最適化問題に対するLNPS(Large Neighborhood Prioritized Search)を提案する。
LNPSはメタヒューリスティックであり、初期解から始まり、次に現在の解の探索を交互に破壊し優先順位付けすることでより良い解を見つけようとする。
本稿では,ASP に基づく LNPS の実装について述べる。その結果,LNPS が ASP の最適化性能を大幅に向上させることができることを示す。
- 参考スコア（独自算出の注目度）: 3.759879849096294
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose Large Neighborhood Prioritized Search (LNPS) for solving combinatorial optimization problems in Answer Set Programming (ASP). LNPS is a metaheuristic that starts with an initial solution and then iteratively tries to find better solutions by alternately destroying and prioritized searching for a current solution. Due to the variability of neighborhoods, LNPS allows for flexible search without strongly depending on the destroy operators. We present an implementation of LNPS based on ASP. The resulting heulingo solver demonstrates that LNPS can significantly enhance the solving performance of ASP for optimization. Furthermore, we establish the competitiveness of our LNPS approach by empirically contrasting it to (adaptive) large neighborhood search.
- Abstract（参考訳）: 本稿では,LNPS(Large Neighborhood Prioritized Search)を提案する。
LNPSはメタヒューリスティックであり、初期解から始まり、次に現在の解の探索を交互に破壊し優先順位付けすることでより良い解を見つけようとする。
近傍の変動のため、LNPSは破壊演算子に強く依存せず、柔軟な探索を可能にする。
ASP.NET に基づいた LNPS の実装を提案する。
その結果,LNPS は ASP の最適化性能を大幅に向上させることができることを示した。
さらに,LNPS手法の競争力を実証的に(適応的な)大近傍探索と対比することで確立する。
関連論文リスト
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Iterative or Innovative? A Problem-Oriented Perspective for Code Optimization [81.88668100203913]
大規模言語モデル(LLM)は、幅広いプログラミングタスクを解く上で強力な能力を示している。
本稿では,パフォーマンス向上に着目したコード最適化について検討する。
論文 参考訳（メタデータ） (2024-06-17T16:10:10Z) - Large Language Model-Aided Evolutionary Search for Constrained Multiobjective Optimization [15.476478159958416]
我々は,制約付き多目的最適化問題に対する進化探索を強化するために,大規模言語モデル(LLM)を用いる。
私たちの目標は、進化の集団の収束を早めることです。
論文 参考訳（メタデータ） (2024-05-09T13:44:04Z) - Ant Colony Sampling with GFlowNets for Combinatorial Optimization [68.84985459701007]
本稿では、最適化(CO)のためのニューラルネットワークによる確率的探索アルゴリズムであるGFACS(Generative Flow Ant Colony Sampler)を紹介する。
GFACSは生成フローネットワーク(GFlowNets)と、確率的探索アルゴリズムであるアリコロニー最適化(ACO)を統合している。
論文 参考訳（メタデータ） (2024-03-11T16:26:06Z) - Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
大規模言語モデルの複雑な推論能力を高めるために,textbftextitThought Propagation (TP)を提案する。
TP はまず LLM に対して,入力問題に関連する類似問題の集合を提案し,解決するよう促す。
TPは、類似問題の結果を再利用して、新しいソリューションを直接生成したり、スクラッチから得られた初期ソリューションを修正するための知識集約的な実行プランを導出する。
論文 参考訳（メタデータ） (2023-10-06T01:40:09Z) - Searching Large Neighborhoods for Integer Linear Programs with
Contrastive Learning [39.40838358438744]
線形プログラム(ILP)は、多数の最適化問題のモデリングと解決のための強力なツールである。
アルゴリズムとしてLarge Neighborhood Search (LNS)は、ブランチやバウンドよりも高速に、ILPの高品質なソリューションを見つけることができる。
本稿では,メトリクスによって測定された複数のILPベンチマークに対して,最先端のリアルタイム性能を実現する新しいアプローチCL-LNSを提案する。
論文 参考訳（メタデータ） (2023-02-03T07:15:37Z) - Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning [4.374837991804085]
DR-ALNSと呼ばれる深層強化学習に基づくアプローチを導入し、演算子を選択し、パラメータを調整し、検索全体を通して受け入れ基準を制御する。
提案手法は,IJCAIコンペティションで提示されたオリエンテーリングウェイトと時間窓の問題に対して評価する。
その結果,本手法はバニラALNSよりも優れており,ALNSはベイジアン最適化と2つの最先端DRLアプローチに適合していることがわかった。
論文 参考訳（メタデータ） (2022-11-01T21:33:46Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Combining Particle Swarm Optimizer with SQP Local Search for Constrained
Optimization Problems [0.0]
先行するアルゴリズムの違いは局所的な検索能力にある可能性が示唆された。
ベンチマークスイートの他のリードと比較すると、他の主要なPSOアルゴリズムと競合するようにローカル検索を実装したGP-PSOのハイブリッドが示される。
論文 参考訳（メタデータ） (2021-01-25T09:34:52Z) - A General Large Neighborhood Search Framework for Solving Integer Linear
Programs [46.62993477453986]
我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。
我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
論文 参考訳（メタデータ） (2020-03-29T23:08:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。