计算机科学与探索 ›› 2017, Vol. 11 ›› Issue (11): 1733-1746.DOI: 10.3778/j.issn.1673-9418.1609032

• 系统软件与软件工程 • 上一篇    下一篇

代理模型帮助的SA层性能差分演化优化算法

杜  欣1,吴晓斌1+,倪友聪1,2,叶  鹏3,李  松1   

  1. 1. 福建师范大学 软件学院,福州 350117
    2. 伦敦大学学院 计算机科学学院,英国 伦敦 WC1E 6BT
    3. 武汉纺织大学 数学与计算机学院,武汉 430200
  • 出版日期:2017-11-01 发布日期:2017-11-10

Surrogate Model Assisted Differential Evolutionary for Performance Optimization at SA Level

DU Xin1, WU Xiaobin1+, NI Youcong1,2, YE Peng3, LI Song1   

  1. 1. Faculty of Software, Fujian Normal University, Fuzhou 350117, China
    2. Department of Computer Science, University College London, London, WC1E 6BT, UK
    3. College of Mathematics and Computer, Wuhan Textile University, Wuhan 430200, China
  • Online:2017-11-01 Published:2017-11-10

摘要: 为了在庞大空间中搜索软件体系结构(software architecture,SA)层最优性能改进方案,当前已涌现出一些以NSGA-II为代表的性能优化算法。然而这些算法大多未充分考虑性能改进空间的离散特性和性能评估的高计算代价特点,导致了解质量不高和优化时间过长的问题。针对这一问题,提出一种代理模型帮助的SA层性能差分演化优化算法SMDE4PO(surrogate model assisted differential evolution algorithm for performance optimization)。该算法采用多种交叉和变异策略以增大搜索空间和提高收敛速度,并运用随机森林作为代理模型以大幅减少实际性能评估的次数。在4个不同规模案例上的实验结果表明:(1)在贡献度、世代距离和超体积3个指标上SMDE4PO显著优于NSGA-II算法;(2)通过使用随机森林代理模型,在最好情况下SMDE4PO较NSGA-II算法的运行时间可降低48%。

关键词: 软件体系结构, 性能优化, 差分演化, 代理模型

Abstract: A few of evolutionary algorithms for performance optimization at software architecture (SA) level have been proposed to obtain the near optimal performance improvement solutions in large search space, and the NSGA-II is the typical representative of these algorithms. However, most of these algorithms do not fully consider two factors: the performance improvement space with discrete feature and the performance evaluation with the high computational effort. As a result, the solutions obtained by these algorithms are not good and the corresponding processes of performance optimization are also considerably time-consuming. Aiming at this problem, this paper proposes a surrogate model assisted differential evolution algorithm for performance optimization at SA level, which is named by SMDE4PO. In the SMDE4PO, many strategies of crossover and mutation are adopted to enlarge the search space and accelerate the convergence. Furthermore, the random forest is regarded as surrogate model to substantially reduce the number of performance evaluation. The experimental results from four different size of cases show that (1) The SMDE4PO is significantly better than the NSGA-II in three indicators of contribution, generation distance and hyper volume; (2) By means of the random forest to predict performance indices, the run time of the SMDE4PO is reduced by 48% than the NSGA-II in the best results in the experiments.

Key words: software architecture, performance optimization, differential evolution, surrogate model