Ant Colony Optimization for Feature Selection in Software Product Lines

doi:10.1007/s12204-013-1468-0

Abstract

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

摘要： 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

CLC Number:

TP 311.5

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.

References

[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.