结合子树分解的软件产品线特征选择方法

Software Product Lines Feature Selection Based on Feature Tree Decomposition

软件产品线的特征选择通常在一个高维且高度约束的目标空间进行.采用多目标优化算法并借助约束求解器可以在满足时间空间要求下得出满意的配置方案.在评价最终解集时,满足所有约束条件的配置(即有效解)才是实际工程所需要的产品配置,这样有效产品率是评价产品最终解集的重要指标.在应用多目标遗传算法作为产品选择的优化搜素方式时,典型的变异交叉算子在很大概率下会引入新的约束违反项,特别地,经过交叉算子后有效解的合法性有可能会被破坏.本文通过设计基于特征树子树的新交叉算子,使得交叉算子环节不再引入新的约束违反项,实验表明这种方法能显著的提高最终解集的有效产品率,在超体积指标和有效产品率指标间找到平衡.同时本文还探讨了优先考虑约束违反目标的方法对提高产品有效率的影响,对环境选择算子进行了新的定义,使得环境选择过程优先挑选出约束违反项较少的个体,这种方法能得到很高的产品有效率.

A Software Product Line（ SPL） feature selection involves the optimization of multiple objectives in a large and highly constrained search space. By using the multi-objective optimization algorithm augments constraint solving,we can find constraint-satisfying software products meeting the requirements of time and space. An invalid product is totally useless from practical perspective. During the mutation and crossover,it is very likely to turn a valid product into a invalid one. Thus,we design a novel crossover operatorSubtree Crossover,which will not introduce new violations. The result show that novel crossover significantly outperforms the state-oftheart-SATIBEA on the valid product rate. And the new approach called SATIBEA_ST only lose little scores on the hypervolume. We also demonstrate the idea of viewing number of constraint violations as the first considered objective and the rest objectives as secondary objectives to be optimized.