論文の概要: Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem

• arxiv url: http://arxiv.org/abs/2210.03918v2
• Date: Sat, 14 Oct 2023 07:40:32 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-18 06:49:16.511173
• Title: Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem
• Title（参考訳）: 0-1多次元クナップサック問題の探索空間の探索と探索
• Authors: Jitao Xu, Hongbo Li, and Minghao Yin
• Abstract要約: 0-1 多次元クナップサック問題(MKP)は、多くの工学的応用において古典的なNPハード最適化問題である。 我々は,0-1 MKPを解くために,進化計算と正確なアルゴリズムを組み合わせた新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 18.19836641663039
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The 0-1 Multidimensional Knapsack Problem (MKP) is a classical NP-hard combinatorial optimization problem with many engineering applications. In this paper, we propose a novel algorithm combining evolutionary computation with exact algorithm to solve the 0-1 MKP. It maintains a set of solutions and utilizes the information from the population to extract good partial assignments. To find high-quality solutions, an exact algorithm is applied to explore the promising search space specified by the good partial assignments. The new solutions are used to update the population. Thus, the good partial assignments evolve towards a better direction with the improvement of the population. Extensive experimentation with commonly used benchmark sets shows that our algorithm outperforms the state of the art heuristic algorithms, TPTEA and DQPSO. It finds better solutions than the existing algorithms and provides new lower bounds for 8 large and hard instances.
• Abstract（参考訳）: 0-1 Multidimensional Knapsack Problem (MKP) は古典的なNPハード組合せ最適化問題である。 本稿では,0-1 MKPを解くために,進化計算と正確なアルゴリズムを組み合わせた新しいアルゴリズムを提案する。 一連のソリューションを維持し、人口の情報を利用して優れた部分的割り当てを抽出する。 高品質な解を見つけるために、優れた部分代入によって指定された有望な探索空間を探索するために正確なアルゴリズムを適用した。 新しいソリューションは人口を更新するために使われます。 このように、良い部分的な割り当ては、人口の改善とともにより良い方向に進化する。 一般的なベンチマークセットによる大規模な実験により、我々のアルゴリズムは、アートヒューリスティックアルゴリズムであるPTEAとDQPSOの状態を上回ります。 既存のアルゴリズムよりも優れたソリューションを見つけ、8つの大規模およびハードインスタンスに新しい下限を提供する。

関連論文リスト

• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。 我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-05-28T19:02:30Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Self-adjusting optimization algorithm for solving the setunion knapsack problem [0.3128201162068913]
  set-union knapsack problem (SUKP) は制約付き合成最適化問題である。 アイテムと要素の観点からSUKPを近似する2つの自己調整最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-01-23T14:15:49Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• 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)
• Towards Solving Large-scale Expensive Optimization Problems Efficiently Using Coordinate Descent Algorithm [3.1600708674008393]
  計算予算が限られているLSEGO問題に対処するために,修正された座標 Descent アルゴリズム (MCD) を提案する。 提案アルゴリズムは,関心領域の探索と,指数速度で半分に折り畳むことで検索空間の縮小という,2つの主要なステップの恩恵を受ける。 提案アルゴリズムは,次元1000の20個のベンチマーク関数上でのデルタグルーピングと協調的共進化との比較を行った。
  論文  参考訳（メタデータ） (2020-03-07T22:48:38Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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