論文の概要: gBeam-ACO: a greedy and faster variant of Beam-ACO
- arxiv url: http://arxiv.org/abs/2004.11137v1
- Date: Thu, 23 Apr 2020 13:35:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-10 09:49:11.211053
- Title: gBeam-ACO: a greedy and faster variant of Beam-ACO
- Title（参考訳）: gBeam-ACO:ビームACOのグリーディで高速な派生型
- Authors: Jeff Hajewski and Suely Oliveira and David E. Stewart and Laura Weiler
- Abstract要約: グリーディパス選択を用いたビームACOのグリーディ変種を導入する。
欲求経路の選択の活用は、経路のビームを維持するのに必要な探索によって相殺される。
我々の実験は、従来のビームACOよりも高速であるだけでなく、発見された溶液の品質を犠牲にするものではないことを実証した。
- 参考スコア（独自算出の注目度）: 0.1529342790344802
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Beam-ACO, a modification of the traditional Ant Colony Optimization (ACO)
algorithms that incorporates a modified beam search, is one of the most
effective ACO algorithms for solving the Traveling Salesman Problem (TSP).
Although adding beam search to the ACO heuristic search process is effective,
it also increases the amount of work (in terms of partial paths) done by the
algorithm at each step. In this work, we introduce a greedy variant of Beam-ACO
that uses a greedy path selection heuristic. The exploitation of the greedy
path selection is offset by the exploration required in maintaining the beam of
paths. This approach has the added benefit of avoiding costly calls to a random
number generator and reduces the algorithms internal state, making it simpler
to parallelize. Our experiments demonstrate that not only is our greedy
Beam-ACO (gBeam-ACO) faster than traditional Beam-ACO, in some cases by an
order of magnitude, but it does not sacrifice quality of the found solution,
especially on large TSP instances. We also found that our greedy algorithm,
which we refer to as gBeam-ACO, was less dependent on hyperparameter settings.
- Abstract（参考訳）: ビーム探索を組み込んだ従来のアントコロニー最適化(ACO)アルゴリズムの修正であるビームACOは、トラベリングセールスマン問題(TSP)を解決するための最も効果的なACOアルゴリズムの1つである。
acoヒューリスティック探索プロセスにビーム探索を追加することは効果的であるが、アルゴリズムが各ステップで行う作業量(部分経路)も増加させる。
本研究では, グリーディパス選択ヒューリスティックを用いたビームACOのグリーディ変種を紹介する。
グリーディパスの選択の活用は、経路のビームを維持するのに必要な探索によって相殺される。
このアプローチには、乱数生成器へのコストのかかる呼び出しを回避し、アルゴリズムの内部状態を減らし、並列化を容易にするというメリットが追加されている。
実験では,従来のビームacoよりも高速で,場合によっては桁違いに高速であるだけでなく,特に大規模なtspインスタンスでは,検出した溶液の品質を犠牲にしないことを示した。
また、gBeam-ACOと呼ばれるこのグレディアルゴリズムは、ハイパーパラメータ設定に依存しないことがわかった。
関連論文リスト
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Hybrid ACO-CI Algorithm for Beam Design problems [0.4397520291340694]
The novel hybrid version of the Ant colony optimization (ACO) method was developed using the sample space reduction technique of the Cohort Intelligence (CI) algorithm。
提案した研究は、工学領域や医療問題を含む現実世界の応用について検討することができる。
論文 参考訳（メタデータ） (2023-03-29T04:37:14Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Improving Ant Colony Optimization Efficiency for Solving Large TSP
Instances [0.0]
我々は新しいAnt Colony Optimization(ACO)、すなわちFocused ACO(FACO)を提案する。
FACOは、新しく構築されたソリューションと選択された前のソリューションの差の数を制御するメカニズムである。
このメカニズムにより、より焦点を絞った検索プロセスが実現し、既存のソリューションの品質を維持しながら改善点を見つけることができる。
論文 参考訳（メタデータ） (2022-03-04T10:26:02Z) - Planning and Learning with Adaptive Lookahead [74.39132848733847]
ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。
近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。
本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
論文 参考訳（メタデータ） (2022-01-28T20:26:55Z) - Adaptive Multi-Goal Exploration [118.40427257364729]
我々は、AdaGoalが$epsilon$-optimal goal-conditioned policyを学習する目的を達成するためにどのように使えるかを示す。
AdaGoalは、ゴール条件の深い強化学習のための既存の手法の高レベルなアルゴリズム構造に固定されている。
論文 参考訳（メタデータ） (2021-11-23T17:59:50Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - Towards Dynamic Algorithm Selection for Numerical Black-Box
Optimization: Investigating BBOB as a Use Case [4.33419118449588]
シングルスウィッチな動的アルゴリズムの選択(dynAS)でさえ、大きな性能向上をもたらす可能性があることを示す。
また、dynASにおける重要な課題についても論じ、BBOBフレームワークがこれらを克服する上で有用なツールになり得ると論じる。
論文 参考訳（メタデータ） (2020-06-11T16:36:11Z) - Hybrid 2-stage Imperialist Competitive Algorithm with Ant Colony
Optimization for Solving Multi-Depot Vehicle Routing Problem [0.0]
本稿では,2つの集団ベースアルゴリズムに基づくハイブリッド2段階アプローチを提案する。
提案したハイブリッドアルゴリズムでは、ICAがデポへの顧客の割り当てを担当し、ACOが顧客のルーティングとシークエンシングを行っている。
その結果、単純なACOやICAよりも明らかに改善され、他の競合アルゴリズムと比較して非常に競争力のある結果が得られた。
論文 参考訳（メタデータ） (2020-04-07T17:43:06Z) - Adaptive Large Neighborhood Search for Circle Bin Packing Problem [8.855116523397935]
我々は、円ビンパッキング問題(CBPP)と呼ばれる新しいパッキング問題に対処する。
CBPPは、使用済みのビンの数を最小限に抑えるために、複数の正方形のビンに円のアイテムを密に詰め込むことである。
本稿では,Corner Occupying Action (GACOA) を用いたグレディアルゴリズムを用いて,初期レイアウトを構築する適応型大近傍探索(ALNS)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-20T10:14:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。