論文の概要: Performance Analysis of Meta-heuristic Algorithms for a Quadratic Assignment Problem

• arxiv url: http://arxiv.org/abs/2007.14885v1
• Date: Wed, 29 Jul 2020 15:02:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-05 19:50:59.691275
• Title: Performance Analysis of Meta-heuristic Algorithms for a Quadratic Assignment Problem
• Title（参考訳）: 二次代入問題に対するメタヒューリスティックアルゴリズムの性能解析
• Authors: Zohreh Raziei, Reza Tavakkoli-Moghaddam, Siavash Tabrizian
• Abstract要約: 二次代入問題 (QAP) はNPハード問題に属する最適化問題である。 ヒューリスティックスとメタヒューリスティックスアルゴリズムはこの問題の一般的な解法である。 本稿では,QAPの解法に異なるメタヒューリスティックアルゴリズムを適用するための比較研究の1つである。
• 参考スコア（独自算出の注目度）: 6.555180412600522
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A quadratic assignment problem (QAP) is a combinatorial optimization problem that belongs to the class of NP-hard ones. So, it is difficult to solve in the polynomial time even for small instances. Research on the QAP has thus focused on obtaining a method to overcome this problem. Heuristics and meta-heuristics algorithm are prevalent solution methods for this problem. This paper is one of comparative studies to apply different metaheuristic algorithms for solving the QAP. One of the most popular approaches for categorizing meta-heuristic algorithms is based on a search strategy, including (1) local search improvement meta-heuristics and (2) global search-based meta-heuristics. The matter that distinguishes this paper from the other is the comparative performance of local and global search (both EA and SI), in which meta-heuristics that consist of genetic algorithm (GA), particle swarm optimization (PSO), hybrid GA-PSO, grey wolf optimization (GWO), harmony search algorithm (HAS) and simulated annealing (SA). Also, one improvement heuristic algorithm (ie, 2-Opt) is used to compare with others. The PSO, GWO and 2-Opt algorithms are improved to achieve the better comparison toward the other algorithms for evaluation. In order to analysis the comparative advantage of these algorithms, eight different factors are presented. By taking into account all these factors, the test is implemented in six test problems of the QAP Library (QAPLIB) from different sizes. Another contribution of this paper is to measure a strong convergence condition for each algorithm in a new way.
• Abstract（参考訳）: 二次代入問題(英: quadratic assignment problem、qap)は、np-ハードのクラスに属する組合せ最適化問題である。 したがって、小さな例であっても多項式時間で解くことは困難である。 そこでQAPの研究は,この問題を克服する手法の獲得に重点を置いている。 ヒューリスティックスとメタヒューリスティックスアルゴリズムはこの問題の一般的な解法である。 本稿では,QAPの解法に異なるメタヒューリスティックアルゴリズムを適用するための比較研究の1つである。 メタヒューリスティックアルゴリズムを分類する最も一般的なアプローチの1つは,(1)局所検索改善メタヒューリスティックス,(2)グローバル検索ベースメタヒューリスティックスなどの検索戦略に基づいている。 遺伝的アルゴリズム(ga)、粒子群最適化(pso)、ハイブリッドga-pso(ga-pso)、grey wolf optimization(gwo)、harmony search algorithm(has)、simed annealing(sa)からなるメタヒューリスティックスによる局所的および大域的探索(eaとsiの両方)の比較性能である。 また、改良ヒューリスティックアルゴリズム(すなわち2-Opt)を他のアルゴリズムと比較する。 PSO, GWO, 2-Opt のアルゴリズムを改良し, 評価のための他のアルゴリズムと比較した。 これらのアルゴリズムの利点を解析するために、8つの異なる要因が提示される。 これらの要因をすべて考慮し、テストは異なるサイズのQAPライブラリ(QAPLIB)の6つのテスト問題で実施される。 この論文のもう1つの貢献は、各アルゴリズムの強い収束条件を新しい方法で測定することである。

関連論文リスト

• A Novel Ranking Scheme for the Performance Analysis of Stochastic Optimization Algorithms using the Principles of Severity [9.310464457958844]
  複数の単目的最適化問題に対してアルゴリズムをランク付けする新しいランキング方式を提案する。 アルゴリズムの結果は、ロバストなブートストラップに基づく仮説テスト手法を用いて比較される。
  論文  参考訳（メタデータ） (2024-05-31T19:35:34Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Combining K-means type algorithms with Hill Climbing for Joint Stratification and Sample Allocation Designs [0.0]
  これは、基本層のすべての可能な成層集合から最適成層を探索するサンプル問題である。 それぞれのソリューションのコストを評価するのに 費用がかかります 上記のアルゴリズムと最近の3つのアルゴリズムの多段階組み合わせを比較し、ソリューションコスト、評価時間、トレーニング時間を報告する。
  論文  参考訳（メタデータ） (2021-08-18T08:41:58Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Towards Meta-Algorithm Selection [78.13985819417974]
  インスタンス固有のアルゴリズム選択(AS)は、固定された候補集合からのアルゴリズムの自動選択を扱う。 メタアルゴリズムの選択は、いくつかのケースで有益であることを示す。
  論文  参考訳（メタデータ） (2020-11-17T17:27:33Z)
• Benchmarking Meta-heuristic Optimization [0.0]
  多くのメタヒューリスティックアルゴリズムは非線形関数を解く際に非常に効率的である。 メタヒューリスティックアルゴリズムは、幅広い問題に適用できる問題に依存しない手法である。
  論文  参考訳（メタデータ） (2020-07-27T12:25:31Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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