論文の概要: A bi-level encoding scheme for the clustered shortest-path tree problem
in multifactorial optimization
- arxiv url: http://arxiv.org/abs/2102.09954v1
- Date: Fri, 12 Feb 2021 13:36:07 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-05 00:36:49.474192
- Title: A bi-level encoding scheme for the clustered shortest-path tree problem
in multifactorial optimization
- Title（参考訳）: 多因子最適化におけるクラスタ化短絡木問題に対する二段階符号化方式
- Authors: Huynh Thi Thanh Binh, Ta Bao Thang, Nguyen Duc Thai, Pham Dinh Thanh
- Abstract要約: CluSPT(Clustered Shortest-Path Tree Problem)は、実生活における様々な最適化問題において重要な役割を果たしている。
近年、CluSPTを扱うためにMFEA(Multifactorial Evolutionary Algorithm)が導入されている。
本稿では,MFEAに基づくCluSPTの解法について述べる。
- 参考スコア（独自算出の注目度）: 1.471992435706872
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The Clustered Shortest-Path Tree Problem (CluSPT) plays an important role in
various types of optimization problems in real-life. Recently, some
Multifactorial Evolutionary Algorithm (MFEA) have been introduced to deal with
the CluSPT, however these researches still have some shortcomings such as
evolution operators only perform on complete graphs, huge resource consumption
for finding the solution on large search spaces. To overcome these limitations,
this paper describes a MFEA-based approach to solve the CluSPT. The proposed
algorithm utilizes Dijkstra's algorithm to construct the spanning trees in
clusters while using evolutionary operators for building the spanning tree
connecting clusters. This approach takes advantage of both exact and
approximate algorithms so it enables the algorithm to function efficiently on
complete and sparse graphs alike. Furthermore, evolutionary operators such as
individual encoding and decoding methods are also designed with great
consideration regarding performance and memory usage. We have included a proof
on the repairing method's efficacy in ensuring all solutions are valid. We have
conducted tests on various types of Euclidean instances to assess the
effectiveness of the proposed algorithm and methods. Experiment results point
out the effectiveness of the proposed algorithm existing heuristic algorithms
in most of the test cases. The impact of the proposed MFEA was analyzed and a
possible influential factor that may be useful for further study was also
pointed out.
- Abstract（参考訳）: CluSPT(Clustered Shortest-Path Tree Problem)は、実生活における様々な最適化問題において重要な役割を果たしている。
近年、CluSPTを扱うためにMFEA(Multifactorial Evolutionary Algorithm)がいくつか導入されているが、これらの研究には、進化演算子が完全なグラフ上でのみ動作すること、大規模な検索空間上で解を見つけるための膨大なリソース消費など、いくつかの欠点がある。
これらの限界を克服するため,本論文では,mfeaに基づく手法を提案する。
提案手法はジクストラのアルゴリズムを用いてクラスタ内のスパンディングツリーを構築し,また進化演算子を用いてスパンディングツリー接続クラスタを構築する。
このアプローチは正確なアルゴリズムと近似アルゴリズムの両方を利用するので、アルゴリズムは完全かつスパースなグラフでも効率的に機能することができる。
さらに、個々のエンコーディングやデコードといった進化的演算子も、パフォーマンスやメモリ使用について非常に考慮して設計されている。
我々は,すべてのソリューションが有効であることを保証するための補修方法の有効性の実証を行った。
提案手法の有効性を評価するため,様々な種類のユークリッドインスタンスについて実験を行った。
実験結果から,既存のヒューリスティックアルゴリズムの有効性が示唆された。
また,提案するmfeaの影響を解析し,今後の研究に有用である可能性が示唆された。
関連論文リスト
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - 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) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
車両ルーティング問題(VRP)は典型的な離散最適化問題である。
多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。
本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
論文 参考訳（メタデータ） (2021-07-15T02:13:03Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Identifying Co-Adaptation of Algorithmic and Implementational
Innovations in Deep Reinforcement Learning: A Taxonomy and Case Study of
Inference-based Algorithms [15.338931971492288]
我々は、アルゴリズムの革新と実装決定を分離するために、一連の推論に基づくアクター批判アルゴリズムに焦点を当てる。
実装の詳細がアルゴリズムの選択に一致すると、パフォーマンスが大幅に低下します。
結果は、どの実装の詳細がアルゴリズムと共適応され、共進化しているかを示す。
論文 参考訳（メタデータ） (2021-03-31T17:55:20Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳（メタデータ） (2021-03-10T03:16:12Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - CSCF: a chaotic sine cosine firefly Algorithm for practical application
problems [0.0]
いくつかの最適化アルゴリズム、すなわちファイアフライアルゴリズム、正弦コサインアルゴリズム、粒子群最適化アルゴリズムは、計算複雑性、収束速度などの欠点はほとんどない。
本稿では,最適化問題を解くために,多数の変種を持つ新しいCSCFアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-11-20T08:54:28Z) - A Heuristic Based on Randomized Greedy Algorithms for the Clustered
Shortest-Path Tree Problem [2.099922236065961]
本稿では, RGA とショート・パス・ツリー・アルゴリズム (SPTA) の主な特徴を組み合わせたクラスタ・ショート・パス・ツリー問題 (CluSPT) を扱うアルゴリズムを提案する。
提案アルゴリズムの性能を評価するため,ユークリッドベンチマークが選択される。
論文 参考訳（メタデータ） (2020-05-05T08:34:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。