論文の概要: Evolutionary Algorithms for One-Sided Bipartite Crossing Minimisation
- arxiv url: http://arxiv.org/abs/2409.15312v1
- Date: Thu, 5 Sep 2024 15:12:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-06 20:05:48.762058
- Title: Evolutionary Algorithms for One-Sided Bipartite Crossing Minimisation
- Title（参考訳）: 1-Sided Bipartite Crossing Minimizationのための進化的アルゴリズム
- Authors: Jakob Baumann, Ignaz Rutter, Dirk Sudholt,
- Abstract要約: 進化アルゴリズム (EA) は自然進化の原理にインスパイアされた普遍的な解法である。
いわゆるtextscOne-Sided Bipartite Crossing Minimisation (OBCM) について考察する。
OBCMにおける単純なEAの性能を実験的に解析し、置換順序付け問題に対する異なる突然変異演算子を比較した。
ジャンプを用いたEAは、合理的な数世代の後、ソリューションの品質の観点から、すべての決定論的アルゴリズムを容易に上回ります。
- 参考スコア（独自算出の注目度）: 1.382553192164386
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Evolutionary algorithms (EAs) are universal solvers inspired by principles of natural evolution. In many applications, EAs produce astonishingly good solutions. As they are able to deal with complex optimisation problems, they show great promise for hard problems encountered in the field of graph drawing.To complement recent theoretical advances in the analysis of EAs on graph drawing, we contribute a fundamental empirical study. We consider the so-called \textsc{One-Sided Bipartite Crossing Minimisation (OBCM)}: given two layers of a bipartite graph and a fixed horizontal order of vertices on the first layer, the task is to order the vertices on the second layer to minimise the number of edge crossings. We empirically analyse the performance of simple EAs for OBCM and compare different mutation operators on the underlying permutation ordering problem: exchanging two elements (\textit{exchange}), swapping adjacent elements (\textit{swap}) and jumping an element to a new position (\textit{jump}). EAs using jumps easily outperform all deterministic algorithms in terms of solution quality after a reasonable number of generations. We also design variations of the best-performing EAs to reduce the execution time for each generation. The improved EAs can obtain the same solution quality as before and run up to 100 times faster.
- Abstract（参考訳）: 進化アルゴリズム (EA) は自然進化の原理にインスパイアされた普遍的な解法である。
多くのアプリケーションにおいて、EAは驚くほど優れたソリューションを生み出します。
複雑な最適化問題に対処できるため、グラフ描画の分野で遭遇する困難な問題に対して大きな期待を示し、グラフ描画におけるEAの分析における最近の理論的進歩を補完するため、基礎的な実証研究に貢献する。
いわゆる「textsc{One-Sided Bipartite Crossing Minimisation (OBCM) 」を考える: 両部グラフの2つの層と、第1層上の頂点の固定水平順序を与えられた場合、第2層上の頂点を順序付けして、エッジ交差の数を最小化する。
OBCM の単純な EA の性能を実証的に解析し、2つの要素 (\textit{exchange} ) を交換し、隣接する要素 (\textit{swap} ) を交換し、要素を新しい位置 (\textit{jump} ) にジャンプする(\textit{jump} )。
ジャンプを用いたEAは、合理的な数世代の後、ソリューションの品質の観点から、すべての決定論的アルゴリズムを容易に上回ります。
また、各世代の実行時間を短縮するために、最高のパフォーマンスのEAのバリエーションを設計する。
改善されたEAは、以前と同じソリューション品質を得ることができ、最大100倍高速に動作します。
関連論文リスト
- ELRA: Exponential learning rate adaption gradient descent optimization
method [83.88591755871734]
我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。
本手法の主な考え方は,状況認識による$alphaの適応である。
これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
論文 参考訳（メタデータ） (2023-09-12T14:36:13Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids [0.190365714903665]
エージェントを2つのチームに分けた2色MAPFがNPハードのままであることを示す。
フロータイムの目的のために,エージェントの移動数に基づいてトラクタビリティフロンティアを確立する。
この結果は最適解の構造に新たな光を当て、一般的な問題のアルゴリズム設計を導くのに役立つかもしれない。
論文 参考訳（メタデータ） (2023-05-25T17:56:24Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Focused Jump-and-Repair Constraint Handling for Fixed-Parameter
Tractable Graph Problems Closed Under Induced Subgraphs [3.495114525631289]
グラフ問題における不可能な子孫の確率的修復に使用できる調整されたジャンプ・アンド・リペア操作を備えた(1+1)EAについて検討する。
論文 参考訳（メタデータ） (2022-03-25T19:36:02Z) - Time Complexity Analysis of Evolutionary Algorithms for 2-Hop
(1,2)-Minimum Spanning Tree Problem [20.624629608537894]
2-Hop (1,2)-Minimum Spanning Tree problem (略MSTP) の制約付きバージョンを進化アルゴリズムの文脈で検討し、NPハードであることが示されている。
2-ホップスパンニングツリーの特別な構造に着想を得て、(1+1) EA はエッジベース表現の探索点を持ち、これは問題にはあまり自然とは思えず、期待する時間に上限を与えて$frac32$-approximate の解を得る。
論文 参考訳（メタデータ） (2021-10-10T04:35:02Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - Evolutionary Algorithm and Multifactorial Evolutionary Algorithm on
Clustered Shortest-Path Tree problem [2.578242050187029]
CluSPT(Clustered Shortest-Path Tree Problem)はNPハード問題である。
探索処理の性能を向上させるために,2つの手法を提案する。
論文 参考訳（メタデータ） (2020-10-19T08:37:18Z) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳（メタデータ） (2020-08-12T08:52:50Z) - Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the
Multi-Objective Minimum Spanning Tree Problem [12.098400820502635]
我々は,Spanning Tree (MST) 問題を単目的および多目的バージョンで検討する。
我々は、低い支配数の観点から低いランクのエッジの選択に重点を置くバイアス付き突然変異を導入する。
我々は、非偏見または偏見のあるエッジ選択を決定する突然変異演算子の組み合わせが、最悪の場合、上界(unbiased mutation)を示すことを示した。
論文 参考訳（メタデータ） (2020-04-22T07:47:00Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。