論文の概要: Nearest-Better Network for Visualizing and Analyzing Combinatorial Optimization Problems: A Unified Tool

• arxiv url: http://arxiv.org/abs/2507.22440v1
• Date: Wed, 30 Jul 2025 07:31:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-31 16:14:18.062959
• Title: Nearest-Better Network for Visualizing and Analyzing Combinatorial Optimization Problems: A Unified Tool
• Title（参考訳）: 組合せ最適化問題の可視化と解析のためのNearest-Better Network:統一ツール
• Authors: Yiya Diao, Changhe Li, Sanyou Zeng, Xinye Cai, Wenjian Luo, Shengxiang Yang, Carlos A. Coello Coello,
• Abstract要約: Nearest-Better Network (NBN) は、連続最適化問題に対するサンプルデータを視覚化する強力な手法である。 本稿では,NBNネットワークがアルゴリズムの最大確率遷移ネットワークとして機能することを示す。 また、時間を要する問題に対処するために、対数線形時間複雑性を持つ効率的なNBNアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 4.255722698272975
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Nearest-Better Network (NBN) is a powerful method to visualize sampled data for continuous optimization problems while preserving multiple landscape features. However, the calculation of NBN is very time-consuming, and the extension of the method to combinatorial optimization problems is challenging but very important for analyzing the algorithm's behavior. This paper provides a straightforward theoretical derivation showing that the NBN network essentially functions as the maximum probability transition network for algorithms. This paper also presents an efficient NBN computation method with logarithmic linear time complexity to address the time-consuming issue. By applying this efficient NBN algorithm to the OneMax problem and the Traveling Salesman Problem (TSP), we have made several remarkable discoveries for the first time: The fitness landscape of OneMax exhibits neutrality, ruggedness, and modality features. The primary challenges of TSP problems are ruggedness, modality, and deception. Two state-of-the-art TSP algorithms (i.e., EAX and LKH) have limitations when addressing challenges related to modality and deception, respectively. LKH, based on local search operators, fails when there are deceptive solutions near global optima. EAX, which is based on a single population, can efficiently maintain diversity. However, when multiple attraction basins exist, EAX retains individuals within multiple basins simultaneously, reducing inter-basin interaction efficiency and leading to algorithm's stagnation.
• Abstract（参考訳）: Nearest-Better Network (NBN) は、複数のランドスケープ特性を保ちながら、連続最適化問題のサンプルデータを視覚化する強力な手法である。 しかし、NBNの計算は非常に時間がかかるため、組合せ最適化問題への拡張は困難であるが、アルゴリズムの振る舞いを分析する上では非常に重要である。 本稿では,NBNネットワークがアルゴリズムの最大確率遷移ネットワークとして機能することを示す。 また, 時間的問題に対処するために, 対数線形時間複雑性を持つ効率的なNBN計算手法を提案する。 この効率的なNBNアルゴリズムをOneMax問題とトラベリングセールスマン問題(TSP)に適用することにより、我々は初めて注目すべき発見を行った。 TSP問題の主な課題は、頑丈さ、モダリティ、騙しである。 2つの最先端のTSPアルゴリズム(EAXとLKH)は、それぞれモダリティと騙しに関連する課題に対処する際に制限がある。 局所探索演算子に基づくLKHは、グローバルオプティマ付近に偽りの解が存在する場合に失敗する。 EAXは単一人口に基づいており、効率よく多様性を維持することができる。 しかし、複数のアトラクション盆地が存在する場合、EAXは同時に複数の盆地内の個人を保持し、バス間相互作用効率を低下させ、アルゴリズムの停滞につながる。

関連論文リスト

• Multi-Objective Routing Optimization Using Coherent Ising Machine in Wireless Multihop Networks [4.4727509471456495]
  Coherent Ising Machines (CIM) は、無線ネットワークにおける多目的ルーティング最適化のための量子インスパイアされたアルゴリズムである。 CIMは、トポロジ固有の調整を必要とせずに、多様なネットワークトポロジにわたって強力なスケーラビリティを示す。 その結果、CIMは数百のノードと数千のエッジを含むネットワークに対して、実現可能でほぼ最適のソリューションを提供することがわかった。
  論文  参考訳（メタデータ） (2025-03-10T23:59:50Z)
• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。 我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
  論文  参考訳（メタデータ） (2024-05-28T10:28:45Z)
• Neural Quantile Optimization for Edge-Cloud Networking [13.509945075582447]
  我々は,バースト可能な請求書に基づいて制約を満足し,コストを最小化するエッジ・クラウド・コンピューティング・ネットワークにおいて,最適なトラフィック割当方式を模索する。 本稿では,教師なし学習による最適化問題を解決するため,Gumbel-softmaxサンプリングネットワークを提案する。 トレーニングされたネットワークは、効率的なトラフィック割当スキームサンプリングとして機能し、実現可能性およびコスト関数値のランダム戦略を著しく上回る。
  論文  参考訳（メタデータ） (2023-07-11T11:05:10Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)

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

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