論文の概要: Memetic collaborative approaches for finding balanced incomplete block designs
- arxiv url: http://arxiv.org/abs/2411.02250v1
- Date: Mon, 04 Nov 2024 16:41:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-05 14:50:24.011912
- Title: Memetic collaborative approaches for finding balanced incomplete block designs
- Title（参考訳）: バランスの取れた不完全ブロック設計を見つけるためのメメティックコラボレーティブアプローチ
- Authors: David Rodríguez Rueda, Carlos Cotta, Antonio J. Fernández-Leiva,
- Abstract要約: 平衡不完全ブロック設計(BIBD)問題は、多数の対称性を持つ難しい問題である。
本稿では,古典的二元数定式化の代替として機能する双対(整数)問題表現を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: The balanced incomplete block design (BIBD) problem is a difficult combinatorial problem with a large number of symmetries, which add complexity to its resolution. In this paper, we propose a dual (integer) problem representation that serves as an alternative to the classical binary formulation of the problem. We attack this problem incrementally: firstly, we propose basic algorithms (i.e. local search techniques and genetic algorithms) intended to work separately on the two different search spaces (i.e. binary and integer); secondly, we propose two hybrid schemes: an integrative approach (i.e. a memetic algorithm) and a collaborative model in which the previous methods work in parallel, occasionally exchanging information. Three distinct two-dimensional structures are proposed as communication topology among the algorithms involved in the collaborative model, as well as a number of migration and acceptance criteria for sending and receiving data. An empirical analysis comparing a large number of instances of our schemes (with algorithms possibly working on different search spaces and with/without symmetry breaking methods) shows that some of these algorithms can be considered the state of the art of the metaheuristic methods applied to finding BIBDs. Moreover, our cooperative proposal is a general scheme from which distinct algorithmic variants can be instantiated to handle symmetrical optimisation problems. For this reason, we have also analysed its key parameters, thereby providing general guidelines for the design of efficient/robust cooperative algorithms devised from our proposal.
- Abstract（参考訳）: 平衡不完全ブロック設計(BIBD)問題は、多くの対称性を持つ複雑な組合せ問題である。
本稿では,古典的二元数定式化の代替として機能する双対(整数)問題表現を提案する。
まず,2つの異なる探索空間(二進法と整数法)を別々に扱うことを目的とした基本的アルゴリズム(局所探索手法と遺伝的アルゴリズム)を提案する。
協調モデルに関わるアルゴリズム間の通信トポロジとして,3つの異なる2次元構造が提案されている。
我々のスキームの多数の例を比較した経験的分析(おそらく異なる探索空間と対称性の破れのない手法で動くアルゴリズム)により、これらのアルゴリズムのいくつかは、BIBDの発見に適用されるメタヒューリスティックな手法の最先端と見なすことができる。
さらに、協調的な提案は、対称最適化問題に対処するために、異なるアルゴリズムの変種をインスタンス化できる一般的なスキームである。
このため,本提案では,提案手法から考案した効率的・ロバストな協調アルゴリズムの設計に関する一般的なガイドラインを提供するとともに,その重要なパラメータも分析した。
関連論文リスト
- Metaheuristics for the Template Design Problem: Encoding, Symmetry and Hybridisation [0.0]
テンプレート設計問題(TDP)は、多くの対称性を持つ難しい問題であり、それをより複雑にしている。
本稿では,テンプレート設計の適合性を評価することを目的として,多種多様なメタヒューリスティクスを探索し,解析する。
論文 参考訳（メタデータ） (2024-11-05T06:29:12Z) - Deep memetic models for combinatorial optimization problems: application to the tool switching problem [0.0]
この研究は、ディープなメタ協調、すなわち、一部のコンポーネントがそれ自身で協調メソッドとなるような協調最適化アルゴリズムの使用に取り組む。
本研究の目的は,このようなモデルが,従来の協調アルゴリズムの代替として有効であることを示すことである。
以上の結果から, 深層モデルでは, メタヒューリスティックスパラメータよりも優れていることが示唆された。
論文 参考訳（メタデータ） (2024-11-04T09:39:03Z) - Distributed Linear Regression with Compositional Covariates [5.085889377571319]
大規模合成データにおける分散スパースペナル化線形ログコントラストモデルに着目する。
2つの異なる制約凸最適化問題を解くために2つの分散最適化手法を提案する。
分散化されたトポロジでは、通信効率の高い正規化推定値を得るための分散座標ワイド降下アルゴリズムを導入する。
論文 参考訳（メタデータ） (2023-10-21T11:09:37Z) - Doubly Stochastic Matrix Models for Estimation of Distribution
Algorithms [2.28438857884398]
本稿では,自然置換問題のマッチングと割当てにDSM(Douubly Matrices)を用いる方法について検討する。
具体的には、分散アルゴリズムの推定の枠組みを採用し、DSMを置換問題に対する既存の提案と比較する。
二次代入問題の事例に関する予備実験は、この研究の行を検証し、DSMが非常に競争力のある結果が得られることを示した。
論文 参考訳（メタデータ） (2023-04-05T14:36:48Z) - On a class of geodesically convex optimization problems solved via
Euclidean MM methods [50.428784381385164]
ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。
最終的に、より広い範囲、より広い範囲の作業を支援するのです。
論文 参考訳（メタデータ） (2022-06-22T23:57:40Z) - Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。
代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。
データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
論文 参考訳（メタデータ） (2021-12-06T20:34:55Z) - Algorithm Selection on a Meta Level [58.720142291102135]
本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。
本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
論文 参考訳（メタデータ） (2021-07-20T11:23:21Z) - Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。
本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
論文 参考訳（メタデータ） (2021-07-05T00:51:02Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳（メタデータ） (2021-03-10T03:16:12Z) - 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) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。