摘要:由于软件可靠性模型大多是非线性模型，导致其参数难于估计。总结了常用的软件可靠性模型的参数估计方法，提出一种基于蚁群算法的可靠性模型参数估计方法。通过对Musa软件可靠性模型分类方案中三个不同类型模型（G.O模型、Weibull模型以及M.O模型）的实验，发现本算法对不同模型具有很好的适应性，解决了应用传统数值计算方法时的无法收敛问题；与粒子群算法相比，本算法的收敛速度比粒子群算法快一倍以上，且对于部分实验对象的拟合结果精度比粒子群算法高一个数量级以上。
关键词:蚁群算法；软件可靠性模型；参数估计�
中图分类号: TP311文献标志码:A
�
Estimating parameters of software reliability models by ant colony algorithm
ZHENG Chang.you�1�*, LIU Xiao.ming�1, HUANG Song�2
�
1.Institute of Command Automation, PLA University of Science and Technology, Nanjing Jiangsu 210007, China�;�
2.Engineering Institute of Corps of Engineers, PLA University of Science and Technology, Nanjing Jiangsu 210007, ChinaAbstract:
Software reliability modeling is one of the basements of software reliability engineering. Most software reliability models’ parameters are hard to estimate, as they are nonlinear functions. The most widely used methods for parameters estimating of software reliability models have been summarized, and a new approach based on Ant Colony Algorithm is proposed in this paper. Experiments with three typical models－G.O model, Weibull model and M.O model－show that this algorithm demonstrates good applicability. And the results demonstrate that the proposed method has solved the nonconvergent problem resulted from traditional methods. Comparing with Particle Swarm Optimization, the method given in this paper shows up to two times faster convergence rate, and for some subjects, the new method shows ten times higher precision.
It is difficult to estimate the parameters of software reliability models, since most of them are non.linear models. The most widely used methods for parameters estimating of software reliability models have been summarized, and a new approach based on ant colony algorithm was proposed. The experiments with three typical models, G.O model, Weibull model and M.O model, show that this algorithm demonstrates good applicability. And the results demonstrate that the proposed method has solved the nonconvergent problem that resulted from traditional methods. Compared with Particle Swarm Optimization (PSO), the method given in this paper shows up to two times faster convergence rate, and for some subjects, the new method shows ten times higher precision.
�Key words:
ant colony algorithm; software reliability models; parameters estimating
�
0 引言�
随着计算机技术的发展，各种各样高度复杂的软件系统正逐步渗透到航空航天、工业过程控制、交通运输、金融、医疗卫生等关键领域，并发挥着越来越大的作用。运用于这些领域的软件一旦失效，将会给人类的生命、财产造成重大乃至灾难性的损失。因此，软件可靠性越来越受到研究者的重视。IEEE计算机学会对软件可靠性做出如下的定义�［1］：1)在规定的条件下，在规定的时间内，软件不引起系统失效的概率；2)在规定的时间周期内，在所述条件下程序执行所要求的功能的能力。软件可靠性建模是针对软件可靠性的理论研究和工程实践的重要领域之一�［2］。到目前为止，已经发表了近百种软件可靠性模型。这些模型大多是非线性函数模型，其参数难于估计。蚁群算法最初由Dorigo等于1991年提出�［3-4］，本质是一种基于种群的模拟进化算法。该算法采用正反馈并行自催化机制，具有鲁棒性强、计算机制优越、易于与其方法结合等优点。蚁群算法最初用于解决旅行商问题（Traveling Saleman Problem，TSP）问题�［5］，经过多年的发展，已经陆续渗透到其他领域中，如图着色问题、大规模集成电路设计以及负载平衡问题、车辆调度问题等。近年来，在求解通信网络中的组播路由问题�［6-7］和网络服务发现�［8-9］方面，蚁群算法也得到了较好的应用。同时，它对一般函数的优化问题也有较好的性能�［10］，能够克服传统优化方法的许多不足和缺陷，操作和实现简单，解的全局性好，收敛速度快，因而适用于可靠性模型参数的最优估计。�
1 相关工作�
传统上两种最常用的参数估计方法是极大似然法和最小二乘法。极大似然法在处理大规模样本数据时较为常用，最小二乘法主要适合于样本数据较小的情况�［11］。由于极大似然法和最小二乘法都包含了概率论与数理统计方面的特性，因此可能破坏软件可靠性模型参数估计的约束条件�［12-13］。当可靠性模型较为复杂或者软件失效数据规模较为庞大时，这两种方法通常无法找到参数估计的最优解，此时大多转而采用数值计算方法�［14］。而传统数值方法常常需要面临不能收敛或迭代过程过分依赖初值等问题，因此需要寻找更好的模型参数估计方法。�
近年来，研究者们针对不同的软件可靠性模型先后提出了一些新的参数估计方法。文献［15］在认真分析了超几何模型的似然函数的基础上,提出了一种进行最大似然估计的新算法。日本广岛大学的Okamura和Dohi等�［16-18］提出了基于期望最大（Expectation.Maximization，EM）原则的可靠性模型参数估计方法，并将该方法先后应用于混合软件可靠性模型、离散时间的软件可靠性模型和基于马尔可夫调制的软件可靠性模型的参数估计中。一种新的思路是将智能搜索算法应用到可靠性模型的参数估计中：文献［13］提出将遗传算法用于超几何软件可靠性模型的参数估计，该方法通过一个比例系数缩短所需编码的位串长度，以解决由于软件可靠性模型的参数取值范围广泛且难以事先确定带来的搜索空间过大的问题；由于文献［13］的方法中比例系数的值只能通过反复实验人工加以确定，针对这个问题，文献［2］提出了以有效数字的思想和计算机中对浮点数的表示方法为核心的编码策略，该方法可在满足一般精度要求的情况下，扩大定长编码可表示的参数空间；张克涵等�［19］使用粒子群优化算法（Particle Swarm Optimization，PSO）进行软件可靠性模型的参数估计，该方法的缺陷在于由于搜索范围大，导致算法收敛速度较慢。�
本文将蚁群算法应用到软件可靠性模型的参数估计中来。第2节简要概述了蚁群算法的有关原理和主要思想；第3节将蚁群算法进行改进，使其适用于软件可靠性模型的参数估计，提出了用于软件可靠性模型参数估计的算法；第4节介绍了软件可靠性模型的分类方法，并选择了属于不同类别的三个模型――G.O模型、Weibull模型以及M.O模型作为本文的实验对象，实验结果显示本文提出的算法对不同类型的可靠性模型具有较好的适应性，与传统数值计算方法（高斯-牛顿法）相比，本算法不存在无法收敛的情况，与对比方法粒子群算法相比，收敛速度更快，精度更高。