論文の概要: A random-key GRASP for combinatorial optimization
- arxiv url: http://arxiv.org/abs/2405.18681v1
- Date: Wed, 29 May 2024 01:07:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-30 21:13:51.633361
- Title: A random-key GRASP for combinatorial optimization
- Title（参考訳）: 組合せ最適化のためのランダムキーGRASP
- Authors: Antonio A. Chaves, Mauricio G. C. Resende, Ricardo M. A. Silva,
- Abstract要約: 本稿ではランダムキーGRASPのための問題非依存コンポーネントと問題依存デコーダについて述べる。
概念実証として、ランダムキーGRASPは5つのNPハード最適化問題でテストされる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper proposes a problem-independent GRASP metaheuristic using the random-key optimizer (RKO) paradigm. GRASP (greedy randomized adaptive search procedure) is a metaheuristic for combinatorial optimization that repeatedly applies a semi-greedy construction procedure followed by a local search procedure. The best solution found over all iterations is returned as the solution of the GRASP. Continuous GRASP (C-GRASP) is an extension of GRASP for continuous optimization in the unit hypercube. A random-key optimizer (RKO) uses a vector of random keys to encode a solution to a combinatorial optimization problem. It uses a decoder to evaluate a solution encoded by the vector of random keys. A random-key GRASP is a C-GRASP where points in the unit hypercube are evaluated employing a decoder. We describe random key GRASP consisting of a problem-independent component and a problem-dependent decoder. As a proof of concept, the random-key GRASP is tested on five NP-hard combinatorial optimization problems: traveling salesman problem, tree of hubs location problem, Steiner triple covering problem, node capacitated graph partitioning problem, and job sequencing and tool switching problem.
- Abstract（参考訳）: 本稿ではランダムキーオプティマイザ(RKO)パラダイムを用いた問題独立なGRASPメタヒューリスティックを提案する。
GRASP (greedy randomized Adaptive search procedure) は、半グレディな構成手順を繰り返し適用し、その後局所的な探索手順を施すメタヒューリスティックな組合せ最適化法である。
すべてのイテレーションで見つかる最良のソリューションは、GRASPのソリューションとして返される。
Continuous GRASP (C-GRASP) は、ユニットハイパーキューブの継続的な最適化のためのGRASPの拡張である。
ランダムキー最適化器(RKO)は、ランダムキーのベクトルを用いて、組合せ最適化問題の解を符号化する。
デコーダを使用して、ランダムキーのベクトルによって符号化されたソリューションを評価する。
ランダムキーGRASPは、デコーダを用いてユニットハイパーキューブの点を評価するC-GRASPである。
問題非依存のコンポーネントと問題依存のデコーダからなるランダムキーGRASPについて述べる。
概念実証として、ランダムキーGRASPは、旅行セールスマン問題、ハブのツリー配置問題、スタイナー三重被覆問題、ノード容量グラフ分割問題、ジョブシークエンシングとツール切替問題という5つのNPハード組合せ最適化問題でテストされる。
関連論文リスト
- A Random-Key Optimizer for Combinatorial Optimization [0.0]
Random-Key Hubs (RKO) は最適化問題に適した汎用的で効率的な局所探索手法である。
ランダムキーの概念を用いて、RKOは解をランダムキーのベクトルとしてエンコードし、後に問題固有のデコーダを介して実現可能な解へとデコードする。
RKOフレームワークは古典的メタヒューリスティクスの多元体を組み合わせ、それぞれが独立して、あるいは並列に動作可能であり、エリートソリューションプールを通じてソリューション共有が促進される。
論文 参考訳（メタデータ） (2024-11-06T22:23:29Z) - Finding Quantum Codes via Riemannian Optimization [0.0]
本稿では、既知の量子ノイズチャネルに対して最適に修正可能な部分空間符号を求めるための新しい最適化手法を提案する。
各候補部分空間コードに対して、まず、コードが修正可能であるかのように、ユニバーサルリカバリマップを関連付け、性能を最大化する。
固定次元の符号の集合は複素値のスティーフェル多様体でパラメータ化される。
論文 参考訳（メタデータ） (2024-07-11T12:03:41Z) - A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical
Initialization [107.07093621337084]
正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。
1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。
有名な座標降下法に基づく新しいN-Cut解法を提案する。
論文 参考訳（メタデータ） (2023-11-26T07:11:58Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳（メタデータ） (2023-05-22T17:43:34Z) - Approximately Optimal Core Shapes for Tensor Decompositions [7.1439425093981574]
我々は,高次特異値への接続による再構成誤差の証明可能な近似保証付きアルゴリズムを提案する。
具体的には、NPハードであることが証明された新しいタッカーパッキング問題を導入し、マトロイドを用いた2次元クナップサック問題への還元に基づく制約時間近似スキームを提案する。
論文 参考訳（メタデータ） (2023-02-08T05:24:01Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - On a class of geodesically convex optimization problems solved via
Euclidean MM methods [50.428784381385164]
ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。
最終的に、より広い範囲、より広い範囲の作業を支援するのです。
論文 参考訳（メタデータ） (2022-06-22T23:57:40Z) - Optimization of Robot Trajectory Planning with Nature-Inspired and
Hybrid Quantum Algorithms [0.0]
産業規模でロボット軌道計画問題を解く。
我々のエンドツーエンドソリューションは、高度に多目的なランダムキーアルゴリズムとモデル積み重ねとアンサンブル技術を統合している。
我々は、後者が我々のより大きなパイプラインにどのように統合され、問題に対する量子対応ハイブリッドソリューションを提供するかを示す。
論文 参考訳（メタデータ） (2022-06-08T02:38:32Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - Combining Reinforcement Learning and Constraint Programming for
Combinatorial Optimization [5.669790037378094]
目標は、有限個の可能性の集合の中で最適解を見つけることである。
深部強化学習(DRL)はNP-ハード最適化問題を解くことを約束している。
制約プログラミング(CP)は最適化問題を解決する汎用ツールである。
本研究では,最適化問題の解法としてDRLとCPを用いた汎用ハイブリッド手法を提案する。
論文 参考訳（メタデータ） (2020-06-02T13:54:27Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。