論文の概要: A Genetic Algorithm Meta-Heuristic for a Generalized Quadratic Assignment Problem

• arxiv url: http://arxiv.org/abs/2308.07828v1
• Date: Tue, 15 Aug 2023 15:13:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-16 12:22:18.131152
• Title: A Genetic Algorithm Meta-Heuristic for a Generalized Quadratic Assignment Problem
• Title（参考訳）: 一般化二次代入問題に対する遺伝的アルゴリズムのメタヒューリスティック
• Authors: Mojtaba A. Farahani
• Abstract要約: 一般化二次代入問題(GQAP)は、運用研究分野において最も解決が難しい問題の1つである。 GQAPは、一組の施設を一組の場所に割り当てる際の割り当てと輸送コストを最小化するタスクとして定義される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The generalized quadratic assignment problem (GQAP) is one of the hardest problems to solve in the operations research area. The GQAP addressed in this work is defined as the task of minimizing the assignment and transportation costs of assigning a set of facilities to a set of locations. The facilities have different space requirements, and the locations have different space capacities. Multiple facilities can be assigned to each location if the space capacity is not violated. In this work, three instances of GQAP in different situations are presented. Then, a genetic algorithm is developed to solve the GQAP instances. Finally, the local neighborhood search with the steepest descend strategy is constructed and applied to the final solution obtained by the GA, and the final solution is compared with the best solution found by MPL/CPLEX software and reference papers. The results show that the developed GA heuristic is effective for solving the GQAP.
• Abstract（参考訳）: 一般化二次代入問題(GQAP)は、運用研究分野において最も解決が難しい問題の1つである。 本研究で取り組んだGQAPは、一組の施設を一組の場所に割り当てる際の割り当てと輸送コストを最小化するタスクとして定義される。 施設は異なる空間要件を持ち、場所は異なる空間容量を持つ。 スペース容量に違反しない場合、複数の施設が各場所に割り当てられる。 本稿では,異なる状況におけるgqapの3つの例を示す。 そして、GQAPインスタンスを解決するために遺伝的アルゴリズムを開発する。 最後に、最急降下戦略を有する局所近傍探索を構築し、gaで得られる最終解に適用し、mpl/cplexソフトウェアおよび参照論文で得られた最良解と比較する。 その結果,GAヒューリスティックはGQAPの解法に有効であることが示唆された。

関連論文リスト

• Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem [27.33966993065248]
  本研究は,2次割当て問題(QAP)を効率的に解くための学習ベースソリューションに焦点を当てる。 QAPに関する現在の研究は、限られた規模と非効率性に悩まされている。 そこで本研究では,QAPの学習と改善のカテゴリにおける第1の解法を提案する。
  論文  参考訳（メタデータ） (2024-06-14T10:15:03Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• New Characterizations and Efficient Local Search for General Integer Linear Programming [17.80124240223163]
  本研究では境界解の概念を用いた線形プログラミング(ILP)の新たな特徴付けを提案する。 そこで我々は,局所探索アルゴリズムのLocal-ILPを開発した。 MIPLIBデータセットで行った実験は、大規模ハードILP問題の解法におけるアルゴリズムの有効性を示した。
  論文  参考訳（メタデータ） (2023-04-29T07:22:07Z)
• Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding [25.11387753357413]
  本稿では,多目的タスク割り当てと経路探索(MG-TAPF)問題を理論的およびアルゴリズム的観点から検討する。 理論的には、MG-TAPF問題は最適解法としてNPハードであることが証明される。 本稿では,多エージェントパス探索問題に対するアルゴリズムに基づくアルゴリズムを提案し,MG-TAPF問題を最適・準最適に解く。
  論文  参考訳（メタデータ） (2022-08-02T03:17:29Z)
• Maximum Spatial Perturbation Consistency for Unpaired Image-to-Image Translation [56.44946660061753]
  本稿では,最大空間摂動整合(MSPC)と呼ばれる普遍正規化手法を提案する。 MSPCは空間摂動関数(T)と変換演算子(G)を可換(TG = GT)に強制する。 提案手法は,ほとんどのI2Iベンチマークにおいて最先端の手法よりも優れている。
  論文  参考訳（メタデータ） (2022-03-23T19:59:04Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Flipping the switch on local exploration: Genetic Algorithms with Reversals [0.0]
  著者らは、勾配のない探索手法が離散領域における最適解を提供するのに適していることを示した。 また、複数のローカル検索を使用することで、ローカル検索のパフォーマンスが向上することを示した。 提案したGA変種は,提案した問題を含む全てのベンチマークにおいて,最小平均コストであり,ICが構成成分よりも優れた性能を発揮することが観察された。
  論文  参考訳（メタデータ） (2022-02-02T08:27:11Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Partition-Guided GANs [63.980473635585234]
  私たちは、スペースを小さな領域に分割し、それぞれがよりシンプルな分布を持ち、各パーティションごとに異なるジェネレータを訓練するパーティションーを設計します。 これはラベルを必要とせずに教師なしの方法で実行される。 各種標準ベンチマーク実験の結果,提案手法が近年の手法を上回っていることがわかった。
  論文  参考訳（メタデータ） (2021-04-02T00:06:53Z)
• Ridge Rider: Finding Diverse Solutions by Following Eigenvectors of the Hessian [48.61341260604871]
  Gradient Descent(SGD)は、ディープニューラルネットワーク(DNN)の成功の鍵となる要素である 本稿では、ヘッセンの固有ベクトルを従えば「尾根」と呼ばれる別のアプローチを示す。 理論的および実験的に、我々の手法であるリッジライダー(RR)が様々な課題に対して有望な方向を提供することを示す。
  論文  参考訳（メタデータ） (2020-11-12T17:15:09Z)
• sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission Planning Problems [2.191505742658975]
  いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。 本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。 このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
  論文  参考訳（メタデータ） (2020-02-20T17:07:08Z)

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

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