論文の概要: CMSA algorithm for solving the prioritized pairwise test data generation
problem in software product lines
- arxiv url: http://arxiv.org/abs/2402.04597v1
- Date: Wed, 7 Feb 2024 05:43:57 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-08 16:40:59.693685
- Title: CMSA algorithm for solving the prioritized pairwise test data generation
problem in software product lines
- Title（参考訳）: ソフトウェア製品ラインにおける優先度付きペアワイズテストデータ生成問題を解決するcmsaアルゴリズム
- Authors: Javier Ferrer, Francisco Chicano, Jos\'e Antonio Ortega Toro
- Abstract要約: ソフトウェア製品ライン(SPL)では、多数の有効な機能の組み合わせが存在するため、家族のすべての製品をテストするのは難しい、あるいは不可能かもしれない。
本研究では,Construct, Merge, Solve & Adapt というハイブリッド・メピエリスト的アプローチに基づく新しいアプローチを提案する。
- 参考スコア（独自算出の注目度）: 1.1970409518725493
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In Software Product Lines (SPLs) it may be difficult or even impossible to
test all the products of the family because of the large number of valid
feature combinations that may exist. Thus, we want to find a minimal subset of
the product family that allows us to test all these possible combinations
(pairwise). Furthermore, when testing a single product is a great effort, it is
desirable to first test products composed of a set of priority features. This
problem is called Prioritized Pairwise Test Data Generation Problem.
State-of-the-art algorithms based on Integer Linear Programming for this
problema are faster enough for small and medium instances. However, there
exists some real instances that are too large to be computed with these
algorithms in a reasonable time because of the exponential growth of the number
of candidate solutions. Also, these heuristics not always lead us to the best
solutions. In this work we propose a new approach based on a hybrid
metaheuristic algorithm called Construct, Merge, Solve & Adapt. We compare this
matheuristic with four algorithms: a Hybrid algorithm based on Integer Linear
Programming ((HILP), a Hybrid algorithm based on Integer Nonlinear Programming
(HINLP), the Parallel Prioritized Genetic Solver (PPGS), and a greedy algorithm
called prioritized-ICPL. The analysis reveals that CMSA results in
statistically significantly better quality solutions in most instances and for
most levels of weighted coverage, although it requires more execution time.
- Abstract（参考訳）: ソフトウェア製品ライン(SPL)では、多数の有効な機能の組み合わせが存在するため、家族のすべての製品をテストするのは難しい、あるいは不可能かもしれない。
ですから私たちは,これらすべての組み合わせ(pairwise)をテスト可能な,製品ファミリの最小限のサブセットを見つけたいと思っています。
さらに、1つの製品をテストすることは大きな努力であり、優先順位のあるフィーチャのセットからなる製品を最初にテストすることが望ましい。
この問題は優先順位付きペアワイズテストデータ生成問題と呼ばれる。
この問題に対する整数線形プログラミングに基づく最先端のアルゴリズムは、中小のインスタンスでは十分高速である。
しかし、これらのアルゴリズムで計算するには大きすぎる実例がいくつか存在するが、これは候補解の数の指数関数的増加のためである。
また、これらのヒューリスティックスは必ずしも最良のソリューションに導くとは限らない。
本研究では,コンストラクタ,マージ,解決,適応と呼ばれるハイブリッドメタヒューリスティックアルゴリズムに基づく新しいアプローチを提案する。
整数線形プログラミング(hilp)に基づくハイブリッドアルゴリズム、整数非線形プログラミング(hinlp)に基づくハイブリッドアルゴリズム、並列優先順位付き遺伝的ソルバ(ppgs)、および優先度付きicplと呼ばれる欲望アルゴリズムである。
分析の結果、cmsaは、より多くの実行時間を必要とするものの、ほとんどのインスタンスとほとんどのレベルの重み付きカバレッジにおいて、統計的にはるかに優れた品質ソリューションをもたらすことが判明した。
関連論文リスト
- GreedyML: A Parallel Algorithm for Maximizing Submodular Functions [2.9998889086656586]
分散メモリマルチプロセッサ上での単調部分モジュラ関数の最大化のための並列近似アルゴリズムについて述べる。
我々の研究は、データ要約、機械学習、グラフスカラー化といった分野における実践的な応用のために、大規模データセットのサブモジュラー最適化問題を解決する必要性によって動機付けられている。
論文 参考訳（メタデータ） (2024-03-15T14:19:09Z) - Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。
プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。
各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
論文 参考訳（メタデータ） (2023-06-07T14:07:35Z) - ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle
Verifiers [60.6418431624873]
大きな言語モデル(LLM)は、機能記述からコードを実装するのに優れているが、アルゴリズムの問題に悩まされている。
我々は,アルゴリズムプログラムを LLM 生成 Oracle で合成するフレームワーク ALGO を提案し,その生成をガイドし,その正確性を検証する。
実験の結果,ALGOを装着すると,Codexモデルよりも8倍,CodeTよりも2.6倍の1サブミッションパス率が得られることがわかった。
論文 参考訳（メタデータ） (2023-05-24T00:10:15Z) - Combining K-means type algorithms with Hill Climbing for Joint
Stratification and Sample Allocation Designs [0.0]
これは、基本層のすべての可能な成層集合から最適成層を探索するサンプル問題である。
それぞれのソリューションのコストを評価するのに 費用がかかります
上記のアルゴリズムと最近の3つのアルゴリズムの多段階組み合わせを比較し、ソリューションコスト、評価時間、トレーニング時間を報告する。
論文 参考訳（メタデータ） (2021-08-18T08:41:58Z) - Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。
本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
論文 参考訳（メタデータ） (2021-07-05T00:51:02Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。