論文の概要: Gray-Box Optimization and the Vertex Coloring Problem
- arxiv url: http://arxiv.org/abs/2606.08128v1
- Date: Sat, 06 Jun 2026 12:12:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-09 14:42:05.860063
- Title: Gray-Box Optimization and the Vertex Coloring Problem
- Title（参考訳）: グレーボックス最適化と頂点色問題
- Authors: Johanna Gasse, Antonia Heinen, Hendrik Higl, Timo Kötzing,
- Abstract要約: グレーボックス最適化は問題固有の情報をアルゴリズムで利用できるようにするためのアプローチである。
RLS は、ランダムな 2$-coloring から始まる2$-coloring を $mathcalO(n log n)$ の時間で適切な 2$-coloring を見つけることができることを示す。
対照的に、適切な$n$-coloringから始めると、 (1+1) EA は検索空間のプラトーに付加的なガイドを提供する場合を除いて、そのような色を見つけることができない。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Gray-box optimization is an approach for making some problem-specific information available to the algorithm while still relying on fitness information as the main guide to an optimum. This approach was shown to be beneficial in various combinatorial optimization tasks and neatly captures the continuum between fully black-box algorithms and tailored algorithms. In this work, we discuss different flavors of gray-box algorithms. We show that RLS can find a proper $2$-coloring in a bipartite graph starting from a random $2$-coloring, in an expected time of $\mathcal{O}(n \log n)$. In contrast, when starting from a proper $n$-coloring, the (1+1) EA cannot find such a coloring except when offered additional guiding on plateaus of the search space. Finally, we show the run time for this setting can be much improved by using gray-box operators.
- Abstract（参考訳）: グレーボックス最適化は、アルゴリズムに問題固有の情報を利用できるようにするためのアプローチである。
このアプローチは、様々な組合せ最適化タスクにおいて有用であることが示され、完全にブラックボックスのアルゴリズムと調整されたアルゴリズムの間の連続性を適切にキャプチャする。
本研究では,グレーボックスアルゴリズムの異なるフレーバーについて論じる。
RLS は、ランダムな 2$-coloring から始まる2$-coloring を$\mathcal{O}(n \log n)$ の時間で適切な 2$-coloring を求めることができることを示す。
対照的に、適切な$n$-coloringから始めると、 (1+1) EA は検索空間のプラトーに付加的なガイドを提供する場合を除いて、そのような色を見つけることができない。
最後に、グレーボックス演算子を用いることで、この設定の実行時間を大幅に改善できることを示す。
関連論文リスト
- Neural Algorithmic Reasoning for Approximate $k$-Coloring with Recursive Warm Starts [5.645823801022895]
ノードカラー化におけるグラフニューラルネットワーク(GNN)の利用について検討する。
我々は,軽量なグリーディ局所探索アルゴリズムを導入し,暖かいスタートに使用するために$(k-1)-coloringを使用することで,それを改善することを示す。
数値実験により、局所探索アルゴリズムは小さな入力に対して優れているが、GNN$はスケールにおいて優れた性能を示すことが示された。
論文 参考訳（メタデータ） (2026-01-08T17:28:09Z) - Landscape Surrogate: Learning Decision Losses for Mathematical
Optimization Under Partial Information [48.784330281177446]
学習統合最適化の最近の研究は、最適化が部分的にのみ観察される場合や、専門家のチューニングなしに汎用性が不十分な環境では有望であることを示している。
本稿では,$fcirc mathbfg$の代替として,スムーズで学習可能なランドスケープサロゲートを提案する。
このサロゲートはニューラルネットワークによって学習可能で、$mathbfg$ソルバよりも高速に計算でき、トレーニング中に密度が高く滑らかな勾配を提供し、目に見えない最適化問題に一般化でき、交互最適化によって効率的に学習される。
論文 参考訳（メタデータ） (2023-07-18T04:29:16Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - Bayesian Optimization of Expensive Nested Grey-Box Functions [11.523746174066702]
ブラックボックス関数とホワイトボックス関数の両方からなるグレーボックス目的関数を最適化する問題を考察する。
このようなグレーボックス問題に対する一般的な定式化が与えられ、これは既存のグレーボックス最適化の定式化を特別な場合としてカバーしている。
次に、最適化駆動型アルゴリズムを設計して解決する。
論文 参考訳（メタデータ） (2023-06-08T12:18:18Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Chasing Convex Bodies and Functions with Black-Box Advice [7.895232155155041]
ブラックボックスアドバイスによる凸関数追跡の問題点を考察する。
オンラインの意思決定者は、$textitConsistency$.com($textitConsistency$.com)と呼ばれる、うまく機能するときにアドバイスに匹敵するコストを求める。
本稿では,この問題の凸性を利用して,この制限を回避できる2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-23T15:30:55Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Time Complexity Analysis of Randomized Search Heuristics for the Dynamic
Graph Coloring Problem [15.45783225341009]
エッジを現在のグラフに追加する動的設定について検討する。
次に、ランダム化された検索の予測時間を分析し、高品質な解を再計算する。
論文 参考訳（メタデータ） (2021-05-26T13:00:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。