《基于混合二进制粒子群-遗传算法的 测试优化选择研究》由会员分享，可在线阅读，更多相关《基于混合二进制粒子群-遗传算法的 测试优化选择研究（8页珍藏版）》请在金锄头文库上搜索。
1、基于混合二进制粒子群-遗传算法的 测试优化选择研究摘 要：测试优化选择是一个组合优化问题。通过对测试选择的H标和约束条件进行深入分析建立了其数学模型，并提出了 一种混合粒子群-遗传算法用于求解满足测试性指标要求的故小完备测试集。该算法将遗传算法中的遗传算子引入到二进制粒 子群算法中，既避免陷入局部瑕优和早熟收敛现象，又提高了搜索效率。大量实验证明,对于测试优化选择问题,混合粒子群 遗传算法能够快速有效的获得全局最优解。关键词：测试性设计；测试选择；遗传算法；二进制粒子群算法Optimal test selection based on hybrid BPSO and GAAbstract： T
2、est 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 complete test set that satisfies the testability requir
3、ements. Through introducing genetic operators into the BPSO, the algorithm not only avoids the local optimization and premature convergence, but also improves the searchi ng efficiency. Experiments show that the proposed algorithm is fast and effective to achieve global optimal solution of test opti
4、mization selection problems.Key words： design for testability; test selection; GA; BPSO1引 言随着武器装备系统性能的提高和复杂性的II益增加, 对其进行故障检测与诊断的难度越來越大，开展测试性设 计己是当务Z急。系统测试性方案优化设计是测试性设 计的重要组成部分。作为测试性方案的重要内容之一，测 试优化选择Z是测试性方案优化工作的开始，将关系到 整个测试性设计工作的好坏，这一问题越來越受到人们的 关注。测试选择的的在于：在系统所有可能的测试配置 中，寻找满足系统测试性参数指标要求的最佳测试组合, 使得测试代
5、价最小。从数学上讲，测试选择问题是一个组 合优化问题，可用集合覆盖模型进行描述。集合覆盖问题 是一个NP完全问题，目前许多文献都提出了相应的求解 算法,其中遗传算法(genetic algorithm, GA)和粒子 群算法(particle swarm optimization, PSO)都取得了一 定的效果，但山于问题本身固有的难度，求解效率与准确 性都不尽如人意。尤其随着装备系统复杂程度的提高，集 合规模的増大，需要寻求新的有效算法以获得最优解。无免费午餐定理皿说明，对于所有优化问题集，任意 两种不同的优化算法平均优化性能是相同的。也就是说, 没有一种优化算法在所有性能上，包括计算效率、
6、全局搜 索性、通用性和简洁性等方面都占有优势。因此本文针对 遗传算法和粒子群算法的不足，将遗传算法和二进制粒子 群算法(binary version of PSO, BPSO)结合起來，提出 一种用于求解测试选择的混合二进制粒子群遗传算法 (hybrid BPSO and GA, HBPSOGA)。实验证明该算法能 够有效、快速地收敛到全局最优解。2问题的描述与建模当考虑故障率时，故障检测率可农示为:2.1故障-测试相关性矩阵对系统进行FMECA分析，获得系统所有的潜在故障 集m佥,令&表示故障乃的故障率,定义故障 率矢量2=A1-2Jt。可供选择的测试构成/维备选测 试集厂二，乙,其测试代价
7、矢量C=c-cJ，此 处的测试代价是一个广义的概念,指测试过程中所有消耗 性属性的综合。通过可达性分析（分析每个测试所覆盖的 故障集）便可得到描述故障与测试关联矩阵 FT = （ ft.）m%n。若假设每个测试均对应一个二值输出， 且各测试相互独立，此时当测试/.可以观测到ft时 % = 1 ,否则 ftjj = 0 O2.2测试集完备性描述在测试选择Z前，必须确保备选测试集满足完备性要求。定义1:若测试集丁能满足系统要求的相关测试性指 标，则该测试集是完备测试集。定义2:给定完备测试集丁，若剔除任意-个测试就不 再满足完备性要求，则该测试集为最小完备测试集。因此,完整的测试选择过程应该包括下
8、面3个方的内 容：1）判断备选测试集的完备性，即利用该测试集能否 满足系统测试性指标要求；2）若备选测试集不完备，则适当地增加测试，使其 完备；3）选择最小完备测试集。2.3测试性指标参数与指标的确定山于系统同时发生多个故障的儿率很小，假设系统在 任意时刻最多只有一个故障发生。令待求测试集为 7；（匸厂），记此时的故障-测试相关性矩阵为D = dn o故障检测率一般足义为：在规定时间内山测试系统正 确检测到的故障模式的总故障率同系统所有故障模式的 总故障率Z比。对于故障拆，如果能被7；检测出來，故障-测试矩阵 中/所对应的行向量至少有一个元索为loW厶=1。t卢T, 式中：U为布尔变量的或运算
9、，M为集合7；的个数。设 T.能检测的所有故障构成的集合为Fd ,则有：I沖设|F|表示集合F的个数，则故障检测率可表示为： y _N_N丙一肓。细七因此对于检测率不小于给定的的要求，可以形 式化描述为：yFD FDR .关键故障检测率：设7；能检测的所有关键故障构成 的集合为你曲，则有：%严川处胳”力厂上FK纱I何关键故障检测率可表示为：_ I %I仏I7叫 FKey I 一 r当考虑故障率时，故障检测率可表示为：Z入fFKey因此关键故障的检测要求可以形式化描述为:YFbKey = I%故障隔离率一般定义为:在规定的时间内，由测试系 统正确隔离到不大于规走的可更换单元数的总故障率与 同一时
10、间内检测到的总故障率之比。山于存在一个测试可 以覆盖多个故障以及一个故障被多个测试观测到的悄况， 因此故障隔离问题要远比故障检测问题复杂。若故障J 和/；可以被隔离，则必须满足矩阵D第i行0与其第j 行0相异。设为能检测故障拆的所有测试纽成的集合，设T（j 为能检测故障/的所有测试组成的集合，那么拆能被隔离 的条件是：Tfi 丁勺w F、fj# fj o其中“”表示集合与或，当两个集合不同时，结果 为In反Z，故障力和故障/位于同一模糊组的条件是： 乙 Tfj = QP fj 丘 F f fj a可以定义另一个运算符,当7；7； =0时， r, 7；. = 1 ,表示故障拆和力属于同一模糊组。
11、设7；能隔离的所有故障构成的集合为尺，若给上故 障隔离模糊度厶，则有：件=/； “訂，工。UF0J山此可以获得故障隔离率形式化要求：当考虑故障率时，故障检测率可表示为:fF(因此对于满足给定模糊度为L下隔离率不小于FIR 的要求，可以形式化描述为：yn FIR2.4优化模型综合前面分析得到的约束条件和日标函数可以得到 测试优化选择模型如下：min 工 J s.t. yn） FDR丫FDKey =/, n FIR3基于混合BPSO-GA的测试优化选择3.1标准遗传算法（SGA）受生物进化机制启发，Holland T 20世纪60年代提 出-种计算模型，称Z为遗传算法冏。经过多年的发展， 遗传算法
12、理论逐渐成熟，已经被成功地用于优化设计、模 糊逻僻控制、神经网络、专家系统等领域“叫对于一个 特定的问题，遗传算法从代表问题可能潜在解集的一个种 群开始，而一个种群山经过基因编码的一定规模的个体组 成。每个个体实际上是染色带有特征的实体，表示一个可 行解。冇先需要対种群进行初始化，按照适者生存和优胜 劣汰的竟争原理。在每-代，采纳了口然进化模型，根据 问题域个体的适应度大小选择优良个体，并借助口然遗传 学的遗传算子进行组合交叉和变异，逐代进化以产生代表 新的解集的种群。周而复始，反复迭代，直到满足终止准 则，最后将运算结果作为问题最优解。3.2二进制粒子群算法（BPSO）粒子群算法z是一个进化
13、计算模型，受人工生命启 发，1995年Kennedy和Eberhtm模仿生物种群（鸟群和 鱼群）觅食的行为模式，提出了粒子群算法。同遗传算法一样，粒子群优化算法是基于群体的演化 算法。PSO求解优化问题时，问题的解对应于M维搜索 空间的一个粒子。每个粒子丿都有口己的位置 X严（,%）和速度Vy = （vyI,.,v7W）T （决定粒子飞 行的方向和跖离），还有一个山目标函数决宦的适应度函 数。各个粒子记忆、追随当前的最优粒子，在解空间中搜 索。每次迭代的过程不是完全随机的，粒子通过跟踪两个 “极值”來不断更新口己：第一个就是粒子本身所找到的最 优解，叫做个体极值点（PBes6另一极值点是整个种群 33 混合二进制粒子群-遗传算法（HBPSOGA） 目前找到的最优解，称为全局极值点（GBm）。在找到这 两个最优解后，根据如下的两个式子來更新粒子速度与位 置信息，决定粒子的飞行方向和速率大小，从而产生下一 代群体。噸=呵;”+唧（如爲-兔）+M（G血瞪-易）（5）4Sigmoid (v) = 1 + e0.02,-4 v 4
