論文の概要: Convergence and Running Time of Time-dependent Ant Colony Algorithms
- arxiv url: http://arxiv.org/abs/2501.10810v1
- Date: Sat, 18 Jan 2025 16:20:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-22 14:23:37.986974
- Title: Convergence and Running Time of Time-dependent Ant Colony Algorithms
- Title（参考訳）: 時間依存型アントコロニーアルゴリズムの収束と実行時間
- Authors: Bodo Manthey, Jesse van Rhijn, Ashkan Safari, Tjark Vredeveld,
- Abstract要約: Ant Colony Optimization (ACO) はアリの捕食行動にインスパイアされたよく知られた手法である。
我々は、AttiratanasunthronとFakcharoenpholの$n$-ANTアルゴリズムの2つの時間依存的な適応について考察する。
以上の結果から,n$-ANT/tdev は最短経路問題に対して極端ポリノミカル時間以下であることがわかった。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Ant Colony Optimization (ACO) is a well-known method inspired by the foraging behavior of ants and is extensively used to solve combinatorial optimization problems. In this paper, we first consider a general framework based on the concept of a construction graph - a graph associated with an instance of the optimization problem under study, where feasible solutions are represented by walks. We analyze the running time of this ACO variant, known as the Graph-based Ant System with time-dependent evaporation rate (GBAS/tdev), and prove that the algorithm's solution converges to the optimal solution of the problem with probability 1 for a slightly stronger evaporation rate function than was previously known. We then consider two time-dependent adaptations of Attiratanasunthron and Fakcharoenphol's $n$-ANT algorithm: $n$-ANT with time-dependent evaporation rate ($n$-ANT/tdev) and $n$-ANT with time-dependent lower pheromone bound ($n$-ANT/tdlb). We analyze both variants on the single destination shortest path problem (SDSP). Our results show that $n$-ANT/tdev has a super-polynomial time lower bound on the SDSP. In contrast, we show that $n$-ANT/tdlb achieves a polynomial time upper bound on this problem.
- Abstract（参考訳）: アントコロニー最適化(Ant Colony Optimization, ACO)は、アリの捕食行動にインスパイアされたよく知られた手法であり、組合せ最適化の問題を解決するために広く用いられている。
本稿では、まず、構築グラフの概念に基づく一般的なフレームワークについて考察する。これは研究中の最適化問題のインスタンスに関連付けられたグラフであり、実現可能な解はウォークによって表現される。
時間依存蒸発率 (GBAS/tdev) を持つグラフベースAntシステム (Graph-based Ant System) として知られるこのACO変種の実行時間を分析し、アルゴリズムの解が、以前よりもやや強い蒸発率関数に対する確率1の最適解に収束することを証明した。
次に、Attiratanasunthron と Fakcharoenphol の $n$-ANT アルゴリズムを時間依存の蒸発速度 (n$-ANT/tdev) を持つ $n$-ANT と、時間依存の低フェロモン境界 (n$-ANT/tdlb) を持つ $n$-ANT の2つの時間依存的な適応を考える。
目的最短経路問題(SDSP)の両変種を解析する。
以上の結果から,$n$-ANT/tdev は SDSP 上の超ポリノミカル時間以下であることがわかった。
対照的に、$n$-ANT/tdlb が多項式時間上界を達成することを示す。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) on the Concatenated Trap Function [2.038038953957366]
GOMEAは、リンク学習を利用して問題構造を効率的に活用する進化的アルゴリズムである。
GOMEAは確率の高い$O(m32k)$で解くことができ、$m$はサブファンクションの数、$k$はサブファンクションの長さである。
これは (1+1) 進化的 EA と比較して大きなスピードアップであり、これは$O(ln(m)(mk)k)$期待される評価を必要とする。
論文 参考訳（メタデータ） (2024-07-11T09:37:21Z) - Markov Chain-based Optimization Time Analysis of Bivalent Ant Colony Optimization for Sorting and LeadingOnes [0.0]
2つのフェロモン値の比がバイバレントACO(BACO)のランタイム挙動を著しく制御していることを示す。
我々は,フェロモンが解法に与える影響に関して,大幅に単純化されたアリアルゴリズムを持っているにもかかわらず,その問題の期待する最適化時間に対する既知の境界であるOneMax(O(nlog n)$)とLeadingOnes(O(n2)$)は,我々のアプローチの副産物として再生産可能であることを示す。
論文 参考訳（メタデータ） (2024-05-06T11:02:50Z) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - 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) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Fast Learning for Renewal Optimization in Online Task Scheduling [18.935043109084543]
本稿では,リニューアル・リワードシステムのオンライン最適化について考察する。
タスク型ベクトルの確率分布は未知である。
提案アルゴリズムは,古典的なRobins-Monroイテレーションに従って更新される補助変数を用いる。
論文 参考訳（メタデータ） (2020-07-18T22:44:13Z) - A new regret analysis for Adam-type algorithms [78.825194932103]
理論的には、オンライン凸最適化に対する後悔の保証は、急速に崩壊する$beta_1to0$スケジュールを必要とする。
最適なデータ依存リセット境界を一定の$beta_1$で導出できる新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-21T19:19:51Z) - Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in
the Presence of Stragglers [31.309253646602933]
我々は、マスターが分散勾配降下(SGD)アルゴリズムを、データのサブセットを持つそれぞれ$n$ワーカー上で実行したいという設定について検討する。
分散SGDは、遅延を引き起こす遅い作業者や非応答的な作業者など、ストラグラーの影響に悩まされることがある。
本稿では,統計的概念に基づく適応分散SGDのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-25T16:25:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。