論文の概要: Massively parallel hybrid search for the partial Latin square extension problem

• arxiv url: http://arxiv.org/abs/2103.10453v1
• Date: Thu, 18 Mar 2021 18:09:50 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-22 23:47:18.113124
• Title: Massively parallel hybrid search for the partial Latin square extension problem
• Title（参考訳）: 部分ラテン二乗拡大問題に対する大規模並列ハイブリッド探索
• Authors: Olivier Goudet and Jin-Kao Hao
• Abstract要約: 本稿では,ラテン方形部分拡張問題に対する最初の超並列ハイブリッド探索アルゴリズムを提案する。 アルゴリズムのコードは公開される予定だ。
• 参考スコア（独自算出の注目度）: 18.224344440110862
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The partial Latin square extension problem is to fill as many as possible empty cells of a partially filled Latin square. This problem is a useful model for a wide range of relevant applications in diverse domains. This paper presents the first massively parallel hybrid search algorithm for this computationally challenging problem based on a transformation of the problem to partial graph coloring. The algorithm features the following original elements. Based on a very large population (with more than $10^4$ individuals) and modern graphical processing units, the algorithm performs many local searches in parallel to ensure an intensified exploitation of the search space. It employs a dedicated crossover with a specific parent matching strategy to create a large number of diversified and information-preserving offspring at each generation. Extensive experiments on 1800 benchmark instances show a high competitiveness of the algorithm compared with the current best performing methods. Competitive results are also reported on the related Latin square completion problem. Analyses are performed to shed lights on the understanding of the main algorithmic components. The code of the algorithm will be made publicly available.
• Abstract（参考訳）: 部分的なラテン正方形拡張問題は、可能な限り多くのラテン正方形の空セルを埋めることである。 この問題は、多様なドメインにおける幅広い関連するアプリケーションにとって有用なモデルである。 本稿では,この問題から部分グラフ彩色への変換に基づく,この計算上困難な問題に対する最初の超並列ハイブリッド探索アルゴリズムを提案する。 このアルゴリズムは以下の元要素を特徴としている。 膨大な人口(10^4$個人以上)と現代のグラフィカルな処理ユニットに基づいて、アルゴリズムは多くのローカル検索を並行して実行し、検索空間の強化された利用を確実にする。 特定の親マッチング戦略と専用のクロスオーバーを使用して、各世代で多種多様で情報保存された子孫を生成する。 1800のベンチマークインスタンスに対する大規模な実験は、アルゴリズムの競争力が高いことを示している。 競合の結果は、関連するラテン正方形補完問題でも報告されている。 分析は、主要なアルゴリズムコンポーネントの理解に基づいて光を遮る。 アルゴリズムのコードは公開される予定だ。

関連論文リスト

• CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines [1.1970409518725493]
  ソフトウェア製品ライン(SPL)では、多数の有効な機能の組み合わせが存在するため、家族のすべての製品をテストするのは難しい、あるいは不可能かもしれない。 本研究では,Construct, Merge, Solve & Adapt というハイブリッド・メピエリスト的アプローチに基づく新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2024-02-07T05:43:57Z)
• Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
  我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。 使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。 我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
  論文  参考訳（メタデータ） (2023-06-29T14:57:56Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• Massive-scale Decoding for Text Generation using Lattices [34.2658286826597]
  多数の生成オプションを符号化する格子を構成するための探索アルゴリズムを提案する。 我々のアルゴリズムは、文法的かつ高品質な数百から数千の多様な選択肢を1つの線形サイズの格子に符号化している。
  論文  参考訳（メタデータ） (2021-12-14T18:56:11Z)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。 代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。 データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
  論文  参考訳（メタデータ） (2021-12-06T20:34:55Z)
• Efficient Large Scale Inlier Voting for Geometric Vision Problems [3.1231364554255636]
  コンピュータビジョンにおける多くの応用において、アウター・リジェクション(英語版)と等価に不整集合最適化(英語版)が重要な要素である。 我々は、$Rd$の「交差」$k$次元曲面に基づいて、外周拒絶に対する効率的で一般的なアルゴリズムを提案する。 本手法は, 複数枚のカメラにおいて, 多数の一致が低い不整合比で発生する問題に対するアプローチの汎用性を示す。
  論文  参考訳（メタデータ） (2021-07-25T14:13:07Z)
• Determinantal Beam Search [75.84501052642361]
  ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。 複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。 ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
  論文  参考訳（メタデータ） (2021-06-14T13:01:46Z)
• 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)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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