論文の概要: A Multi-Parent Edge Assembly Crossover Driven Hybrid Genetic Algorithm for the Hamiltonian \textit{p}-Median Problem
- arxiv url: http://arxiv.org/abs/2611.15219v1
- Date: Wed, 11 Nov 2026 09:14:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.088456
- Title: A Multi-Parent Edge Assembly Crossover Driven Hybrid Genetic Algorithm for the Hamiltonian \textit{p}-Median Problem
- Title(参考訳): Hamiltonian \textit{p}-Median問題に対する多経路エッジアセンブリクロスオーバー駆動型ハイブリッド遺伝的アルゴリズム
- Abstract要約: ハミルトンテキスト-中間問題(英語版)は、グラフの頂点を正確に$p$不整環に分割しようとする。
本稿では,マルチペアエッジアセンブリ・クロスオーバー演算子を組み込んだハイブリッド遺伝的アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 16.909374320210564
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The Hamiltonian \textit{p}-median problem seeks to partition the vertices of a graph into exactly $p$ disjoint cycles while minimizing their total cost. This paper presents a hybrid genetic algorithm incorporating a multi-parent edge assembly crossover operator. The crossover combines a base solution with multiple donor solutions in a single recombination operation, thereby expanding the space of available edge exchanges. It uses virtual copies of the base solution to establish edge balance, together with an auxiliary directed graph and a budgeted search to construct valid AB-cycles. Extensive experiments on 215 benchmark instances across four sets show that the proposed algorithm improves the best-known solution values for 34 instances and matches those for another 168. Additional experiments indicate that a moderate number of parents provides beneficial diversity, whereas excessive parent counts, particularly when $p$ is large, lead to excessive population dispersion and hinder convergence.
- Abstract(参考訳): ハミルトニアン \textit{p}-中間問題(英語版)は、グラフの頂点を総コストを最小化しながら、正確に$p$不整環に分割しようとする。
本稿では,マルチペアエッジアセンブリ・クロスオーバー演算子を組み込んだハイブリッド遺伝的アルゴリズムを提案する。
クロスオーバーは、基本解と複数のドナー解を1つの組換え操作で組み合わせ、利用可能なエッジ交換の空間を拡大する。
エッジバランスを確立するためにベースソリューションの仮想コピーを使用し、補助的な有向グラフと予算付き検索を使って有効なABサイクルを構築する。
4つのセットにまたがる215のベンチマークインスタンスに対する大規模な実験により、提案アルゴリズムは34のインスタンスの最もよく知られたソリューション値を改善し、さらに168のインスタンスにマッチすることを示した。
追加の実験では、適度な数の親が有益な多様性を提供するのに対し、特に$p$が大きすぎると人口の分散が過度に増加し、収束を妨げている。
関連論文リスト
- Parent Selection Mechanisms in Elitist Crossover-Based Algorithms [4.640835690336653]
本稿では,最遠距離の親の選抜を優先する遺伝的アルゴリズム(GA)の親選択戦略を提案する。
適切に選択された集団サイズにより、このアルゴリズムは、期待時間$O(k4knlog(n))$Jump$_k$問題を解く。
本分析から得られた知見は,遺伝的アルゴリズムの集団動態におけるクロスオーバーの役割の理論的理解に寄与する。
論文 参考訳(メタデータ) (2026-04-05T12:02:25Z) - Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
我々はパラメータフリーで、歪んだ局所探索法と同じ近似保証を実現できるMultinoulliSCGという新しいアルゴリズムを導入する。
また、分割制約に関する未探索オンラインサブセット選択問題に対して、Multinoulli-CGとMultinoulli-GAGAという2つの新しいオンラインアルゴリズムを提案する。
論文 参考訳(メタデータ) (2026-03-23T02:30:01Z) - Exact and Heuristic Algorithms for Constrained Biclustering [0.0]
コクラスタリング(co-clustering)または双方向クラスタリング( two-way clustering)とも呼ばれるビクラスタリングは、データマトリックスの行と列を同時にパーティショニングすることで、コヒーレントパターンによるサブマトリクスを明らかにする。
我々は、オブジェクトが同一または異なるビクラスタに属するべきか否かを規定する制約付きビクラスタリング、すなわち、マスタリンクとナントリンクの制約について研究する。
論文 参考訳(メタデータ) (2025-08-07T15:29:22Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳(メタデータ) (2025-02-07T15:57:56Z) - A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering [0.0]
本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。
提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
論文 参考訳(メタデータ) (2024-03-17T21:43:19Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳(メタデータ) (2023-08-17T21:15:04Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。