論文の概要: Self-adjusting optimization algorithm for solving the setunion knapsack problem

• arxiv url: http://arxiv.org/abs/2202.05698v1
• Date: Sun, 23 Jan 2022 14:15:49 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-20 16:37:33.612682
• Title: Self-adjusting optimization algorithm for solving the setunion knapsack problem
• Title（参考訳）: setunion knapsack問題を解くための自己調整最適化アルゴリズム
• Authors: Congcong Wu, Xiangyun Gao, Xueyong Liu, Bowen Sun
• Abstract要約: set-union knapsack problem (SUKP) は制約付き合成最適化問題である。 アイテムと要素の観点からSUKPを近似する2つの自己調整最適化アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.3128201162068913
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The set-union knapsack problem (SUKP) is a constrained composed optimization problem. It is more difficulty for solving because values and weights depend on items and elements respectively. In this paper, we present two self-adjusting optimization algorithms for approximating SUKP from items and elements perspective respectively. By analyzing the dynamic characters in the SUKP, we design two types of self-adjusting repair and optimization operators that are based on the different loading process. We use the novel teaching-learning-based optimization algorithm (TLBO) to design a general discrete framework (DTLBO) suitable for these two types of operators. In addition, we introduce elite opposite search and natural selection mechanism into DTLBO to furtherly improve the performance of the algorithm from the perspective of population. Finally, we performed experimental comparisons on benchmark sets to verify the effectiveness of the proposed algorithm. The experimental results show that the item-based self-adjusting optimization algorithm I-DTLBO is outstanding, and the algorithm is superior to the other swarm intelligence methods for solving SUKP. IDTLBO algorithm reaches the upper boundary of the current swarm intelligence algorithms for solving SUKP in 10 instances, and gotten new upper boundary in 15 instances. The algorithm E-DTLBO based on element loading only perform slightly better on small and middle data sets, but worse on large-scale instances. It shows that element-based design is not suitable for solving SUKP.
• Abstract（参考訳）: 集合対knapsack問題(SUKP)は制約付き合成最適化問題である。 値と重みはそれぞれアイテムと要素に依存するため、解決はより困難である。 本稿では,アイテムと要素の観点からSUKPを近似する2つの自己調整最適化アルゴリズムを提案する。 SUKPの動的キャラクタを解析することにより、異なるロードプロセスに基づく2種類の自己調整修理と最適化演算子を設計する。 これら2種類の演算子に適した汎用離散フレームワーク(DTLBO)を設計するために,新しい学習型最適化アルゴリズム(TLBO)を用いる。 さらに,DTLBOには,検索と自然選択の相反するエリートな機構を導入し,集団の観点からアルゴリズムの性能をさらに向上させる。 最後に,提案アルゴリズムの有効性を検証するために,ベンチマークセットで実験的比較を行った。 実験の結果,アイテムベースの自己調整最適化アルゴリズムであるI-DTLBOは優れており,SUKPを解くための他のスワムインテリジェンス手法よりも優れていることがわかった。 IDTLBOアルゴリズムは、現在のSwarmインテリジェンスアルゴリズムの上界に到達し、SUKPを10インスタンスで解き、15インスタンスで新たな上界を得た。 要素ローディングに基づくアルゴリズムE-DTLBOは、小さなデータセットとミドルデータセットではわずかに良いが、大規模インスタンスでは悪い。 要素ベース設計はSUKPの解決には適していない。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• A Pure Quantum Approximate Optimization Algorithm Based on CNR Operation [0.0]
  汎用的な純粋量子近似最適化アルゴリズムを提案する。 このアルゴリズムは$p$レベルの分割・対数構造に構成されている。 2つの最適化問題の必要なキュービット数が10である場合、アルゴリズムの性能を詳細に示す。
  論文  参考訳（メタデータ） (2023-10-27T06:54:39Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity [17.870370505179014]
  本稿では,一階オラクル,ヘッセンベクター,ヤコビアンベクターのみを必要とする分散二段階最適化(DSBO)アルゴリズムを提案する。 このアルゴリズムの利点は、全ヘッセン行列とヤコビ行列を推定する必要がなく、それによってイット毎の複雑性が向上するということである。
  論文  参考訳（メタデータ） (2022-10-23T20:06:05Z)
• Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem [18.19836641663039]
  我々は,0-1 MKPを解くために,進化計算と正確なアルゴリズムを組み合わせた新しいアルゴリズムを提案する。 一連のソリューションを維持し、人口の情報を利用して、優れた部分的な割り当てを抽出する。 既存のアルゴリズムよりも優れた解を見つけ、大規模で難しい10のインスタンスに新しい下位境界を提供する。
  論文  参考訳（メタデータ） (2022-10-08T05:11:47Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。 我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
  論文  参考訳（メタデータ） (2021-12-09T02:27:52Z)
• Bayesian Optimization over Permutation Spaces [30.650753803587794]
  BOPS (Permutation Spaces) に対する2つのアルゴリズムの提案と評価を行った。 BOPS-Tの性能を理論的に解析し,その後悔がサブリニアに増加することを示す。 複数の合成および実世界のベンチマーク実験により、BOPS-TとBOPS-Hは、空間に対する最先端のBOアルゴリズムよりも優れた性能を示した。
  論文  参考訳（メタデータ） (2021-12-02T08:20:50Z)
• ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
  バイレベル最適化(BO)は多くの現代の機械学習問題を解決する強力なツールとして生まれてきた。 既存の勾配法では、ヤコビアンあるいはヘッセンベクトル計算による二階微分近似が必要となる。 本稿では,進化戦略(ES)に基づく新しいBOアルゴリズムを提案し,BOの過勾配における応答ヤコビ行列を近似する。
  論文  参考訳（メタデータ） (2021-10-13T19:36:50Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)

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

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