《2022年混合二进制粒子群遗传算法的测试优化选择分析研究 .pdf》由会员分享，可在线阅读，更多相关《2022年混合二进制粒子群遗传算法的测试优化选择分析研究 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 / 7 基于混合二进制粒子群-遗传算法的测试优化选择研究*陈希祥，邱静，刘冠军 Abstract ：Test selection is one of the combinatorial optimization problems. Based on deep analysis of objectives and constraints of test selection, a mathematical model is founded, and a hybrid algorithm based on BPSO and GA is proposed to solve the minimum
2、complete test set that satisfies the testability requirements. Through introducing genetic operators into the BPSO, the algorithm not only avoids the local optimization and premature convergence, but also improves the searching efficiency. Experiments show that the proposed algorithm is fast and eff
3、ective to achieve global optimal solution of test optimization selection problems.Key words ：design for testability 。 test selection。 GA 。 BPSO1引言随着武器装备系统性能的提高和复杂性的日益增加，对其进行故障检测与诊断的难度越来越大，开展测试性设计已是当务之急1。系统测试性方案优化设计是测试性设计的重要组成部分。作为测试性方案的重要内容之一，测试优化选择1-2是测试性方案优化工作的开始，将关系到整个测试性设计工作的好坏，这一问题越来越受到人们的关注。测试
4、选择的目的在于：在系统所有可能的测试配置中，寻找满足系统测试性参数指标要求的最佳测试组合，使得测试代价最小。从数学上讲，测试选择问题是一个组合优化问题，可用集合覆盖模型进行描述。集合覆盖问题是一个NP 完全问题，目前许多文献都提出了相应的求解算法2-7，其中遗传算法genetic algorithm，GA）和粒子群算法 particle swarm optimization ，PSO）都取得了一定的效果，但由于问题本身固有的难度，求解效率与准确性都不尽如人意。尤其随着装备系统复杂精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 7 页2
5、/ 7 程度的提高，集合规模的增大，需要寻求新的有效算法以获得最优解。无免费午餐定理8说明，对于所有优化问题集，任意两种不同的优化算法平均优化性能是相同的。也就是说，没有一种优化算法在所有性能上，包括计算效率、全局搜索性、通用性和简洁性等方面都占有优势。因此本文针对遗传算法和粒子群算法的不足，将遗传算法和二进制粒子群算法binary version of PSO，BPSO）结合起来，提出一种用于求解测试选择的混合二进制粒子群-遗传算法 hybrid BPSO and GA，HBPSOGA）。实验证明该算法能够有效、快速地收敛到全局最优解。2 问题的描述与建模2.1故障 -测试相关性矩阵对系统进
6、行FMECA 分析，获得系统所有的潜在故障集，令表示故障的故障率，定义故障率矢量。可供选择的测试构成n 维备选测试集，其测试代价矢量，此处的测试代价是一个广义的概念，指测试过程中所有消耗性属性的综合。通过可达性分析 因此对于检测率不小于给定的的要求，可以形式化描述为：。关键故障检测率：设能检测的所有关键故障构成的集合为，则有：关键故障检测率可表示为：当考虑故障率时，故障检测率可表示为：(2 因此关键故障的检测要求可以形式化描述为：故障隔离率一般定义为：在规定的时间内，由测试系统正确隔离到不大于规定的可更换单元数的总故障率与同一时间内检测到的总故障率之比。由于存在一个测试可以覆盖多个故障以及一个
7、故障被多个测试观测到的情况，因此故障隔离问题要远比故障检测问题复杂。若故障 fi和 fj可以被隔离，则必须满足矩阵D 第 i 行 Di与收稿日期： 2008-12Received Date：2008-12 *基金工程：国家“十一五”部委预研工程资助精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 7 页3 / 7 其第 j 行 Dj相异。设 Tfi为能检测故障fi的所有测试组成的集合，设为能检测故障fj的所有测试组成的集合，那么fi能被隔离的条件是：。其中 “” 表示集合与或，当两个集合不同时，结果为 1。反之，故障fi和故障 fj位于同
8、一模糊组的条件是：。可以定义另一个运算符“ ” ，当时，表示故障 fi和 fj属于同一模糊组。设 Ts能隔离的所有故障构成的集合为Fl，若给定故障隔离模糊度L，则有：由此可以获得故障隔离率形式化要求：当考虑故障率时，故障检测率可表示为：(3 因此对于满足给定模糊度为L 下隔离率不小于FIR的要求，可以形式化描述为：2.4优化模型综合前面分析得到的约束条件和目标函数可以得到测试优化选择模型如下：(4 3基于混合 BPSO-GA 的测试优化选择3.1标准遗传算法 SGA）受生物进化机制启发，Holland 于 20 世纪 60 年代提出一种计算模型，称之为遗传算法9。经过多年的发展，遗传算法理论逐
9、渐成熟，已经被成功地用于优化设计、模糊逻辑控制、神经网络、专家系统等领域10。对于一个特定的问题，遗传算法从代表问题可能潜在解集的一个种群开始，而一个种群由经过基因编码的一定规模的个体组成。每个个体实际上是染色带有特征的实体，表示一个可行解。首先需要对种群进行初始化，按照适者生存和优胜劣汰的竞争原理。在每一代，采纳了自然进化模型，根据问题域个体的适应度大小选择优良个体，并借助自然遗传学的遗传算子进行组合交叉和变异，逐代进化以产生代表新的解集的种群。周而复始，反复迭代，直到满足终止准则，最后将运算结果作为问题最优解。3.2二进制粒子群算法 BPSO）粒子群算法11是一个进化计算模型，受人工生命启
10、发，1995 年 Kennedy 和 Eberhart 模仿生物种群 鸟群和鱼群）觅食的行为模式，提出了粒子群算法。同遗传算法一样，粒子群优化算法是基于群体的演化算法。 PSO求解优化问题时，问题的解对应于维搜索 空 间 的 一 个 粒 子 。 每 个 粒 子 j 都 有 自 己 的 位 置和速度决定粒子飞行的方向和距离），还有一个由目标函数决定的适应度函数。各个粒子记忆、追随当前的最优粒子，在解空间中搜索。每次迭代的过程不是完全随机的，粒子通过跟踪两个 “ 极值 ” 来不断更新自己：第一个就是粒子本身所找到的最优解，叫做个体极值点PBest）；另一极值点是 整 个 种 群 目 前 找 到 的
11、 最 优 解 ， 称 为 全 局 极 值 点 (6 式中：和分别为粒子在第次迭代时在第维 空 间 的 速 度 和 位 置 ；为 惯 性 权 重 ，为当前迭代次数，为最大迭代次数）；c1、 c2为加速因子，都是正实数； r1k、r2k为随机产生的一个介于之间的正实数；为粒子 j 至第 k 次迭代为止在第m 维空间找到的个体最优值所在的位置；为粒子j 至第k 次迭代为止在第m 维空间找到的群体最优值所在的位置。该算法结构非常简单，参数少，只需简单的数学运算便可以实现，自出现以来受到了广泛的关注12-13。然而早期的粒子群算法主要用于实数空间问题的求解，已成功应用于求解连续域问题。为了解决实际工程中
12、广泛存在的离散问题，Kennedy 和 Eberhart 于1997 年又提出了粒子群算法的二进制版本 式 中 ：为之间随机产生的一个正实数。3.3混合二进制粒子群 -遗传算法 式中： C、均为常数。Step3：计算中所有个体的适应度，并对其进行评价，采用轮盘赌选择方法挑选出染色体对，以概率两两进行交叉操作，得到种群；Step4：对中的个体以概率进行变异操作，得到种群；Step5：对中的个体进行适应度评估，得到个体最优位置和全局最优位置，并按照式 (5和式(7分别对种群速度和位置进行更新，产生下一代种群；Step6：若迭代次数已经达到最大迭代次数则算法结束，转 Step7；否则转 Step3；
13、Step7：输出最优个体作为问题最优解。4仿真与验证案例 1：文献21中给出了反坦克导弹发射器武器系统故障 -测试相关性矩阵。该系统存在26 个故障源 含无故障状态），系统初始设计的测试工程共有20个。在该系统中，存在6 个模糊组。在备选测试集合下，当不考虑故障率时，该系统的故障检测率为96%，考虑故障率时，其故障检测率为99.45%。基于篇幅所限，测试性指标要求及基本数据如下：故障检测率和故障隔离率要求均为95%；每个测试的代价相同，且均为1 个标准单位；故障率 1-14. 3PATTIPATI K R, ALEXANDRIDIS M. Application of heuristic se
14、arch and information theory to sequential fault diagnosisJ. IEEE Transactions on System, Man, And Cybernetics, 1990,20(4:872-887. 4钱彦岭 . 测试性建模技术及其应用研究D. 长沙 :国防科技大学 , 2002.QIAN Y L. Research on testability modeling technology and its applicationD. Changsha: NationalUniversity of Defence Technology, 2
15、002. 5苏永定 . 机电产品测试性辅助分析与决策相关技术研究D. 长沙 :国防科技大学, 2004.SU Y D. Research on relevant technology in analysis and decision at the testability aid design for mechatronics equipmentsD. Changsha:National University of Defence Technology, 2004. 6蒋荣华 ,王厚军 ,龙兵 .基于离散粒子群算法的测试选择J.电子测量与仪器学报,2008,22(2:11-15. JIANG R
16、 H, WANG H J, LONG B. Test selection based on binary particle swarm optimizationJ. Journal of Electronic Measurement and Instrument, 2008,22(2:11-15. 7连光耀 .基于信息模型的装备测试性设计与分析方法研究D. 石家庄 :军械工程学院,2007.LIAN G Y. Research on design and analysis methods for testability of equipment based on information mod
17、elD. Shijiazhuang:OrdnanceEngineeringCollege, 2007. 8WOLPERT D H, MACREADY W G. No free lunch theorems for optimizationJ. IEEE Transactions on Evolutionary Computation. 1997,1(1:67-82. 9HOLLAND J H. Adaption in nature and artificial systemM. Ann Arbor:The University of Michigan Press, 1975. 10MAN K
18、F, TANG K S and WONG S K. Genetic algorithms: Concepts and applicationsJ. IEEE Transactions on Industrial Electronics, 1996,43:519-532. 11KENNEDY J, EBERHART R C. Particle swarm optimizationC. Proceedings of the IEEE International Conference on Neural Networks, 1995:1942-1948. 12周驰 ,高亮 ,高海兵 .基于粒子群优化
19、算法的约束布局优化J. 控制与决策 ,2005,20(1:36-40.ZHOU CH, GAO L, GAO H B. Particle swarm optimization based algorithm for constrained layout optimizationJ. Control and Decision, 2005,20(1:36-40. 13张利彪 ,周春光 ,马铭 ,等.基于粒子群算法求解多目标优化 问 题 J. 计 算 机 研 究 与 发 展 ,2004,41(7:1286-1291.ZHANG L B, ZHOU CH G, MA M, et al. Solutio
20、ns of multi-objective optimization problems based on particle 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 7 页7 / 7 swarm optimizationJ. Journal of Computer Research and Development, 2004,41(7:1286-1291. 14KENNEDY J, EBERHART R C. A discrete binary version of particle swarm optimizationC. Pr
21、oceedings of the World Multiconference on Systemics, Cybernetics and InformaticsC. Piscataway, NJ: IEEEServiceCenter, 1997: 4104-4109. 15叶东毅 ,廖建坤 .基于二进制粒子群优化的一个最小属性约 简 算法 J. 模式识别与人工智能, 2007,20(3:295-300.YE D Y, LIAO J K. Minimum attribute reduction algorithm based on binary particle swarm optimizati
22、onJ. PR&AI, 2007,20(3:295-300. 16黄艳新 ,周春光 ,邹淑雪 ,等 .一种求解类覆盖问题的混合算 法 J. 软 件 学 报 ,2005,16(4:513-522.HUANG Y X, ZHOU CH G, ZOU SH X, et al. A hybrid algorithm on class cover problemsJ. Journal of Software, 2005,16(4:513-522. 17马慧民 ,叶春明 ,柳毅 .基于改进粒子群算法的生产批量计划问题研究 J. 计 算 机 集 成 制 造 系 统 ,2006(9:75- 78,147.MA
23、 H M, YE CH M, LIU Y. Improved particle swarm optimization algorithm for dynamic lot-sizing problemJ. Computer Integrated Manufacturing Systems, 2006(9:75- 78,147. 18AMONCHANCHAIGUL T, KREESURADEJ W. Input selection using binary particle swarm optimizationC. International Conference on Computational
24、 Intelligence for Modeling Control and Automation, and International Conference on Intelligent Agents, Web Technologies and Internet Conference(CIMCA- IAWTIC06, 2006.19SADRI J, SUEN C Y. A genetic binary particle swarm optimizationC. 2006 IEEE Congress on Evolutionary Computation Sheraton Vancouver
25、Wall Centre Hotel, Vancouver, BC, Canada, July 16-21, 2006:656-663. 20AFSHINMANESH F, MARANDI A, RAHIMI-KIAN A. A novel binary particle swarm optimization method using systemC. EUROCON 2005: Serbia & November 22-24, 2005:217-220. 21SIMPSON W R, SHEPPARD J W. System test and diagnosisM. USA: Kluwer A
26、cademic Publisher, 1994. 作者简介陈希祥 ，国防科技大学博士研究生，主要从事系统测试性设计、分析与评估技术等研究。E-mail: Chen_X Chen Xixiang now is a doctoral candidate in College of Mechatronics Engineering and Automation, National University of Defense Technology. His current research interests include system testability analysis, design and evaluation. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 7 页