集成偏好的高维多目标最优软件产品选择算法

在基于搜索的软件工程研究领域,高维多目标最优软件产品选择问题是当前的一个研究热点.既往工作主要采用后验方式(即先搜索再选择)处理软件工程师或终端用户的偏好.与此不同,将用户偏好集成于优化过程,提出了一种新算法以定向搜索用户最感兴趣的软件产品.在算法中,运用权向量表达用户偏好,采用成就标量化函数(achievement scalarizing function,简称ASF)集成各个优化目标,并定义一种新关系比较个体之间的优劣.为了增强算法快速搜索到有效解的能力,分别采用DPLL/CDCL类型和随机局部搜索(SLS)类型可满足性(SAT)求解器实现了替换算子和修复算子.为了验证新算法的有效性,采用21个广泛使用的特征模型进行仿真实验,其中最大特征数为62482,最大约束数为343 944.实验结果表明,基于DPLL/CDCL类型SAT求解器的替换算子有助于算法返回有效软件产品;基于SLS类型SAT求解器的修复算子有助于快速搜索到尽可能满足用户偏好的最终产品.在处理带偏好的高维多目标最优软件产品选择问题时,综合运用两类SAT求解器是一种行之有效的方法.     

面向巡线无人机高压线实时检测与识别算法

以巡线无人机巡航中识别高压输电线为背景,提出一种准确、实时的高压输电线检测与识别算法.首先,针对高压输电线成像是线状结构和低灰度值的特征而且其空间分布近似水平,提出一种基于方向约束的多尺度线状目标强化算法.此方法把近似水平方向的高压输电线目标强化出来的同时,能够很好地抑制竖直方向线状干扰物体和非线状背景及噪声.然后,对强化后的结果进行基于角度约束的Radon变换.由于高压输电线邻近区域的灰度分布近似,在Radon变换中引入用于识别高压输电线的识别因子,以获得高压输电线的识别结果,并抑制近似水平的干扰物体.实际的飞行试验结果表明,该算法对高压输电线识别具有很好的抗噪性、抗干扰性和实时性.     

面向软件产品线中特征选择的多目标优化算法

软件产品线中产品定制的核心是选择合适的特征集.由于多个非功能需求间往往相互制约甚至冲突,特征选择的本质是多目标优化过程.优化过程的搜索空间被特征间错综复杂的依赖和约束关系以及明确的功能需求大大限制.另外,有些非功能需求有明确的数值约束,而有些则仅要求尽可能得到优化.多样的非功能需求约束类型也给优化选择过程带来极大挑战.本文提出一种含修正算子的多目标优化算法MOOFs.文中首先设计特征间依赖和约束关系描述语言DCF-DL来统一规范特征选择过程中必须遵守的规则.所有的非功能需求都转化为优化目标,相关的数值约束则作为优化过程中特征选择方案的过滤器.另外,设计了修正算子用于保证选择出的特征配置方案必满足产品线的特征规则约束.通过与四个常用的多目标优化算法在四个不同规模的特征模型上的运行结果做对比,证明本文的方法能够更快地产生满足约束的优化解,且优化解具备更好的收敛性与多样性.     

基于搜索的上下文一致性错误处理

近年来,随着智能设备的普及和传感技术的发展,上下文感知程序的应用越来越广泛。但是由于环境噪声难以预测和控制,程序所获得的上下文经常存在一致性错误。处理这类错误的方法很多,但大都忽视了两方面的问题:1)不同一致性约束之间存在相互干扰;2)处理这类错误的操作本身可能对程序的正常运行造成负面影响。以处理这两方面的问题为目标,提出了一种新的基于搜索的上下文一致性错误处理方法,亦即既设计出一个搜索空间来查找避免约束间相互干扰和对程序产生负面影响的解,又采用了一种增量式评估方案来加速搜索的效率。经实验评估,新方法能够在很短的时间内达到非常接近最优解的效果。     

一种基于新型差分进化模型的MOEA/D改进算法

针对MOEA/D算法中差分进化操作收敛精度不高且速度较慢的不足,提出了一种综合基于可控支配域的向量差生成策略和基于主成分的动态缩放因子的新型差分进化模型,均衡显性与隐性搜索引导;并实现了一种基于新型差分进化模型的MOEA/D改进算法（MOEA/D-iDE）。新型差分进化是借助基于可控支配域的非支配排序对邻域进行分层,根据分层信息生成与不同进化阶段相匹配的向量差,实现对种群收敛速度的显性引导;同时对决策空间进行主成分分析,动态调整差分进化缩放因子,实现对种群收敛精度的隐性引导。实验选取ZDT、DTLZ和WFG等为测试问题,以IGD+,ER作为评价指标,将MOEA/D-iDE算法与6个同类算法进行对比实验,结果表明新算法在保证多样性的同时具有更好的收敛速度与精度,从而验证了新型差分进化模型的有效性。     

