Ant Colony Optimization for Feature Selection in Software Product Lines

doi:10.1007/s12204-013-1468-0

上海交通大学学报（英文版） ›› 2014, Vol. 19 ›› Issue (1): 50-58.doi: 10.1007/s12204-013-1468-0

Ant Colony Optimization for Feature Selection in Software Product Lines

WANG Ying-lin1,2* (王英林), PANG Jin-wei2 (庞金伟)

(1. School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China; 2. Department of Computer Science and Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

出版日期:2014-01-15 发布日期:2014-01-15
通讯作者: WANG Ying-lin(王英林) E-mail:dr.y.wang@ieee.org

Ant Colony Optimization for Feature Selection in Software Product Lines

WANG Ying-lin1,2* (王英林), PANG Jin-wei2 (庞金伟)

(1. School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China; 2. Department of Computer Science and Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

Online:2014-01-15 Published:2014-01-15
Contact: WANG Ying-lin(王英林) E-mail:dr.y.wang@ieee.org

摘要/Abstract

摘要： Software product lines (SPLs) are important software engineering techniques for creating a collection of similar software systems. Software products can be derived from SPLs quickly. The process of software product derivation can be modeled as feature selection optimization with resource constraints, which is a nondeterministic polynomial-time hard (NP-hard) problem. In this paper, we present an approach that using ant colony optimization to get an approximation solution of the problem in polynomial time. We evaluate our approach by comparing it to two important approximation techniques. One is filtered Cartesian flattening and modified heuristic (FCF+M-HEU) algorithm, the other is genetic algorithm for optimized feature selection (GAFES). The experimental results show that our approach performs 6% worse than FCF+M-HEU with reducing much running time. Meanwhile, it performs 10% better than GAFES with taking more time.

关键词: ant colony optimization, ant colony system, software product lines, feature model

Abstract: Software product lines (SPLs) are important software engineering techniques for creating a collection of similar software systems. Software products can be derived from SPLs quickly. The process of software product derivation can be modeled as feature selection optimization with resource constraints, which is a nondeterministic polynomial-time hard (NP-hard) problem. In this paper, we present an approach that using ant colony optimization to get an approximation solution of the problem in polynomial time. We evaluate our approach by comparing it to two important approximation techniques. One is filtered Cartesian flattening and modified heuristic (FCF+M-HEU) algorithm, the other is genetic algorithm for optimized feature selection (GAFES). The experimental results show that our approach performs 6% worse than FCF+M-HEU with reducing much running time. Meanwhile, it performs 10% better than GAFES with taking more time.

Key words: ant colony optimization, ant colony system, software product lines, feature model

中图分类号:

TP 311.5

WANG Ying-lin1,2* (王英林), PANG Jin-wei2 (庞金伟). Ant Colony Optimization for Feature Selection in Software Product Lines[J]. 上海交通大学学报（英文版）, 2014, 19(1): 50-58.

WANG Ying-lin1,2* (王英林), PANG Jin-wei2 (庞金伟). Ant Colony Optimization for Feature Selection in Software Product Lines[J]. Journal of shanghai Jiaotong University (Science), 2014, 19(1): 50-58.

参考文献

[1] Carnegie Mellon Software Engineering Institute. Software product lines [EB/OL]. (2012-11-10). http://www.sei.cmu.edu/productlines/.
[2] Pohl K, Bockle G, Van Der Linden F. Software product line engineering: Foundations, principles, and techniques [M]. Heidelberg, Berlin: Springer-Verlag,2005.
[3] Kang K C, Kim S, Lee J, et al. FORM: A featureoriented reuse method with domain-specific reference architectures [J]. Annals of Software Engineering,1988, 5(1): 143-168.
[4] White J, Dougherty B, Schmidt D C. Selecting highly optimal architectural feature sets with filtered Cartesian flattening [J]. Journal of Systems and Software,2009, 82(8): 1268-1284.
[5] Dorigo M, Birattari M, St¨utzle T. Ant colony optimization: Artificial ants as a computational intelligence technique [M]. Cambridge, MA: MIT Press,2004.
[6] Wikipedia. Ant colony optimization algorithms[EB/OL]. (2012-11-10). http://en.wikipedia.org/wiki/Ant colony optimization algorithms#cite ref-0.
[7] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies [C]//Proceedings of RCAL91: European Conference on Artificial Life.Paris, France: Elsevier, 1991: 134-142.
[8] Dorigo M. Optimization, learning and natural algorithms[D]. Italy: Politecnico di Milano, 1992 (in Italian).
[9] Mannion M. Using first-order logic for product line model validation [C]//Proceedings of the 2th International Conference on Software Product Lines(SPLC’02). San Diego, USA: Springer-Verlag, 2002:176-187.
[10] Batory D. Feature models, grammars, and propositional formulas [C]//Proceedings of the 5th International Conference on Software Product Lines(SPLC’05). Rennes, France: Springer-Verlag, 2005: 7-20.
[11] Czarnecki K, Wasowski A. Feature diagrams and logics: There and back again [C]//Proceedings of the 7th International Conference on Software Product Lines (SPLC’07). Kyoto, Japan: Springer-Verlag,2007: 23-34.
[12] Benavides D, Trinidad P, Ruiz-Cortes A. Automated reasoning on feature models [C]//17th International Conference on Advanced Information Systems Engineering. Porto, Portugal: CAiSE’05 Workshops,2005: 491-503.
[13] Karatas A S, Oguztuzun H, Dogru A H. Mapping extended feature models to constraint logic programming over finite domains [C]//Proceedings of the 10th International Conference on Software Product Lines (SPLC’10). Jeju Island, South Korea: Springer-Verlag, 2010: 286-299.
[14] Alsuwaiyel M H. Algorithms design techniques and analysis [M]. Singapore: World Scientific, 1999.
[15] Guo J M, White J, Wang G X, et al. A genetic algorithm for optimized feature selection with resource constraints in software product lines [J]. Journal of Systems and Software, 2011, 84(12): 2208-2221.
[16] St¨utzle T, Hoos H H. MAX-MIN ant system [J].Future Generation Computer Systems, 2000, 16: 889-914.
[17] Dorigo M, Gambardella L M. Ant colony system:A cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[18] Akbar M M, Manning E G, Shoja G C, et al. Heuristic solutions for the multiple-choice multidimension knapsack problem [C]//Proceedings of the 9th International Conference on Conceptual Structures(ICCS’01). Heidelberg, Berlin: Springer-Verlag, 2001:659-668.
[19] Thum T, Batory D, Kastner C. Reasoning about edits to feature models [C]//Proceedings of the 31st International Conference on Software Engineering.Vancouver, Canada: IEEE, 2009: 254-264.

Ant Colony Optimization for Feature Selection in Software Product Lines

Ant Colony Optimization for Feature Selection in Software Product Lines

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价