多目标测试用例优先排序(Multi-objective Test Case Prioritization, MOTCP)在测试用例集中寻找同时满足多个优化目标的测试用例执行序列,是软件测试领域中的重要研究方向之一。在多个优化目标的作用下,所有最优解形成的集合构成MOTCP...
详细信息
多目标测试用例优先排序(Multi-objective Test Case Prioritization, MOTCP)在测试用例集中寻找同时满足多个优化目标的测试用例执行序列,是软件测试领域中的重要研究方向之一。在多个优化目标的作用下,所有最优解形成的集合构成MOTCP问题的最优解集,即帕累托最优解集(Pareto Front)。在理想的情况下,采用多目标进化算法求解MOTCP问题的过程是一个不断逼近并最终达到帕累托最优解集的过程。但是在实际求解的过程中,多目标的进化算法并不能保证能找到真正的帕累托最优解集。蚁群优化算法(Ant Colony Optimization, ACO)是一种群体智能的启发式优化算法被应用于解决MOTCP问题,但存在收敛速度缓慢且容易陷入局部最优的问题。生物学中,上位效应(Epistatic-Domain Effect)是遗传学中基因相互作用的现象,具体是指一个位点能够掩盖或减弱另一个位点基因效应的表达。MOTCP问题中同样存在上位效应,即在一个可行解中,测试优化目标受不同序列位上的测试用例共同作用,排列在前面的测试用例能够阻止或减弱排列在后面的测试用例对某测试目标的表达。相关研究表明,排列在前端的测试用例序列段能决定MOTCP的适应度值,该段序列被称作是上位基因段(Epistatic-Domain Test Case Segment, ETS)。我们将这种测试用例间的相互关系称作是测试用例优先排序(Test Case Prioritization, TCP)的上位效应。本文将TCP问题的上位效应与多目标蚁群优化算法相结合,提出了一种基于ETS的信息素更新策略,并进一步对蚁群算法进行优化改进,研究一种面向MOTCP问题的基于上位效应的蚁群优化算法。在信息素更新策略中,首先选取ETS作为信息素更新范围；其次,基于蚁群优化算法分布求解的方式,利用测试用例间的适应度增量调整路径上的信息素增量,采用信息素标记测试用例间的上位关系。在保证蚁群算法解集质量的情况下,通过估算ETS长度动态设置蚂蚁遍历测试用例的搜索终点,降低蚂蚁依次访问测试用例序列的时间消耗,进一步提升算法性能。两组对比实验结果表明,上位效应与蚁群算法相结合能够提升求解MOTCP问题时的收敛速度和求解效果。与目前应用最广泛的NSGA-Ⅱ相比较,基于上位效应的帕累托最优解集可以支配NSGA-Ⅱ的帕累托最优解集。
含路径和终端约束的动态多目标优化是过程系统工程的一个重要研究方向,难度较高。传统蚁群算法仅适于离散问题,今采用混合正态分布描述信息素分布,并设计相应的解构造操作,使之拓宽至连续优化问题。通过对目标函数和约束矩阵的非劣排序,确定解的等级,用以克服传统约束处理方法的局限性。借鉴了免疫系统的浓度概念,将其与解的等级结合,共同确定解的适应度,有助于保持种群的多样性。在更新信息素时将利用外部优解库和种群信息,可加快收敛速度。基于拥挤度距离更新外部优解库可更均匀地逼近Pareto最优解集。由此构建了一种基于免疫机制的多目标蚁群算法(Immune Mechanism based Multi-Objective Ant Colony Algorithm,IM-MOACA),并用于间歇反应器的动态多目标优化问题,效果良好,显示出较强的全局优化性能,能以较快的速度逼近真实的Pareto最优前沿,可为用户进行合理的决策分析提供有效的支持。
暂无评论