Fugu-MT 論文翻訳(概要): Boosting Ant Colony Optimization via Solution Prediction and Machine Learning

論文の概要: Boosting Ant Colony Optimization via Solution Prediction and Machine Learning

arxiv url: http://arxiv.org/abs/2008.04213v2
Date: Sun, 7 Nov 2021 05:54:16 GMT
ステータス: 処理完了
システム内更新日: 2022-11-05 19:27:08.747798
Title: Boosting Ant Colony Optimization via Solution Prediction and Machine Learning
Title（参考訳）: ソリューション予測と機械学習によるアントコロニー最適化の強化
Authors: Yuan Sun, Sheng Wang, Yunzhuang Shen, Xiaodong Li, Andreas T. Ernst, and Michael Kirley
Abstract要約: 本稿では,機械学習(ML)とアリコロニー最適化(ACO)を組み合わせたメタヒューリスティック(ML-ACO)を導入し,最適化問題を解く。
参考スコア（独自算出の注目度）: 10.687150889251031
License: http://creativecommons.org/licenses/by/4.0/
Abstract: This paper introduces an enhanced meta-heuristic (ML-ACO) that combines machine learning (ML) and ant colony optimization (ACO) to solve combinatorial optimization problems. To illustrate the underlying mechanism of our ML-ACO algorithm, we start by describing a test problem, the orienteering problem. In this problem, the objective is to find a route that visits a subset of vertices in a graph within a time budget to maximize the collected score. In the first phase of our ML-ACO algorithm, an ML model is trained using a set of small problem instances where the optimal solution is known. Specifically, classification models are used to classify an edge as being part of the optimal route, or not, using problem-specific features and statistical measures. The trained model is then used to predict the probability that an edge in the graph of a test problem instance belongs to the corresponding optimal route. In the second phase, we incorporate the predicted probabilities into the ACO component of our algorithm, i.e., using the probability values as heuristic weights or to warm start the pheromone matrix. Here, the probability values bias sampling towards favoring those predicted high-quality edges when constructing feasible routes. We have tested multiple classification models including graph neural networks, logistic regression and support vector machines, and the experimental results show that our solution prediction approach consistently boosts the performance of ACO. Further, we empirically show that our ML model trained on small synthetic instances generalizes well to large synthetic and real-world instances. Our approach integrating ML with a meta-heuristic is generic and can be applied to a wide range of optimization problems.
Abstract（参考訳）: 本稿では,機械学習(ML)とアリコロニー最適化(ACO)を組み合わせたメタヒューリスティック(ML-ACO)を導入し,組合せ最適化問題を解く。 ML-ACOアルゴリズムの基盤となるメカニズムを説明するために、テスト問題、オリエンテーリング問題を記述することから始める。この問題では、収集したスコアを最大化するために、時間予算内でグラフ内の頂点のサブセットにアクセスするルートを見つけることが目的である。 ML-ACOアルゴリズムの第1フェーズでは、最適解が知られている小さな問題インスタンスの集合を用いてMLモデルを訓練する。具体的には、問題固有の特徴と統計的測度を用いて、エッジが最適経路の一部であるか否かを分類するために分類モデルが用いられる。訓練されたモデルは、テスト問題インスタンスのグラフのエッジが対応する最適経路に属する確率を予測するために使用される。第2段階では,予測確率をアルゴリズムのACO成分,すなわち確率値をヒューリスティックな重みとして利用したり,フェロモン行列を温めたりする。ここでは、予測可能なルートを構築する際に、予測された高品質エッジを優先する確率値バイアスサンプリングを行う。我々は,グラフニューラルネットワーク,ロジスティック回帰,サポートベクターマシンなど,複数の分類モデルを検証し,実験結果から,ACOの性能を継続的に向上させる解予測手法が得られた。さらに、我々のMLモデルは、小さな合成インスタンスで訓練され、大規模な合成インスタンスや実世界のインスタンスによく一般化されることを実証的に示す。メタヒューリスティックとMLを統合するアプローチは汎用的であり、幅広い最適化問題に適用できる。

