論文の概要: Stochastic Item Descent Method for Large Scale Equal Circle Packing Problem

• arxiv url: http://arxiv.org/abs/2001.08540v1
• Date: Wed, 22 Jan 2020 02:40:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-07 19:01:27.015778
• Title: Stochastic Item Descent Method for Large Scale Equal Circle Packing Problem
• Title（参考訳）: 大規模等円充填問題に対する確率アイテム降下法
• Authors: Kun He, Min Zhang, Jianrong Zhou, Yan Jin, and Chu-min Li
• Abstract要約: 勾配降下(SGD)は、機械学習領域における大規模最適化問題に対する強力な手法である。 本稿では,古典的最適化問題に対して,サンプルのバッチ選択を伴うSGDを適用した。 具体的には、単位円をランダムにバッチに分割する大規模ECPP用アイテム降下法(SIDM)を提案する。
• 参考スコア（独自算出の注目度）: 22.230497408207594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic gradient descent (SGD) is a powerful method for large-scale optimization problems in the area of machine learning, especially for a finite-sum formulation with numerous variables. In recent years, mini-batch SGD gains great success and has become a standard technique for training deep neural networks fed with big amount of data. Inspired by its success in deep learning, we apply the idea of SGD with batch selection of samples to a classic optimization problem in decision version. Given $n$ unit circles, the equal circle packing problem (ECPP) asks whether there exist a feasible packing that could put all the circles inside a circular container without overlapping. Specifically, we propose a stochastic item descent method (SIDM) for ECPP in large scale, which randomly divides the unit circles into batches and runs Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm on the corresponding batch function iteratively to speedup the calculation. We also increase the batch size during the batch iterations to gain higher quality solution. Comparing to the current best packing algorithms, SIDM greatly speeds up the calculation of optimization process and guarantees the solution quality for large scale instances with up to 1500 circle items, while the baseline algorithms usually handle about 300 circle items. The results indicate the highly efficiency of SIDM for this classic optimization problem in large scale, and show potential for other large scale classic optimization problems in which gradient descent is used for optimization.
• Abstract（参考訳）: 確率勾配勾配(SGD)は、機械学習領域における大規模最適化問題、特に多数の変数を持つ有限サム定式化のための強力な方法である。 近年、ミニバッチsgdは大きな成功を収め、大量のデータを供給したディープニューラルネットワークのトレーニングの標準技術となっている。 深層学習の成功にインスパイアされ,サンプルのバッチ選択によるSGDのアイデアを,決定バージョンにおける古典的最適化問題に適用する。 n$の単位円が与えられたとき、等円パッキング問題(ECPP)は、すべての円を重なり合うことなく円形の容器の中に配置できる、実現可能なパッキングが存在するかどうかを問う。 具体的には、単位円をランダムにバッチに分割し、対応するバッチ関数上でbroyden-fletcher-goldfarb-shanno(bfgs)アルゴリズムを実行し、計算を高速化する大規模ecppの確率アイテム降下法(sidm)を提案する。 また、バッチイテレーション中のバッチサイズを増やして、より高い品質のソリューションを得ます。 現在の最高のパッケージングアルゴリズムと比較して、SIDMは最適化プロセスの計算を大幅に高速化し、1500円のアイテムを持つ大規模インスタンスのソリューション品質を保証する一方、ベースラインアルゴリズムは一般的に300円のアイテムを扱う。 その結果,この古典的最適化問題に対するsidmの高効率性が示され,勾配降下を最適化に用いる他の大規模古典的最適化問題に対する可能性を示した。

関連論文リスト

• Optimizing Posterior Samples for Bayesian Optimization via Rootfinding [2.94944680995069]
  我々は,グローバルなルートフィンディングに基づく後方サンプルの効率的な大域的最適化手法を提案する。 内ループ最適化と外ループ最適化の両方において顕著な改善が示された。 GP-TSのサンプル平均定式化も提案する。
  論文  参考訳（メタデータ） (2024-10-29T17:57:16Z)
• A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
  既存の量子処理ユニット(QPU)がマルチレベル戦略においてサブソルバとしてどのように機能するかを実験的に検証する。 完全連結な 82$-qubit Sherrington-Kirkpatrick グラフに対して 10$ の近似解を求める。 量子最適化の結果は古典学と比較して解の質に関して競争力がある。
  論文  参考訳（メタデータ） (2024-08-14T20:06:32Z)
• A Particle-based Sparse Gaussian Process Optimizer [5.672919245950197]
  本稿では,下降の動的過程を利用した新しいスワム・スワムベースのフレームワークを提案する。 このアプローチの最大の利点は、降下を決定する前に現在の状態についてより深い探索を行うことである。
  論文  参考訳（メタデータ） (2022-11-26T09:06:15Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Learning the Step-size Policy for the Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Algorithm [3.7470451129384825]
  本稿では,L-BFGSアルゴリズムのステップサイズポリシの学習方法について考察する。 入力として電流勾配の局所的な情報を用いたニューラルネットワークアーキテクチャを提案する。 ステップ長ポリシは、同様の最適化問題のデータから学習され、目的関数のさらなる評価を回避し、出力ステップが予め定義された間隔内に留まることを保証します。
  論文  参考訳（メタデータ） (2020-10-03T09:34:03Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Adaptive Large Neighborhood Search for Circle Bin Packing Problem [8.855116523397935]
  我々は、円ビンパッキング問題(CBPP)と呼ばれる新しいパッキング問題に対処する。 CBPPは、使用済みのビンの数を最小限に抑えるために、複数の正方形のビンに円のアイテムを密に詰め込むことである。 本稿では,Corner Occupying Action (GACOA) を用いたグレディアルゴリズムを用いて,初期レイアウトを構築する適応型大近傍探索(ALNS)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-20T10:14:15Z)

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

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