（计算机应用技术专业论文）基于遗传算法的软件可靠性分配应用研究.pdf

璺主塑塞竺兰丝鲨苎苎三望堡竺堕堕苎壁旦茎丝坌里堕壁! 里堕堡 论文题目： 基于遗传算法的软件可靠性分配应用研究 专业：计算机应用技术 姓名：韩冰青 导师：高建华( 教授) 论文摘要 f 软件可靠性分配是软件可靠性工程的一门新的分支技术。它是指在保证可靠 硅岔标的前提下，对组成软件内部的成份做出分析，把软件分离为一个个基本元 素，并由此对软件各个元素进行可靠性目标的分配，以达到在软件开发成本一定 的情况下，使用户得到的软件可靠性尽可能地大。其中，软件元素被定义为诸如 操作、子系统、模块、对象或者是其它的能够用于可靠性分配的实体。y 本论文致力于多模块软件系统的可靠性分配技术的研究与实现，全面分析并 讨论了软件可靠性分配的三种模式框架：r c c m 模式框架、b c r m 模式框架和b c u m 模式框架，研究了软件开发的三种成本函数，并对每个模式框架进行了实例论证 和实验分析。 本论文将遗传算法应用于软件可靠性分配中，对基于遗传算法的可靠性分配 技术和传统的可靠性分配方法进行了比较。针对标准遗传算法存在着收敛速度 慢、易陷入局部极小值等缺点，本文设计并实现了自适应多种群并行遗传算法 ( a m p g a ) ，来解决大型、复杂软件系统的可靠性分配问题。最后，对“江苏省邮 政物流信息系统开发”项目中的“礼仪中心子系统”、“递送中心子系统”及“系 统管理子系统”进行了可靠性分配实验。 关键词：软件可靠性，可靠性分配，故障率，软件系统，遗传算法， 岛屿模型，症粼 堡主竺壅生堂垡笙壅 翌堑旦墨堡塞鲨堕苎生旦墨丝坌堡堕旦i ! ! 壅旦 t i t l e ： m a j o r ： n a m e ： t u t o ro r e l i a b i l i t y a l l o c a t i o na n da p p l i e dr e s e a r c h o fs o f t w a r es y s t e m b a s e do ng e n e t i ca l g o r i t h m a p p l i e dc o m p u t e rt e c h n o l o g y h a nb i n g q i n g p r o f g a oj i a n h u a a b s t r a c t s o f t w a r er e l i a b i l i t ya l l o c a t i o n i san e wb r a n c ho fs o f t w a r e e n g i n e e r i n g u n d e rt h ea s s u r a n c eo ft h e s o f t w a r er e l i a b i l i t yt a r g e t ，w e a n a l y z et h e i n n e rp a r to ft h es o f t w a r ea n ds e p a r a t et h es o f t w a r e i n t o d i f f e r e n te l e m e n t s t om a x i m i z et h er e l i a b i l i t ya t t a i n e db yt h ec u s t o m e r a tc e r t a i ns o f t w a r ed e v e l o p m e n tb u d g e t ，w ea l l o c a t ee a c he l e m e n ta c c o r d i n g t ot h er e l a t e ds o f t w a r er e li a b i l it yt a r g e t a n dt h es o f t w a r ee l e m e n t sa r e d e f i n e da so p e r a t i o n ，s u b s y s t e m ，o b j e c t o rt h ee n t i t yw h i c hc a nh e a 1l o c a t e d i nt b i st h e s i s ，w ec o n c e n t r a t eo nt h er e s e a r c ha n dr e a l i z a t i o no ft h e m u l t i m o d u l es o f t w a r er e l i a b i l i t ya l l o c a t i o nt e c h n i q u e t h r e e m o d e l f r a m e w o r k so ft h es o f t w a r er e l i a b i l i t ya l l o c a t i o n a r ed i s c u s s e da n d a n a l y z e di nd e t a i l ，w h i c h a r ea sf o l l o w s ：r c c mm o d e lf r a m e w o r k ，b c r mm o d e l f r a m e w o r ka n db c u mm o d e lf r a m e w o r k t h ec o s t f u n c t i o n so f s o f t w a r e d e v e l o p m e n t a r ed i s c u s s e d a n da l lf r a m e w o r k sa r ei l l u s t r a t e da n d e x p e r i m e n t e dw i t hd e t a i l e de x a m p l e s g e n e t i ca l g o r i t h mi sa p p l i e d t ot h es o f t w a r er e l i a b i l i t y a l l o c a t i o n ，a 1 s o ，t h ea 1 1 0 c a t i o nt e c h n i q u eb a s e do ng e n e t i ca l g o r i t h mi s c o m p a r e d w i t ht h ec o n v e n t i o n a a l l o c a t i o nt e c h n i q u e s f o r s t a n d a r d g e n e t i ca l g o r i t h mh a st h ed e f e c t so fs l o w l yc o n v e r g i n ga n de a s i l yf a l l i n g i n t ol o c a le x t r e m u m ，t h ea u t h o rd e s i g n e da n dr e a l i z e dt h ea d a p t i v e m u l t i - p o p u l a r i o np a r a l l e lg e n e t i ca l g o r i t h m ( a m p g a ) t o s o l v et h e r e l i a b i l i t y a l l o c a t i o np r o b l e m o f l a r g e a n d c o m p l i c a t e d s o f t w a r e s y s t e m s f i n a l l y ，w ee x p e r i m e n t e do nt h ec o m i t yc e n t e rs u b s y s t e m ，d e l i v e r y c e n t e rs u b s y s t e ma n ds y s t e mm a n a g e m e n ts u b s y s t e mo ft h ep r o j e c t ：t h e j i a n g s up r o v i n c ep o s t a ll o g i s t i c s i n f o r m a t i o ns y s t e m ” k e y w o r d s ：s o f t w a r er e l i a b i l i t y ，r e l i a b i l i t ya l l o c a t i o n ，f a u l tr a t e ， s o f t w a r es y s t e m ，g e n e t i ca l g o r i t h m ，i s l a n dm o d e l ，m i g r a t es t r a t e g y i i 堡主堕窒生兰垡丝苎 堡王望堕苎堕堕苎堕旦壹型望墨塑生! ! ! 型 第一章绪论 1 1 论文研究的背景 可靠性工程是人们研究的一个重要课题。所谓可靠性，是指“一个系统在一 定的环境下，在所给定的时间内能按预定的要求完成一定功能的概率”。可靠 性工程可分为硬件可靠性工程与软件可靠性工程两大类：硬件可靠性工程着重研 究模拟、数字电路系统的可靠性设计、故障诊断及容错技术，目前已有很多成熟 的理论和方法，如最小割集法、故障树分析法、蒙特卡洛法及马尔科夫过程法； 软件可靠性工程着重研究软件系统的可测性设计、可靠性预计模型及可靠性分配 等。 软件可靠性分配是软件可靠性工程的一门新的分支技术。它是指在保证可靠 性目标的前提下，对组成软件内部的成份做出分析，把软件分离为一个个基本元 素，并由此对软件各个元素进行可靠性目标的分配，以达到在软件开发成本一定 的情况下，使用户得到的软件可靠性尽可能地大。其中，软件元素被定义为诸如 操作、子系统、模块、对象或者是其它的能够用于可靠性分配的实体。 本论文致力于多模块软件系统的可靠性分配技术( s o f t w a r er e l i a b i l i t y a l l o c a t i o n ) 的研究与实现。目前软件可靠性分配技术仍处于萌芽状态，研究也 很初步，公开发表的各种论文和资料也比较少，这给论文的研究带来了一定的难 度。但是，软件可靠性分配技术作为可靠性工程中的一门新的分支技术、一个重 要的技术难点，激发出作者的研究热情和迎接挑战的勇气。另外，软件可靠性分 配技术在我国的研究还比较薄弱，作为一名普通的科技工作者，有责任和义务认 真钻研这门技术，如能为此领域做一点微薄的贡献，将是作者1 9 年寒窗读书的 心愿。 在纵向课题“上海市曙光计划”项目“应用软件的可靠性设计和实现策 略”项目中，作者参与了其中部分的研究、设计工作。这些研究工作为作者在软 件可靠性分配领域的研究打下了扎实的理论基础，积累了一定的实际经验。2 0 0 1 年5 月一9 月，在导师高建华教授的安排下，作者有幸参与了“江苏省邮政物流 信息系统”项目中可靠性分配技术的前期研究工作，为作者提供了良好的研究平 台和探索机会，促使作者对大型、复杂软件系统的可靠性分配技术的难点和新问 题、新方法进行了深入的思考和研究。 堡主堑窒竺堂垡笙壅 ! 薹主望堡簦莲塑竺生里蔓竺坌堡堡旦! ! ! 翌 1 2 软件可靠性分配研究的意义 软件可靠性是衡量软件质量的一个重要指标。一般情况下，为了达到一定的 可靠性目标，开发人员必须经过不懈的努力和反复的测试。但是由于软件内部是 非常复杂的，软件的各个组成部分对软件总体可靠性的影响各不相同。如果我们 对组成软件的各个部分一视同仁的话，所造成的直接结果就是为了达到可靠性目 标而耗费了大量的资源。 软件可靠性分配技术就是在保证可靠性目标的前提下，对组成软件内部的成 份做出分析，把软件分离为一个个基本元素并由此对软件各个元素进行可靠性目 标的分配，以达到在软件开发成本一定的情况下，使用户得到的软件可靠性尽可 能地大。我们在软件开发过程中实施计划管理的目标也就是把有效的费用、人力 资源和测试用例等资源分配给指定的系统可靠性目标。此时的系统可靠性度量为 各个元素故障率的函数。因此，选取对软件熬体可靠性贡献较大的元素，使之达 到较低的故障率，可以在较低的成本水平下提高整个的软件可靠性水平。 软件可靠性分配也是软件系统开发过程中一个重要的可靠性工作项目。面向 模块的可靠性分配则充分体现了软件开发过程的实质，是软件开发在成本一定的 情况下达到高可靠性目标的有效手段。软件可靠性分配的目的是将系统的可靠性 指标转换为每一个分系统的可靠性指标，用以指导分系统的开发，在一定资源约 束的条件下寻求一种最佳设计方案，使系统获得高可靠性。因此，软件可靠性分 配可以为系统的可行性研究提供依据，具有重要的实际意义。 1 3 论文工作 论文的工作主要分为四个阶段，具体如下： 第一阶段：对软件系统模块化结构进行系统分析，构建模块化软件的成本预 测模型和可靠性分配模型，对软件系统进行可靠性指标分配。 第二阶段：将遗传算法应用于多模块软件系统的可靠性分配中，解决多变量、 多约束条件的组合优化问题，给出实际的优化分配方案。 第三阶段：进行编码工作，完成软件可靠性分配数学模型的建立，编程实现 自适应多种群并行遗传算法( a m p g a ) ，并将遗传算法应用于多模块软件系统 的可靠性指标分配工作中。 第四阶段：测试与评价，对礼仪中心子系统、递送中心子系统及系统管理三 个子系统进行可靠性分配试验，并给出详细的报告。 2 堡主堕壅生兰垡笙苎 ! 苎主望堡篓堕堕墼堡里墨苎坌垦里旦! ! ! 翌 论文的安排大致与上面的工作情况一致，分为八章，各章节安排如下： “第一章绪论”。介绍了软件可靠性分配的研究背景和意义，简要介绍了作 者参与的两个项目，以及本论文的结构安排等。 “第二章软件可靠性分配的基本概念”。介绍了软件可靠性的定义、软件可 靠性的数学描述、软件可靠性分配的目的和要求等基本概念。并对软件可靠性与 硬件可靠性的差异进行了比较。 “第三章软件可靠性分配的模式框架研究”。本章对e z a h e d i 、p o o r e 及k u b a t 等人提出的软件可靠性分配模型进行了研究，针对传统可靠性分配模型的局限 性，总结出三种可靠性分配的模式框架：r c c m 模式框架、b c r m 模式框架及 b c u m 模式框架。并着重对软件开发的成本模型进行了研究。 “第四章基于遗传算法的软件可靠性分配技术”。本章首先对传统的软件可 靠性分配技术进行了研究，指出各种可靠性分配方法与技术的优缺点。然后，着 重研究基于遗传算法的软件可靠性分配技术，详细讨论了编码、初始种群生成、 选择、交叉和变异等主要操作。最后给出一个基于遗传算法的软件可靠性分配实 例，并将遗传算法与其它求解方法进行了比较。 “第五章自适应多种群并行遗传算法的设计与实现”。针对标准遗传算法收 敛速度慢、易陷入局部极小值等缺点，本文设计了自适应多种群并行遗传算法 ( a m p g a ) ，来解决复杂系统的可靠性分配问题。对并行遗传算法的模型、相 关数据结构设计、多种群进化思想进行了深入的研究并给出具体实现方案。 “第六章基于遗传算法的软件可靠性分配实现方案”。主要研究r c c m 模 式、b c r m 模式及b c u m 模式三种模式框架下的软件可靠性分配及具体实现方 案，着重分析模块化的软件系统中各模块对软件整体可靠性的贡献。同时从软件 开发成本函数、系统可靠性函数着手，分析各个模块的可靠性分配方案，并将遗 传算法应用于软件系统的可靠性分配中，进行可靠性指标优化分配。 “第七章试验结果与评价”。对礼仪中心子系统、递送中心子系统及系统管 理三个子系统进行可靠性分配试验，给出试验数据和相关图表。 “第八章总结与展望”。对本文工作进行了总结，并展望项目中若干核心技 术未来的进一步改进和发展方向。 堡主翌窒圭兰篁堡茎 ! 苎王望焦簦鲨堕燮堡里差堡坌堡壁旦! ! 型 第二章软件可靠性分配的基本概念 2 1 软件可靠性 2 1 1 软件可靠性的定义 软件可靠性是软件的一个质量要素。关于软件可靠性的确切含义，学术界有 过长期的争论。1 9 8 3 年美国i e e e 计算机学会对“软件可靠性”一词正式做出如 下的定义”3 ： ( 1 ) 在规定的条件下，在规定的时间内，软件不引起系统失效的概率，该概 率是系统输入和系统使用的函数，也是软件中存在的错误的函数；系统输入将确 定是否会遇到已存在的错误( 如果错误存在的话) ； ( 2 ) 在规定的时间周期内，在所述条件下程序执行所要求的功能的能力。 这个定义后来经美国标准化研究所批准作为美国的国家标准。1 9 8 9 年我国 国标g b t - 1 1 4 5 7 采用了这个定义。1 。这个定义表明，软件可靠性具有定性和定 量的两层禽义。在强调其定量含义时，工程上常用软件可靠度来代替软件可靠性。 2 1 2 软件可靠性的数学描述h 1 以t 表示给定的时间，设系统从时间0 开始运行，直到t 时发生故障，则： r ( t ) = p r ( t t ) 就表示软件系统在特定的环境下正常工作到时刻t 时的概率，其中，t 是从时刻 0 开始，软件系统运行到发生故障的时间。 按照概率论的观点，“软件系统正常工作”是一事件，则它的对立事件“软 件系统运行出错”定义了一个故障概率函数q ( t ) ，因而显然有： r ( t ) + q ( t ) = 1 一般地，我们用a ( t ) 来表示故障率，也有人称它为风险函数( h a z a r d f u n c t i o n ) ，a ( t ) 就是程序正确地运行到时刻t 时，单位时间内程序发生故障的 概率。于是有： 2 ( t ) a t = p r p 0 ， 因此，我们又可以写： r ( t + a t ) = e ， o + 垃) ) = 只 ( 丁 f ) 且在l i f t ，h f 】内程序不发生故障) = r ( f ) 1 2 ( t ) a t 】( 2 1 1 4 硕士研究生学位论文 基于遗传算法的软件可靠性分配应用研究 对等式( 2 1 ) 关于t 求微分，得到： d r = a ( t ) r ( t ) d t 从而可以导出下面的微分方程： j d ! 竺= 一五( f ) 出f 2 2 ) r 解之，得： r ( f ) = e x p 一【a ( t ) d t 】 ( 2 3 ) 上式描述了风险函数2 ( 0 与可靠度函数r n ) 的关系。 2 1 3 软件可靠性与硬件可靠性的差异 软件是人类脑力的产物，只能书写在文件上或存储在介质中。因此，软件不 受任何物理、化学规律的制约。硬件是由自然界中的基本元素构成的、可用感官 识别的实体。硬件的存在形式和运动规律，必须服从基本的物理和化学规律。硬 件和软件在可靠性特征上的差异，主要有以下七点”1 。 ( 1 ) 软件失效，是由程序运行过程中软件错误被触发所致。软件错误是设计 原因造成的，如果不进行更改，则将经久不变，时间的长短对软件错误不起作用。 硬件失效则是由于物理和化学的作用，使物质的性质和结构发生变化，致使硬件 发生耗损性失效。 ( 2 ) 软件的失效率，将随使用时间的增加而下降。这是因为软件排错可以穿 插在软件使用过程中进行。硬件在使用过程中，则呈现出可靠性衰减的趋势，因 而硬件的失效率将随时间增加而上升。 ( 3 ) 软件经过一段时间的使用之后，也会被废弃，但是软件和硬件被废弃的 原因不同。软件报废的主要原因是，软件版本的功能已不能满足用户新的需求， 硬件报废的主要原因则是，产品经过长时间的使用，已经进入损耗失效期，无法 继续正常工作。 ( 4 ) 软件在设计完成之后，可以大量她复制，复制件和原版本完全一样，而 同种型号和规格的硬件产品，尽管原材料完全相同，制造过程完全相同，但是每 个产品的微观结构必然存在差异。 ( 5 ) 维修和维护方面，软件对普通的用户是不可维护的，只能通过软件开发 方的再设计和排错来消除错误。硬件的一部分维修工作，可以由用户在使用现场 进行。 ( 6 ) 环境因素方面，影响软件失效的环境因素是指软件开发环境与使用环境 的差异，如操作系统、硬件配置等，外部的自然环境对软件的可靠性设计没有直 接的影响。硬件失效与使用现场的自然环境或人为环境密切相关，因此硬件可靠 堡主竺塞竺堂堡堡苎 堡王望堡墨鲨塑鏊生旦苎堡坌垦里里! ! 型 性设计工作中的环境设计十分重要。 ( 7 ) 标准件的采用方面，硬件设计虽然变化万千，但多数可用标准零部件、 标准电路搭配构成，这些标准件，其质量和可靠性有较好的保证，各种标准零部 件的失效模式也有公认的分类方法。在软件领域可以通用的标准模块非常缺乏， 多数程序需要设计人员独创构思。 对比硬件和软件的可靠性特征，得到的一个重要的结论是，设计质量对于软 件可靠性具有特殊的重要意义。硬件的可靠性，除了设计的影响之外，还受到物 质老化过程的影响，产品的老化是无法避免的。相比之下，软件的可靠性对设计 的依赖程序更大。这里所指的软件是广义的设计，它包括了从需求分析开始，直 至实现的全过程。 2 2 软件可靠性分配 2 2 1 基本概念 软件可靠性分配是软件可靠性工程的一门新的分支技术。它是指在保证可靠 性目标的前提下，对组成软件内部的成份做出分析，把软件分离为一个个基本元 素，并由此对软件各个元素进行可靠性目标的分配，以达到在软件开发成本一定 的情况下，使用户得到的软件可靠性尽可能地大。其中，软件元素被定义为诸如 操作、子系统、模块、对象或者是其它的能够用于可靠性分配的实体。 2 2 2 可靠性分配的目的和要求 可靠性分配是系统开发过程中的一个重要的可靠性工作项目，可靠性分配的 目的是将系统的可靠性指标，转换为每一个分系统的可靠性指标，用以指导分系 统的开发，可靠性分配的方法应该是科学的，分配的结果应该是合理的和可行的， 如果各分系统分配的可靠性指标经论证，确实难以实现或者需要投入巨额的资金 才能实现，这样的结果通常表明原有的系统可靠性指标脱离实际。因此，可靠性 分配可以为分系统的可行性研究提供依据“1 。 软件可靠性分配的指标以采用故障率和m t b f 为宜。用故障率和m t b f 作 为分配指标，可以与硬件和整个系统的可靠性要求相适应。当系统的故障率为常 数时，故障率和m t b f 互为倒数，因此用故障率作为分配的指标与用m t b f 作 为分配指标，在工程上是等效的。 软件系统可靠性分配必须满足的基本要求如下： 兄( 兄1 ，a 2 ，五n ) s 以 其中五。系统的故障率指标； 五，( i = 1 ，2 ，n ) 第i 个子系统分配的故障率指标； 兄( 旯，旯：，a 。) 系统的故障率函数 6 堡圭塑窒兰堂堡堡苎 ! 苎三j | 皇堕苎鲨塑竺堡旦墨丝坌望壁旦! ! 型 从上面可以看到有n 个待求解的参数，这种情况表明满足上式的解有无限多 组。如何从各种可能的解中选出一组合理的、可行的解呢? 这正是软件可靠性分 配所要解决的问题。 2 3 软件可靠性分配的基本关系式 2 3 1 标记和符号 p 。( 0 p 1 ) 整体程序中执行第i 项操作的概率； “。( o p 。 0 ) 是软件系统开发的最高预算成本，该决策问题给出了一个目 标函数，多个约束条件集。通过求得相应模块的故障率 的分配值，以使得在 总预算成本q 给定的情况下，达到最大化软件系统的可靠性r ( ， ：， 。，t ) 的目标。 3 3 预算约束实用性最大化模式( b c t n v ；模式) 从用户的角度，人们最为关心的是软件的实用性，一般而言，软件的开发费 用不能超过预算q ，同时要保证用户得到的软件实用性尽可能地大，设软件系统 有n 个功能模块，记为( m 。，m 2 i “，i i l | l ，软件的实用性定义如下： 9 堡主堡壅兰兰垡堡苎 ! 苎三望堡兰堕堕苎堡旦整丝坌篓鏖! ! ! ! 型 u 化。) ：u ，r ，+ u ：r 2 + + u 。r 。，其中。，为功能模块i 的重要度，也即用户的 关心程度，其数据可由需求分析得出嘲。r 。为功能模块i 的可靠性，不失一般性， 规定o 万 q 妒 粤：i 1 4 0 1 2 0 1 口0 8 口 6 0 4 0 2 0 0 1 4 0 1 2 0 1 0 0 苗即 召6 d 4 d 2 0 口 图3 - 4 不同q ，b ，6 时负幂成本函数图形 图3 4 画出了几条不同a ，b ，6 时负幂成本函数图形。从图形中我们可以看 到，对应于不同的a 、6 ，成本函数随b 不同的变化趋势。同时，我们可以看到 软件开发成本随模块故障率 的增加而逐步减小的曲线关系。 3 5 小结 本章对软件可靠性分配的模式框架进行了研究。着重研究r c c m 模式中的 成本最小化问题、b c r m 模式中可靠性最大化问题，并从实用性的角度，扩展 出b c u m 模式，给出了各个模式框架的数学描述。研究并讨论了软件开发的线 性成本模型、对数指数成本模型及负幂形式成本模型，同时分析了各种成本模型 下软件开发成本随模块故障率变化的曲线关系。 硕士研究生学位论文基于遗传算法的软件可靠性分配应用研究 第四章基于遗传算法的软件可靠性分配实现技术 软件可靠性分配是软件系统开发过程中的一个重要的可靠性工作项目。其目 的是将软件系统的可靠性指标分配给软件的各个子系统。进行软件可靠性分配， 必须具备下列四个条件：必须制定出软件需求说明和软件的可靠性开发大 纲；必须要有定量的可靠性指标和定义了软件的运行剖面；必须对系统失效 作出明确的定义；程序赫须能够进行结构分解。 本章将着重分析传统的软件可靠性分配技术的优缺点，同时详细论证了基于 遗传算法的软件可靠性分配技术，并给出具体的实现技术。 4 1 传统的软件可靠性分配技术 软件可靠性分配是软件可靠性工程中必不可少而且是十分重要的一个环节。 目前，人们对软件系统的可靠性分配方法已经有了一定的研究，下面简要列出已 有的各种方法与技术的优缺点： 4 1 1 快速分配法n 妇 假设软件系统由n 个子系统组成，并且这n 个子系统，从可靠性的角度观察， 呈现出串联配置的逻辑关系。用r ( t ) 表示软件系统在规定的运行时间内的可靠 度，则r i ( t ) ( i - 1 ，2 ，“n ) 表示系统i 的可靠度，用 ( i - 1 ，2 ，n ) 表示子系统i 的故障率，则： r ( t ) = r l 。r 2 r n s = 九l + x2 + + 。 设子系统i 分配到的可靠度用r ；表示，子系统i 分配到的故障率用 i 表示， 且都是按照串联配置为基础得到。在某些特殊的情况下，如果串联配置关系不能 成立，可以按照系统或子系统实际的逻辑关系，构造相应数学模型，参照本节的 方法进行可靠性分配。 ( 1 ) 相似程序法 相似程序法是一种简单和有效的软件可靠性分配方法。如果项目开发组在开 发新的项目时，能够找到一个旧的软件系统其结构与新开发的软件系统相似， 而且这个旧系统在过去的使用过程中，已经积累了相当的可靠性数据，这时应该 充分的利用这些宝贵的信息，进行新系统的可靠性分配。 假设新旧系统由n 个子系统组成，新系统的故障率指标为 s - 。，旧系统的 故障率为 m 。 i 求新旧系统故障率比例系数 堡主竺塑生堂垡笙奎堡王望焦苎鲨竺竺堡旦蔓竺坌墼生里竺! 翌 ： so l d i i 求子系统分配的故障率 九l 旧fb 入，一。山 i = i ，2 ，n ( 2 ) 相似模块法 如果对于新开发的系统，没有类似的旧系统可以借鉴，但是新系统中的部分 模块，与其它系统的模块相似，这时可借鉴这些相似模块的可靠性数据进行可靠 性分配。假定新系统由n 十k 个模块构成，其中有k 个模块有相似模块的数据可 供借鉴。相似模块的可靠性数据为 一，m ，入。+ 2 - 0 。，oo l 九m - 0 。令 入o l d = n + l _ 0 凹+ 九n + 2 o l n + + 入n + k 0 山 新系统的可靠性指标为 。将新系统分解为两部分，一部分由n 个没有参考数 据的模块构成，这一部分应该分配到的可靠性指标为 。+ ，另部分由k 个有参 考数据的模块构成，这一部分应该分配到的可靠性指标为 。 快速分配法是借鉴功能类似的旧系统成旧模块的可靠性数据进行可靠性分 配，该方法方便实用，但需要有可借鉴的系统或模块的可靠性指标数据，对于新 开发的软件系统，如果没有相应的参考数据，则该方法无法应用。 4 1 2 等分配法n 幻 该方法的适应范围虽仅适应于设计初期，但理论简单，故假设各单元的条件 相同，下面分别介绍串、并联系统的等分配法。 ( 1 ) 串联系统 对于由n 个单元组成的串联系统，按等分原则，每个单元分给相等的可靠度， 分配方法如下：， r ，= ( r 。) ”扛1 ，2 ，肝( 4 1 ) 其中，风为系统要求的可靠度：r i 为第i 个单元所分配的可靠度。 ( 2 ) 并联系统 将( 4 1 ) 式中的r 换成f ，即得并联系统的等分配方法： ll ，= ( 只) “= ( 1 一r 。) ”f = l ，2 ，6( 4 2 ) 式中，f 。为系统要求的非可靠度，丘为为第i 个单元分配的非可靠度，b 为子系 统的个数。 等分配法可用于顺序或并行执行的软件系统，优点是它非常简单，但是它没 有考虑各模块之间的不同属性，如重要性，复杂性等的不同，只是单纯的平均分 配，因此该种方法缺乏效率，对于那些需要精确分配各模块的可靠性指标的系统 则无法采用。 1 4 堡主堕窒兰堂竺垒苎 ! 薹王望堡苎鲨竺竺堡旦墨丝坌垦垦里! ! ! 翌 4 1 3 比例分配法n 幻 本方法用于新设计系统与原有系统基本相同。已知原有系统规定了新的可靠 度要求；或根据掌握的可靠性资料，已能预测得新设计系统各单元的r ，但尚未 满足新设计系统可靠度的要求。这时，可对串联系统取新系统分配给各单元的可 靠度预测值豆成正比；对并联系统，取新系统分配给各单元的非可靠度f 。与相 应单元的非可靠度预测值声成正比。 串联系统比例分配法公式为： 月= 并联系统比例分配法公式为 e = r 兀五， 只 兀只 ( 4 - 3 ) 比例分配法的优点是它非常简单，但是它需要借鉴功能类似的旧系统成旧模 块的可靠性数据进行可靠性分配，对于新开发的软件系统，如果没有相应的参考 数据，则该方法无法应用。 4 1 4 基于重要度、运行时间和复杂度的分配法n ” ( 1 ) 子系统的重要度 子系统的重要度是指子系统发生失效后，对系统功能影响的程度。子系统k 的重要度可用重要度系数u k 描述，u k 的数值可通过工程分析确定。如果子系统 k 发生失效后，将使系统失效或造成严重的后果，u k 可取值为1 ，如果子系统k 发生失效后，只引起比较轻微的损失，u k 的取值可小于1 。 考虑子系统的重要度后，串联配置系统的可靠性分配方程可表示为 = 玑无 ( 2 ) 子系统的运行时间 用调用系数i k 近似的表示各个子系统的相对运行时间。即定义 仁等 堡主婴窒生兰堡堡奎 ! 兰主望堡兰鲨塑鏊壁旦差堡坌堡查旦! ! 型 w = 以上两式中，w k 是第k 个子系统被调用的次数，w 是各个子系统被调用次数的 总和。这种定义方法蕴含了各个子系统运行一次的时间是相同的假设，这是一个 近似的假设。有了这个假设，在设计的初期根据经验估计出各个子系统的调用次 数，就可确定调用系数。 在考虑子系统的运行时间之后，串联配置系统的可靠性分配方程应表示为 五，丁= u 以i t ( 3 ) 子系统的复杂度系数 用c k 表示子系统k 的复杂性系数，c k 应满足 c 。= 1 子系统的复杂性系数与子系统的复杂程度有关。用c x k 表示第k 个子 系统的复杂性度量值，c x k 可用软件工程中的复杂性度量法求出。则 r y c x 。袁舞 ( 4 ) 子系统分配的失效率 子系统k 应分配的失效率可用下式求出： 不= 辜 丑。 k = 1 , 2 ， u f 4 1 5a h p ( a n a l y t i c h i e r a r c h y p r o c e s s ) 法1 3 1 f z a h e d i 和n a s h r a f i ”3 确定的软件可靠性分配原则是：在最大限度地满足用 户对软件系统的可用性要求的基础上，进而确定每个单个软件部件应达到的软件 可靠性指标。该模型实际上是一个优化问题，它所确定的统一的软件可靠性划分 方法是一种层次划分方法。他们指出，软件产品首先按功能划分功能层( f 级) ， 再把功能按程序进一步纫分为程序层( p 级) ，最后把程序划分为模块层( m 级) 。 再往下可以进一步划分为子模块层，但规定：每个模块下面的子模块属于且仅属 于该模块，不得由另外的任一模块调用。而且，该模型只将可靠性指标分配到模 块级为止。 设共有m 个互相独立的模块，记为m 1 ，m 2 ，m 。首先要确定在p 级 的每个程序的相对重要性。这里有两种不同的观点：用户观点。用户仅关心f 级，不可能( 也不应) 看到p 级和m 级。因此在确定相对重要性时，不可能仅靠 对用户的直接询问来解决。程序员观点。他们最关心p 级和m 级的实现，对 f 级的了解，远不如用户。这时，应用a h p 法可以很好地解决这一问题。 6 堡主堕窒生堂笪垒奎 ! 苎三垄堡苎垄塑竺壁里查丝坌墼堡旦! ! 篓翌 a h p 法分4 步： 1 ) 规定划分层次的结构( 这一步已在上面的讨论中解决) 。 2 ) 在每一层上通过逐对比较收集数据( 带主观性) 。 3 1 通过计算特征值，在每一层上计算相对权值。 4 1 归并。 总体来看，a h p 法是一种基于功能概图的分配方法，它考虑了软件的开发 费用，既能保证软件的可靠性达到一定的要求，又可节约开发资源，但是其算法 比较复杂，而且功能概图的确定也具有一定的主观性，且功能概图的最后确定不 是在系统设计阶段就能完成的，它需多次反复，而软件可靠性指标的分配要在设 计阶段完成。 4 2 基于遗传算法的软件可靠性分配技术 软件系统的可靠性分配问题实质上是一种数学规划问题：由相应的目标函数 和约束条件两部分组成。通常可描述成下列形式： 目标函数： 约束条件 m a x f ( x ) f g j ( x ) 0 ， ( x ) = o ， l _ x ? ， ，= 1 ，q ， ，= q + 1 ，m ， i = 1 ，n 其中，目标函数为f ( x ) ，该优化问题有一组约束条件集：1 至q 个不等式约 束，q + l 至m 个等式约束，以及1 至n 个边界约束。 一般说来，该问题通常带有大量的局部极值点，往往是不可微的、不连续的、 多维的、高度非线性的组合优化问题。因此，精确地求解全局最优解一般是非常 困难的。传统的求解算法( 如拉格朗日乘子法、单纯形法、爬山法、模拟退火法 等) 并不能获得满意的全局最优解。本文将遗传算法应用于软件系统的可靠性分 配中，对可靠性指标进行全局优化分配。与传统的启发式优化求解算法相比，遗 传算法的主要特征在于群体搜索策略和简单的遗传算子。群体搜索使遗传算法得 以突破领域搜索的限制，可以实现整个解空间上分布式信息搜索；遗传算子则利 用适应值度量作为运算指标进行随机操作，降低了一般启发式算法在搜索过程中 对人机交互的依赖。遗传算法作为种新型的模拟生物进化过程的随机化搜索方 法，在解决此类问题时已显示了良好的效果。 遗传算法1 ( g n e t i ca l g o r i t h m ) 通过维持一群个体，模拟生物进化的适者 生存原则，反复对这群个体进行选择、交叉和变异，直到获得全局最优解或接近 1 7 堡主堕窒竺兰焦堡苎 ! 萎王望堡苎鎏塑墼生卫生丝坌! i 壁旦! ! 型 全局最优解为止。下面将遗传算法应用到上述多模块软件系统的可靠性分配问题 中，并就算法设计中几个主要问题的处理方法进行讨论a 4 2 1 编码 遗传算法中个体的染色体表示采用实数编码，每个染色体由可行解向量九的 元素列( l ， ：， 。) 表示，则相应染色体是v = ( 1 ， ：， 。) ，同时根 据给定的约束条件可以确定 。的上下限入。入，。( i = 1 ，2 ，n ) ，即确定其搜索 空间。在求出相应的解( 九1 ，x 矿， 。) 后，即可通过式( 2 6 ) 求得单独模块的 可靠性分配值。通过反复运用式( 2 6 ) 、式( 2 7 ) ，就可以求出所有模块应该分配 的可靠性指标。 4 2 2 初始种群的生成 定义整数p o pn 作为染色体的个数，根据x 。九，随机产生p o pn 个初 始可行染色体v 。，v ：，v 。，并用式( 2 9 ) 检验该种群是否达到系统的可靠性目 标，如不符合，则重新生成新的个体，直至该种群符全约定条件为止，即总的软 件开发成本必须在特定的范围之内，且系统的可靠性目标需达到给定目标。 4 2 3 适应度函数 本文采用基于模拟退火算法的适应度拉伸方法( 用f i t ( v ) 表示) ，对种群中的 每个染色体v 设定一个概率，以使该染色体被选择的可能性与该种群中其他染 色体的适应性成比例。通过轮盘赌的方式，适应性好的染色体被选择产生后代的 机会大。设目前该代中的染色体为v 1 ， v l ，v 2 ，v p o p _ n 由好到坏进行重排。 伸方法“”： v 2 ，v p o pn ，根据适应值对染色体 同时，对适应度进行如下的模拟退火拉 f a ( u ) ：善兰 y e 一7 ( ”) 7 7 j _ 一 t = r o ( o 9 9 ) g 一1 这样，在温度高时( 遗传算法的前期) ，适应度相近的个体产生的后代概率 相近；而当温度不断下降后，拉伸作用加强，使适应度相近的个体适应度差异放 大，从而使得优秀的个体优势更加明显。 4 2 4 选择操作 采用轮盘赌选择法( r o u l e t t ew h e e ls e l e c t i o n ) ，选择过程是以旋转赌轮p o p _ n 次为基础，每次旋转都为新种群选择一个染色体，选择过程如下： 1 8 堕主竺塞生堂焦堡苎 ! 苎三望堡苎鲨盟墼竺里墨垡坌墼窒星! ! ! 翌 对每个染色体v 。计算累积概率q i l q o ：0q = f i t ( v j ) i = 1 ，2 ，p o p n ，= 1 从区间【0 ，p o p _ n 中产生一个随机数r ； 若q i - i r q 。，则选择第i 染色体v i ( 1 i p o p - n ) ： 重复和共p o p _ n 次，这样可以得到p o p - n 个复制的染色体。 4 2 5 交叉操作 本文采用多点交叉法，先将实值编码转换为对应的二进制编码。设置m 个 多点交叉位k i ，并随机生成这m 个交叉点，在交叉点之间间续地相互交换，产 生两个新的后代，考虑如下两个l l 位变量的个体： 多点交叉的思想源于控制个体特定行为的染色体表示信息的部分无须包含于邻 近的子串中，同时，多点交叉的破坏性可以促进解空间的搜索，而不是促进过早 地收敛，因此使得搜索更加健壮。下图为多点交叉示意图： 图4 1 多点交叉示意图 4 2 6 变异操作 定义参数p 。为变异概率，类似交叉操作中选择父代过程，从i = l 到p o pn 重复以下过程：从【o ，1 中产生随机数r ，如r p 。则选择v i 作为父代，用v l ，v 2 ，v 3 表示上面选择的父代，对之施加一变异操作矩阵，随机选择两列互换产生新的子 个体，并使之满足约束条件，在不能满足可靠性约束时，可以再选择其它两列互 换以产生新的个体，直至满足给定的约束条件为止。 1 9 堡主婴茎竺兰竺堡苎 ! 茎王望堡苎鲨塑竺堡里苎丝坌堡堡里! ! ! 鲨 4 3 数值仿真与分析 为了将遗传算法与传统的可靠性分配方法以及其它的组合优化方法进行比 较，选取一个软件系统的可靠性分配实例。 实例一： 一个2 模块的软件系统，含2 项子操作，开发成本为线性成本函数，输入参 数如下： ，z = 2 p = 0 9 9 m = 2f = 1 p 2 一 2 p p 螂0 - 3 ：jlj 1 1 “2 ff 0 60 4 2 1 2 2 jl o 01 o j a 。= - i n ( p ，f = 。， 象 = ；：竺：2 ：兰 = 0 4 2 阱瞄阱圈 c ( a ) = 一五+ 届= 一9 5 a + 1 3 5 0 c ( 如) = 一友4 - 屈= 一5 5 五4 - 1 2 5 0 l，。l 堡主竺壅生兰堡丝壅 ! 苎主望竺兰鎏塑竺竺里墨丝坌里壁旦! ! 型 图4 - 2 两模块的成本函数图 根据( 2 8 ) 式，得到系统总的开发成本： 彤( a ，如，以) = c ( 乃) = c ( ) + c ( 如) = l = ( 一9 5 a + 1 3 5 0 ) + ( 一5 5 五+ 1 2 5 0 ) = - 9 5 丑一5 5 如+ 2 6 0 0 根据r c c m 模式可得到如下的可靠性分配数学模型： 目标函数： m i n 弼( a ，如，以) = c ( 乃) ) = l 约束条件： 【e - o 舵 m 5 8 如1 o 9 9 l 五0 l 彳2 0 对于上述的可靠性分