下载  >  课程资源  >  C/C++  > 一种求解极小诊断的遗传模拟退火算法

一种求解极小诊断的遗传模拟退火算法 评分:

一种求解极小诊断的遗传模拟退火算法,将遗传算法与模拟退火结合的一种算法
黄杰等:一种求解极小诊断的遗传模拟退火算法 1347 子集A不包含构件j同样,定义一个0/1向量x=(x1x2…xn)∈R,当x,=1时表示构件j属于击中集x,否则表示 构件j不属于击中集 定理2.x是{A|i=1.m}的击中集,当且仅当Ax≥b,其中b=(1,1,1)∈R 定义R上的范数,x=∑|x)1.定义R上的范数,4:=∑∑lan 由定理2不难证明 4×x124x2l2|b21:=m 由式(1)知 lxm/All (2) 不等式(2)指岀了极小击中集基数的下限这个下限对于我们快速求解极小诊断十分重要根据上述分析我 们给岀求解极小诊断的遗传模拟退火算法. 用二值向量代表集合,则击中集的染色体编码为(x1,x2,…,xn)的形式,其中x1=0或1.下面给出遗传算法部 分的算子 交叉算子对于染色体(x1,x2…,xn)和(y,y2,…,yn),随机地选取一个整数0<r≤m,它们产生的后代为 )和(v1y2,ynx+1,x 变异算子对于染色体(x1,x2,…,xn),随机地选取一个整数0<r≤m,变异后的个体为(x1…,x2…,xn),其中 反转算子染色体(x1,x2…,xn)反转后的染色体为(xn,xn1…,x1) 适应度函数(x)=Ax1x,适应度函数f(x)反映了当个体x击中的冲突集越多和x的范数越小时,它 的适应度越强的特性.不难看出,这种适应度的评价是符合事实,并且是合理的 选择算子同时使用最优保存策略和赌轮选择法10,从n个中间群体中选择适应度最优的1/5个体复制到下 代中其余的个体按照P=/∑为选取概率被复制到下一代个体中 为了加快搜索速度和増强算法的局部搜索能力,冋时还需要使用模拟退火算法.将单个个体的能量评估函 数被定义为E(x)=(lrl1-m/A)(x).设初始温度To=xl1同时,求解过程中的集合基数如果不满足不等式(2),我 们就可以认为退火算法中的温度达到冷却状态 下面给出求解极小诊断的遗传模拟退火算法. 算法1. Genetic simulated annealing(GSA) (1)初始化进化计数器 (2)随机产生初始群体P(ω),初始规模为αm/4H(α为大于1的系数). (3)以概率磁进行个体间的交叉操作:P(t)← Crossover[P(t)] (4)以概率戏进行个体变异操作:P"(t)← Mutation[P(t) (5)以概率进行个体反转操作:P"()←- Invertion[P"(t) (6)调用个体模拟退火算法:P"(t)←- Simulated nnealing[P"(t)] (7)通过f(x)=Axlx1评估P"()中个体的适应度 (8)将适应度最优的15个体直接复制到下一代中按照P=/2∑为选取概率选择其余的个体到下 代中,产生下一代P(+1) (9)若连续10代中包含的击中集没有变化,则判断这些击中集是否为极小击中集并输出结果否则转(3) 算法2. Simulated annealing(SA). (1)设置初始温度T。=‖x1和循环计数器t←-0 (2)随机地将向量x中n个为1的位反转,其中n=((x)-m4)/log2(+3),从而产生新个体x (3)计算能量的增量A=E(x)-E(x),若4≤0,则接受新个体否则以概率p=exp(-(E(x)-E(x)/7(x)接受新个体, 如果拒绝新个体,则转(2),重新退火 1348 Journal of software软件学报2004,15(9) (4)若新个体的温度T(x)≤m/41=Tma(x)或者t>g,则算法结束否则t←t+1并转(2) 3算法说明和分析 算法1中使用fx)=Axl/xl1作为适应度评价函数,分子Ax是个体击中冲突集的数目,4x1同f(x)成 正比关系,即在个体包含构件数目一定的情况下,Axl1越大,说明x的适应度越强分母x1同f(x)成反比关 系,反映了在击中的沖突集一定的情况下,个体所代表的集合基数越小,越有可能成为极小集中集的特性.正确 的适应度评价函数使得算法可以准确地把握搜索的方向 在选择算子设计中,算法1同时使用了最优保存策略和赌轮选择法.最优保冇策略使得最好的1/5个体不被 淘汰对于其余的中间个体采用赌轮选择法,这样的选择既不丢失最好的中间个体,同时按比例保留了各个适应 度上的个体,这使得搜索避免陷入局部最优点 尽管算法1具有把握搜索方向好和在一定程度上避免陷入局部最优的特性.但是无论是交叉算子、变异算 子,还是反转算子,都不能使算法快速地向正确的方向收敛.事实上,也很难设计出这样快速收敛的算子因为这 些算子既不知道搜索的方向,也不知道以什么样的速度收敛能够快速地达到目标,同时又不丢失太多正确的解. 算法1(GSA)的第6步使用模拟退火算法使整个算法在搜索粒度上加大以温度的下限7(x)≤m/4为标 准避免不必要的搜索在算法2(SA)的第2步,使用的降温方式为r:(x)=(T(x)=m4)/og2(+3)图1是这 种降温方式在几种不同参数下的折线图 T0=50,Tmin=20 T0=50,Tmin=10 To=50. Tmin=3 Fig. 1 Temperature decreasing curve in variant condition 图1不同情况下的降温曲线 可以看岀,这种降温方式使得个体温度越高降温越快,个体温度越低降温越慢.这样,越是接近目标,搜索粒 度就越是细化通过大量的实验表明在通常情况下,通过15步的退火过程,个体的温度达到或者接近于最低温 度而基本达到冷却状态因此在实际应用中,选择退火的最大步长=15算法2以E(x)=((x)-m/4)(x) 为函数评估新个体的能量这个函数反映了在个体适应度不变情况下,越是接近最低温度,个体的能量就越少, 同时也反映了在个体温度不变情况下,适应度越强,个体能量越低.为了确保正确的搜索方向,避免搜索陷入局 部最优,在个体降温后对其能量进行评估.若个体的能量减少,则直接接受这一事实,这也是我们所期望的.若能 量增加,则以概率p=exp(-(E(x')-E(x)/7(x)接受.如果拒绝能量的增加,则对个体重新进行退火算法要能够以 定的概率接受能量的暂时增加才能避免搜索陷入局部最优.图2是这种降温方式在实际测试中能量的变化折 线图其中初始温度(x)=50,冷却温度为Tn-(x)=10,冲突集的数目为15,3个个体的能量变化和降温折线图 如图2所示图2中实线为能量变化线虚线为温度变化线 正如文献[7中指出,HSee的空间复杂度为O(m"),其中m为冲突集的平均基数,n为系统中的构件总 数BHS-re的空间复杂度为O(2").不难看出,采用GSA的空间复杂度为O(m) 采用GSA算法求解不仅能够发挥遗传算法的优势,把握正确的搜索方向,而且可以发挥模拟退火算法快速 收敛的优势同时,模拟退火算法部分的设计还能够使搜索避免过早地收敛于局部最优状态合理的评估函数以 及算法的各个参数设计极大地提高了算法在实际应用中的效果 黄杰等:一种求解极小诊断的遗传模拟退火算法 1349 Fig 2 Energy and temperature curve of variant individual 图2不同个体的能量和温度曲线 文献[刀中已经将GA算法与HS-tre和 BHS-tree等非遗传算法的性能进行了比较这里,我们通过编写测 试程序,对本文提出的GSA算法和文献[刀]中的GA算法性能作一个比较算法的测试平台为PIV2 GHZ CPU, 512 M DRAM.测试用例中,系统构件的总数为500,冲突集数目从5~100.GSA算法的参数取值为 a=10,B=0.8,x=0.8=0.1,q=15.图3是GA和GSA在各种冲突集数目下击中集的求解时间 从图3中可以看出,尽管在冲突集较少的情况GSA算法比GA算法性能略有差别,但是从冲突集数目大于 35开始,由于GSA算法有较快的收敛速度,求解时间节省了约1/3~1/2. 200 5 一GA GSA 5 15 25 55 65 Number of conflict sets Fig 3 Efficiency comparison between gSa and ga 图3GSA和GA的性能比较 同样是在500个构件的系统中,多次构造20个冲突集和100个冲突集我们分别对GSA和GA的求解精度 进行了测试图4反映了冲突集一定和不同击中集数目情况下,算法的求解精度我们提出的GSA算法不仅在遗 传算法部分保留了各个层次上的个体,而且模拟退火算法部分的设计能够使算法避免陷入局部最优,从而较大 地提高了算法的求解精度.在大多数情况下,GSA算法可以求解出98%极小诊断 Total 20 conflict sets Total 100 conflict sets %0 100卩 100 98 口GA □GA 94 97 日GAS 口GAS 61829437785 61829437785 Number of hit sets Number of hit sets Fig 4 Accuracy comparison between two algorithms 图4两种算法的求解精度比较 4结论 本文将遗传算法和模拟退火算法相结合,提岀一种新颖的GSA求解极小诊断的算法.同时,通过将击中集 1350 Journal of software软件学报2004,15(9) 求解问题映射到0/1整数规划问题,给岀了模拟退火算法的冷却温度.GSA算法使用模拟退火算法达到快速收 敛的目标,在一定程度上较大地改善了原有GA方法的性能同时,GSA算法通过保留不同适应度层次上个体的 多样性,在一定程度上提高了算法的求解精度在降温方式上,个体能够以一定的能量脱离局部最优状态,也使 得算法的求解精度得到了较大的提高.在冲突集大于35以后,GSA较GA算法表现出了很大的性能优势,节省了 约1/3~12的计算时间大多数情况下,GSA算法能够求解出98%~100%的解 References [1 Raymond R. A Theory of diagnosis from first principles. Artificial Intelligence, 1987, 32(1): 5795. [2 Jodan DK, Brian CW. Diagnosing multiple faults. Artificial Intelligence, 1987, 32(1): 97-130 [3 Luan SM, Dai Gz, Chen YD. A logic-based approach to diagnosis. Journal of Guizhou University of Technology(Natural Science Edition), 2002, 31(4): 61-68(in Chinese with English abstract) 4 Peter F, Wolfgang N. a static model-based engine for model-based reasoning. In: Proc. of the 15th Int'l Joint Conf of on Artificial Intelligent Nagoya: Morgan Kaufmann Publishers, 1997.466-473 [5 Junquera BP, Gonzalez CA. Possible conflicts, ARRs and conflicts. In: Proc. of the Int'l Workshop on Principles of Diagnosis Semmering,2002.122-128.http://www.dbai.tuwien.ac.at/user/dx2002/proceedings/dx02final08.pdf [6 Jiang YF, Lin L Computing the minimal hitting sets with binary HS-tree. Journal of Software, 2002, 13(12): 2267-2274(in Chinese withEnglishabstract).http://www.jos.org.cn/1000-9825/13/2267.pdf [7 Lin L, Jiang Y F, Computing minimal hitting sets with genetic algorithm. In: Proc. of the Int'l Workshop on Principles of Diagnosis Semmering,2002.77-80.http://www.dbai.tuwien.ac.at/user/dx2002/proceedings/dx02final25.pdf [8 Li Zs, Jiang YF. A correction and extension to the testing theory for model-based diagnosis. Journal of Software, 2000 11(7): 979-983(in Chinese with English abstract) [9 Fijany A, Vatan F, Barrett A, Mackey R. New approaches for solving the diagnosis problem. IPN Progress Report, 2002. 42149 http://ipnpr.jpl.nasagov/tmo/progressreport/42-149/149k.pdf [10] Shi ZZ. Knowledge Discover. Beijing: Tsinghua University Press, 2002. 265-293(in Chinese) 附中文参考文献 [3]栾尚敏,戴国忠,陈由迪基于逻辑的一种诊断方法贵州工业大学学报(自然科学版,2002,31(4):61~68 [6]姜云飞,林笠用对分HS-树计算最小碰集软件学报2002,13(12):2267-2274.http://www.jos.orgcn/1000-9825/13/2267.pdf [8]李占山,姜云飞.对基于模型诊断测试理论的修正与扩充.软件学报,2000,11(7):979~983 [10]史忠植知识发现北京:清华大学出版社,2002265~293

...展开详情
2011-12-10 上传 大小:472KB
举报 收藏
分享
一种求解极小诊断的遗传模拟退火算法

一种求解极小诊断的遗传模拟退火算法,将遗传算法与模拟退火结合的一种算法

立即下载
Newton迭代法求解极小值点

程序说明详细,适合matlab初学者 %Newton迭代法求解极小值点 0311 %===================================== %定义函数 disp '函数 f(x) 为:' syms x1 x2 f=(x1-2)^4+(x1-2)^2*x2^2+(x2+1)^2 disp '初始点的值:' x0=[1;1] %===================================== %求函数的梯度和海色阵 disp '函数f的梯度:' g=jacobian(f,[x1;x2]) disp '函数f的Hesse矩阵:' G=jacobian([g(1);g(

立即下载
黄金分割法及程序设计求解极小值

运用黄金分割法和简单的Matlab程序求解函数极小值

立即下载
求解极小SMT不可满足子式的宽度优先搜索算法

一篇关于求解极小SMT不可满足子式的宽度优先搜索算法的论文《求解极小SMT不可满足子式的宽度优先搜索算法j》

立即下载
一种求解SAT问题的新方法

一种求解SAT问题的新方法。与大家分享。一种求解SAT问题的新方法。与大家分享。

立即下载
一种求解旅行商问题的新算法

一种求解tsp问题的新算法 希望对大家有所帮助

立即下载
规则迷宫的一种求解思想及算法源码.

规则迷宫的一种求解思想及算法.规则迷宫的一种求解思想及算法.

立即下载
一种求解MSA问题的自适应遗传算法

:多序列比对(MSA)在生物信息学研究中占有重要地位,MSA问题是一个典型的NP问题,遗传算法是求解NP完全问题的一种有效 方法。文章针对MSA问题,提出了一种新型自适应遗传算法,根据群体的多样性自适应调节变异概率,有效消除了算法中的欺骗性条件,使 用突变算子来确保算法的搜索能力。整个算法模拟了自然界进化的周期性,较好的解决了群体的多样性和收敛深度的矛盾。算法的分析和测 试表明,该算法是有效的。

立即下载
一种求解旅行商问题的改进蚁群算法

介绍了一种求解旅行商问题的改进蚁群算法。

立即下载
一种求解无约束优化问题的共轭梯度法

一种求解无约束优化问题的共轭梯度法,对非线性最优接是很好的一宗

立即下载
基本遗传算法—一种求解方程的有效算法

别的地方能够下的,还没看完,希望有用! 基本遗传算法—一种求解方程的有效算法

立即下载
一种求解矩形packing问题的智能枚举算法.pdf

一种求解矩形packing问题的智能枚举算法

立即下载
一种求解高维约束优化问题的γ—PSO算法

一种求解高维约束优化问题的γ—PSO算法 PSO算法,约束优化问题,适应度函数,全局极值,局部极值

立即下载
共轭梯度法求解方程的极小值解.程序

用共轭梯度法求解方程f=x1*x1+x2*x2-x1*x2-10x1-4x2+60的极小值解.

立即下载
关于一种求解复Hermite矩阵特征值的方法的验证

复 Hermite矩阵求特征值和特征向量的问题转化为求解实对称阵的特征值和特征向量

立即下载
一种求解关键路径的新算法——数字信号处理课程论文

通过定义节点编码图概念,提出一种不需要拓扑排序的求解关键路径的新算法。

立即下载
一种求解TSP问题的改进遗传算法源代码+论文

求解TSP问题的一种改进遗传算法,附源代码和论文,研究遗传算法特别有用,代码可直接拿来改进。改进算法有效解决了群体多样性和收敛速度的矛盾。

立即下载
一种求解广义逆的新方法在图像复原中的运用.kdh

一种求解广义逆的新方法在图像复原中的运用.kdh

立即下载
正定稀疏矩阵的一种快速求解方法

关于正定稀疏矩阵的一种快速求解方法。对Cholesky分解的一种优化。具体内容见附件吧。

立即下载
论文研究-一种求解多目标资源受限项目调度的遗传算法.pdf

采用基于非支配性排序的多目标遗传算法—NSGA-Ⅱ,设计了一种求解多模式、多种类资源约束的多目标资源受限项目调度问题的遗传算法,该算法所设计的编码包含两部分,一部分为一个任务链表,另一部分为任务链表中各任务所对应的执行模式组成的模式向量。将所设计的算法用于求解文献中的以项目总工期和资源均衡为目标的农业项目调度问题,结果表明此算法对于求解多目标资源受限项目调度问题是有效的。

立即下载