論文の概要: Generalizing and Unifying Gray-box Combinatorial Optimization Operators

• arxiv url: http://arxiv.org/abs/2407.06742v1
• Date: Tue, 9 Jul 2024 10:44:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-10 18:26:46.474617
• Title: Generalizing and Unifying Gray-box Combinatorial Optimization Operators
• Title（参考訳）: Gray-box Combinatorial Optimization Operatorの一般化と統一
• Authors: Francisco Chicano, Darrell Whitley, Gabriela Ochoa, Renato Tinós,
• Abstract要約: 本稿では、最適化問題に対するすべての既知のグレーボックス演算子を包含する一般的なフレームワークを提案する。 また,グレイボックス・クロスオーバー演算子のスピードアップを数学的に説明し,グレイボックス・ヒルクライマーの運動改善の効率的な同定について述べる。 本稿では, 2つの関連する置換問題に対して, 効率的な登山とクロスオーバーを提案することによって, 新たな枠組みの力を説明する。
• 参考スコア（独自算出の注目度）: 2.6624014064407717
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gray-box optimization leverages the information available about the mathematical structure of an optimization problem to design efficient search operators. Efficient hill climbers and crossover operators have been proposed in the domain of pseudo-Boolean optimization and also in some permutation problems. However, there is no general rule on how to design these efficient operators in different representation domains. This paper proposes a general framework that encompasses all known gray-box operators for combinatorial optimization problems. The framework is general enough to shed light on the design of new efficient operators for new problems and representation domains. We also unify the proofs of efficiency for gray-box hill climbers and crossovers and show that the mathematical property explaining the speed-up of gray-box crossover operators, also explains the efficient identification of improving moves in gray-box hill climbers. We illustrate the power of the new framework by proposing an efficient hill climber and crossover for two related permutation problems: the Linear Ordering Problem and the Single Machine Total Weighted Tardiness Problem.
• Abstract（参考訳）: グレーボックス最適化は、最適化問題の数学的構造に関する情報を活用して効率的な探索演算子を設計する。 擬ブール最適化の領域では、効率的な登山家やクロスオーバー作用素が提案され、またいくつかの置換問題でも提案されている。 しかし、これらの効率的な作用素を異なる表現領域で設計する方法には一般的な規則はない。 本稿では、組合せ最適化問題に対するすべての既知のグレーボックス演算子を包含する一般的なフレームワークを提案する。 このフレームワークは、新しい問題や表現領域のための新しい効率的な演算子の設計に光を当てるのに十分である。 また,グレイボックス・ヒルクライマーとクロスオーバーの効率性の証明を統一し,グレイボックス・クロスオーバー演算子のスピードアップを説明する数学的性質を示すとともに,グレイボックス・ヒルクライマーの移動改善の効率的な同定について説明する。 線形順序問題と単機全重度目標問題という2つの関連する置換問題に対して,効率的な登山者および交差問題を提案することで,新しい枠組みの力を説明する。

関連論文リスト

• Permutation Picture of Graph Combinatorial Optimization Problems [3.607883549126603]
  本稿では、置換に基づく表現を用いて、幅広いグラフ最適化問題を定式化するフレームワークを提案する。 これらの問題には、旅行セールスマンの問題、最大独立セット、最大カット、その他様々な問題が含まれる。
  論文  参考訳（メタデータ） (2024-10-22T15:36:04Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• Bayesian Optimization of Expensive Nested Grey-Box Functions [11.523746174066702]
  ブラックボックス関数とホワイトボックス関数の両方からなるグレーボックス目的関数を最適化する問題を考察する。 このようなグレーボックス問題に対する一般的な定式化が与えられ、これは既存のグレーボックス最適化の定式化を特別な場合としてカバーしている。 次に、最適化駆動型アルゴリズムを設計して解決する。
  論文  参考訳（メタデータ） (2023-06-08T12:18:18Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• Branch & Learn for Recursively and Iteratively Solvable Problems in Predict+Optimize [9.772500430303285]
  本稿では,解決時に未知のパラメータを含む最適化問題に取り組むための,予測+のフレームワークであるブランチ・アンド・ラーニングを提案する。 我々のフレームワークは、それらを退化的な再帰形式と見なして反復アルゴリズムにも適用している。
  論文  参考訳（メタデータ） (2022-05-01T08:41:30Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  ブランチ・アンド・カット(ブランチ・アンド・カット)として知られる分岐・アンド・バウンドアルゴリズムにおける切断平面の組み入れは、現代の整数計画解法のバックボーンを形成する。 入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。 この分析の主な応用は、機械学習を用いてブランチ・アンド・カット時にどの切断面を適用するかを決定するためのサンプルの複雑性保証を導出することである。
  論文  参考訳（メタデータ） (2022-04-15T03:32:40Z)
• Improved Algorithm for the Network Alignment Problem with Application to Binary Diffing [0.0]
  本稿では,ネットワークアライメント問題に対処する新しいアルゴリズムを提案する。 実験により,提案モデルが他の最先端の解法よりも優れていることが示された。 また,バイナリ・ディッフィング問題に対処するため,本手法の応用を提案する。
  論文  参考訳（メタデータ） (2021-12-31T07:52:14Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。 本研究では,理論特性の知見を得るための後悔分析法を提案する。 二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
  論文  参考訳（メタデータ） (2021-02-26T10:15:57Z)

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

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