（通信与信息系统专业论文）基于遗传算法与ahp的软件可靠性分配方法.pdf

西北工业大学硕七学位论文 摘要 摘要 软件可靠性分配表明了“此软件应该有多可靠”。软件可靠性分配在计划、 设计阶段为不同产品部件在时间、工作量的分配上提供指导，为开发管理提供有 效的控制工具，并把可靠性设计融入到系统之中，因此，软件可靠性分配对系统 后来的可靠性的影响是十分关键的。 鉴于此，本文概括并分析了软件可靠性分配模型，深入讨论了基于a h p 方 法的软件可靠性分配模型，详述了递阶层次结构的建立、全局相对权重的计算方 式与符合“严格结构”和“线性费用模型”与“线性可用性模型”的a h p 软件 可靠性分配模型的建立。通过对此模型的分析，本文从软件结构方面、费用模型 方面和可用性模型三个方面对基于a h p 的软件可靠性分配模型进行优化，提出 三个优化方案，分别建立优化模型。对于基于a h p 的软件可靠性分配模型的求 解方面，本文分析比较了几种现代优化技术，并针对此a h p 模型的特点，提出 了基于遗传算法的求解软件性可靠性分配a h p 模型方法，分析了适应该a h p 模型的遗传算法的编码方法、遗传算子与约束条件的处理方式；随后应用此理论， 对实习期间所做的3 g 计费系统进行可靠性分配实验：建立可靠性分配模型并应 用遗传算法求解。实验结果表明采用遗传算法来求解，求得的可靠性分配方案作 为指标进行软件可靠性分配可使得保证费用最低的前提下软件有较好的可用性。 本文最后总结全文并展望了进一步的研究内容。 关键字：软件可靠性分配，层次分析法，遗传算法，非线性规划，3 g 西北1 = 业大学硕士学位论文 a b s t r a c t 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 ne x p l a i n sh o wr e l i a b i l i t yt h es o f t w a r ei s s o f t r w a r er e l i a b i l i t ya l l o c a t i o ns u p p o r t sg u i d e st oa l l o c a t i o no ft i m ea n dt a s k so f d i f f e r e n tp a r t s i ta l s os u p p o r t se f f e t i a lc o n t r o it o o l ，a n dm a k er e l i a b i l i t yd e s i g ni n t o s v s t e m s a sar e s n l t ，t h i sp h a s em a k e sa ni m p o f l a n t1 o l ei nc o n t i n u er e l i a b i l i t y a c c o r d i n gt ot h i s ，t h i sp a p e rg e n e r a l i z e sa n da n a l y s e ss o f t w a r er e l i a b i l i t ym o d e l , d i s c u s s e sd e e p l y 御s o f t w a r er e l i a b i l i t ym o d e l ，d e s c r i b e sh i e r a r c h ys t r u c t u r e ， s o l u t i o no ft o t a lr e l a t i o nw e i g h ta n dp r o p o s e da 册s o f t w a r er e l i a b i l i t ym o d e l a c c o r d i n gt o “s c v e ms t r u c t u r e a n d “l i n e rc o s tm o d e l ”a n d “l i n e ru t i l i t ym o d e l b y a n a t y i n gt h i sm o d e l ，t h i sp a p e ri m p r o v e sm o d e l sf r o ms o f t w a r es t r u c t u r e ，c o s tm o d e l a n dm i l i t ym o d e la s p e c t s r e f e r i n gt os o l u t i o nw a y so fs 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 m o d e l s t h i sp a p e ra n a l y s e sa n dc o m p a r e ss e v e r a lm o d e r ni m p r o v i n gt e c l m i e sa n d a c c o r d i n gt ot r a i t so ft h i sa h p m o d e l t h i sp a p e rp r o p o s e sg as o i n t i o n i ta n a l y s e s c o d i n gw a y , g e n e t i co p e r a t o r sa n dm a n a g e m e n to fr e s t r i c t i o n s t h e na p p l l n gt h e t h e o r yt od oe x p e r i m e n t st o3 gb i l l i n gs y s t e m ：s e t su ps 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 m o d e l d os o l u t i o nb vg 色1 1 1 er e s u l lo fe x p e r i m e n ti n d i c a t e st h a ta p p l i n gg a t 0 肿 s o f t w a r er e l i a b i l i t va l l o c t i o nm o d e li sb e t l e rt h a ng a mt o o l s a sar e s n i t , t h a ta p p l y i n g g at oa 肿s o f t w a r er e f i a b i l l t ym o d e lc a ng e tb e s tr e s u i t al a s t , w es u m m a r i z e sa l l a n d p r o s p e c t sa d v a n c e d r e s e a r c h e s k e yw o r d s ：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 , a h p , g a ，n o n l i n e ro p t i m a l ，3 g 西北工业大学 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，印：研究生在校攻读学位期问论文工作 的知识产权单位属于西j l 3 2 业大学。学校有权保留并向国家有关部门或机构送交论文的复 印件和电子版。本人允许论文被查阅和借阅。学校可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北工业 大学。 保密论文待解密后适用本声明。 学位论文作者签名：垂疆 d 7 嘭叫日 指导教师签名：遨 。7 年弓月彤日 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德本人郑重声明：所呈交的学位论文，是本 人在导师的指导下进行研究j 2 作所取得的成果。尽我所知，除文中已经注明引用的内容 和致谢的地方外，本论文不包含任何其他个人或集体已经公开发表或撰写过的研究成 果，不包含本人或其他己申请学位或其他用途使用过的成果。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式表明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名：五! i 幺! 敌 0 7 年乡蒯日 西北工业大学硕士学位论文第一章绪论 1 1 引言 第一章绪论 1 9 6 8 年在西德召开的国际软件工程会议上提出的“软件危机”的主要问题 之一，就是软件可靠性低，经常出故障。从那时起，人们开始认识到软件可靠性 的重要性。据统计，计算机系统中，由于软件错误引起的故障占所有故障的6 5 。 美国贝尔( b e l l ) 实验室曾对一个a t & t 运行支持系统作了统计，发现8 0 的故障 与软件有关。究其原因是软件太复杂了，一个小小的程序，其可能的路径可以是 天文数字，以至于在软件开发过程中难以对其作穷尽的测试，或者说难于完全排 除软件缺陷。应用严格的技术、工程和方法学来解决软件危机的学科称为软件工 程。软件工程旨在使软件开发生产过程规范化、工程化，以提高软件质量，加速 软件开发进度，降低软件开发费用，实现软件生产的工程化和社会化。 软件可靠性分配是软件工程中一个新的分支，在软件设计阶段进行，在保证 软件可靠性的前提下对软件可靠性分配指标进行分配。影响软件可靠性分配的因 素有软件的复杂性，模块的重要性，软件开发成本等等，这些因素不仅可以影响 软件可靠性分配的结果，还对可靠性分配模型的参数确定具有决定性的作用。结 合上述因素，对可靠性分配模型进行研究是保证软件可靠工程的重要内容。 软件可靠性分配也是软件系统开发过程中一个重要的可靠性工作项目。面向 模块的可靠性分配则充分体现了软件开发过程的实质，是软件开发在成本一定的 情况下达到高可靠性目标的有效手段。软件可靠性分配的目的是将系统的可靠性 指标转换为每一个分系统的可靠性指标，用以指导分系统的开发，在一定资源约 束的条件下寻求一种最佳设计方案，使系统获得高可靠性。因此，软件可靠性分 配可以为系统的可行性研究提供依据，具有重要的实际意义。 因此，本文致力于对软件可靠性分配模型及其技术进行研究，并侧重于对可 靠性分配模型的求解方法的讨论。 1 2 国内、外研究概况 软件可靠性分配与软件可靠性工程中的另外两项工作一可靠性的预计、评价 组成了整个软件可靠性的主要工作。以前软件可靠性研究的主要目的是评价和度 量软件的可靠性和对软件的可靠性进行预测。可靠性的预计、评价经过多年的发 展，己经形成了一套相对较为成熟的理论，而软件可靠性分配研究是在近些年才 发展起来的研究工作，所以软件可靠性分配相对于可靠性的评价和度量技术还显 1 西北工业大学硕士学位论文第一章绪论 得不够成熟，还有待进一步完善。 从国内外的发展状况来看，国内较国外相对落后。m u s a f r a n 等人在影响可 靠性分配的因素如操作剖面、收集历史数据的特性等方面有了一定的研究。 s h o o m a n 1 3 将软件复杂性考虑到软件可靠性分配问题中，提出“将软件划分为 模块进行可靠性分配研究”。s h o o m a n 和r a m a m o o r t h y 2 3 提出基于软件结构 的可靠性分配研究。l i t t l e w o o d 基于模块化程序结构建立了可靠性分配模型； c h e u n g 的面向对象模型和a s h r a f i 的软件可靠性预计的分解模型，都是基于结 构进行可靠性分配的进_ 步研究。f a t e m e hz a h e d i 和n o u s h i na s h r a f i 4 基于 4 - t p 方法，考虑软件结构、费用，以软件可用性为目标，完成软件可靠性指标的 分配。 在国内，徐仁佐、杨晓青等专家也开展了相应的可靠性分配研究工作 5 ， 如面向多用户的模块化软件系统的可靠性分配、软件可靠性指标分配的故障树分 析法等在理论上都具有一定的创新性。但是由于国内软件业发展起步较晚，这方 面工作还没有得到充分的重视，可靠性分配方法和模型方面的研究较国外相对要 少。一些方法因为同实际工程结合获得的经验较少，还缺乏在实际工程中的检验。 1 3 论文工作和章节安排 本文主要做了以下几个方面的工作： 研究软件可靠性分配模型、a h p ( 层次分析) 法以及应用a h p 法的软件可 靠性分配模型； 从软件系统模块结构上、软件可用性与可靠性的函数关系上和软件开发费 用与模块可靠性的函数关系上- - 4 方面提出a h p 软件可靠性分配优化模型，并 建立优化模型。 研究约束条件下非线性规划的模型与求解方法； 研究遗传算法及应用遗传算法对约束条件下非线性问题的优化方案； 提出应用遗传算法优化软件可靠性分配a h p 模型问题； 编码实现算法，对3 g 计费系统进行软件可靠性分配实验。 首先，本文介绍软件可靠性与软件可靠性分配以及它们的异同，指出软件可 靠性分配的必要性，同时对软件可靠性分配模型进行研究与分析；其次讨论了 a h p 方法与rz a h e d i 和n a s h r a f i 的基于a h p 的软件可靠性分配方法。 通过讨论，对于上述软件可靠性分配的a h p 模型，本文从软件系统模块结 构上、软件可用性与可靠性的函数关系上和软件开发费用与模块可靠性的函数关 系上三个方面提的几个改进方案，建立优化的软件可靠性分配模型。同时，在针 2 西北工业大学硕士学位论文第一章绪论 对上述软件可靠性分配的a h p 模型的研究中，得出此模型属于“有约束条件的 非线性规划问题”。基于此优化问题，本文深入研究了模拟退火法、神经网络 法与遗传算法等几种现代优化技术。通过对遗传算法与其他算法的分析比较，提 出将遗传算法应用在软件可靠性分配的a h p 模型中。并且分析了适应该a h p 模型的遗传算法的编码方法、遗传算子与约束条件的处理方式。 随后，将本文提出的基于遗传算法的软件可靠性分配a h p 方法应用在作者 实习期间完成的3 g 计费系统中，对3 g 计费系统进行分析、建立递阶层次模型， 并应用上述遗传算法对其进行软件可靠性分配实验，进一步验证了该方法的适应 性与可行性。 最后，就基于遗传算法的可靠性分配a h p 模型的求解问题进行了总结和展 望。主要指出通过混合其他启发式算法的遗传算法的局部搜索能力会更强，结果 会更优。 全文的内容安排如下： 第一章：绪论部分，主要阐述本文研究的背景和意义、国内外研究概况、论 文中的主要工作以及全文结构安排。 第二章：讨论了软件可靠性分配的概念、模型与分配技术与层次分析方法， 详细讨论了f z a h e x t i 和n 舡h m f i 的基于层次分析法的软件可靠性分配模型。 第三章：探讨了此软件可靠性分配模型的几个改进方案，从软件的模块结构、 软件可用性模型与费用模型三个方面进行了改进可靠性分配模型的探讨。 第四章：此章是本文的核心。研究了遗传算法的原理与实现，讨论了非线性 规划问题的模型和包括遗传算法的现代优化算法，通过分析和比较，得出应用遗 传算法解决非线性规划问题具有较强的全局搜索能力。根据对软件可靠性分配的 a h p 模型的分析，应用其适应的编码方法、交叉算子和变异算子，并应用d c p m 解决约束条件，将遗传算法应用到软件可靠性分配的a i 口模型中。最后，将编 码实现的算法应用到3 g 计费系统中，求得全局最优解。 第五章：总结了本文内容与创新点，并对该领域进行了展望。 3 两北丁业大学硕士学位论文第二章软件可靠性分配研究 第二章软件可靠性分配研究 2 1 软件可靠性分配概述 2 1 1 软件可靠性分配概念 1 软件可靠性 可靠性( r e l i a b i l i t y ) 6 是产品在规定的条件下和规定的时间内完成规定 功能的能力，它的概率度量称为可靠度。 软件可靠性( s o f t w a r er e l i a b i l i t y ) 7 是软件系统的固有特性之一，它 表明了一个软件系统按照用户的要求和设计的目标，执行其功能的正确程度。软 件可靠性与软件缺陷有关，也与系统输入和系统使用有关。理论上说，可靠的软 件系统应该是正确、完整、一致和健壮的。但是实际上任何软件都不可能达到百 分之百的正确，而且也无法精确度量。一般情况下，只能通过对软件系统进行测 试来度量其可靠性 8 ： 这样，给出如下定义e 9 】：“软件可靠性是软件系统在规定的时间内及规定的 环境条件下，完成规定功能的能力”。 目前所有的软件可靠性模型都用于测试阶段，通过对软件运行时故障次数与 平均故障发生时间的记录与分析，判定其从属的故障模型。因此软件可靠性模型 一般是指软件可靠性增长模型，或者说是故障增长模型。 2 软件可靠性分配 软件可靠性分配是软件可靠性工程的一门新的分支技术。它是指在保证可靠 性目标的前提下，对组成软件内部的成份做出分析，把软件分离为一个个基本元 素，并由此对软件各个元素进行可靠性目标的分配，以达到在软件开发成本一定 的情况下，使用户得到的软件可靠性尽可能地大。其中，软件元素被定义为诸如 操作、子系统、模块、对象或者是其它的能够用于可靠性分配的实体。 可靠性分配是系统开发过程中的一个重要的可靠性工作项目，可靠性分配的 目的是将系统的可靠性指标，转换为每一个分系统的可靠性指标，用以指导分系 统的开发，可靠性分配的方法应该是科学的，分配的结果应该是合理的和可行的， 如果各分系统分配的可靠性指标经论证，确实难以实现或者需要投入巨额的资金 才能实现，这样的结果通常表明原有的系统可靠性指标脱离实际。因此，可靠性 分配可以为分系统的可行性研究提供依据。 软件可靠性分配要求在软件生存周期的定义阶段进行，即在软件的可行性论 证、需求分析、初步设计、详细设计阶段进行。随着软件设计的深入，我们可以 4 西北工业大学硕士学位论文第二章软件可靠性分配研究 得到更多的相关信息，从而可以使可靠性分配结果也越来越趋向于合理。比如在 可行性论证方面，我们可以用类比的方法进行可靠性初步分配；而到详细设计阶 段，由于可以获得软件复杂性、操作剖面等信息，我们可以使用更好的软件可靠 性分配方法，使结果更加精确。事实上，可靠性分配还可以在开发阶段进行调整。 3 软件可靠性分配的意义 软件可靠性的分析与模型的建立只是表明了“此软件有多可靠”，模型的使 用用于在开发和编码的初始阶段后数据的产生，因此，它们几乎对软件工程的设 计不产生任何影响。 可靠性分配表明了“此软件应该有多可靠”。软件可靠性分配在计划、设计 阶段为不同产品部件在时间、工作量的分配上提供指导，为开发管理提供有效的 控制工具，并把可靠性设计融入到系统之中，因此，这个阶段对系统后来的可靠 性的影响是十分关键的。 2 1 2 软件可靠性分配模型【1 0 】 1 简单软件可靠性分配模型 按照软件系统的结构，可以分为串联分配模型、并联分配模型和混联的复杂 系统分配模型。简单软件可靠性分配模型用于系统的初始设计阶段的分析。 ( 1 ) 串联系统模型 图2 暑1 串联系统 串联系统模型是指系统的各个模块各自执行各自的功能，互不干扰，且系统 的任一功能只由唯一模块实现。有以下几个特点： 任意一个模块发生故障，系统就发生故障 n 个模块都正常，系统才会正常。 串联的模块数越多，系统的可靠性越低 若每个模块的寿命均服从指数分布，则系统寿命也服从指数分布。 ( 2 ) 并联系统模型 5 西北工业大学硕七学傻论文第二章软件可靠性分配研究 图2 - 2 并联系统 与串联系统模型不同的是，并联系统模型有多个模块实现系统的某一功能。 系统有一下几个特点； o n 个模块均故障，系统才故障； 只需一个模块正常，系统就正常； n 个模块的寿命均服从指数分布时，系统的寿命不服从指数分布。 ( 3 ) 混联系统模型 对于复杂系统，并不能简单只使用串联或并联的模型来概括，因此需要综合 以上两种模型，先将混联模型等效为串联模型，根据串联基本计算公式，计算各 串联等效模块的可靠度，再根据串联、并联的基本计算公式，按照数学表达式分 配具体各模块的可靠度。 以上简单的可靠性分配模型通过考虑模块问串、并联之间的关系来进行可靠 性分配。这种技术简单、易行，但没有考虑模块的重要性和复杂性，而且在软件 系统中，也无法表示模块之间嵌套以及互相调用之间的关系。 2 权衡模块复杂度与重要度的软件可靠性分配模型 重要度就是描述单元故障能引起的系统故障的概率，复杂度是指单元基本构 造部件数与总构造部件数的比率，比率越大的单元越复杂。 如果仅考虑重要度来分配，则重要度越大的部件分配的可靠性指标越大；同 样的，如果仅考虑复杂度来分配，因为越复杂的部件越容易出故障，因此可靠度 就要分配的低一些。如果综合考虑分系统的重要度和复杂度，系统可靠度的分配 方法如下； 设系统的可靠性指标为 磐分蠢 墨= 敛“一q t ，秀j ，包n ) 一【( b ) 1 7 ”r - ( r r 即 一q j 加0 , - 告l n r j 6 西北工业大学硕士学位论文 第二章软件可靠性分配研究 8 1 ( j ) 希舞 ，k i 一n ， 式中，第i 个分系统的基本构成部件数； n 一整个系统的基本构成部件数； i r _ 分系统数； q 第i 个分系统( 第j 个模块) 的重要度； 白n 第i 个分系统( 第j 个模块) 的工作时间； 吼) 分配给第i 个分系统( 第j 个模块) 的平均故障间隔时间； 见系统规定的可靠度指标。 从上式可以看出，分配给第i 个分系统( 第j 个模块) 的可靠性指标q ( 与 该分系统的重要度正比，与它的复杂度成反比。 权衡模块重要度和复杂度的可靠性分配模型虽然顾及到了每个模块的特别 之处，但没有考虑到软件开发费用的问题，而往往开发费用会限制软件的可靠度。 即使再重要的模块也会由开发费用所限制，不能达到完全可靠。 3 权衡费用的软件可靠性分配模型 1 1 以上两个小节的可靠性分配模型均为无约束软件可靠性模型，但是在实际的 软件系统可靠性分配过程中，保证足够的软件可靠性是需要以足够的费用为代价 的。因此软件可靠性分配问题需要权衡软件开发费用，保证满足费用符合某一条 件的情况下，保证系统总体的可靠性最小；或保证系统总体可靠性最小的前提下， 使费用最小；或保证费用最小的前提下满足软件可用性最大。即可靠性约束代价 最小化模式，简称r c c m ( r e l i a b i l i t yc o n s t r a i n e dc o s tm i n i m i z a t i o n ) 模式； 预算约束可靠性最大化模式，简称b c 雕( b u d g e tc o n s t r a i n e dr e l i a b i l i t y m a x i m i z a t i o n ) 模式；预算约束实用性最大化模式，简称b c 删( b u d g e t c o n s t r a i n e du t i l i t y ( 1 ) r c c m 模型 模块化的软件系统是为多个用户设计的，它包括n 个模块，共完成m 项操 作。一般完成一项操作，需要执行几个模块( 见图1 3 ) 7 西北工业大学硕士学位论文第二章软件可靠性分配研究 图2 - 3 模块化软件系统 于是，得到如下的r cc m 模式： min t c ( 九1 ，尥，h ) 约束条件： r ( 丸1 ，勉，札t ) - p 砑= 0 ( j = 1 ，2 ，n ) 即，在软件系统的可靠性目标给定约束条件的情况下，通过对各个模块进行故障 率村的分配，从而达到最小化总开发成本tc ( 九1 ，地，h ) 的目标。 ( 2 ) b c r m 模型 该模式描述了在开发预算给定的情况下，最大化软件系统的总体可靠性， 具体如下； 目标函数：max r ( 九1 ，尥，h ，t ) 约束条件：t c ( 九l ，砭a n ) = 0 蝎= 0 ( j = l ，2 ，n ) 其中，o ( 0 0 ) 是软件系统开发的最高预算成本，该决策问题给出了一 个目标函数，多个约束条件集。通过求得相应模块的故障率村的分配值，以使 得在总预算成本o 给定的情况下，达到最大化软件系统的可靠性r ( 九l 。 弛a n ，t ) 的目标。 ( 3 ) b c u m 模型 从用户的角度，人们最为关心的是软件的实用性，一般而言，软件的开发费 用不能超过预算o ，同时要保证用户得到的软件实用性尽可能地大，设软件 系统有1 1 个功能模块，记为( m1 ，m2 ，m n ) ，软件的实用性定义如下： u ( r ，妨= 1r1 + t 0 2r 2 + + f 0 nr1 1 ， 其中i 为功能模块i 的重要度，也即用户的关心程度，其数据可由需求 分析得出 5 。ri 为功能模块i 的可靠性，不失一般性，规定0 c t oi l j j = 1 2 ，m 口j + c l n l j a ， j - - 1 ，2 ，m 善q 册j ) c ( 。f 2 j 这个模型满足了软件可用性由该软件功能与可靠性决定这一准则，将程序 层和模块层都考虑进去，符合原模型基于a h p 方法的要求。因此b - f 力式可以作 为当软件可用性与可靠性呈非线性关系时软件可靠性分配的a h p 模型之一。 本文提出的模型并不是统一的模型，除了本文提出的模型，非线性模型还 有很多，而且不同的系统因其不同的架构与模块问的复杂关系，应有不同的非线 性模型。如果通过软件可用性测试来确定可用性模型，模型会建立的更加准确与 实际。 3 3 基于非线性费用模型的软件可靠性分配 h p 模型 软件可靠性是软件质量概念中最重要的固有特性，达不到可靠性指标的软 件，再好的功能也发挥不出来。软件费用几乎渗透到软件工程的所有环节，其重要 性不言而喻 1 4 。 软件系统的开发费用与该软件的可靠程度有非常密切的关系：如果开发费 用不足，就不能完全保证此软件可靠，而且会增加软件的维修费用，造成开发费 用的浪费；另一方顶，提高软件可靠性也是以增加软件开发的支出为代价，面软 件成本的提高又制约了软件的销售和推广。 大多数现有的可靠性分配模型都忽略了软件开发费用模型。l i t t l e w o o d 1 5 提出将软件生命周期费用考虑到软件可靠性模型中。m u s a 1 6 讨论了软件生命周 期费用的最优模型。这个模型假定了测试费用与软件故障率之间是非线性关系， 而将软件的开发费用与软件故障率之间设定为线性关系。 2 0 西北工业大学硕士学位论文第三章软件可靠性分配a h p 模型的优化 在本文所讨论的软件可靠性分配的a h p 模型中，f a t e m e hz a h e d i 和n o u s h i n a s h r a f i 将成本费用模型简单设定为线性模型，即软件中各模块的开发费用随模 块可靠性的增长呈现线性变化趋势( 见眨珊式中最后一个约束条件) 。但是在 很多实际情况中，这种关系并不能够成立。 根据m a r ye h 1 7 的分类，软件开发的成本函数包括如下三种形式： 线性成本模型： c 叫邶籍口， 其中芦对应使得模块1 0 0 可靠所需要的费用，而a 则指出了软件开发成本 随模块故障率a 的增加而线性减少的函数关系。 这个模型与f a t e m e hz a h e d i 和n o u s h i na s h r a f i 提到的费用模型并不矛盾。 后者的费用是包括开发、测试和维修费用的总费用，会随着故障率的增大而增大。 而m a r ye h 的模型表明，当软件总费用一定，若故障率增长，维修费用( 或测 试费用) 必然增大，则开发费用降低。 m a r ye h 指出，除了线性模型之外，模块费用与模块可靠性之间还存在着 两种非线性关系： 对数指数成本模型 一仁4 - 蚺唰以的巍。 i 具他 负幂形式成本删硼，+ c 叫? 句r 籍d 简单来看，m a r ye h 将软件费用与故障率的关系定义为指数关系和对数关 系。参考以上两种非线性费用模型，提出两种非线性费用模型： ( 1 ) 指数非线性费用模型 令 a2 删 ( 专一1 3 ) 西北工业大学硕士学位论文 第三章软件可靠性分配a l p 模型的优化 ，则第i 个模块的费用为 c ( ) 一a i e 4 睁f 牛) 由于c 的取值区间为( 0 ，1 ) ( c = o 则该模块利润率1 0 0 ，e = l 则该模块无利润) ， 而且c 对该函数变化的影响较小，所以取定e = o 5 ，描绘随a 的变化曲线的变 化趋势的改变。则模块开发费用与故障率的关系图如下t 图3 ：1 不同a 值下软件开发费用与粥 诀可靠性的函数关系 图中绘出了不同a 值软件开发费用随模块可靠性呈指数非线性增长的趋势。由此 可见，当模块达到某一可靠性的最低费用已定的情况下，随着最高费用的增大， 软件的总体开发费用随模块可靠性的增长而增长的更加剧烈。 可见随着故障率的增长，模块的开发费用增长的剧烈。 按照指数费用模型建立的软件可靠性分配的) d i p 模型为式f ；f 5 ) 西北工业大学硕七学位论文第三章软件可靠性分配a h p 模型的优化 警u 。薹旧取堋， r m ji “j j = l ，2 ，m ，m 苫l j = 1 2n ，m 4 p “ l j j = l ，2 ，m a j + l g ( 。j 1 1 3 1 1 j ) o 为事先确定的常数，一般取口= o 5 。 ( 4 ) 平坦交叉算子 平坦交叉算子就是b l x - a 中口= o 的特殊情形。 西北工业大学硕士学位论文第四章基于遗传算法的软件可靠性分配a h p 方法 4 4 3f g a 变异算子 f g a 在进行变异操作时，首先根据均匀分布选择出要变异的，- 【以卅个个体 ( p 曩为变异概率，p 为群体大小) ，然后对选中的个体采用某种变异算子进行 变异。设x = ( 薯，工：，毛) ，经编译算子作用后为善= ( x 1 ，而，7 ) 。常 按均匀分布随机选择一个变元毛，并将它变异为 q ，岛 中的均匀随机数r ： 而- 仨絮，一亿2 ，瑚均匀随机选择 ， 按均匀分布随机选择一个变元毛，并根据( o ，1 ) 上的均匀随机数r 将它变 心，5 昔i = j ，r 0 ，d c p m 方法按照如下准则比较两个个体x 和一的 优劣： ( 1 ) 当两个个体x 和石都可行时比较他们之间的适应值， ) 和，o ，) ，适 应值小的个体为最优( 对极小化问题) ； ( 2 ) 当两个个体x 和x 都不可行时，比较v i o l ( 力和v i o l ( x ) ，v i o l 小的个体 为优( 极大化和极小化问题) ； ( 3 ) 当x 可行而r 不可行时，如果v i o l ( x ) 毫，比较它们之间的适应值，o ) 和厂o ，) ，适应值小的个体为优，否则x 为优。 对于本文要解决的软件可靠性分配a h p 模型，以上两种方法都可以使用。但 是d c p m 方法具有更强的通用性，对问题本身和约束基本上没有要求，而且实施 起来十分方便。同时，它将处理约束条件的传统惩罚函数方法，转变为直接通过 比较个体违反约束条件的惩处或适应值来确定个体之间的序的关系，这样可以避 免去定罚因子选择的问题，充分发挥遗传算法的优势。同时，考虑到不可行解在 搜索中的作用，通过动态适应性的调节机制，使得群体中始终保持一定比例的靠 近边界的不可行瞬啦并将它们按可行解对待。这样就使得遗传算法群体搜索的特 点得到了很好的利用。因此决定采用d c 硎方法处理本文的软件可靠性分配a h p 模型的约束条件问题。 4 4 5 软件可靠性分配a h p 模型的求解方法 下图是基于遗传算法的软件可靠性分配a i p 模型的求解流程图。 4 1 西北工业大学硕十学位论文第四章基于遗传算法的软件可靠性分配a h p 方法 卅li 毫遗传算法和各个参数值 i i i h 两 | 根据适应值、v i o l 值和 值， 按照比较准则用竞争选择方 法从p ( t - t ) 中选择出p ( t ) 机生成初始化群体p ( o ) l 每个个体的适应之和v i o i 值i 根据交叉概率用交叉算子 对p ( i ) 的个体进行交叉操 作，得到群体p m 人 r _ 看无可藉j 鬻潞| 根据变异算子对p 啪 w 中的个体进行变异操 作，得到群体聃 人 n l 。埘i 趸终止秋、 | 芝 计算p ( t ) 中个体适应使和v i o l 值，判断有无可行解，若有 y 则计算不可行解的比例 l 厂素、l l 二二 在群体中第一次出现可行 自目p _ z 删，呼州，1 x ，鼬7 i 可行解的比例修正t 的值 图4 - 4d c p m - f g a 方法求解约束优化问题流程 4 4 6 算法的编码实现 相对于面向过程的结构化编程技术，面向对象编程技术编写的程序可以使 得程序的维护和调试更加容易，并且写好的模块可以直接拿来用，而不必重写代 码。但是对于简单的程序流程，一般使用结构化编程。因此本文的算法采用过程 化c 语言编写。 1 数据结构的设计 4 2 西北工业大学硕士学位论文第四章基于遗传算法的软件可靠性分配a h p 方法 考虑到种群是由相同结构的个体组成的集合，因此有必要编写个体的结构 体和最佳个体的结构体如下。a 衫部分为注释内容。 沁令聱睁 u n s i g n e d * c h r o m ；滓繇雠 d o u b l e f i t n e s s ； d o u b l ev a r i b l e ； i n t i n t i n t u n s i g n e d * c h r o m ； d o u b l e f i t n e s s ： d o u b l e v a r i b l e ： 肛个体适应度木 a 个体对应的变量值奉 a 交叉位置宰 堙父令辚肆 a 特定数据指针变量宰 宰最佳个体木 a 最佳个体染色体木 序最佳个体适应度奉 木最佳个体对应的变量值衫 i n t g e n e r a t i o n ；木最佳个体生成代奉 2 主要变量 结合上一小节的流程图，程序主要变量设计如下。 s t r u e ti n d i v i d u a l * o l d p o p ； a 当前代种群幸 西北工业大学硕士学位论文第四章基于遗传算法的软件可靠性分配a h p 方法 s t r u c ti n d i v i d u a l * n e w p o p ；木新一代种群木 s t r u c tb e s t e v e rb e s t f i t ：a 最佳个体衫 d o u b l es u m f i t n e s s d o u b l ea v g ； d o u b l em i n ： f l o a t p c r o s s ： f l o a tp m u t a t i o n ； a 种群中个体适应度累计衫 a 种群中个体最大适应度乖 a 种群中个体平均适应度 肛种群中个体最小适应度宰 a 交叉概率衫 宰变异概率半 序种群大小衫 序染色体长度率 办存储一染色体所需字节数木 序当前世代数枣 i n t m a x g e n ；序最大世代数衫 i n t r u n ；序当前运行次数木 i n tm a x r u n s ；a 总运行次数奉 i n t p r i n t s t r i n g sa 输出染色体编码的判断，o - 不输出，卜输出木 i n t n m u t a t i o n ；a 当前代变异发生次数衫 i n t n c r o s s ：序当前代交叉发生次数衫 3 主要函数 为了完成流程图中的操作，设计程序主要函数如下。 西北工业大学硕士学位论文 第四章基于遗传算法的软件可靠性分配a h p 方法 a 遗传算法初始化衫 a 遗传算法参数输入衫 v o i di n i t p o p ( )序随机初始化种群衫 木遗传算子木 v o i di n i t m a l l o c ( )a 为全局数据变量分配空间幸 v o i df r e e a l l ( ) 宰释放内存空间半 i n tc r o s s o v e r ( u n s i g n e d * p a r e n t l ，u n s i g n e d * p a r e n t 2 ，u n s i g n e d * c h i l d l 。u n s i g n e d * c h i l d 2 )幸由两个父个体交叉产生两个予个体衫 v o i dr a n d o m i z e0 幸设定随机数种子并初始化随机数发生器幸 f l o a tr a n d o m p e r c 0a 与库函数r a n d o m ( ) 作用相同，产生 0 ，1 之间一个随机数幸 4 5 应用实例- - 3 q 计费系统软件可靠性分配实验 为了证明上述算法的可行性，作者结合在实习公司所做的项目进行算法的说 明和验证。 4 5 1 递阶层次结构 构： 按照上文介绍的递阶层次结构，建立3 g 计费系统可靠性分配的递阶层次结 西北工业大学硕十学位论文第四章基于遗传算法的软件可靠性分配a h p 方法 功能层 程序层 模块层 图4 - 53 g 计费系统递阶层次模型 如图，3 g 计费系统面向用户有三个功能：话单的可配置功能、话单的检错 功能和话单入库功能。此软件可用性与这三个功能有关。在模块层上有四个模块 组成：采集程序、预处理程序、一次批价程序和二次批价程序。对于话单可配置 功能，由采集程序和预处理程序提供；对于话单检错功能，由预处理程序和一次 批价程序提供；而话单入库功能来自所有程序。再往下细分，采集程序由配置文 件的读取与基于规则的采集模块构成；预处理程序由以上两个模块和格式转换及 检错三个模块构成；一次批价程序由格式转换及检错两个模块构成；二次批价由 格式转换及检错模块；计费规则配置文件的读取模块、对计费要素的提取模块和 入库模块构成。它们共同决定着这个系统的软件可用性。 4 5 2 模块的合成权重矩阵 首先，要对同一层次的个元素关子上一层此种某一准则的重要性进行两两 比较，构造两两比较判断矩阵。 1 功能层的全局权重 因为功能层的对目标的局部权重就是全局权重，因此只需计算功能层对目 标层的局部权重即可。 对于目标软件可用性： 西北工业大学硕士学位论文 第四章基于遗传算法的软件可靠性分配a i i p 方法 w f 一( 峨峨嘎) - ( o 5 5 8 0 3 2 0 0 1 2 2 ) 矛盾率；0 0 1 7 ( 4 - 1 0 ) 对于( 辱1 们式的两两比较判断矩阵是存在矛盾的：用户认为功能1 是功能2 重要性的2 倍，是功能3 重要性的4 倍，则可以推测功能2 是功能3 重要性的2 倍。但是实际上用户认为是3 倍。实际中的确存在这种现象，这时，便需要计算 矛盾率。且当矛盾率小于某一数值时( 一般为0 1 ) ，认为此两两比较判断矩阵 可以接受。否则，便需要重新构造。关于矛盾率的计算参见 2 6 ，下同。 2 程序层的全局权重 首先需要计算程序层对每个功能的局部权重。 对于话单可配置功能： 对于话单拣错功能： 对于话单入库功能： - ( 1 ：) 一一( 耐硝) 一( o 8o 2 ) 矛盾率= o ( 争i i ) 九( 1 ；)2 ， f 俨一( 哦暖) - ( o 6 6 70 3 3 3 ) 矛盾率= o 吼“1 v 2 ，班。班班 ，fil_il_l_、 i 4 西北工业大学硕士学位论文第四章基于遗传算法的软件可靠性分配a h p 方法 九 1 1 21 112 11 1 - ( 谓谢啊喇) ( 辱1 3 ) - 、 0 2 9 3 0 2 9 3 0 2 0 7 0 2 0 7 ) 矛盾率= o 0 4 6 至此，程序层对功能层的局部权重已计算出来。应月耜靶) 式，可得程序层对于 目标的全局权重为： w p ；( w p l w p 2w p 3 w p 4 ) - ( 0 5 5 8 0 3 2 0o 1 2 2 1 o 8 0 0 2 9 3 - ( 0 4 8 0 3 60 1 3 0 0 3 ) 0 2 0 6 6 7 0 2 9 3 0 0 3 3 3 o 2 0 7 o 0 o 2 0 r 7 ( 辱一4 ) g 一埠j 式所得的是每个程序的全局权重，即对目标的权重。下面计算模块层。 3 模块层的全局权重 对于采集程序： 对于预处理程序： 一2 一 “( 1 ；) 删1 一( 叫叫) 一( 0 7 5o 2 5 ) 矛盾率= o 12 8 1 5 1 w m 2 - ( 叫啊2 叫) 一( o 6 0 4 0 3 2 6 o 0 7 0 ) ( 4 - l 占) 西北工业大学硕十学位论文第四章基于遗传算法的软件可靠性分配a i - i p 方法 矛盾率= o 0 0 5 对于一次批价程序： a 3 - ( 1 ) 阡m 3 一( w m b - ( 1 ) 矛盾率= o 对于二次批价程序： 彳4 14 4 ll l w m ( 叫删4 慨4 慨4 ) - ( 0 6 1 5 o 1 5 40 1 5 4 0 0 7 7 ) 矛盾率= o ( 4 - - 1 7 ) ( z i - i g ) 至此，模块层对程序层的局部权重已计算出来。应用式，可锝模块层 对于目标的全局权重为： w m - ( w m 2 m 码w m 4 w m 6 ) 1 ( 0 4 80 3 60