A parallel portfolio approach to configuration optimization for large software product lines

Software product line (SPL) engineering demands for optimal or near‐optimal products that balance multiple often competing and conflicting objectives. A major challenge for large SPLs is to efficiently explore a huge space of various products and satisfy a large number of predefined constraints simultaneously. To improve the optimality and convergence speed, we propose a parallel portfolio approach, called IBEAPORT, which designs three algorithm variants by incorporating constraint solving into the indicator‐based evolutionary algorithm in different ways and performs these variants by utilizing parallelization techniques. Our approach utilizes the exploration capabilities of different algorithms and improves optimality as far as possible within a limited time budget. We evaluate our approach on five large‐scale real‐world SPLs. Empirical results demonstrate that our approach significantly outperforms the state of the art for all five SPLs on a quality indicator and a diversity indicator. Moreover, IBEAPORT quickly converges to a relatively stable hypervolume value even for the largest SPL with 6888 features.     

Heuristic and exact algorithms for product configuration in software product lines

Software product line (SPL) is a set of software applications that share a common set of features satisfying the specific needs of a particular market segment. SPL engineering is a paradigm to develop software applications that commonly use a feature model to capture and document common and variable features, and their relationships. A big challenge is to derive one product among all possible products in the SPL, which satisfies the business and customer requirements. This task is known as product configuration. Although product configuration has been extensively investigated in the literature, customer's preferences are frequently neglected. In this paper, we propose a novel approach to configure a product that considers both qualitative and quantitative feature properties. We model the product configuration task as a combinatorial optimization problem, and heuristic and exact algorithms are proposed. As far as we are concerned, this proposal is the first work in the literature that considers feature properties in both leaf and nonleaf features. Computational experiments showed that the best of our heuristics found optimal solutions for all instances where those are known. For the instances where optimal solutions are not known, our heuristic outperformed the best solution obtained by a one‐hour run of the exact algorithm by up to 67.89%.     

一种适用于软件产品线的特征模型

针对传统的特征模型中存在的对软件产品线可变性需求表达不准确、缺乏特征描述方法的问题,在FODA等方法的研究基础上,从特征模型的层次分解、特征间依赖关系、变化性表示方法等方面进行描绘,提出一种适用于软件产品线的特征模型和特征描述方法．该特征模型能够帮助产品设计人员和开发人员正确理解产品需求,也是为后续实现软件产品线自动化生产打下基础．     

基于复用的软件产品线工程关键技术研究

软件复用技术在软件工程领域具有重要作用并且被广泛应用,尤其是在软件产品线工程领域,系统化的软件复用技术为软件产品线的设计和实现提供了基础。论文首先详细阐述了具有代表性的系统化软件复用支撑技术,随后在一个通用的软件产品线参考架构的基础上,探讨了复用技术在软件产品线工程领域的主要应用形式,最后针对可变性定义及其管理问题,引人并着重探讨了三种可变性管理模型及技术。     

A systematic mapping study of search-based software engineering for software product lines

ContextSearch-Based Software Engineering (SBSE) is an emerging discipline that focuses on the application of search-based optimization techniques to software engineering problems. Software Product Lines (SPLs) are families of related software systems whose members are distinguished by the set of features each one provides. SPL development practices have proven benefits such as improved software reuse, better customization, and faster time to market. A typical SPL usually involves a large number of systems and features, a fact that makes them attractive for the application of SBSE techniques which are able to tackle problems that involve large search spaces.ObjectiveThe main objective of our work is to identify the quantity and the type of research on the application of SBSE techniques to SPL problems. More concretely, the SBSE techniques that have been used and at what stage of the SPL life cycle, the type of case studies employed and their empirical analysis, and the fora where the research has been published.MethodA systematic mapping study was conducted with five research questions and assessed 77 publications from 2001, when the term SBSE was coined, until 2014.ResultsThe most common application of SBSE techniques found was testing followed by product configuration, with genetic algorithms and multi-objective evolutionary algorithms being the two most commonly used techniques. Our study identified the need to improve the robustness of the empirical evaluation of existing research, a lack of extensive and robust tool support, and multiple avenues worthy of further investigation.ConclusionsOur study attested the great synergy existing between both fields, corroborated the increasing and ongoing interest in research on the subject, and revealed challenging open research questions.