本发明属于基于搜索的软件工程领域，具体为一种基于多目标优化算法的软件产品线配置方法。
背景技术：
软件产品线工程中开发单个产品的过程称为产品定制，这其中一个关键步骤就是根据产品需求选择合适的功能模块。这实际上是特征选择问题，一般而言，若无自动化支持，特征选择过程是很难达到最优化的。原因在于，这些功能模块之间的约束关系一般是通过树形结构的关系以及跨树的约束关系表示，限制可组合产品的可能性；且当软件产品线的规模较大时，其中的特征数量将会十分庞大。这种情况下，在软件产品线中选择一个或一组符合需求的软件产品，其本质上是在一个极大的搜索空间中选择满足多个目标的最优产品，并且搜索空间中多数目标之间还存在约束关系，这就为最优化选择工作带来了极大的限制。
软件产品线的多目标最优特征选择问题，面临的关键问题主要包括：
(1)特征间的依赖和约束关系是判断配置方案有效性重要依据，任何违反约束的配置方案都是无效的；而随着特征数量的增大，这些关系变得数量庞大且错综复杂，往往会因为选择一个新特征而导致已选的多个其他特征变得无效，这样的情况非常普遍，需耗费大量时间。
(2)对非功能性需求的满足，越来越成为软件产品成败的关键；非功能性需求实质上是用户的偏好需求，这对于当前软件即服务的生产理念而言至关重要，但满足一个其他质量属性的同时会导致系统性能在一定程度上下降，因此必须权衡多个非功能性需求的满足，以达到系统整体质量最优。
(3)一个产品线中明确的功能需求往往成百上千，但用户明确需要的并不多，所以有效避免用户对规模庞大的无关特征进行逐个判断。
目前，相关研究人员提出了许多方法来解决软件产品线最优产品选择问题，主要方法有两类。
单目标最优软件产品选择方法，在此类方法中，选择的目标只有一个，常见的目标就是希望产品的成本最低；采用遗传算法定义一种代价函数，并将软件产品线的特征模型建模成最小费用流问题，其中产品配置网络被表示为流网络。在相应的产品配置网络找出最短路径即可轻松获得满足优化目标的最优产品。
多目标最优软件产品选择方法，在此类方法中搜索目标考虑更多的特征信息，优化的目标更多，有3个以上甚至10个以上。主要采用演化多目标优化算法(emo)，并采用在初试种群植入有效产品、提出启发式技术push和pull最小化产品违反约束数等方式提高算法得到的产品结果的有效性和多样性。
可满足性(sat)求解器是软件工程领域通用的约束满足性求解技术，相比前面所述的在通过改进多目标优化算法机制来提高产品结果的有效性和多样性，可满足性(sat)求解器更具有针对性，有研究结果也证明了将可满足性(sat)求解器应用到多目标优化算法的世代种群演化中对个体的修复，产品结果的有效性和多样性会更优。但在返回大比例有效产品方面依然存在一定困难，有待尝试和对比更多类型的可满足性(sat)求解器应用到多目标优化算法的效果。
这些方法从最优化选择的角度出发，采用遗传算法框架为基础的演化算法求解单目标和多目标最优软件产品选择问题，实现了自动化的从软件产品线中配置符合需求目标的有效产品，但对于高维多目标的最优选择问题，即优化需求目标在5个以上甚至更多时，这些方法在运行时间和返回大比例有效解方法表现还存在困难。
技术实现要素：
有鉴于此，本发明提出了一种基于多目标优化算法的软件产品线配置方法，能够有效降低软件产品线配置过程中所执行的时间成本，并在优化过程中修正种群中的特征个体，大大减少无效解在优化流程中花费的时间，提升配置效率；具体包括以下步骤：
s1、根据软件产品的功能性需求，提取出软件产品线的特征规则，即特征间的依赖关系和约束关系，将这些特征间的依赖和约束规则描述成特征模型规则，并将特征模型规则按照深度遍历的序号标识出每一个特征；
s2、随机生成指定个数的特征模型配置解，这n个随机配置解形成特征模型配置解的初始种群；
s3、根据特征规则，对初始化随机生成的特征模型配置进行修正；
s4、计算修正后初始种群中每个特征模型随机解的适应度，在该种群中选择适应度较高的特征模型配置随机解进入下一代，将子代种群置于父代种群进行演化直至得到最终的特征模型配置集合；
s5、根据用户对软件产品配置的非功能性需求，对最终的特征模型配置集合进行pareto排序，并去除其中的无效特征个体，得到软件产品的特征最优解集，按照所述最优解集对软件产品进行配置。
本发明的有益效果：
本发明相比现有解决多目标最优软件产品选择问题的方法，具有如下优点：采用深度遍历的序号标识出每一个特征，使用左右元二元组的方式来表示特征间的依赖关系和约束关系，大大减少特征规则数量，提高方法的执行效率；本发明使用随机局部搜索(sls)类型可满足性(sat)请求器，在每次演化过程中都对新的特征种群中特征配置方案进行修正，减少无效配置方案在优化过程所带来的影响，本发明能够在求解大规模的软件产品线时也可快速的产生有效解，并且能够返回大比例的有效产品。
附图说明
图1为本发明实施例的一种基于多目标优化算法的软件配置线方法的流程图；
图2为本发明实施例给出的一个手机产品线特征模型图。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
图1是本发明实施例提供的一种基于多目标优化算法的软件产品线配置方法，如图1所示，所述方法包括如下步骤：
s1、根据软件产品的功能性需求，提取出软件产品线的特征规则，即特征间的依赖关系和约束关系，将这些特征间的依赖和约束规则描述成特征模型规则，并将特征模型规则按照深度遍历的序号标识出每一个特征；
每个软件产品都具有一定的功能性需求，主要是对于某一具体功能实现的需求；软件产品线中的产品集合是由多个特征构建而成，这些特征之间的约束关系用树形结构的关系以及跨树的约束关系表示，因此本实施例将软件产品所需的功能需求转换为特征和特征间的约束表达，并通过一定的方式提取出软件产品的特征以及特征间的约束关系；所述特征模型是由特征以及特征之间的关系组成的属性结构。
本实施例中的在一些实施例中，本发明将软件产品线的特征间的依赖关系和约束关系采用元组的方式进行表达，以便计计算机程序识别，其中元组中的元素是由深度遍历特征模型的序号作为特征的唯一标识。
所述特征规则模型由一个二元组和数值约束区间组成，二元组中的元素可以包括单个特征也可以包括特征组，当为所述单个特征时，所述数值约束空间为空，当为所述特征组时，所述特征组包括多个特征成员和数值约束区间，所述数值约束区间表示特征组中可以选择的特征个数下限与上限。
具体的，所述二元组(a,b)的元素a成为左元，b成为右元；二元组(a,b)表示左元a满足即特征a被选择时，右元b即特征b必须被选择；当右元是特征组时，特征模型规则(a,[b,c,d]){m，n}表示当左元a被满足时，右元[b,c,d]中被满足的元素个数必须在m到n之间；m和n可以分别表示组合中可以同时选中的特征个数下限和上限。
在特征模型中，根特征是必须被选择的，因此为了简化表示特征模型中根特征的必须特征相关的关系规则时，需要将至少一个特征设置为根特征，设定一个特征左元
s2、随机生成指定个数的特征模型配置解，这n个随机配置解形成特征模型配置解的初始种群；
假设所求解的特征模型中有n个特征，那么生成的初始种群中的随机解的个数就是n，将每个特征作为一个个体，共有n个特征个体，产生每个特征个体的随机解；随机生成指定数量n个特征模型配置解，每个配置解是一个长度为特征模型的特征数m的二进制序列，采用二进制序列表示是否选中特征模型中的特征，所述二进制序列的顺序与深度遍历软件产品的特征模型得到的序列一致；其中，1表示选择该序列位置的特征，0表示排除该序列位置的特征；这n个随机配置解形成特征模型配置解的初始种群。
对于软件产品配置，其核心思想就是为了选择特征进行配置，因此通过01二进制序列这种二分类方式能够有效的挑选出合适的特征。
s3、计算修正后初始种群中每个特征模型随机解的适应度，在该种群中选择适应度较高的特征模型配置随机解进入下一代，将子代种群置于父代种群进行演化直至得到最终的特征模型配置集合；
对初始种群中的每个特征个体和每条特征规则，本着尽可能最大化的修正个体中的所选特征的原则进行修正；由于在初始种群中，每个特征被随机分配了初始解，该初始解对于该特征的具体值为0或者1，为0时，表示该特征未被选择，为1时，表示该特征已被选择，本实施例正是根据特征规则对这些初始解进行修正，去除其中不满足特征规则的解，并重新分配新的解。
在一个优选实施例中，为了对排他性类型的跨层次约束及其他强制存在的特征项进行表达，本实施例还定义了特殊特征规则左元ε，其对应的特征规则后项一定要被满足；特征规则左元可以作为特征规则后项的根特征；举个例子，图2给出了一个手机产品线的特征模型示例，如图2所示，手机是一个抽象特征，对于这个抽象特征我们需要对其具象化，对于一个手机，首先，其通话和屏幕是基本特征，所以通话和屏幕将作为强制性特征；而对于定位和媒体需求，这些可以作为可选的特征；而对于屏幕特征，分辨率、颜色和基本需求可以作为替代组特征。在手机产品线中，根特征手机是必须要选的，那么对于这个特征的约束关系处理规则就表示为<ε，手机>；而手机的子特征通话特征是它的必选子特征，可以表示为<手机，通话>，而手机本身就是必选特征，所以这个规则等价于<ε，通话>，也就是说，当定义出了特殊特征规则左元ε，如果某些特征之间的约束(手机特征和通话特征之间的特征约束)满足了特殊特征规则左元，则不需要再继续判断，其对应的特征规则后项肯定也满足了这些约束(手机特征与通话特征之间的特征约束)。
如果是根特征所对应的必选子特征，往下层则一直有必选子特征，那么就一直用特殊特征规则左元
在上述实施例中，考虑到特征位于特殊特征左元规则
在一个具体实现方式中，对特征选择和特征规则构建三个空集合si、se、rg；
其中s1集合是存放被选择的特征集，se集合是被排除的特征集；s1集合和se集合是互斥的特征集合，包含了所有的特征；rg集合是修正特征规则集合，也即是所有特征规则右元为特征组，且该组合中至少有一个特征元素被选择的特征规则集合，rg集合是基于上述规则修正后特征规则集合。
首先，从输入的特征规则集合中选择出所有特征规则右元为特征组，且该特征规则右元的下限大于0的修正特征规则集合rg；
在所述修正特征规则集合rg的特殊特征规则左元中，若其对应的特征规则右元为单个特征，则选择该单个特征，并根据特征规则对所述单个特征有依赖关系的相关特征选择或排除并放入对应的特征集合si或se中；
从所述修正特征规则集合rg的特征规则右元中选择特征，若该特征既不在被选择的特征集合si中也不在被排除的特征集合se中，则选中该特征，并将该特征加入到被选择的特征集合si中；
若特征规则右元中已被选择的特征个数小于下限，则将特征规则右元中既不在被选择的特征集合si中也不在被排除的特征集合se中的特征加入到被选择的特征集合si；
以上步骤执行完以后，再依次取待修正特征选择方案中的被排除特征即未被修正的初始种群中的初始解中，如果该特征其不在集合si也不在集合se中，则将该特征加入到集合si中；最后将集合si和se都映射到修正后的特征选择方案集合s′中。
直到特征规则右元中已被选择的特征大于下限，完成对特征个体的修正，并在修正后的初始种群中产生对应的解。
s4、计算修正后的初始种群中每个特征个体的适应度，在该种群中选择适应度较高的特征个体进入下一代，将子代种群置于父代种群进行演化直至得到最终的种群；
首先，从修正后的初始种群中随机选两个特征个体使用sat求解器算子进行交叉和变异操作产生子代，根据特征规则修正子代个体，并将修正后的子代个体合并去解集，计算修正后的初始种群中每个个体的适应度，根据适应度在种群中进行环境选择，在该种群中选择适应度较高的特征个体进入下一代，将子代种群置于父代种群进行演化直至得到最终的种群。修正后该步骤依次循环指定演化次数，直至演化完成得到最终的种群。
上述实施例中，对于修正后的初始种群，首先需要随机选两个特征个体使用sat求解器算子进行交叉和变异操作构成子代种群；在子代种群中按照适应度的规则进行演化，将子代种群置于父代种群进行演化直至得到最终的种群。
根据适应度函数计算修正后的种群中每个特征个体的适应度，其适应度函数为：
s5、根据用户对软件产品配置的非功能性需求，对最终的特征模型配置集合进行pareto排序，并去除其中的无效特征个体，得到软件产品的特征最优解集，按照所述最优解集对软件产品进行配置。
其中，特征模型的精化关系和跨层次的约束关系表示的是产品功能需求的约束，软件工程师和终端用户在基于特征模型进行产品定制时，除了功能需求还会有非功能性的需求，所述非功能性需求比如实现该功能需要的成本、特征对应的组件出错的次数等。
在本实施例中，排除无效特征个体，是因为参与遗传过程的配置方案可能不满足某些功能属性的数值约束，但直到优化过程结束后的pareto排序时才判断生成方案是否违反数值约束；若违反，则为无效，需排除；原因在于，在随机的优化过程中，无效解极有可能产生出有效的优化配置方案，这不符合特征约束规则的意义。
在一个实施例中，本实施例采用该研究问题中研究者们普遍采用的splot(http://www.splot-research.org/，这是一个公用的特征模型库平台)特征模型库中的真实特征模型eshop和webportal，特征模型的配置参数如表1所示。
表1特征模型的配置参数
两个特征模型中，每个特征有三个属性，分别是cost，used_before，defects。其中，cost是区间[5.0，15.0]内满足正态分布的实数值，used_before是符合均匀分布的布尔值，defects是区间[0，10]内符合正态分布的自然数。另外，used_before与defects之间存在着一定的关系：如果一个特征的used_before为false，则defects必为0。
以上者两个特征模型是相关研究者根据真实软件系统，通过逆向工程生成的特征模型，相比随机生成的特征模型，更具有实际应用意义。
为了验证本发明提出算法的正确性和有效性，同时使用现有的主流算法ibea和nsga-ii，以相同的实验条件和配置在这两个特征模型上运行，并分别采用ibea算法常采用的两个指标ε 和hd。具体步骤如下：
step1：将特征模型eshop以深度遍历的方式得到每个特征的序号做为特征的唯一标识，根据软件产品的功能性需求，提取出软件产品线的特征规则，即特征间的依赖关系和约束关系，将这些特征间的依赖和约束规则描述成特征模型规则；
step2：输入群体规模(即特征选择方案数)和最大遗传代数、特征规则集，随机生成特征选择方案初始种群，每个特征选择方案的长度与特征数相同；
step3：对初试种群使用随机局部搜索类型可满足性求解器对随机生成的初始种群个体进行修正，修正种群中不符合功能性约束规则的特征选择方案；
step4：根据适应度函数计算修正后的种群中每个个体的适应度，其适应度函数为：
step5：根据用户对软件产品的非功能性需求，也就是优化目标，对最终的种群进行pareto排序，排出无效个体，得到的就是最优解集。
分别对eshop和webportal特征模型运行nsga-ii、ibea和本发明提出的算法，产生有效解的时间对比和关于hv、spread、igd的性能指标对比结果如表2和表3所示。
表2对比的几种方法在优选特征模型上的运行时间对比
表3对比算法在优选例特征模型上的性能指标对比
其中，表3中的性能指标hv(hypervolume)计算优化解在目标空间所覆盖的体积；spread通过度量扩展程度来评估优化解的分布性，其值越大说明优化解越多样化；igd(invertedgenerationaldistance)定义最优解与优化解的距离，其值越小，说明优化解越接近最优解。
本发明可以减少多目标最优软件产品选择算法中特征约束规则的条数，提高算法效率，并及时修正违反特征规则的解，提高结果的正确性和效率。
在本发明的描述中，需要理解的是，术语“同轴”、“底部”、“一端”、“顶部”、“中部”、“另一端”、“上”、“一侧”、“顶部”、“内”、“外”、“前部”、“中央”、“两端”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。
在本发明中，除非另有明确的规定和限定，术语“安装”、“设置”、“连接”、“固定”、“旋转”等术语应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或成一体；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通或两个元件的相互作用关系，除非另有明确的限定，对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。
尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。
1.一种基于多目标优化算法的软件产品线配置方法，其特征在于：所述方法包括：
s1、根据软件产品的功能性需求，提取出软件产品线的特征规则，即特征间的依赖关系和约束关系，将这些特征间的依赖和约束规则描述成特征模型规则，并将特征模型规则按照深度遍历的序号标识出每一个特征；
s2、随机生成指定个数的特征模型配置解，这n个随机配置解形成特征模型配置解的初始种群；
s3、根据特征规则，对初始化随机生成的特征模型配置进行修正；
s4、计算修正后初始种群中每个特征模型随机解的适应度，在该种群中选择适应度较高的特征模型配置随机解进入下一代，将子代种群置于父代种群进行演化直至得到最终的特征模型配置集合；
s5、根据用户对软件产品配置的非功能性需求，对最终的特征模型配置集合进行pareto排序，并去除其中的无效特征个体，得到软件产品的特征最优解集，按照所述最优解集对软件产品进行配置。
2.根据权利要求1所述的一种基于多目标优化算法的软件产品线配置方法，其特征在于，所述将特征模型规则按照深度遍历的序号标识出每一个特征包括所述特征模型规则由一个二元组和数值约束区间组成，二元组的元素包括单个特征或特征组，当为所述单个特征时，所述数值约束空间为空，当为所述特征组时，所述特征组包括多个特征成员和数值约束区间，所述数值约束区间表示特征组中可以选择的特征个数下限与上限。
3.根据权利要求2所述的一种基于多目标优化算法的软件产品线配置方法，其特征在于，所述二元组(a,b)的元素a成为左元，b成为右元；二元组(a,b)表示左元a满足即特征a被选择时，右元b即特征b必须被选择；当右元是特征组时，特征模型规则(a,[b,c,d]){m，n}表示当左元a被满足时，右元[b,c,d]中被满足的元素个数必须在m到n之间。
4.根据权利要求3所述的一种基于多目标优化算法的软件产品线配置方法，其特征在于，将至少一个特征设置为根特征，设定一个特征左元
5.根据权利要求1所述的一种基于多目标优化算法的软件产品线配置方法，其特征在于，所述步骤s2包括随机生成指定数量n个特征模型配置解，每个配置解是一个长度为特征模型的特征数m的二进制序列，其中，1表示选择该序列位置的特征，0表示排除该序列位置的特征；这n个随机配置解形成特征模型配置解的初始种群。
6.根据权利要求1所述的一种基于多目标优化算法的软件产品线配置方法，其特征在于，所述步骤s3包括从输入的特征规则集合中选择出所有特征规则右元为特征组，且该特征规则右元的下限大于0的修正特征规则集合rg；在所述修正特征规则集合rg的特殊特征规则左元中，若其对应的特征规则右元为单个特征，则选择该单个特征；并根据特征规则对所述单个特征有依赖关系的相关特征选择或排除并放入对应的特征集合si或se中；依次从所述修正特征规则集合rg的特征规则右元中选择特征，若该特征既不在被选择的特征集合si中也不在被排除的特征集合se中，则选中该特征，并将该特征加入到被选择的特征集合si中；若特征规则右元中已被选择的特征个数小于下限，则将特征规则右元中既不在被选择的特征集合si中也不在被排除的特征集合se中的特征加入到被选择的特征集合si，直到特征规则右元中已被选择的特征大于或等于下限，完成对特征个体的修正，并在修正后的初始种群中产生对应的特征模型配置；将si集合中的特征在解中的标记设置为1，将集合se中的特征在解中的标记设置为0。
7.根据权利要求1所述的一种基于多目标优化算法的软件产品线配置方法，其特征在于，所述步骤s4中包括从修正后的初始种群中随机选两个特征模型配置使用遗传算子进行交叉和变异操作产生子代特征模型配置，根据特征规则修正子代特征模型配置，计算合并后的初始种群中每个特征个体的适应度，在该种群中选择适应度较高的特征个体进入下一代，对下一代特征模型配置进行修复，将子代特征模型配置集合置于父代特征模型配置集合进行演化直至得到最终的特征模型配置集合。
8.根据权利要求1所述的一种基于多目标优化算法的软件产品线配置方法，其特征在于，所述非功能性需求为用户预设的需求，包括实现产品功能所需要的成本以及特征对应的组件出错的次数。
9.根据权利要求1所述的一种基于多目标优化算法的软件产品线配置方法，其特征在于，所述无效特征个体为不满足功能属性的数值约束。
技术总结