SSBSE 2015, Bergamo Transformed Search Based Software Engineering: A New Paradigm of SBSE He JIANG, Zhilei Ren, Xiaochen Li, Xiaochen Lai jianghe@dlut.edu.cn School of Software, Dalian Univ. of Tech.
Outline Roadmap of Search Based Software Engineering Transformed Search Based Software Engineering Search Space Reduction for the NRP Search Space Smoothing for the NRP Related Work
Roadmap of Search Based Software Engineering Challenges: 1.Numerous Local Optimal Solutions 2.Rugged Landscape of Search Space across all the stages of the software lifeycle many search algorithms are employed
Outline Roadmap of Search Based Software Engineering Transformed Search Based Software Engineering Search Space Reduction for the NRP Search Space Smoothing for the NRP Related Work
Transformed Search Based Software Engineering Transformed Search Based Software Engineering (TSBSE): we firstly transform the search space to facilitate the process of searching solutions, by 1) search space reduction 2) search space smoothing. Then search the solution of the SE task on the transformed search space. Search out of the sea Search in the pool Search space reduction Search space smoothing 1.How to incorporate the search space reduction into SBSE 2. How to apply search space smoothing techniques into SBSE
Backbone Based Search Space Reduction Search space reduction by the backbone Backbone: the shared common parts of the optimal solutions backbone muscle fat Related Problems Intractability Can we achieve backbone within polynomial time? Approximating backbone Backbone based reduction How to achieve approximate backbone How to apply (approximate) backbone onto the search space reduction?
Backbone Based Search Space Reduction TSBSE: framework for search space reduction Obtain the backbone Search space reduction Refine the solution Achieve the best solution
Search Space Smoothing for SBSE Design search space smoothing techniques for SBSE Smoothing:normalizing the rugged search space Related Problems Smoothing techniques Time cost How to design smoothing techniques for SE tasks? To balance between time cost and solution quality
Search Space Smoothing for SBSE TSBSE: framework for search space smoothing Generate initial solutions and search space Smoothing iteratively Searching Achieve the best solution
Outline Roadmap of Search Based Software Engineering Transformed Search Based Software Engineering Search Space Reduction for the NRP Search Space Smoothing for the NRP Related Work
Search Space Reduction for the NRP The NRP Problem In the requirements analysis phase Each requirement need a budget The candidate requirements may interdependency Each customer provides a potential profit for the company when being satisfied Determine a subset of customers to achieve maximum profits under a predefined budget bound Xuan, Jifeng,Jiang, He(*),Ren, Zhilei,Luo, zhongxuan,solving the Large Scale Next Release Problem with a Backbone Based Multilevel Algorithm,IEEE Transactions on Software Engineering,2012
Search Space Reduction for the NRP The NRP: time complexity for obtaining the backbone It is intractable to obtain the backbone within polynomial time. NP-Hard. The NRP: approximate backbone Obtain the approximate backbone from the common part of local optimal solutions. Xuan, Jifeng,Jiang, He(*),Ren, Zhilei,Luo, zhongxuan,solving the Large Scale Next Release Problem with a Backbone Based Multilevel Algorithm,IEEE Transactions on Software Engineering,2012
Search Space Reduction for the NRP The NRP: backbone based search space reduction Xuan, Jifeng,Jiang, He(*),Ren, Zhilei,Luo, zhongxuan,solving the Large Scale Next Release Problem with a Backbone Based Multilevel Algorithm,IEEE Transactions on Software Engineering,2012
Search Space Reduction for the NRP The NRP: backbone based search space reduction Xuan, Jifeng,Jiang, He(*),Ren, Zhilei,Luo, zhongxuan,solving the Large Scale Next Release Problem with a Backbone Based Multilevel Algorithm,IEEE Transactions on Software Engineering,2012
Search Space Reduction for the NRP The NRP: backbone based search space reduction Xuan, Jifeng,Jiang, He(*),Ren, Zhilei,Luo, zhongxuan,solving the Large Scale Next Release Problem with a Backbone Based Multilevel Algorithm,IEEE Transactions on Software Engineering,2012
Outline Roadmap of Search Based Software Engineering Transformed Search Based Software Engineering Search Space Reduction for the NRP Search Space Smoothing for the NRP Related Work
Search Space Smoothing for the NRP The NRP: smoothing techniques Power law, Reciprocal, Sigmoidal Smoothing, etc. The NRP: Power law Formula [1] (Memetic Algo.) α:the degree of smoothing (1) where i is the profit of customer i is the average profit of all customers controls the degree of smoothing Smoothing the rugged search space with α, and optimizing the initial solution [1] Coy S. P., Golden B. L., Runger G. C., Wasil, E. A.: See the forest before the trees: fine-tuned learning and its application to the traveling salesman problem. IEEE SMCA (2004)
Search Space Smoothing for the NRP The NRP: search space smoothing for the NRP Generate initial solutions Smoothing Memetic Algo. (MA) Best solution achieved Jiang, He(*), Ren, Zhilei,Li, Xiaochen,Lai, Xiaochen,Transformed Search Based Software Engineering: A New Paradigm of SBSE,SSBSE,2015
Search Space Smoothing for the NRP The NRP: search space smoothing for the NRP Parameter α Small scale instances Large scale instances Results: search space smoothing is effective for the NRP and obtains solutions that are better than the currently best known solutions over 6 instances Jiang, He(*), Ren, Zhilei,Li, Xiaochen,Lai, Xiaochen,Transformed Search Based Software Engineering: A New Paradigm of SBSE,SSBSE,2015
Outline Roadmap of Search Based Software Engineering Transformed Search Based Software Engineering Search Space Reduction for the NRP Search Space Smoothing for the NRP Related Work
Related Work Jifeng Xuan,He Jiang(*),Yan Hu,Zhilei Ren,Weiqin Zhou,Towards Effective Bug Triage with Software Data Reduction Techniques,IEEE Transactions on Knowledge and Data Engineering,2015,27(1):264-280 Zhilei Ren,He Jiang(*),Jifeng Xuan,Yan Hu,Zhongxuan Luo,New Insights Into Diversification of Hyper-Heuristics,IEEE Transactions on Cybernetics,2014,44(10): 1747-1761 Xuan, Jifeng,Jiang, He(*),Ren, Zhilei,Luo, zhongxuan,solving the Large Scale Next Release Problem with a Backbone Based Multilevel Algorithm,IEEE Transactions on Software Engineering, 2012, 38(5): 1195-1212 Ren, Zhilei,Jiang, He(*),Xuan, Jifeng,Luo, Zhongxuan,An Accelerated-Limit- Crossing-Based Multilevel Algorithm for the p-median Problem,IEEE Transactions on Systems, Man, and Cybernetics. Part B-Cybernetics,2012,42(4):1187-1202 Xuan, Jifeng1,Jiang, He1(*),Ren, Zhilei1,Zou, Weiqin1,Developer prioritization in bug repositories,34th International Conference on Software Engineering,2012.7.2-2012.7.9 Webstie for TSBSE:oscar-lab.org/stbse/
Conclusion Transformed Search Based Software Engineering (TSBSE) provides a new framework for SBSE, which can be incorporated into existing studies as you like. Future directions: When it works? Which one (reduction/smoothing) works better?
Thanks!