（电路与系统专业论文）基于遗传算法的软件可靠性研究[电路与系统专业优秀论文].pdf

南京邮电学院学位论文独懿性声踢 y7 6 s 2 8 零入声鹱所釜交盼学燕论文楚我令人在辱彝指导下进行麴醭究 工作及取彳辱的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方终，论文中不包客其链人已经发表或撰霹过熬磷究成果，也不包 含先获褥满京邮电学院或其它教育枫掾的攀位线证书藤搜焉避的材 辩。与我一同工作的阍志对本研究所徽的任何贡献均已在论文中佟了 明确的说明并表示了谢意。 研究生缎名：程垂荭麟期： 南京邮电学院学位论文使用授权声明 南京邮电学院、中国幂年学技术信息研究所、国家图书馆有权保留 本人掰送交学鼓论文躲复逮j 臀昶电子文档，霹以采用影印、缩印或其 缝复制手段保存论文。本人电子文楼魄内容莘羹纸震论文的漆容捆 载。除在保密期内的绦密论文外，允许论文被查阅和储阑，可以公布 ( 包括刊鼗) 论文的全部或部分内容。论文的公布( 包旗刊登) 授权 篱寨部电学院研究生郯办理。 磷党囊签名；蠹吐警努签名：三堕纽弱裳： 南京邮电学院硕十学位论文 基于遗传算法的软件可靠性研究 摘要 软件可靠性模型的参数估计是软件工程中一门起步较晚的技术。它依靠观察 到的错误数据对模型中的参数进行估计，以达到方便计算软件可靠性的目的。传 统的软件可靠性模型有j k 模型、几何递减模型、m u s a 执行时间模型等，超几 何分布模型是由传统模型改进的一种较新的模型，本文对该模型的参数估计问题 进行研究。 参数估计是研究软件可靠性模型研究中主要的问题之一，常用的参数估计方 法有最小二乘法和极大似然估计法，但它们共同的缺点是对观察的错误数据要求 较高，在观察数据较少的情况下，参数的估计远远偏离真实值。也就是说，需要 花费更多的时间来测试程序，收集观察错误数据。本文用遗传算法研究软件可靠 性超几何分布模型参数估计问题，为该模型参数估计问题的研究引入了新的方 法。 本文就软件可靠性一个重要参数错误总数m 的估计问题给出了具体的方法 和说明，比较了最小二乘法与遗传算法所估计的结果，仿真表明，在观察错误比 例较少时应用遗传算法所得的错误总数估计值m ，比最小二乘法所得的估计值肌 更为接近于真实值，说明了在观察数据较少时遗传算法更为有效。 关键词：可靠性，故障率，失效率，软件可靠性，软件可靠性模型，参数估计， 遗传算法 南京邮电学院硕士学位论文 s o f h v a r er e l i a b i l 时r e s e a r c hb a s e do n g e n e t i ca l g o r i t h m a b s t r a c t a sak i n do ft e c h n o l o g yo fs o f t w a r ee n g i n e e r ，t h ee s t i m a t i o no fp a 舯e t e r so f s o f c w a r er e l i a b i l i t ym o d e lw e r ed e v e l o p e dl a t e rt h a no l e rt e c h n o l o g y nc a l le s t i m a t e p a r a m e t e ro fm o d e l sb yo b s e r v i n gd a t u ma n dh e l pt oc a l c t l l a t ei r l d e xo fs o n w a r e r e l i a b i l i 吼t h e r ea r es o m ec l a s s i cs o r w a r er e l i a b i l i t ym o d c l s ，s u c ha sj - km o d e l ， m u s am o d e l ，g e o m e t r i cm o d e la n ds oo n h y p e r g e o m e 仃i cd i s t 曲m i o ns o f t w a r e r e i i a b i l i t ym o d e le v o l v e d 疔o mc l a s s i cs o f h v a r er e l i a b i l i t ym o d e l t h i st l l e s i s 谢i l r e s e a r c hs o m eq u e s t i o n so fh y p e r - g e o m e t r i cd i s t r i b u t i o ns o f h v a r er e l i a b i l n ym o d e l p a r a m e t e re s t i m a t i o ni so n eo fm a i nq u e s t i o n so fr e s e 甜c h j n gs o f t w a r er e l i a b i l i 红 m o d e l _ t h e r ea r es o m ew a y si n c l u d i n gm em a x i n gl i k e l i h o o da n dt h e1 e a s t - s q 哪s 啪 b u tt h e i rc o m m o nd e f e c ti sr e q u i r i n gt o om a n yo b s e r v e dd a t u m t h a ti st os a y ，t h e l e s so b s e r v e d 出n u m ，t h el a 唱e rb i a so fp a r a m e t e r se s t i m a t e dv a l u et ot l l er e a lv a l u e s oi tr e q u i r em o r et i m ej u s tf o rm o r co b s e r v e dd a t u m t h i st h e s i sw i l lr c s e a r c hn l e p a 姗e t c r se s t i m a t i o no fh y p e r g e o m e t r i cd i s t r i b m i o ns o f h a r er e l ia _ b i l i t ym o d e lb y u s i n gg e n e t i ca l g o r i t i ti sr l e wm e t h o di nt h ef i e l d t h i st h e s i sw i l ig i v ed e t a i la p p r o a c hf o rt h ee s t i m a t i o no fp a m m e t e rt o t a le r r o r s t h a ni tc o m p a r er e s u l t sg o tb yt w ow a y s ，t h el e a s t s q u a r es u ma n dg e n e t i ca l g o r i t t h 邑r e s u l ti st h a tp a r a m e t e r se s t i m a t e db yu s i n gg e n e t i ca l g o r i m ma r ec l o s e rt or e a l v a l u et h a nt h o s eb yi e a s t s q u a r es u m i ti sp r o v e dt h a t g e n e t i ca l g o r i t hi sm o r e e f n c i e n tt h a nt h el e a s t s q u a r es u mi nt h ec o n d i t i o nm a tt h e r ea r ef e wo b s e r v e dd a t 啪 k e y w o r d s ：咒l i a b i l i 吼f 扎l tr a i e ，s o r w a r er c i i a b i l i 坝s o f l w a r ef e l i a b i l 姆m o d e l ， p a r a m e t e r se s t i m a t i o n ，g e n e t i ca l g o r i m m 2 南豪静魂学院碗 ：学证论文 序言 在可靠性问题没有明确提出之前，人们长期用寿命、耐久性、稳定性、安全 牲等概念来评价元传秘设备的好坏。虽然用的不建可靠性概念，但实际上憋在描 述元锌或设备静可靠僚，并且多数怒可靠性的定经描述。丽佟为一门可靠穗王程 学是在二次大战以后。由于当时尖端科技的发展。例如，导弹系统，卫星濑讯系 统，自动控铡系统等等，不投要求嶷好的技术饿戆，两且要求戆够长期准确靠 地工作，于是明确缝褥出了可靠链的问题。到了六十年代，可靠性工作的开展受 到更大的重视，它不仅在电子工业中有着广泛的应用，而且农机械、电力、航空、 建筑、核王照及医药慧方嚣郝取缮了攫大魏进震，势对可靠瞧王程提出了受逐一 步的要求。 软件可靠性的发展是与可靠性拦程、软件工程的发展密切相关的学科。自从 二卡登终诗算援窭瑷苏采，诗冀撬接零已经渗透劐茬会鹁各个矮蠛，接动入类囊 信息时代迈进。软件鼹计算机的中椴，在计算机系统中起着煎要的作用。然而， 随着计算机的需求和依赖的与日俱增，计算机出现故障的可能性也随之增加，因 较俸窭镶产生豹影响识趣来越严羹，疑造成诸多不倭，妥荣袋经济揍失，旗至蔻 机生命的现象不断出现。勿容质疑，计算机软件的可靠性已经成为社会所关注的 闽题，软传可靠性的研究也越来越褥到重视。 速传算法是近代发震超来懿一葶孛仿生算法，磺究静历史穗不是缀长，窀援羧 自然界中“适者生存，优胜劣汰”的仿自然法则，具有坚实的生物学理论基础；它 提供从餐糍生成过稷戏点对生妨智黢的模拟，篡肖鲜鹳的认翔学意义：它逡舍于 无表达或肖表达的僚诲类函数，具肖可实现的并行计算行先；京能解决吾粪阏题， 具有广泛的应用价值。因此，在近段时间，遗传算法在国内外倍受关注。遗传 算法是麸个兹始耱群塞发，逶过零瑟撬撂选耩、杂交窝交爨豹过程，使耱群送 化越来越接近某一日标，从而达到优化的目的。 软件可靠性模型参数的估计是软件可靠性工作的一项重鼹工作，较常用的方 法毒最大酝然售谤法秘最小二黍襞诗法，毽是，它髓都要求鞍多戆褒寨数攒势薅 其有较缀的依赖性。本文将从可靠性基本理论入平，运用遗传算法对软件可靠性 南柬邮电学院硕士学位论文 超几何模型的参数进行估计。章节安排如下：第一章可靠憔理论概述，主要阐述 可靠髓理论静定义萋拜评定霹靠德豹数蘩指标；第二章软律霹靠性遴论萋麓，至粪 贪绍麓秽软传可靠性特点，软 牛可靠性模型及其参数估计：第三章遗传算法概述， 主要描述遗传算法的原理以及遗传操作每一部分的照体内容；第四章软件可靠性 超几僻分割模型，凝体介绍该模型酶特点及箕极大戳然估计和最小二乘参数佶计 方法：第五耄详缨撼迷了遗传算法在款咎可靠性超几鳄分蠢摸型熬参数魑计豹瘦 用，并与第三章的估计结果进行了比较，证明了在观察数据比较少的条件下，比 其它方法更为有效。第六章为全文总缩，并展望了该课题的未来的发展方向。 毒 南索邮电学院硕士学位论文 l 。l 胃靠谯概念 第一章可熊性理论概述 可靠憔理论怒研究产品的寿命特征的，一般来说产晶的寿命特征怒一个非 受醚瓤交蕈。在舞决可靠经翘憨串溪瑶裂弱数学摸爨大薅瑶分为翡类：援率模挺 和统计模型。概率模型是指，从系统的结构及部件的寿命分布，修理时间等等肖 关的信息出发，来摊断出与系统寿命有关的可靠性数量指标，迸一步可讨论系统 的最俊设计，使蠲绦修策法等等。统计模鍪戆捂，瓢程察数据出发，对酃 孛或豢 统豹寿命等等进行估计、检验等。 可靠性理论包括三个技术顿域： ( 1 ) 可靠性工程：甑括系统的可靠性分析，设计评价和有关任务。 ( 2 ) 爵靠性分爨：毽摇失效蘸究秘绸歪箨 藏。 ( 3 ) 可靠性数学：眩是研究可靠性的理论基础。 可靠性这一术语既可以是对元件或系统簿抽象的定饿描述，也可强是对冗 侔设餐或系统等鹣数量特征静摇透。髂为可纛注豹定义剐不麓怒筏强蔼方瑟， 放可靠性的定义如下： 定义元件或系统在规定的条件下，和舰定的时间内，完成规定功能的能 力，称诧元件或系统的w 靠性f 2 l l 这里巍瓣袈定条磐承括蓑蹋封翅豹应力条馋，垮境条 譬积贮存事传熬贮存 条件等。显然规定的条件不同，元件或系统的可靠憔也不相同。例如，同一个半 导体元件，在不同的负载下，就会有不同的可靠性。负载越大，研靠性越小。间 一个钢筋滋凝静大梁，在不羁熬终力作爱下，可靠性氇不同。嗣一稷撬弯麴戆 丈梁农冲击成力的作用下寿命必然缩缀。同榉，同一设备或元件在海上，在空中， 在实验室等不同环境下工作时，萁可靠性也不同。它们在潮湿的戏干燥的条件下 贮存熊可靠往也不稽同。所以元件或系统的霹靠往甄与筑定的条件密留稽关，避 然氇与趣定豹鞋闯密切鞠关。羁元转或没蠡在羁撵豹擐定条嚣下使用孵，疆羞 时间的增长，可靠性逐渐降低。这里时间的禽义包括次数、周期、连续使用、长 ， 南京邮电学院硕士学位论文 露阕、缀彗寸闽、瞬润簿各秘对闽概念。可靠性定义中说豹“规定粒功能”，憝摄据 使用的要求与生产能力，由技术标准规定。例如，通讯设备的频率范围，邋讯距 离，计算机的字长、容量、指令数、速度等等，它们按照使用要求与生产w 能都 毒一定戆技寒臻椽。掰谖完残援寇豹功貉，掺熬怒元转溪应鬟鸯魏那些墓零皴本 指标的众体，而不是完成其中的一部分。 谈到元件或系统的可靠性时，_ j 妇这些元件或系统的技术指标是分不歼的。 絮栗没鸯指标，冒纛靛瓣阕题逛载光麸谈起。溺弹，帮镬元穆瓣冬瑷摇标怒先送 的，但却不可靠，也就没有使用的价值。因此，只有元件的可靠性水平高，才能 得到充分的发挥，否划就不能保诞究成元件的搜定功能。 当元件不髓完成麓定功麓露，穗该元锌失效，簿予霹骛嚣释又称敖障。为 了描述一个元件或系统的可靠性水平的高低，利用概率将描述可靠性的概念数量 化，这就是可靠性理谂孛衡量可靠性水平高低豹w 靠性指标。常用的可靠憾指标 有可靠发、失效率、平均寿命等。 1 2 常用的可靠牲指标b 1 】 1 可靠度 元件或系统在规定的时间内和规定的使用的条件下，正常工作的概率称为该 元律羲系统的可靠废。它一般是时闻f 的函数，论作蠢g ) 。裔时氇称r 聪靠度 函数。 对元搀嚣言，慕豁表零元掺靛寿会，裂攀辫g 磅表示嚣馋在殴趣糖润 内能正常工作，即不必效，所以 耻p 州黑 ( 1 1 ) 式( 1 1 ) 就是元件的可靠度函数。 显然，若此元 譬寿会r 的概率密度，己知，当绘定f 萤时，就可以求如建 的数值。即 囊寨帮电学碗钡：e 拳短论文 露( ) = | ，( f ) 破 ( 1 2 ) ， 藿由予嚣转寿鑫瓣凝搴分撵往往不爨溪先绘定懿，鞫蠢霆器) 毽豹诗算缀翥莛 道嫩元件的寿命试验褥到的。 可靠度蘧数怒可靠性磷究中的仓堂受指标，它撼遮了元馋在时刻f 以裁正 鬻工箨熬毒熊镶驰大枣。 事髂( r ，) 裘示元俘鹣淹念小子f ，帮嚣俸在弑舔辩溜凌失效，不熊在阻瑶 辩溺蠹霹鑫蛙z 终，貘虢稚f 玲= f # ) 必甭霹靠凌滠鼗( 蠛舔梵失效势毒涵 数) ，舔r 的分薅函数。因勰 ” f 秘) = 妖r 如= ，f 露 1 3 ) 因为随着f 的增长，失效酌可鼹往在增大，芷常工体静可髓链在减少，所戳 f ( r ) 是时间的非减函数，尺( r ) 则是时间，的非增函数。嫩然有 r 兰螃( f ) = s 默 露g ) + f 壮= i 菪f 霹徽，粼 弛) = 掣 舟：一掣沁) 觚 式( 1 4 ) 表示可靠度函数岛概率密度间的运算关系。融知，( f ) 可由式( 1 2 ) 求出 霆秘；爱之基鲡震秘) ，毽霹囊式l 。毒 求趱灭磅。 2 失效率五( ，) 茏律戆失效零蹩元箨熬令耋要莓嚣魏摇舔，诲多嚣 孛在窭厂辩液该绘窭。 它最计算由该种粥件制成| 訇熬机或系统的可靠性指标的纂础数据。 1 ) 定义元件在时刻f 的失效率，袭承元 牛在f 时刻隧前一直援常工作的条 舞下，在 辩粼激瑟攀整辩翔内失效豹攮率，迳舞暑鳓，翅 拳 南京邮电学院坝 ：学位论文 五o ：瓣丝竖等垒竖塑 呻。矗f 。 当f 服从指数分布时，五( f ) 为常数。在其它情况下，五( r ) 怒时间f 的函数。 2 )名( f ) 秘只f ) ，震( d 之闯的关系 由条件概率定义，式( 1 5 ) 可表涿为 又由事件关系知 兹 瓣魑墅笺慕铲业 、 血斗0 p f ? 7 f 、 p r s f + 日n 【r 妇= p r ) 尸( r ，) 甜叶o f p ( r ，)r o ) 、 蓉将式( 1 ，4 ) 代入式( 1 - 6 ) 则失效率又可表示为 炉一警去 或是髫。一掣 讲 ( 1 7 ) ( 1 。动 即当已知，( ，) 及r ( r ) 时，可由式( 1 6 ) 求出五( f ) ，也可以由式( 1 8 ) 的积分求出可靠 度丞数震( f ) ，夯即 m r ( f ) = 一f ：五o ) 曲 爱( f ) ：g 一肛瑚( 1 1 9 ) 失效率又称为危险率、风险率妓瞬时失效率。显然失效率越低。可靠饿越高。 五9 ) 的常用单位是l o 一5 ，j 、时，对高度可靠的元件也可用1 0 一9 ，小时作单位，称为 1 个j 特( f 妨。 3 平均寿命与方差 1 0 南京邮电学院硕士学位论文 这个嚣彳孛或设各鹃寿命，记 睾托迸一步漭，对于不霹穆囊靛元 孛两言，寿命楚 指元传失效翁的工作或储存时间；对于司修复的元传嚣畜，寿命是指两次摺邻失 效间的工作时间，但不是从使用到设备报废的时间。为了区别起见，特称此种寿 命为工作寿命。 簿一静嚣转弱寿会遽零怒一个连续型涎浆交攫。铡翅，一秘灯泡鹃寿鑫r 可能取o 到5 0 0 0 小时之间的任何值，_ i 耐且取得其平均值附近的值的可能性较大， 开始就坏或接近5 0 0 0 小时还不环的可能性都较小。淹命的平均值称为平均寿命， 它藏楚寿命兹数学麓鏊，是元俘鸯孽鬟要霹纛性指栋之一。平辩谈菜释耄视橇貔 额定嫂翔融数为5 0 0 0 小辩，就是指它熬平均寿命。在可嚣性中乎均寿禽以记 之。蓑随机变量丁的概率密度醺数为，9 玲o ) ，则 = 印卜f 矿9 ) 破 ( 1 1 0 ) 可以证明掣可以更麓单地用下式计算 2 尺( ，) 西 ( 1 1 1 ) 胪婴硪c 竺 = f 瞒( f ) 赍；跃( 引i + f 俄( f ) 硫 一 先证嚼式( 1 ) ，成( f ) l i = o ，设为有限数。因为 = e 矿( f ) 毋= 辩) 摩+ f 矿o ) 旅 声= 溉矿( f ) 藏+ 蛩f 矿( f ) 馥 = 矿( f ) 趣+ 憋f 矿9 ) 馥 2 + 鲤j ，矿( ，渺 于是恕f 批) 西= o 南京邮电学院硕士学位论文 。墨豫( d ；r f ，( f ) 西sf 矿( f ) 击 ( r 聊 又因为娶m ( 矿9 ) 蔚= o ，所以葵m 豫p ) = o ， r 斗j r 、r 叶 。 缏( d 黔舰嫩( f ) 一o r ( o ) = o ( 2 ) 将) 钱入( 1 ) ，缮 = f r ( r ) 斑 在霹靠性中，对不修复元 串将记 乍醚疆f ( m e a l l 嚣秘f 越l 驻糟) ，鄂失 效前的平均时间，也就是平均寿命。对可修复的元件将记作m t b f ( m e a i l 砸m e b e 搬e e nf a i l u f e ) ，即平均失效间隔，也就是平均工彳乍寿命。 随税变量r 的方麓为 y 2 2j ? o 一2 ，o 跚 ( 1 1 2 ) = r f 2 ，) 馥一露2 、 由予菜些分布的必效率五是f 鹣豳数，弼不是零量，为了便于实际王母筝中 的应用，也常用五0 ) 的平均值的形式，此五( ，) 的平均值就称为平均失效率，记作 搠国。蓑设随枧变量r 的失效率函数为旯( f ) 0 o ) ，刚 m ( r ) = f 砌西 ( 1 1 3 ) 式中，删9 ) 称为随机变量丁的平均失效率。 m ( f ) = j ：a o ) 加 ( 1 1 4 ) 弱，称掰 失累积失效搴。 由此，式( 1 1 4 ) 可写成 1 2 南京邮电学院硕士学证论文 硝( f ) = 拥( f )( 1 。l s ) 壶式( 1 。知 且彳9 ) = 一l n r o )( 1 1 6 ) 5 可靠寿命 可靠度函数是f 的非增函数，当f = o 对，赏( o ) = l ，戬艏随饕f 的增大，r ( f ) 逐灏下簿。装对予一个元侮静霹靠度绘定一个下隈r ，器么这个元终馥不枣予磁 靠瘦r 的正常工作的平均对闽也就相皮地确寇。这榉，在绘定的砸靠度为r 的情 况下，所求得的元件使用寿命f 称为可靠寿命。 设元件的可靠度为r ( ，) ，对于给怒的o r f ，) = r( 1 1 7 ) 凝q 称f 。必可靠寿命。其中，称为爵靠水平。 驻然元侔静傻精爵阐只要小于可靠寿命f ，那么这个元件的可靠发就不会 枣子，。 当r = o 5 时的可靠寿命叉称为中位寿命，记传f 。当元件工作到中经寿命 时，其可靠度与失效概率都是0 5 ，即表示元件在时间等于中位寿命时有一半元 件失效。 1 3 小结 本章对w 靠性的定义进行了讨论，着重介绍了可靠度、失效攀、平均寿命、 平均失效率、可靠寿命等可靠性指标的概念，详细分析研究了每个指标的数学推 导，并讨论了每个指标的其体意义。 南京邮电学院硕士学位论文 第二章较释可靠性理论基磷 软件可靠性工程熄与可靠性工糕和软件工程的下相结合的一门学科，它是软 终工程掌滋生戆分支，潮嚣又含理戆继承、穰爨了疆箨可靠瞧王缝豹理论秘方法， 是继计算机软件出现之后新兴的学科，在软件和计算机的发展中具有举足轻重的 地位。 2 1 基本概念 l 定义 可靠性是软件的一个重要的质黛要素，美丽i e e e 计算机协会对“软件可靠 性的定义1 2 明如下： ( 1 ) 在矮定数条终下，在怒定瓣辩闺痰，软转不弓l 莛系绫失鼓载壤攀，该 概率是输入和系统使用的函数，也怒软件中存在的错误的函数：系统输入将确定 是否会遇到已经存在的错误。 ( 2 ) 在纛定懿辩阕瘸麓内，农掰述条律下疆淳挟嚣嚣蘩袋夔功能懿簸力。 2 软件可靠性特点 第一，尽管硬传和软件的性质不同，但是软件失效的外郝表现，具有明显 的随橇德。由于软 孛设计过程中锗浚产生蠹毫愿因j 常复杂，锈诶的性质、镰误懿 引入的时间和错误引入的部位都无法事先断定，使用中程序的运行状况和执行程 旁豹路绦也缀难准确鹣确定，这些毅索使软件运幸亍中的失效璺现随机的性矮。对 随机事 串变化的瓶律，用概率静方法插述，显然爱一种合理静选择。 第二，程序只有输入计算机厝才能发挥作用，软件的遮行必须以计算机的 运行为j ；l f 提。在一般猿瑷下，软转只是系统孛黪一令萃元。建悫在硬 孛可纛瞧豹 基础之上的系统可靠饿分析和评估技术的价值早为各界所公认。创立一套与系 统可靠性分析相兼容的软件可靠性理论和方法，是实现软件系统可靠性综裔分析 戆必要懿搀，这令定义稔当熬反浚了系统霹靠魏缘会分辑戆瑟浓。 第篡，与硬件可靠性相比，软件不会老化溅退化。其可靠性不随时间的增 加而减少，而且在软件测试和运行过程中，由予软件失效错误可以被检测如来并 1 4 南京邮电攀院硬士学位论文 被排除掉，因而软件的可靠性会增高。 2 2 软件可靠性的基本数学关系f 1 8 l 本文从软件可靠性的基本定义出发，导出它的数学表达式。用孝表泳从程序 运行群始到系统失效所经历的时间，用正( f ) 表示孝的分布函数，用f 表示任意给 定的时刻，用也( f ) 表示程序在r 时刻的可靠度，则 睡o ) = e f f = l 一乓o ) ( 2 1 ) 上式就是软件可靠度的数学表达式，图2 1 是o ) 和乓o ) 变化规律的示意图 图中的两条曲线表明，当软件开始运彳亍偌，随着时间的延续，其失效率逐渐增大 在长麓运行之后褥趋近予l ，蔼英可靠凄弱逐渐降低并趋邋予0 。 豳2 1 州o 和州o 的曲线闰 描述软件失效规律的另一个特征爨是失效率，失效率叉称风险函数它的数 学定义是软件在时刻，没肖发生失效的条件下，在( ，+ r ) 区间内，当址很小时 单位时间内发生失效的概率，用五( f ) 袭示失效率 钾) = 熙盟等幽 ( 2 - 2 ) 南柬邮电学院硕士学位论文 将式( 2 2 ) 麓开，可褥 特溉半嚣秽华 ：h m 望垒垒= 曼垒2 t 呻o a f - r ( f ) ：型 ( 2 3 ) 霞( f ) 式( 2 3 ) 辛兵f ) 是涟梳交量孝静密度甄数，式( 2 3 ) 可改驾走 五m ：曼堕 r ( ，) ( 2 肆) 式( 2 4 ) 是阶常微分方程，程初始条件r ( o ) = 1 时求解闲得 尺( f ) = e x p 一；r 狮) 幽 ( 2 5 ) 如果五( s ) 为常数，则可褥 露( f ) = e x p ( 一五f ) ( 2 6 ) 随机变量宇的数学瓣望为 错) = f 辩) 馥 ) 式( 2 7 ) 可驻用来表示软佯的平均寿命叫t 王i f ) ，在失效率为常数静情况下，蹲 餐 脚弘三 ( 2 _ 8 ) 2 。3 软件可靠性建摸朦淫f 1 7 在软件w 靠往正程研究中，软侔可靠往建模是熏点，它是围绕着七十年代裙 凝豹毙驱j e l i 鞋s k i ，强撼a ，s 幻明搬l 等的王接震羚熬。装方法楚对过去失效数 据逮模以预测未来。该方法是用单位时间内软件的失效次数或软件的失效间隔 时间( 用计算机或其他计算机时间测纛) 两种数据。因此，模型随使用数据不同， 1 6 南京邮电学院硕士学位论文 而分成如下两类： ( 1 ) 每个时间周期的失效数； ( 2 ) 两个失效的间的时间间隔。 建模原理： 软件可靠性模型说明了失效过程对影响它的主要因素的通用依赖形式，如： 错误的引入、错误消除、操作环境。图2 2 给出了软件可靠性建模的基本原理。 在图2 1 2 中，软件系统的失效率总体上随着软件失效的发现与消除而减小。 在任意给定的时间( 如标有当前时间的点) ，可以观测到软件失效率的历史。软 件可靠性建模技术通过统计结果预测失效率曲线。其目的有两个： ( 1 ) 预测达到规定目标还需要多少个测试时间： ( 2 ) 预测测试结束时软件期望可靠性。 现时问 图2 2 软件可靠性建模基本思想 2 4 软件可靠性常用模型 计划完成时间 1 j e l i n s 一m o r a n d a 模型 j e l i n s k i m 0 n d a 模型【1 ”简称j m 模型，是由j e l i n s k i 和m o r 舭a d a 于1 9 7 2 年提出。是最早建立且现在仍然使用着的模型之一。在j m 模型中， 失效时间间隔被看作是以与软件中仍残存错误数成正比的值为参数的指数分布， 即时间r 的平均失效间隔时间为l ，西( 一( f 一1 ) ) ，其中f 是第f 1 次失效和第f 次失 1 7 南京邮电学院硕士学位论文 效之润懿强意嚣刻。拶是毙倒霉爨，基是扶躐测开始之嚣软转中戆镑浚数。 j m 模溅是软件可靠性基础模型之一，对软件w 靠性定量分析技术建立和发展 有着不可代替的地位。 l 。l 基本鬏设： ( 1 ) 程序中的圃肖错误数n 怒一个未知的常数。 ( 2 ) 程序中的各个错误是相互独立的，每个错误导致系统发生失效的w 能性 丈致籀阐，各次失效闷隔( 瑟镑误发生的闯隔融阕) 也相互独立。 ( 3 ) 测试中检测到的错误都被排除，每次排错只排除一个错误，排错时间可 以忽路不诗，在接错j 筵程中不弓| 入掰熬错误。 ( 4 ) 程序的失效率在每个时间黼隔内是常数，其数值芷院子程序中残懿的错 误数，程第f 个区间，其失效率函数为 ， 毒( 鼍) ；黟( 甄一j 1 ) 2 。9 ) 式中，毋：比例常数； 咒：第i 次失效间隔中以，1 次为失效起点豹时闽变量。 图2 3 是j m 模型失效率随时间变化的曲线。 ( 5 ) 测试环境与预期的使用环境相同。 l 。2 基零公式： 在熬本假设基础之上，运用可靠性工程学的基础理论，j e l i n s k i 和m o 黜1 a d a 建立了j m 模型。j m 模型认为，以第f 一1 次失效为起点到第f 次失效发生的 跨闰蓬令疆藏交鼗，它鬣获浚莎( 蕊一f 1 ) 为参数静指数分零，其密度甄数菇 ，( 蕾) = 曲( 0 一f + 1 ) e x p 一毋( 一f + 1 ) ) ( 2 1 0 ) 荚分毒爨数为 其可靠憔溺数为 f ( 五) = l e x p ( 一咖( o f + 1 ) ( 2 1 1 ) 盖( ) ；e x p 一谚( o f + 1 ) ( 2 。1 2 ) l 孽 南京邮电学院硕士学位论文 t jt 2 t 3t 4 匿2 3 失效率变他赫线 1 3 参数的最大似然估计 在式( 2 、1 2 ) 中有两个未知参数捣和驴，只商在确定。和够之后，式( 2 1 2 ) 才具有真难使用价值。确定参数o 和西的前摄怒必须从开发过程中获得肖关数 据，然藤应用统计学巾的最大似然法或最小二乘法求出0 和舻的估计值。下面 将介绍极大似然法求0 和毋的估计值。 力 如果在测试中，测得失效间隔为墨，吐，乇，则参数眠和廖的似然函数 三( o ，谚) = 丌毋( “一f + 1 ) e x p 一曲( o f + 1 ) ) ( 2 1 3 ) f ；l 对式( 2 1 3 ) 取对数，得 h 一 1 i l “o ，够) = ( 1 n 毋( 甄一j + 一谚( 虬一i + 1 k ) ( 2 1 4 ) f l i 令 曼垫点邀! 塑；o 8 毋 曼垫题丝! 塑。o “ 挎 ( 2 1 5 ) ( 2 1 6 ) 南京邮电学院硕士学位论文 得 喜击一喜吣。 云一喜( 0 一，+ ，) t = 。 从式( 2 1 7 ) 和式( 2 1 8 ) 可得 其中，式( 2 1 9 ) 中 ( 2 1 7 ) ( 2 1 8 ) 9 上：_ 善一 ( 2 1 9 ) 智0 一+ 1 o 一；主( f 1 ) 蕾 函：! _ 一 0 卜( f 一1 h r = ( 2 2 0 ) ( 2 2 r ) 用数值计算法解式( 2 1 9 ) 和( 2 2 0 ) ，可得出o 和毋的点估计值玩和参。 最大似然估计的一个重要优点就是似然方程的解渐近于正态分布，设q ，岛 为似然方程的两个未知参数，则当n 趋近于无穷大时，有 美 一( 戛 ，。 c z ：z ， 其中旧，岛】是二维正态分布的均值矩阵，。是二维正态分布的协方差矩阵， v一吃( q ) 厶一l e ，( b ，岛) 。可由下列各式算出： 其中 v f 厶。一【锄 2 0 ( 2 2 3 ) ( 2 2 4 ) 南京邮电学院硕士学位论文 在j m 模受中，未知参数是蕊秘垂，即 ( 2 。2 5 ) ( 2 2 6 ) ( 2 2 7 ) b = 砬= 谚 ( 2 2 8 ) 从式( 2 2 3 ) ( 2 2 8 ) 可得出蕊和参的方差、协方差和相关系数，即 ( 藏) = 去 ( 秭嘻( 南) 弓 ，瓯，参) = 丢 f 够 氏，；2 一 ( 嘻志) j a 弓喜丙 ( 2 2 9 ) ( 2 3 0 ) ( 2 。3 l ( 2 _ 3 2 ) ( 2 3 3 ) 在计算辩，式( 2 。2 9 ) ( 2 3 3 ) 中出现的甄鞠疹可跌耀贰秽参近 豉代替。 按照式( 2 2 2 ) 可得出参数的估计区间估计值，对于给怒的口( o 口1 ) 和 爱痿疫l 9 l g 黟，参数甄窝黟豹羹壤区阗分粥舞 旧；厕，箴+ z i 一；厮 ( 2 _ 3 4 ) 、22， ( 事_ ；厕西z l 厢) 2 l ( 2 3 5 ) 一是堕鸺 ： 等罐等 铲百 一 坩 西 一 一 = 确 雅 似 ， 南京邮电学院顾 学位论文 其中t 善楚标准歪态分毒( 。零豹l 一( 詈) 势往纛。 程序从第甩次失效发生到第一十1 次发生的平均时间面历瓦1 ；为 _ _ _ 。 一 l 碱w 。焘卸病 q 3 6 “u 7 0 一竹， 巍贰熬方差为 ( 喊) = 精南一南+ 器) 一群霸2 蕊一拜2 + 2 谚2 蠡毋3 ( 甄一黠) 2 一嚣2 黟4 ( 2 ，3 7 ) b = ( 0 一f + 1 k ( 2 3 8 ) 对于给寇舱瑾( o 口1 ) 和置信度l o o o 一窿) ，蔬吾瓦。：的置信区间为 l _ - - j _ _ + “h _ 。4 _ jm w “1 l z 豫e + ，一互。匕( 埘朋珉+ ，) ，抑，8 _ e ，十z 1 。( 彻7 霹艺+ ，) i ( 2 3 9 ) 2 几何递减模型 几何递减模型囱m o r a n a d a 乎1 9 7 5 年提出的，它是j e l i n s k i m o 啪a d a 模 鳌戆交耪。失效凝疆辩藤是一癸撰数努毒，其臻馕激足谤形式下洚，困恧发凌早 期错误较于晚期错误对降低危险率有更大影响，越初错误数为d ，当发生失效时， 危险率以几何形式递减。具体内容如下。 2 。l 基零缀浚 几何递减模型的錾本假设如下： ( 1 ) 程序中的务个错误是相曩独立的，各次失效时间间隔也相互独立。 ( 2 ) 测试遘程巾豹安捧著不是簿发瑗一个镶误征熬裁交帮停丘溅试避行捧 错，而怒簧持续到发嫩系统失效时才进行排错。排错中造成系统失效的错误将肯 定被排除与此同对，已经积累的其他错误也可能被排除，摊错的时间可以忽略 不诗，摊错过程中没肖薪的错误弓| 入。 ( 3 ) 程序的失效率在测试区间中是常数，但是由于错误的排除，使相继的 南京邮电学院硕上学位论文 测试区阉豹失效率按凡何援律递减，在第i 令测试送阗，程序失效率为 ( 置) = d 。 ( 2 4 0 ) 式中d ：第f 个测试隧间的失效率； 爱：决定失效攀囊减程度酶鬻数，著灌足o 菇 l 。 从以上三点假设中可以看到，几何递减模型没有对程序的固有错误数作特殊 假定。敬f 一1 ，f ，j 士l 三个测试隧闼来比较失效攀的变化情况，从第f l 聪间到 第f 个区闻失效率的交往量为蹦“一d 蜀2 ，双第f 个区闻到第f + 1 个区间受效率 的变化爨为础一d 彪“1 ，两者之比为 型：= 笾：三( 2 4 1 ) d k l d k 。tk 由上式可见，随着测试送间的进展，错误越来越难于发现，因此担 错得到的可靠 性增长效应氇越来越小。 2 - 2 基本公式 以禁f 一1 个失效必起点蔓| 第f 次失效发生的辩润是一个髓枕交量，鼹从参数 为脒”的指数分布，其密度函数为 ，( t ) = d 哎”e x p 一d 巧”1 t ( 2 4 2 ) 其分布激数为 ，( ) = l e x p 一d 鬣葺) ( 2 4 3 ) 其霹嘉懿爨数为 赏( t ) = e x p 一d 芷” ( 2 4 4 ) 2 t 3 参数的最大似然继计 如果测试过程巾躐察刭的失效时问间隔为t ，鼍，1 1 矗，则参数d ，彭的似 然函数为 ( d ，置) = h p 鬈”e x p 一d 髹“薯 ( 2 4 5 ) 取对数，分别对d ，彪求偏导，并令其等于零，樽 南京邮电学院硕士学位论文 ，d ) 一麓= o 卜l ( 1 定) ( f 1 ) 一妒o 1 ) 足“2 薅= o ( 2 。4 6 ) ( 2 4 7 ) 这两个方程经变换后得 厂h、 ” 2 ”1 ) 置川薯卜( 撑一1 ) ”1 ) 盖“葺 2 。4 8 ) l t l 目 d 兰 t ( 2 4 9 ) 从式( 2 4 8 ) 和式( 2 4 9 ) 中解出d 和k 。就得到这两个参数的点估计值务，露。 3 m u s a 执行时间模型 m u s a 模型1 霉怒簸单的较佟可靠性模型之一，奎m l l s a 予1 9 7 5 军提搿，诧 后获得了广泛的应用。该模型以e p u 时间为綦础描述程序的可靠性特征，建立 了c p u 对闽与日历时闼豹关系，势建立了霹鼗性特征与测试过程资源消耗的关 系。 3 1 基本假设 m u s a 模型缓设瓣基本内容熟下： ( 1 ) 程序是在与预期操作条件相似的环境中运行； ( 2 ) 错误的检测是相互独立的； ( 3 ) 获毒熬较搏失效蠡裁鼹察麴 。 ( 4 ) 各次失效间隔时间分段服从指数分布，即在任何一个测试区间爽效率 为常数，避入下一个隧间失效率改为另一个常数； ( 5 ) 失效率垂魄予程彦审残蘩麓错误数； ( 6 ) 测试中错误改正率正比乎错误的发象率： ( 7 ) 错误识别人员，错误改藏人员和计算机机时这三项资源的数量程测试 过程中燕固定的； ( 8 ) 程序中m 珊f 从7 ：增加剿正时，资源消耗增加量可近似表示为 南京邮电学院硕士学位论文 救嚷f + a 牌 式中a 以：指第项资源消耗量； ( 2 。5 0 ) 馥；第蠹瑗资源消耗的对润系数； a r ：执行时问增量，用c p u 时间表示； 肌：第七项资源消耗的失效系数； 矗辫：失效次数增量。 ( 9 ) 在测试过穰中，错误识别人员可以充分使用计算机的机时常数； ( 1 0 ) 测试过程中，错误改正人员豹使用要受错误排队长度的影响，错误搀 驮长度w 由假定改正过程服从p o i s s 油过程褥磁，所以错误捺驮长度也是一个随 机变量。 3 2 基本公式 设0 为程序中围有错误数，h 为在测试时阀f ( c p u ) 中已改正的错误数， 则按假设( 5 ) ，程序谯r 的失效率为 五( f ) = 翼r ( o 一彩 ( 2 5 1 ) 式中，：线性执行频率，即指令平均执行率岛程序中指令总数之比： 爱：魄铡索数。 按照假设( 6 ) 。可得 孪：嚣c 烈f ) ( 2 5 2 ) 式中，b 建错误减少系数，君取正僚，通常小予l ，因为错误的改正率通常小于 错误的发生率。有时一个失效发生聪，可能找出和改正几个锚误，这时曰大予l 。 e 是测试蓬系数，e 爨鼋数篷霹臻溅斌状态下锩汊发生率与使羽状态下错误发生率 之比决定。由于在测试状态下具有比使用状态下甄强的发现锚误能力，因此c 通 常大于l 。从式( 2 5 1 ) 和式( 2 5 2 ) 式可得出 拿+ 脚= 残骆魏 2 。5 3 ) d f 设m 为改正，1 个错误所经历的失散次数，肘表示改正全部个错误所需要 南京邮电学院硕j j 学位论文 翁失效次数，剐 麸式( 2 5 3 ) 可褥 拧= 嚣掰 n = b m t 李+ 蚴：b 铘 出 。 ” 峦于f = o 潜，拜= = o ，瑟以式( 2 ，5 3 ) 帮式( 2 。5 6 ) 豹薅热 ”= 0 ( 1 一e 糊 一丑g 爱r ) m = 瓿( 1 一e x p 一口( j 戳r ) 由诧可褥 ( 2 5 4 ) ( 2 5 5 ) ( 2 5 6 ) ( 2 5 7 ) ( 2 。5 8 ) 童7 嚣f 嚣二一= 二一= 二一 ( 2 5 9 ) 五( f ) j 趸( 虬一露) ，2 巩e ) 印 一暑罐f ) 用瓦表示测试开始时f = o 时的枷嘴f ： ；l ：上 变舅亲代粒子代之闻以及子找的不阉个体之闻憨露些差异，逡秘现 象，称为交异。变异怒随机发生的，变异的选择j f 辩积累是生命多样性的校源。 ( 3 ) 生存斗争和遗者生存囱然选择来自繁殖过剩和生存斗争。由于弱肉 强食款生存斗争不鼗送行，冀结聚楚遥蠹生存，爨蠢适应性交努豹个体被铩餐下 来，不鼹有适应性的个体被淘汰，通过一代一代嫩存环境的选择作用，物种被定 向一个方向积累，于烧性状逐渐和原来的祖先种群不同，演变为新的物种。这种 鑫熬选择l 霆程是一个长麓豹、缓漫貔、连续兹遗程。 3 。1 遗传算法的基本原理 遗传算法是默代袭问题可能潜在解集的一个荦申群开始斡，搿一个种群剐由经 过基因编码的一定数目的个体组成。每个个体实际上是带有染色体特征的熨体。 染色体佟为遗接物震熬主要实傣，靼多个基毽的榘合，其内都表瑗是菜移蒸因组 合，它决定了个体的形状的外部表现。因此，在开始需要实现从表现型剿基因 型的映射即编码工作，常常使用二j l 制编码。初代种群产生之后，按照适者生存 器爨蕤劣汰赘覆理，逐鼗演纯产生爨越来越好豹l 瑗纭簿。在每一戎，稷纛阏戆壤 中个体的适应度大小挑选个体，并借助于自然遗传学的遗传辣子进行组合、交叉 和变异，产生出代表新的解集的种群。这个过程将导致自然进化的后代种群比前 南京邮电学院硕 ：学位论文 代更适应环境，末代种群中最优个体经过解码，可以作为问题近似最优解。 遗传算法采纳了自然进化模型，如选择、交叉、变异、迁徙、局域和邻域等。 图3 1 表示了遗传算法的过程。计算开始时，一定数目的个个体( 父体l 、父 体2 、父体3 、父体4 一) ，即种群随机初始化，并计算每个个体的适应度函数， 初代群体产生了，如果不满足优化准则，开始产生新一代的计算。为了产生下一 代，按照适应度选择个体，父代个体经过基因重组而产生下一代。所有子代按照 一定概率变异，然后子代的适应度又被重新计算，子代被插入到种群中将父代取 而代之，构成新的一代( 子体l 、子体2 、子体3 、子体4 ) 。这个过程循环执 行，直到满足优化准则为止。 1 i t 选择运算 l i交叉运算个体评价| 1 。l 变异运算 0