論文の概要: Hybridizing a Grouping Metaheuristic with Reinforcement Learning for the One-Dimensional Bin Packing Problem
- arxiv url: http://arxiv.org/abs/2607.02315v1
- Date: Thu, 02 Jul 2026 15:25:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-03 19:45:08.901998
- Title: Hybridizing a Grouping Metaheuristic with Reinforcement Learning for the One-Dimensional Bin Packing Problem
- Title（参考訳）: 一次元バンドル問題に対する強化学習によるグループ化メタヒューリスティックのハイブリッド化
- Abstract要約: 本稿ではFalkenauerのHybrid Grouping Genetic Algorithmを統合したハイブリッドアルゴリズムRL-HGGAを提案する。
平均計算時間を64.22秒から1.29秒に短縮し,50倍の高速化を実現した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The one-dimensional bin packing problem (1D-BPP) is a canonical NP-hard combinatorial optimization problem with broad industrial applications. We propose RL-HGGA, a hybrid algorithm that integrates Falkenauer's Hybrid Grouping Genetic Algorithm (HGGA) with a tabular Q-learning controller. Rather than applying genetic operators at fixed probabilities, a Q-learning agent dynamically selects among eight macro-actions -- including BPCX crossover, light and heavy mutation, Martello-Toth local search, and population restart -- based on an eight-dimensional state representation encoding generation progress, stagnation level, optimality gap, average fitness, population variance, and average bin fill rate. The agent is trained with an epsilon-greedy policy over 400 episodes, with epsilon decaying to 0.05. Experiments on standard benchmark families (Falkenauer T/U, Scholl 1-3, Hard28) show that RL-HGGA achieves an average optimality gap of 0.95% -- competitive with HGGA (0.75%) and well below FFD (2.47%) -- while reducing mean computation time from 64.22 s to 1.29 s, a 50x speedup. These results demonstrate that learned adaptive operator selection can achieve near-HGGA solution quality at a fraction of the computational cost.
- Abstract（参考訳）: 1次元ビンパッキング問題(英: 1-dimensional bin packing problem)は、広義の産業応用を伴う標準NPハード組合せ最適化問題である。
本稿では,FalkenauerのHybrid Grouping Genetic Algorithm(HGGA)と表型Qラーニングコントローラを組み合わせたハイブリッドアルゴリズムRL-HGGAを提案する。
特定の確率で遺伝的演算子を適用するのではなく、Q学習エージェントは、生成の進行、停滞レベル、最適性ギャップ、平均適合度、集団分散、平均ビンフィリング率に基づいて、BPCXクロスオーバー、軽い突然変異、マーテロー・トゥース局所探索、人口再起動を含む8つのマクロアクションを動的に選択する。
この薬剤は400回以上のエプシロン欲求政策で訓練され、エプシロンは0.05に低下する。
標準ベンチマークファミリ(Falkenauer T/U, Scholl 1-3, Hard28)の実験によると、RL-HGGAの平均最適性ギャップは0.95%であり、HGGA(0.75%)と競合しFFD(2.47%)よりかなり低い。
これらの結果は、学習した適応演算子選択が、計算コストのごく一部で、ほぼHGGAの解の質を達成できることを示した。
関連論文リスト
- Towards Robust Training in NNGPT AutoML Pipeline: A Loss-Optimizer Pairing Selection Study [48.83701310501069]
本稿では, 一つのレシピがヘテロジニアスなアーキテクチャプールに十分であるか, 最適ペアリングが構造的に多様なモデルによって異なるかを検討する。
我々は,CEL(Cross-Entropy),NLL(Negative Log-Likelihood),および最近導入された遺伝学的に進化したNGL損失を,LEMURヘテロジニアス・アーキテクチャー・プールの6つの画像分類データセット上に提示したベースモデル間で比較検討した。
我々の結果は、単一のペアリングが普遍的に最適でないことを確認した。AdamやAdamWとのクロスエントロピーは、最も堅牢な選択である。
論文 参考訳（メタデータ） (2026-06-18T20:51:42Z) - L-System Genetic Encoding for Scalable Neural Network Evolution: A Comparison with Direct Matrix Encoding [45.88028371034407]
ニューラルネットワークのための正式なL-Systemベースの遺伝子アルファベットLsysと、Wp1hgnというニューラルネットワーク遺伝子モデリングツールが導入された。
LsysとMatrixのニューラルネットワークトポロジ遺伝子エンコーディング法は、24回の実験的実行で比較される。
論文 参考訳（メタデータ） (2026-04-23T18:31:26Z) - Quantum-Assisted Optimal Rebalancing with Uncorrelated Asset Selection for Algorithmic Trading Walk-Forward QUBO Scheduling via QAOA [0.2538209532048867]
ポートフォリオ構築と再バランスのためのハイブリッド古典量子フレームワークを提案する。
我々の主な貢献は、ポートフォリオ再バランススケジュールを擬似非制約バイナリ最適化問題として定式化することである。
このアプローチは、動的リバランシングを、変分量子法に対応可能な構造化されたバイナリスケジューリング問題として再キャストする。
論文 参考訳（メタデータ） (2026-03-04T15:15:55Z) - GEGO: A Hybrid Golden Eagle and Genetic Optimization Algorithm for Efficient Hyperparameter Tuning in Resource-Constrained Environments [4.417564179511245]
HyperEGOチューニングは、ハイパーサーチネットワークにおいて、重要ではあるが計算コストのかかるステップである。
ゴールデンイーグル最適化(GEGO)は、ゴールデンイーグル演算子の選択と突然変異のハイブリッド移動戦略を統合する。
GEGOは標準の単調、マルチモーダル、複合ベンチマーク関数で評価される。
論文 参考訳（メタデータ） (2026-01-21T05:35:38Z) - Edge Collaborative Gaussian Splatting with Integrated Rendering and Communication [69.23838350582764]
エッジ協調(ECO-GS)では,各ユーザが小さなGSモデルに切り替えて忠実さを保証し,遠隔大GSモデルで忠実さを保証できる。
低コストのレンダリングステータスとエッジパワー割り当てを協調的に最適化する統合通信(IRAC)を提案する。
論文 参考訳（メタデータ） (2025-10-26T15:33:29Z) - QSpark: Towards Reliable Qiskit Code Generation [1.1787037402510556]
量子回路はエラー耐性を持つ必要があるが、Granite-20B-CodeやStarCoderのようなLCMは欠陥のあるQiskitコードを出力することが多い。
グループ相対ポリシー最適化(GRPO)とOdds-Ratio Preference Optimization(ORPO)の2つのRL法を用いてQwen2.5-Coder-32Bモデルを微調整した。
Qiskit HumanEvalベンチマークでは、ORPOが56.29%のPass@1(Granite-8B-QK上ではapprox+10$ pp)に達し、GRPOが49%に達した。
論文 参考訳（メタデータ） (2025-07-16T21:27:31Z) - Genetic Algorithm with Innovative Chromosome Patterns in the Breeding Process [0.0]
遺伝的アルゴリズム(英: Genetic Algorithm with Border Trades、GAB)は、繁殖過程に新しい染色体パターンを組み込むことで探索を強化する、標準的な遺伝的アルゴリズムの新たな修正である。
GABは、標準的な遺伝的アルゴリズムと比較して、複雑なジョブスケジューリング問題に対する最大8倍の適合性と10倍の高速化を実現している。
論文 参考訳（メタデータ） (2025-01-30T07:35:43Z) - Toward Capturing Genetic Epistasis From Multivariate Genome-Wide Association Studies Using Mixed-Precision Kernel Ridge Regression [4.356528958652799]
英国バイオバンクの305K患者を対象としたGWAS(Genome-Wide Association Studies)の出力精度保存混合精度計算の性能を向上する。
低精度GPU演算によるデータ移動ゲインの強化によるタイル中心適応精度線形代数技術
ほぼ完全なAlpsシステム上で1.805の混合精度ExaOp/sで、最先端のCPU専用REGENIE GWASソフトウェアより5桁高い4精度のColeskyベースの解法を新たに導入する。
論文 参考訳（メタデータ） (2024-09-03T08:50:42Z) - Ant Colony Sampling with GFlowNets for Combinatorial Optimization [68.84985459701007]
Generative Flow Ant Colony Sampler (GFACS)は、階層的に償却推論と並列探索を組み合わせた新しいメタヒューリスティック手法である。
提案手法はまず,生成フローネットワーク(GFlowNets)を利用して,解空間上のエンフルティモーダル事前分布を補正する。
この前者は、Ant Colony Optimization (ACO) の精神で並列探索によって更新され、後部分布がほぼ最適解を生成する。
論文 参考訳（メタデータ） (2024-03-11T16:26:06Z) - DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
グラフベースの拡散フレームワークであるDIFUSCOを導入する。
本フレームワークは, NPC問題を離散0, 1ベクトル最適化問題とみなす。
MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。
論文 参考訳（メタデータ） (2023-02-16T11:13:36Z) - Massively Parallel Genetic Optimization through Asynchronous Propagation
of Populations [50.591267188664666]
Propulateは、グローバル最適化のための進化的最適化アルゴリズムとソフトウェアパッケージである。
提案アルゴリズムは, 選択, 突然変異, 交叉, 移動の変種を特徴とする。
Propulateは解の精度を犠牲にすることなく、最大で3桁高速であることがわかった。
論文 参考訳（メタデータ） (2023-01-20T18:17:34Z) - ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning [91.13797346047984]
本稿では,2次最適化アルゴリズムであるADAHESSIANを紹介する。
ADAHESSIANは、他の適応最適化手法と比較して、新しい最先端の成果を大きなマージンで達成することを示す。
論文 参考訳（メタデータ） (2020-06-01T05:00:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。