論文の概要: Adaptive Large Neighborhood Search for Circle Bin Packing Problem

• arxiv url: http://arxiv.org/abs/2001.07709v1
• Date: Mon, 20 Jan 2020 10:14:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-08 05:41:27.413251
• Title: Adaptive Large Neighborhood Search for Circle Bin Packing Problem
• Title（参考訳）: 円ビン充填問題に対する適応型大規模近傍探索
• Authors: Kun He, Kevin Tole, Fei Ni, Yong Yuan, Linyun Liao
• Abstract要約: 我々は、円ビンパッキング問題(CBPP)と呼ばれる新しいパッキング問題に対処する。 CBPPは、使用済みのビンの数を最小限に抑えるために、複数の正方形のビンに円のアイテムを密に詰め込むことである。 本稿では,Corner Occupying Action (GACOA) を用いたグレディアルゴリズムを用いて,初期レイアウトを構築する適応型大近傍探索(ALNS)アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 8.855116523397935
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address a new variant of packing problem called the circle bin packing problem (CBPP), which is to find a dense packing of circle items to multiple square bins so as to minimize the number of used bins. To this end, we propose an adaptive large neighborhood search (ALNS) algorithm, which uses our Greedy Algorithm with Corner Occupying Action (GACOA) to construct an initial layout. The greedy solution is usually in a local optimum trap, and ALNS enables multiple neighborhood search that depends on the stochastic annealing schedule to avoid getting stuck in local minimum traps. Specifically, ALNS perturbs the current layout to jump out of a local optimum by iteratively reassigns some circles and accepts the new layout with some probability during the search. The acceptance probability is adjusted adaptively using simulated annealing that fine-tunes the search direction in order to reach the global optimum. We benchmark computational results against GACOA in heterogeneous instances. ALNS always outperforms GACOA in improving the objective function, and in several cases, there is a significant reduction on the number of bins used in the packing.
• Abstract（参考訳）: そこで本研究では,複数の正方形箱に円のアイテムを密に詰め込み,使用済みの箱の数を最小限に抑えることを目的とした,CBPP (Circle bin packing problem) と呼ばれるパッキング問題に対処する。 そこで本研究では,Corner Occupying Action (GACOA) を用いたGreedy Algorithm を用いた適応型大近傍探索 (ALNS) アルゴリズムを提案する。 グリーディ解は通常局所最適トラップであり、alnは局所最小トラップに詰まるのを避けるために確率的なアニーリングスケジュールに依存する複数の近傍探索を可能にする。 具体的には、alnは、ある円を反復的に再割り当てすることで、局所最適から飛び出す現在のレイアウトを摂動させ、検索中に、ある確率で新しいレイアウトを受け入れる。 受理確率は、グローバルな最適点に到達するために探索方向を微調整するシミュレートアニールを用いて適応的に調整される。 異種インスタンスのGACOAに対して計算結果をベンチマークする。 ALNSは常にGACOAより優れており、いくつかのケースでは包装に使用されるビンの数が大幅に減少している。

関連論文リスト

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
  我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。 使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。 我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
  論文  参考訳（メタデータ） (2023-06-29T14:57:56Z)
• Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem [18.19836641663039]
  我々は,0-1 MKPを解くために,進化計算と正確なアルゴリズムを組み合わせた新しいアルゴリズムを提案する。 一連のソリューションを維持し、人口の情報を利用して、優れた部分的な割り当てを抽出する。 既存のアルゴリズムよりも優れた解を見つけ、大規模で難しい10のインスタンスに新しい下位境界を提供する。
  論文  参考訳（メタデータ） (2022-10-08T05:11:47Z)
• An Improved Greedy Algorithm for Subset Selection in Linear Estimation [5.994412766684842]
  有限個の予測位置において、観測値の最もよい推定値を与えるような k 個の位置の集合を求める空間場における部分選択問題を考える。 観測選択の1つのアプローチは、空間の格子離散化を行い、グリードアルゴリズムを用いて近似解を得ることである。 本稿では,予測位置と予測位置によって形成される傾斜角の遠心点のみからなる探索空間を考慮し,計算複雑性を低減する手法を提案する。
  論文  参考訳（メタデータ） (2022-03-30T05:52:16Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Stagnation Detection in Highly Multimodal Fitness Landscapes [0.0]
  局所最適化から逃れるためのランダム化探索のメカニズムとして,定常検出法が提案されている。 本稿では,探索半径をより注意深く制御するために,静止検出に付加できる半径メモリと呼ばれる新しい機構について検討する。 このアイデアはSD-RLS$textm$と呼ばれるアルゴリズムで実装され、それまでのステージング検出の変種と比較して高速化された。
  論文  参考訳（メタデータ） (2021-04-09T14:33:52Z)
• CobBO: Coordinate Backoff Bayesian Optimization [45.53400129323848]
  グローバルな景観のスムーズな近似を捉えるために,CobBO(Coordinate Backoff Bayesian Optimization)を導入する。 CobBOは、数十から数百の次元に対する他の最先端の手法に匹敵するソリューションを見つける。
  論文  参考訳（メタデータ） (2021-01-13T15:39:32Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。 本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。 実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
  論文  参考訳（メタデータ） (2020-07-20T12:07:48Z)
• 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)
• Stochastic Item Descent Method for Large Scale Equal Circle Packing Problem [22.230497408207594]
  勾配降下(SGD)は、機械学習領域における大規模最適化問題に対する強力な手法である。 本稿では,古典的最適化問題に対して,サンプルのバッチ選択を伴うSGDを適用した。 具体的には、単位円をランダムにバッチに分割する大規模ECPP用アイテム降下法(SIDM)を提案する。
  論文  参考訳（メタデータ） (2020-01-22T02:40:31Z)

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

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