関連論文リスト

Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。このような問題は医学、物理学、機械学習で発生する。両種類の雑音下で提案アルゴリズムの収束保証を行う。
論文参考訳（メタデータ） (2024-11-21T10:26:17Z)
Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
論文参考訳（メタデータ） (2023-10-10T01:39:04Z)
DynamoRep: Trajectory-Based Population Dynamics for Classification of Black-box Optimization Problems [0.755972004983746]
簡単な統計量を用いて最適化アルゴリズムの軌道を記述する特徴抽出法を提案する。提案するDynamoRep機能は,最適化アルゴリズムが動作している問題クラスを特定するのに十分な情報を取得する。
論文参考訳（メタデータ） (2023-06-08T06:57:07Z)
Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood Estimation for Latent Gaussian Models [69.22568644711113]
我々は,モンテカルロサンプリングと反復線形解法を組み合わせた確率的アンローリングを導入し,行列逆転を回避した。理論的解析により,解法の繰り返しによる解法の解法と逆転が最大値推定の勾配推定を高速化することを示した。シミュレーションおよび実データ実験において、確率的アンロールは、モデル性能の損失を最小限に抑えながら、勾配EMよりも桁違いに高速な潜在ガウスモデルを学習することを示した。
論文参考訳（メタデータ） (2023-06-05T21:08:34Z)
A Novel Plug-and-Play Approach for Adversarially Robust Generalization [38.72514422694518]
本稿では,MLモデルを摂動テストデータから保護するために,逆向きに堅牢なトレーニングを採用する頑健なフレームワークを提案する。私たちの貢献は、計算学と統計学の両方の観点から見ることができます。
論文参考訳（メタデータ） (2022-08-19T17:02:55Z)
Pretrained Cost Model for Distributed Constraint Optimization Problems [37.79733538931925]
分散制約最適化問題(DCOP)は、最適化問題の重要なサブクラスである。本稿では,DCOPのための新しい非巡回グラフスキーマ表現を提案し,グラフ表現を組み込むためにグラフ注意ネットワーク(GAT)を利用する。我々のモデルであるGAT-PCMは、幅広いDCOPアルゴリズムを向上するために、オフラインで最適なラベル付きデータで事前訓練される。
論文参考訳（メタデータ） (2021-12-08T09:24:10Z)
COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization [4.970364068620608]
我々は,勾配オラクルによって出力される雑音の推定値を改善するために,凸性およびL平滑性を利用する。問合せ点の数と近さの増加は、より良い勾配推定に繋がることを示す。また、SGD、Adam、STRSAGAといった既存のアルゴリズムにCOCOをプラグインすることで、バニラ設定にもCOCOを適用します。
論文参考訳（メタデータ） (2021-09-07T17:21:09Z)
A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文参考訳（メタデータ） (2021-06-09T09:18:18Z)
Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文参考訳（メタデータ） (2021-02-16T06:04:27Z)
Cauchy-Schwarz Regularized Autoencoder [68.80569889599434]
変分オートエンコーダ(VAE)は、強力で広く使われている生成モデルのクラスである。 GMMに対して解析的に計算できるCauchy-Schwarz分散に基づく新しい制約対象を導入する。本研究の目的は,密度推定,教師なしクラスタリング,半教師なし学習,顔分析における変分自動エンコーディングモデルの改善である。
論文参考訳（メタデータ） (2021-01-06T17:36:26Z)
Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information [12.836994708337144]
最適なサンプルの複雑さにマッチするアルゴリズムを開発する。我々のアルゴリズムはエラーをモデル化し、予測性能の点で既存のアルゴリズムより優れている。
論文参考訳（メタデータ） (2020-03-16T06:29:24Z)

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

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