IGA-BP混合算法(精选三篇)
IGA-BP混合算法 篇1
小波神经网络(WNN)是由法国信息科学研究机构IRISA的Zhang和Benveniste(1992)首次提出的,它是基于小波分析而构成的一类新型前馈网络模型[1]。它既利用了小波变换的多尺度时频分析手段和良好的逼近特性,又具有传统神经网络的自学习能力、泛化能力及非线性映射能力,非常适用于解决函数逼近、系统识别等问题。但由于小波神经网络的训练主要基于BP算法,同样存在全局搜索能力差、容易陷入局部最优等缺点[2]。为此,学者们通过蚁群算法[3]、遗传算法[4]等智能算法计算网络参数,克服小波神经网络的缺点。其中,蚁群算法属于组合优化算法,通过对初始值的组合排序寻找最优解;遗传算法属于随机优化算法,通过初始值的改变寻找最优解,而在网络维数较大的情况下,随机优化算法较组合排序算法具有更明显的优势。但遗传算法的解空间容易被相似性高的适应值个体充满而缺乏多样性,导致算法早熟,局部搜索能力差;免疫算法基于浓度的抗体繁殖策略通过保证抗体多样性,能够避免早熟收敛。所以,本文通过在遗传算法中引入免疫算子并将BP算法嵌入其中,优化小波神经网络的参数。同时还对遗传算法的初始数据生成、交叉与变异概率,以及BP算法的收敛速度采取了改进措施,并将改进后的算法应用于企业绩效评价,发现该算法能以较高的精度逼近期望数值,有助于提高解决预测、评价中存在的多因素、不确定性和非线性等问题[5]的能力。
2 基于免疫遗传BP算法的小波神经网络模型
模型的基本思想是在小波神经网络参数的选取中,把BP算法有效的局部搜索与遗传算法的全局搜索相结合,这样既可以减小遗传算法的搜索空间、又较容易收敛到最优解[2];在群体选择中,为保证多样性而采用基于免疫算子的遗传算法;在小波神经网络的训练中,为了加速网络的学习收敛速度,采用动态调整学习率及误差熵函数的方式训练网络参数。此外,在遗传算法中还采取了初始种群的小区间生成法[6]及自适应的交叉概率与变异概率[7]等改进措施。
2.1 小波神经网络模型结构及BP算法
小波神经网络用非线性小波函数取代通常BP网络中的S型激活函数,具有一致逼近和L2逼近能力,多输入、单输出的小波网络结构如图1所示。
其中,输入样本的个数为N,输入层结点个数为m、输出层结点个数为1,由样本的模式特征决定;隐含层结点个数为n,由min(m,1)<n≤2m+1确定;xik为输入层第k个输入样本的第个i元素,rik为输入层第k个输入样本的第i个元素的归一化值;yk为第k个输入样本对应的输出值;vj为连接隐含层结点j和输出层结点的权重;wij为连接输入层结点i和隐含层结点j的权重;Ψj(aj,bj)为隐含层到输出层的激活小波函数,aj和bj分别为第j个隐含层结点的伸缩系数和平移系数;dk为第k个样本的期望输出;输出层使用线性函数。则WNN的模型为:
小波分析的前提是选择合适的基本小波函数。常用的小波函数有Morlet小波、Gauss小波及Marr小波等基本小波函数,函数Ψ(x)的选择应该满足框架条件
BP算法通过计算误差熵函数动态调整学习率、计算均方误差对权值及小波参数进行梯度调整。反复进行上述过程,当满足结束条件时,输出训练的权值及小波参数。其中,误差熵函数的计算为:
动态调整学习率η:当本次误差E(t)小于前次误差E(t-1)时,说明网络朝着优化方向前进,此时增大学习率,即η(t)=αη(t-1),α>1;当E(t)>1.04E(t-1)时,说明本次训练不优,应减小学习率,即η(t)=βη(t-1),β<1。
计算均方误差
其中, mc为动量因子,
2.2 免疫遗传算法
遗传算法由美国Michigan大学Holland教授于1962年提出,通过模拟生物的自然选择和群体遗传机制形成的一种自适应全局优化概率搜索算法,可以有效地解决较复杂的非线性组合问题及多目标函数优化问题。但由于遗传算法的解空间容易被相似的高适应值个体充满,导致解空间个体缺乏多样性,从而使算法局部收敛,求解精度低。免疫优化算法模拟了自然免疫系统基于浓度的抗体繁殖策略,对浓度较大的解进行抑制,对浓度较小的解进行促进,利用抗体多样性保持机制,提高算法的解群体多样性,可以避免早熟收敛和提高收敛速度。
免疫遗传算法就是将免疫算法和遗传算法有机地融合起来的优化算法,通过将生命科学中免疫的原理与遗传算法相结合来提高算法的整体性能。融合方式主要有两种,一种是在免疫算法抗体多样性的维持机制中加入遗传算子[8],另一种是将生物体免疫系统的免疫机制引入到遗传算法中。本文采取后一种融合方式,在群体选择时综合考虑个体的适应度与浓度,通过对浓度过高的个体进行抑制,适应值高的个体进行促进,消除解空间中冗余的个体,提高种群的多样性,进而使算法较好地收敛到全局最优解,避免局部收敛现象[9]。
对于小波神经网络模型的学习问题可以等价于如下非线性优化问题:
①初始种群的小区间生成。
为了扩大搜索空间和搜索到全局最优点,改变种群中个体在解空间的分布情况,将待优化参数的取值范围分成种群总数个小区间,再在各小区间中分别随机生成一个初始个体。这样生成的初始个体将会均匀地分布在整个解空间上,并能保证随机产生的各个体间有明显的差距,保证了初始种群含有较丰富的模式,增强了搜索收敛于全局最优点的可能[10]。
②编码与解码。
利用线性变换
进行实数编码,把初始变化区间[a(j),b(j)]第j个优化变量x(j)映射为[0,1]区间上的实数u(j), u(j)即为基因,所有优化变量对应的基因顺次连在一起构成问题解的编码形式u(1)…u(j)…u((m+3)×n);解码时把每个基因值u′(j)代入式(8)得优化变量值x(j),再经式(7)得到相应的目标函数值。这里的x(j)代表wij、vj、aj、bj.
③适应度函数与个体浓度。
优化的目标函数就是求MSE(误差平方和)全局最小值,个体的适应度值即用MSE来衡量,则适应度函数为f=1/(1+MSE),其值越大,表示个体的适应度越高;如果群体中个体v与个体w的适应度值分别是f(v)和f(w),则个体v与个体w的相似度Qs(v,w)=f(v)/f(w)满足1-ε≤Qs(v,w)≤1+ε,其中,ε>0是一个小正数,称为个体的相似度阈值,一般取ε=0.05,即保证个体v与个体w有95%的相似性[11];与个体i相似的个体(包括自身)的个数记为ρ(i),则个体i的浓度概率为pd(i)=ρ(i)/M.
④选择运算采用精英策略与复合选择相结合的策略。
精英策略强迫当前种群中适应度最高的个体无条件存活下来,从而避免概率误差而造成优秀个体的丢失。复合选择综合考虑个体的适应度值与浓度,个体的适应度值越大,则选择的概率越大;个体的浓度越大,则选择的概率越小,这样就可以将那些具有较高适应度且浓度相对较低的抗体保留,进入到下一代操作,维持了进化过程中个体的多样性,从而提高算法的全局搜索能力,避免陷入局部最优解[12]。
个体适应度概率采用经典的赌轮法, 即个体被选中的概率与其适应度大小成正比。选择概率为
⑤群体的交叉与变异。
交叉操作与变异操作的概率均采用自适应调整规则[10,13,14],算法分别为:
其中,f′c为待交叉的两个父代个体的较大适应度值,f′m为待变异个体的适应度值,fmax为种群最大适应度值,favg为种群平均适应度值,这就使得交叉概率pc、变异概率pm随着解的评价函数适应度值相应地改变。
2.3 模型的实现步骤
以评价模型为例,设xik为输入样本,yk为实际输出,dk为期望输出,则建模过程如下:
Step1: 输入指标的一致化及无量纲化处理。由于各评价指标值的范围有一定的差距,为避免训练在网络的平坦区域陷入极值,首先对样本进行归一化处理。对于效益型指标采用式(12)将其归一化,对于成本型指标采用式(13)将其归一化,rik为归一化后的样本。
Step2: 确定网络结构。采用增减法寻找使小波网络稳定的隐含层的结点个数n.
Step3: 种群初始化。根据权值及小波系数的初始值的范围决定初始种群的规模, 采用小区间法生产初 始 种 群并编码, 编码后染色体的结构为w11…wij…wmnv1…vj…vna1…aj…anb1…bj…bn,种群规模M通常取20~100。
Step4: 父代染色体的解码及适应度评价,如果存在满意个体转入Step10,否则转入下一步。
Step5: BP训练。按照式(1)至式(6)进行网络参数的训练,训练次数以100~500次为宜,如果得到满意个体转入Step10,否则转入下一步。
Step6: 对训练后的网络参数重新编码,产生新的父代个体。
Step7: 解码及适应度与浓度计算,按照式(9)进行父代个体的选择。
Step8: 父代群体的交叉与变异操作,产生子代。交叉及变异概率按照式(10)及式(11)计算。
Step9: 将式(7)、式(8)产生的子代个体进行解码及适应度评价,如果存在满意个体转入下一步,否则转入Step5。
Step10: 将解码最好的个体进行BP训练,训练次数可以适当提高(1000~5000)以得到更优的解,输出最终参数并建立模型。
Step11: 将待评价对象根据指标类型进行一致化及无量纲化处理,并将归一化后的样本序列r′代入训练得到网络,得到评价值。在归一化中,为保证被评价对象水平与相应标准的一致性,公式中的xmax、xmin为训练值中相应指标的最大值、最小值;为剔除异常值的影响-r′ik的最大值为1,最小值为0。
3 模型实证
由于样本数量对于神经网络模型的可学习姓有较大的影响,学习样本不充分就会出现过学习,导致模型的泛化能力低,只有样本无限增加才能使学习的结果趋于期望风险最小。为了获得尽可能多的学习样本,实证应用以企业绩效的评价为例,通过按规则产生的随机数据样本进行学习与检验,以保证评价的客观性。
3.1 模型应用实例
①指标体系。
评价指标选取参考财政部等五部委2002年颁布的《企业效绩评价操作细则(修订)》中的指标体系并结合目前我国上市公司特点及指标计算的可获得性及分析的具体需要等因索,从盈利能力、资产质量状况、债务风险状况和经营增长状况等4个方面,选择13个效益指标及1个成本指标进行分析,主要反映企业一定经营期间的投入产出水平和盈利质量,企业的经营增长水平、资本增值状况及发展后劲,企业所占用经济资源的利用效率、资产管理水平与资产的安全性,企业的债务负担水平、偿债能力及其面临的债务风险等情况,具体指标如表1所示。
②研究数据。
根据国务院国资委统计评价局每年斥算制定的年度企业绩效评价标准值,并将其分为优秀值、良好值、平均值、较低值及较差值5类。考虑到企业绩效的指标实际值将会低于或高于以上5类值的具体情况,将企业可能的实际绩效值分为6级,即Ⅰ级(大于优秀值)、Ⅱ级(处于良好值与优秀值间)、Ⅲ级(处于平均值与良好值间)、Ⅳ级(处于较低值与平均值间)、Ⅴ级(处于较差值与较低值间)级及Ⅵ级(低于较差值),在每级内再分为3等,则绩效水平共分成18个等级,每个等级均匀的赋予一个期望评价值,具体的标准及相应的评价值如表2所示。
研究时,每个等级内随机分别生成55组及2组数据,就可以得到990组学习数据及36组检验数据。为使评价符合实际规律,样本数据在学习与检验前均进行随机排序。
③网络结构及计算参数的确定。
经过训练得到网络的结构为14-21-1,遗传种群的规模M=30,个体适应度概率与个体浓度概率的调节系数α=0.70、自适应的交叉概率参数k1=0.9、变异概率参数k2=0.1。
3.2 结果分析
①模型的学习精度。
经过学习训练,最终的模型中有585组数据的绝对误差小于0.005(即等级间差值的10%),占数据总量的59.09%,883组数据的绝对误差小于0.01(即等级差值的20%),占数据总量的89.19%,具有较高的区分度;考虑到在网络结构为14-21-1时,模型共有待优化参数357个,而限制条件有990个,决定了有一部分样本无法达到理想的最优解。所以,该模型满足精度要求。
②检验评价与结果比较。
对36组按规则生成的随机数据进行检验评价,并将结果与采用基于GA算法及基于BP算法的小波神经网络模型的评价结果进行比较,结果如图2所示。
从图2可以看出,三种算法的区分度均能满足评价的要求,但从绝对误差与相对误差(以评价等级的差值0.05作为比较基数)来看,IGA-BP算法相比较基于GA算法及基于BP算法,精度还是有较大的提高,详见表3所示。
注:为消除年度对指标标准值的影响,上表数值根据2005~2007年的建筑企业平均绩效标准值计算获得。
4 结论
①IGA-BP算法的小波神经网络模型充分利用了遗传算法的全局寻优及小波网络算法的局部搜索能力。通过引入免疫算子保证遗传算法个体的多样性提高全局搜索能力,并将BP算法嵌入其中,利用BP算法对遗传算法定位的解空间进行局部的同步搜索,应用结果表明改进后的算法优化的精度有较大的提高。
②小波神经网络模型的学习精度受样本数量的影响较大,考虑到样本的可获得性及客观性,本文以评价为例进行研究,按照等级随机生成多组数据并将数据随机排序,保证了模型的可靠性,证明该方法能够增加模型的泛化能力。
③在满足数据数量要求的前提下,该方法可以进行预测应用。
软件安全中混合加密算法 篇2
目前,根据不同软件系统所应用的领域,比较常见的加密算法有DES加密算法、RSA加密算法、Base64加密算法和维热纳尔加密算法等。
针对不同算法的各自特点,本文首先自定义一种简单的初始加密算法,再对维热纳尔加密算法进行了优化改进,最后结合Base64加密算法共同组成混合加密算法,在很大程度上提高了加密算法的安全性。
2 基础加密算法
2.1 初始加密算法
初始加密算法是根据明文信息中的字符组成,再借助字符的ASCII码,进行相应的变换运算,从而使原有的真实信息进行伪装,避免被轻易的破解,提高了系统加密保护的安全系数。
在一般的软件系统加密过程中,组成明文信息的字符一般可以分为大写英文字母、小写英文字母、阿拉伯数字和其他特殊字符等四部分。
因此,在定义初始加密算法时,需要根据不同种类的字符进行一定的变换运算处理。
具体如下:第一类变换:明文信息的字符是英文字母时,明文在[A,M]范围内,密文为明文的ASCII码值加45;明文在[N,Z]范围内,密文为其ASCII码值加19;明文在[a,m]范围内,密文为其ASCII码值减19;明文在[n,z]范围内,密文为其ASCII码值减45。
第二类变换:明文信息的字符是阿拉伯数字时,明文在[0,4]范围内,密文等于明文乘以2再加1;明文在[5,9]范围内,密文等于明文乘以2再减10。
第三类:当明文信息是其他特殊字符时,密文与明文相同。
2.2 Base64加密算法
Base64加密算法主要的考虑了三个问题,第一为是否加密;第二为加密算法复杂程度和效率;第三为如何处理传输。
加密是必须的,但是加密的主要目的不是让用户发送非常安全的Email。
而是要达到一眼望去完全看不出内容就行。
基于这个目的加密算法,其复杂程度和效率也就不能太大或太低。
2.3 改进的维热纳尔加密算法
维热纳尔密码是一个非常著名的多码加密法,主要是通过采用定义好的维热纳尔方阵,以及自定义的密钥对明文信息进行加密。
以前对于维热纳尔方阵的定义,是通过以二十六个大写英文字母为依据,依次循环不断改变排列顺序,组成26×26级的方阵。
为了提高此算法的复杂度,同时提高保密性能,本文在二十六个大写英文字母的基础之上,再将十位阿拉伯数字随机插入到英文字母序列中,最终构建成36×36级的改进维热纳尔方阵。
在维热纳尔加密算法中,除了维热纳尔方阵之外,还需要明文字符集和密钥。
明文字符集主要是用来记录组成维热纳尔方阵所需要的字符。
密钥是用来在对明文信息加密过程中,指定字符所对应的加密字符。
因此,在改进的维热纳尔加密算法中,改进维热纳尔方阵、明文字符集和密钥,分别记为A、M和K。
改进微热纳尔方阵的明文字符集M定义为:
M={A,B,9,C,8,D,E,7,F,6,G,H,5,I,4,J,K,3,L,2,M,N,1,O,P,0,Q,R,S,T,U,V,W,X,Z}
密钥K定义为:
K={9,D,7,F,6,I,B,X,0,K,P}
因此,针对上述定义的密钥K,对明文信息字符串“HISENSE”进行加密变换,得到的密文是“ILY4UD7K49G”。
3 混合加密算法的设计
混合加密算法是在上述基础加密算法的基础上,由初始加密算法、改进优化的维热纳尔加密算法以及Base64加密算法共同组成的,并且其实现的过程必须按照固定的顺序依次进行,即先使用自己定义的初始加密算法,再使用改进优化的维热纳尔加密算法,最后使用Base64加密算法。
以明文信息字符串“chongq”为例,应用混合加密算法进行加密处理,具体的实现步骤如下:
第一步:字符串“chongq”经过初始加密算法之后,得到的加密字符串为“PUBATD”。
第二步:将改进优化的维热纳尔加密算法中的所使用的密钥K设定为:K={9,D,7,F,6,I}。
利用密钥K对字符串“PUBATD”继续进行加密处理,得出的加密信息字符串为“QZF7B3”。
第三步:使用Base64加密算法继续对字符串“QZF7B3”进行加密换算,得到加密字符串为“UVpGN0Iz”。
在计算机网络信息飞速发展的时代,信息加密算法已经成为研究软件安全的一个重要领域,取得了大量的研究成果。
本文中所设计的混合加密算法,是由三种加密算法组成的,也可以在此基础之上,再增加几种著名的加密算法或自己设计的新算法,只有跟随时代发展而同步进步的技术才有更广阔的的应用空间和更长的生命周期。
[参考文献]
[1]何茗.加密解密算法的实现及改进[J].西南民族大学学报(自然科学版)..1.
[2]徐荣峰.加密算法及其应用研究[D].西北工业大学..
[3]刘玉珍,王丽娜,傅建明,等,译.密码编码学与网络安全原理与实践[M].第三版,北京:电子出版社..
[4]佟晓筠,杜宇,等.基于软件安全混合加密技术的研究[J].计算机工程. 2004.12.
混合加密算法在物联网信息安全传输系统中的应用【2】
[摘 要]混合密码技术是一种新兴的密码技术,兼顾了对称密钥和非对称密钥的优点,表现除较高强度和速度,确保了信息传输的完整性、保密性、不可否认性。
随着信息产业的发展,传统的交流个体人、机器之间的通信已经不能满足日益发展的应用要求,用户呼唤一种人与各种事物间的,或是事物与事物之间的信息交流。
需求的迫切及计算机、网络技术的发展,促进物联网技术的诞生,该技术开启了人类社会信息化进程的新篇章。
[关键词]混合密码技术 物联网 信息安全
从体系架构上看,物联网分为三层。
其中,感知层存在安全性威胁,因为不论是普通节点还是汇聚节点都容易收到攻击,比如拒绝服务攻击,或是非法控制和破坏[I]。
试想一下,假设我们在系统的感知节点没有采取任何安全措施或安全防护不够全面的话 ,并且所感知的信息还涉及国家、军队的重要设施的敏感信息,一旦被非法的第三方获取,其损失是不可估量和弥补的。
通过分析我们得出,在感知节点可以采用硬件加密芯片、公钥基础设PKI和密码技术等安全技术手段来保证节点收集信息的安全三要素。
一、混合密码技术在物联网信息安全传输系统中的设计
按照物联网的三层架构设计,原始数据信息通过感知设备被采集,转发到采集终端,再进入安全系统进行敏感信息处理。
信息安全保密系统首先对转发过来的信息进行隔离处理后进入加密模块处理。
数据通过智能通信接口模块转发至网络层,再到应用层的智能通信接口模块,最终数据进入隔离、解密后被服务器接收。
物联网信息安全传输系统主要包括信息采集收发子系统、智能通信接口子系统、信息安全保密子系统。
其中信息安全保密子系统用于保证感知信息的传输安全;主要用于信息传输信道的选择和信息收发等。
主要包含由内、外网处理单元、网络隔离模块、信息加解密模块、身份认证模块。
二、 模型的`体系结构
基于物联网的信息安全传输系统中,由服务器、安全传输接口、单双向隔离通道、客户端组成的安全保密子系统。
服务器负责算法管理和密钥管理 ;数据传输接口和单向双向隔离通道负责加密数据发送的管理 ;客户端负责解密文件、传送公钥和更改密码。
模型的体系结构图如下:
三、混合密码技术在物联网信息安全传输系统中的应用
在实际的物联网通信系统中, 除考虑保密系统的安全性外,加解密速率、加密灵活性等因素。
部分物联网的信息安全传输系统采用硬件加密技术,虽说一次一密保证了信息的安全,但是额外的设备费用和硬件较高的故障率同时也给系统带来了其他的安全问题。
在对称加密算法中,公开密钥负责数字签名与密钥管理,私有密钥负责明文加密。
前面我们已经分析了AES和ECC算法, 在数字签名和密钥管理方面ECC 算法能够轻松的实现;而对于在较长明文加密中,AES 算法能提供更快的加密速度。
用MD5 算法辅助,因此综合运用 ECC算法和 AES 算法,再辅助于MD5算法就构成了本模型中混合加密算法的方案。
⑴密钥的产生
G为Ep(a,b)椭圆曲线上选的一个基点,其阶数为n(n是大素数 ),并且G(x,y)是公开的。
随机地确定一个整数(区间为 [1,n-1] ),k做为私有密钥,并计算 K=kG,K为公开密钥[5]。
⑵加密和解密
公钥加密:设 Ke 为 AES 的初始密钥,发送方在r上,r ∈ {1,2,…,n-1}取一随机数,计算 u=rKP(KP 为 B 的公钥 ),R1=rG,rG(x1,y1),v=x1Ke,可以得到(u,v) ,发送给接收方。
至此实现对AES 算法密钥加密。
私钥解密:Ks 为接收方的私钥。
用私钥计算 R1=Ks-1u,得到 Ke=x1-1v。
⑶签名及认证
选取一个公开消息摘要函数,用MD5算法计算消息摘要 H(m)。
生成签名:发送方在区间{1,2,…,n-1)上,取L随机数。
计算R2=LG,LG (x2,y2),e=x2H(m),k1=L+eKS,w=k1G,可以得到(w,e) ,作为发送方的签名消息。
身份认证 :计算 R=w-eKeP=(x1,yr),则使 e=xrH(m)成立就是有效的签名,相反为无效的签名。
总之,混合密码算法结合了对称密钥和非对称密钥的优点,更易于加密和密钥分配,结合了AES算法和 ECC算法的混合加密算法具有易于理解和实现的优点,同时又兼具安全性高的优势。
在基于物联网的信息安全传输系统中,对数据信息来源的真实性进行鉴别,有效信息传输安全性的防护,从而保证系统资源的保密性、完整性与不可抵赖性等的基本安全属性要求。
混合密码算法集合了非对称密钥和对称密钥算法的特点与一体,具有运算速度快,安全性高和存储空间小的优势,更适合于物联网这样的一些受限环境中。
参考文献:
[1]苏逸.物联网发展存在的问题及前景[J].才智,2011,(22):76-77.
[2]黄河明.数据加密技术及其在网络安全传输中的应用[D].厦门大学,.05.
IGA-BP混合算法 篇3
关键词:软件容错;majority;median;表决;算法
中图分类号:TP3文献标识码:A文章编号:1007-9599 (2011) 06-0000-02
Hybrid Voting Algorithm Based on Majority and Median Voting Algorithm
Wang Yu
(School of Foreign Languages,Hunan University of Technology,Zhuzhou412008,China)
Abstract:In this paper,and the median combined with majority voting algorithm,the problem is well improved:the first use of majority voting algorithm to work,when there can not vote on the situation,dispersion calculations,if safety is less than a set threshold,Median voting algorithm is used to deal with this situation,if greater than the safety threshold,the output signal of a no vote.The final simulation shows:with majority voting system and the median is a feasible method to improve the voting system output accuracy;error rate although slightly increased,but the majority can not be output to improve the situation,while a certain degree of accuracy improved.The proposed voting algorithm can be applied to the need to improve output accuracy and can be appropriate to reduce the security applications,test results show that for continuous signals and discrete signals have good results.
Keywords:Software fault tolerance;Majority;Median;Voting;Algorithm
表决技术应用在很多领域中:表决系统可以结合分类器而广泛的应用于模式识别领域中。当然还有软件系统中通过容错配合多个专家系统进行共同协作解决问题,以提高可靠性。表决系统可用在分布式系统的人工排除问题中,比如,当集群工作站在因为网络问题等断开联系时来控制升级过程;
表决技术中具有安全性的典型代表就是majority表决,在n个模块中,有超过一半以上模块的数据结果相同,则输出较多模块都输出的结果。当少于一半的模块有一致结果,则输出一个无法表决的安全信号。
在需要实现安全性的应用中,majority是首选的安全表决机制,由于输出率较低,所以对majority进行修改。本文特点:使用majority的安全性来进行表决,对majority无法确定结果是正确或者错误的情况,使用median表决算法,这样能够通过median表决算法的强大选择能力进行数据输出,提高整个系统的有效性。
本文包括以下内容:首先介绍混合表决系统,之后在实验中与其他表决方法进行比较;最后再对本文中的表决系统进行性能评价及得出结论。主要评价的方面有:在测试中,表决的输出率及准确率。为了检验混合表决系统是否具有更优良的性能,我们进行了测试和测试的数据统计分析,从结果来看,相对于基本的majority模型有较好改善。
一、相关算法
应用算法是依赖于系统的设计,由于表决算法是基于诸如NMR/NVP[24]等系统,所以应用表决算法的过程是:首先建立NMR/NVP系统,系统中处理同一数据的模块共由n种不同实现方法完成。当输入数据后,n个模块分别处理,得到n个结果,交由表决算法处理。
(一)Majority算法
majority算法基于如下选择方法:对于某一个具体计算,如果有超过一半的模块有同一个输出数值,则输出该数值,否则输出无法表决的信号。可见该算法对于数据输出有安全性,即使用无法表决信号来通知系统应该进行暂停或者其他处理。
(二)median算法
majority算法基于如下选择方法:在奇数个模块组成的系统中,对模块输出的数据进行排序(通常是实数排序),选择处于正中间位置的那个数据作为整体的输出(如,对7个数排序后取第4个为输出)。可见该算法有百分之百的输出结果的能力,但是没有对系统通知暂停的信号。
二、混合表决
(一)结合majority和median
对于majority和median表决的特点经过分析后,可以发现两者的特性互有不同,但也说明两者特性具有互补性。本文中介绍的算法流程是,首先使用majority进行表决,之后对majority无法解决的数据进一步处理:对数据进行排序,如果最大和最小的数据间距超过某个范围,则输出无法表决,即安全信号,否则使用median处理majority的无法表决情况。
(二)算法流程
在实际使用majority表决算法时,通常使用一个边界极限的概念来确定数据间的一致程度:如果两个数据的距离在某个极限内,则认为两个数据是同一个数据。使用极限来确定数据的一致在数模、模数转换中很常见。
算法中涉及系统参数有:
t:应用majority时判断两个数据一致的极限
thres:MM的算法极限参数,数据离散度大于此参数,则输出安全信号,否则使用median进行表决
算法使用如下流程:
第一步:用V={v1 v2 v3 …vn}表示N个变量结果的集合
第二步:对V进行升序排序,排序后的集合为Vasc={va1 va2 va3 …van}
第三步:建立距离集合D,D={d1 d2 d3 …dn-1},di=|vai+1–vai|,i=1,…,n-1.
第四步:如果D中至少有一个数据满足dj 第五步:如果D中没有数据满足dj (三)算法表决举例 为了更好描述算法的机制,在表1中用数据示例说明,数据1和数据2及数据3都是由原始信号混合噪声后的待表决数据集,以模拟3模块冗余(TMR)情况。设定majority的极限为0.5,选用median的极限为2。在表一中,可以看到原始信号为2.0时,通过混合表决算法可以得到正确输出,而原始信号为1.5时,混合表决也仍能保持安全性,输出一个无法表决的信号。 三、结论 在连续和离散信号的测试中,结果表明,本文提出的MM表决算法相对于单纯的majority和median表决算法都有一定优势:相对于majority表决算法,MM能够提高输出率,这在对于安全性要求不是极其严格,并且需要较高输出率的情况是非常适合的,另外相对于median表决算法(median表决算法在测试中表现出与weighted value表决算法相似的性能),MM能够表现出较高的正确率和median所不具有的安全性,MM表现了majority和median的折中,即能够一定程度上保证安全性,又能输出较多结果。针对不同的系统和具体环境分析,若适合应用MM表决算法,则将比majority、median、weighted value等表决算法得到更好的输出。 参考文献: [1]M. Ahammad and M.Ammar."Performance Characterization of Quorum-Consensus Algorithms for Replicated Data"Proceedings of the 7th Symposium on Reliability in Distributed Software and Database Systems,1987:161-167 [2]Sherif Yacoub,Xiaofan Lin,S simske,J Burns."Automating the Analysis of voting Systems".Proceedings of the 14th International Symposium on Software Reliability Engineering.IEEE,2003:1071-9458/3 [3]F.Di Giandomenico and L.Strigini."Adjudicators for Diverse-Redundant Components".9th Symposium on Reliable Distributed Systems.Huntsville.Alabama.IEEE,1990:114-123 [4]T.K.Ho,J.J.Hull,and S.N. Srihari."Decision Combination in Multiple Classifier Systems".IEEE Transactions on PAMI,1994,16(1):66-75 [5]Li Shao-ming,Yin Qian,Guo Ping,Lyu Michael R."A Hierarchical Mixture of Software Reliability Model for Prediction".Applied Mathematics and Computation,2007,vol.185:1120-1130 [6]尹乾,李邵明,郭平.“软件可靠性分层模型的案例研究”.软件技术进展.梅宏,刘超.北京:机械工业出版社,2004:242-246 [作者简介]王昱(1981-),男,硕士研究生,湖南工业大学助教,研究方向:计算机。