具有最小搜索空间的优化测试生成算法烧砖机
2022-09-15 17:08:10 伟业五金网
具有最小搜索空间的优化测试生成算法
具有最小搜索空间的优化测试生成算法 2011： 1 预言 数字集成电路的测试生成问题一直是一个NP完全问题。随着集成电路规模的扩大和复杂性的提高,传统的测试生成方法在处理规模较大的被测电路时已遇到很大困难,寻找新型有效的测试生成方法已经成为集成电路测试领域内的一个重要研究课题。鉴于一些优化算法在解决NP完全问题方面的成功应用,测试领域内的一些学者正在尝试着将测试生成问题转化为优化问题来解决。1988年,Chakradhar等人首选采用Hopfield神经网络模型将测试生成问题转化为优化问题,利用神经网络的能量函数,通过计算能量函数的最小值来求对应故障的测试矢量[1-2]。该方法不同于传统的方法,它既不需要故障传播过程,也不需要回退过程;另外,该方法易于实现并行计算。其后,Fujiwara对Chakradhar的神经网络模型进篝了改进,提出了三值逻辑电路神经网络模型[3],将神经元的取值状态由(0,1)扩展到(0,1,1/2)。 在优化的测试生成算法中,经常使用的优化工具是遗传算法。此优化工具在国外学者的一些测试生成算法中也得到了一定的应用。国内的一些学者也在;优化的测试生成算法方面做了一些有益的探索。 总的来看,现有的优化测试生成算法由于考虑了被测电路内部的一些变量,间接地扩大了搜索空间,使得其实际应用受到一定的限制。但是,其潜在的并行计算能力使得优化的测试生成算法具有广阔的应用前景。为了解决现有优化算法的上述缺点，本文提出了一种具有最小搜索空间的优化测试生成算法。2 预备知识 2.1 遗传算法 遗传算法是由密西根大学的John Holland于1975年首先提出并加以研究的一种随机优化算法。它模拟达尔文的遗传选择和自然淘汰的计算模型，通过在求解过程中使群体不断优化，进而找到最优解或准最优解。作为一种有效的优化工具，遗传算法具有简单、通用、鲁棒性强和适于并行处理的特点。 遗传算法的主要组成部分包括编码、适应度计算、父代选择、交叉和变异。编码是把参数空间的点转换成位串来表示,常用的有二进制编码和浮点数编码。适应度计算就是计算种群中每个个体的适应度值。选择是从当前一代生成一组新的种群,通常使用与个体适应度值成正比的选择概率来选择作为父代的个体。交叉是按一定的概率随机地选择匹配对,然后随机地互换匹配对中两个个体的一部分形成新个体的操作。变异是按一定的概率随机地改变个体中某一位的值。 2.2 评价函数的构造方法 评价函数是遗传算法与具体应用问题的唯一接口，是种群中个体优劣的一种量化反映,它的构造直接影响问题求解的效率。 在基于遗传算法的优化的测试生成算法中,评价函数主要影响问题的求解空间。现有的优化测试生成算法中，通常需要确定正常电路内部信号线的赋值和故障电路内部信号线的赋值，扩大了算法的搜索空间，降低了算法的效率。 上述原因,本文根据正常电路和故障电路中基本门电路的响应不同来构造一种评价函数,使其具有最小的搜索空间。在下文的叙述中,需要特别说明的是，本文中的算法采用的故障模型为门级故障模型，故障类型为单固定型的故障，被测电路为组合电路。 构造评价函数的思想是：选择故障信号到原始输出端的所有通路，如果将所选通路中的任一信号线看成伪输出，当在原始办理入端施加故障的测试矢量时，该信号线的响应在正常电路和故障电路中应该是不同的。亦即，故障信号传播通路上基本门电路的输出响应在正常电路和故障电路中是不相同的。据此，可以构造如下的评价函数： 其中，n表示电路中故障传播通路上基本门的数量; 对于函数Gp（Vk，Fi）的取值规定为：当输入Vk时，对于第p个门来说，如果无故障和有故障F1时其取值不同，则函数Gp（Vk，Fi）的值取1，反之，则取0。这里，C是一个常数。从上面评价函数的构造过程可以看出，采用故障传播路径上基本门单元的办理出响应来构造评价函数，可以使算法具有最小的搜索空间，从而有利于提高算法的效率。3 优化的测试生成算法 在简单遗传算法中，由于交叉概率和变异概率取为恒定值,使得效率不高,并且存在“早熟”的可能性。为了提高效率和快速获得最优解,本文中根据个体的适应度值,自适应地调节交叉概率和变异概率,当群体有陷入局部最优解的趋势时,就相应地提高交叉概率和变异概率,当群体在解空间发散时,就降低交叉概率和变异概率。对于适应值较高的个体,选择较低的交叉概率和变异概率,使该个体得以保护进入下一代,对于适应值较低的个体,选择较高的交叉概率和变异概率,使该个体被淘汰掉。这样既保持了群体的多样性,又保证了遗传算法的收敛性,有效地提高了遗传算法的优化能力。 本文的测试生成算法如下: 1)初始化在求解空间中随机选取N个个体作为初始种群;2)评价计算种群中每一个体的适应度值Fi;3)保存最好的个体保存适应度值最大(Fmax)的个体;4)选择