論文の概要: Markov Chain-based Optimization Time Analysis of Bivalent Ant Colony Optimization for Sorting and LeadingOnes
- arxiv url: http://arxiv.org/abs/2405.03353v1
- Date: Mon, 6 May 2024 11:02:50 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-07 14:06:06.112503
- Title: Markov Chain-based Optimization Time Analysis of Bivalent Ant Colony Optimization for Sorting and LeadingOnes
- Title（参考訳）: マルコフ連鎖に基づく2価アントコロニー最適化時間解析
- Authors: Matthias Kergaßner, Oliver Keszocze, Rolf Wanka,
- Abstract要約: 2つのフェロモン値の比がバイバレントACO(BACO)のランタイム挙動を著しく制御していることを示す。
我々は,フェロモンが解法に与える影響に関して,大幅に単純化されたアリアルゴリズムを持っているにもかかわらず,その問題の期待する最適化時間に対する既知の境界であるOneMax(O(nlog n)$)とLeadingOnes(O(n2)$)は,我々のアプローチの副産物として再生産可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: So far, only few bounds on the runtime behavior of Ant Colony Optimization (ACO) have been reported. To alleviate this situation, we investigate the ACO variant we call Bivalent ACO (BACO) that uses exactly two pheromone values. We provide and successfully apply a new Markov chain-based approach to calculate the expected optimization time, i. e., the expected number of iterations until the algorithm terminates. This approach allows to derive exact formulae for the expected optimization time for the problems Sorting and LeadingOnes. It turns out that the ratio of the two pheromone values significantly governs the runtime behavior of BACO. To the best of our knowledge, for the first time, we can present tight bounds for Sorting ($\Theta(n^3)$) with a specifically chosen objective function and prove the missing lower bound $\Omega(n^2)$ for LeadingOnes which, thus, is tightly bounded by $\Theta(n^2)$. We show that despite we have a drastically simplified ant algorithm with respect to the influence of the pheromones on the solving process, known bounds on the expected optimization time for the problems OneMax ($O(n\log n)$) and LeadingOnes ($O(n^2)$) can be re-produced as a by-product of our approach. Experiments validate our theoretical findings.
- Abstract（参考訳）: これまでのところ、Ant Colony Optimization(ACO)のランタイム動作に関する制限はわずかしか報告されていない。
この状況を緩和するため、正確に2つのフェロモン値を使用するBivalent ACO (BACO) と呼ばれる ACO 変種について検討する。
我々は、期待される最適化時間を計算するために、新しいマルコフ連鎖に基づくアプローチを提供し、うまく適用する。
E
アルゴリズムが終了するまでのイテレーション数は予想される。
このアプローチでは、SortingとLeadingOnesの問題に対して、期待される最適化時間に関する正確な公式を導出することができる。
その結果、2つのフェロモン値の比がBACOのランタイムの挙動を著しく制御していることが判明した。
我々の知る限り、初めてSorting(\Theta(n^3)$)の厳密なバウンダリを選択的に選択された目的関数で提示し、LeadingOnesの不足する低いバウンダリ$\Omega(n^2)$を証明できます。
フェロモンが解法に与える影響に関して、大幅に単純化されたアリアルゴリズムがあるにもかかわらず、その問題の最適化時間に対する既知の境界であるOneMax(O(n\log n)$)とLeadingOnes(O(n^2)$)は、我々のアプローチの副産物として再生産可能であることを示す。
実験は理論的な結果を検証する。
関連論文リスト
- Stopping Bayesian Optimization with Probabilistic Regret Bounds [1.4141453107129403]
事実上の停止規則を$(epsilon, delta)$-criterionに置き換えることを検討する。
本研究では,後部から引き出された限られた数を用いて,この条件を実際に検証する方法を示す。
論文 参考訳（メタデータ） (2024-02-26T18:34:58Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms [15.038210624870656]
2つの目的を持つマルチアーメッド・バンドイット(MAB)問題: (i) 最適なアームに対する迅速な識別とコミットメント、および (ii) 連続したラウンドで連続して$T$の報酬。
本稿では,これら2つの目的を達成することを目的としたemphRegret Best Arm Identification (ROBAI)を紹介する。
論文 参考訳（メタデータ） (2023-09-01T17:12:43Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Optimal Mutation Rates for the $(1+\lambda)$ EA on OneMax [1.0965065178451106]
我々は、最適な突然変異率の分析を、OneMax問題の2つの変種に拡張する。
すべての集団サイズを2i mid 0 le i le 18$で計算します。
我々の結果は、一般的な進化的アプローチを測ることのできる低い境界を提供するばかりではない。
論文 参考訳（メタデータ） (2020-06-20T01:23:14Z) - Does Comma Selection Help To Cope With Local Optima [9.853329403413701]
我々は、$(mu,lambda)$EAが$(mu+lambda)$EAに対してランタイム上の優位性をもたらすことはないことを示した。
これは、低次項から遠ざかるマルチモーダル問題に対する非エリートアルゴリズムの最初の実行時結果である。
論文 参考訳（メタデータ） (2020-04-02T21:39:33Z) - A New Randomized Primal-Dual Algorithm for Convex Optimization with
Optimal Last Iterate Rates [16.54912614895861]
我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。
我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。
その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
論文 参考訳（メタデータ） (2020-03-03T03:59:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。