离散粒子群算法及其rm电路面积优化毕业论文正文终稿.doc

本科毕业设计（论文）题目：离散粒子群算法及其RM电路面积优化 The discrete PSO algorithm and RM circuit area optimization学 院 专 业 班 级 学 号 姓名 指导教师 职称 完成日期 宁波大学信息科学与工程学院学院本科毕业设计诚 信 承 诺我谨在此承诺：本人所写的毕业论文离散粒子群算法及其RM电路面积优化均系本人独立完成，没有抄袭行为，凡涉及其他作者的观点和材料，均作了注释，若有不实，后果由本人承担。 承诺人（签名）： 年 月 日摘要【摘要】通过对离散PSO算法和细菌觅食优化算法的研究，提出混合极性XNOR/OR电路的面积优化算法。首先，根据混合极性XNOR/OR展开式的特点，改进快速列表技术并将其应用于混合极性XNOR/OR展开式的转换；然后，结合离散二值PSO算法和机率转换法则，在离散三值粒子群优化算法的基础上，结合细菌觅食优化算法，改进PSO算法，并将其应用于MPRM电路的最佳极性搜索中，实现混合极性XNOR/OR电路面积最小化；最后，通过实验验证该算法具有更快的收敛速度和更好的寻优效率。【关键词】离散三值PSO；MPRM电路；极性转换；面积优化；细菌觅食。The discrete PSO algorithm and RM circuit area optimizationAbstract【ABSTRACT】Through study the discrete PSO algorithm and bacterial foraging optimization algorithm， proposed the mixed polarity XNOR/OR circuit area optimization algorithm. First, according to the characteristics in mixed polarity of XNOR/OR expansions , improved fft technology and apply it to the mixed polarity XNOR/OR expansions conversion; then, with discrete binary PSO algorithm and the probability of conversion rules, based on the discrete three value of particle swarm optimization algorithm，combination of bacterial foraging optimization algorithm to improve the PSO algorithm, and applied MPRM search the best polarity circuit to achieve the mixed polarity XNOR/OR circuit area is minimized; Finally, by experimental validation of the algorithm has faster convergence speed and better optimization efficiency.【KEYWORDS】Three-valued discrete PSO；MPRM circuit；Polarity conversion；Bacterial foraging。目录摘要IIAbstractIII1绪论11.1研究背景及意义11.2研究现状及其发展趋势21.3主要内容安排22混合极性MPRM转换32.1混合极性AND/XOR表达式32.2混合极性XNOR/OR表达式42.3混合极性列表技术53粒子群优化算法概述73.1基本粒子群算法73.2离散三值PSO算法93.3基于细菌趋化的改进粒子群算法PSOBC103.3.1PSOBC算法103.3.2PSOBC算法实现步骤114TPSO算法在混合极性XNOR/OR电路上的应用124.1TPSO中粒子与极性的参数映射和适应度函数124.2速度与位置更新124.3XNOR/OR电路的混合极性转换124.4算法描述145 实验结果及其分析166 结论与展望18参考文献19致谢21附录22231 绪论1.1 研究背景及意义随着社会的进步，电子信息产业也随之发展，集成电路不仅在工用、民用电子设备如收录机、电视机、计算机等方面得到广泛的应用，同时在军事、通讯、遥控等方面也得到广泛的应用。集成电路技术及其产业规模已成为衡量一个国家综合实力的重要标志。1958年，德州仪器的Jack Kilby发明了第一块集成电路；1959年，为了适合工业化批量生产，仙童公司的Robert Noyce发明了采用平面工艺研制的集成电路，由此微电子学的历史拉开帷幕；1965年，Intel公司的创始人Gordon Moore撰写了一篇文章，是有关预测对未来半导体元件的工业发展趋势。他指出，如果按目前的发展趋势，一块硅晶片上需要的晶体管的数量大概每一年半的时间增加一倍。这正是摩尔定律，同时，摩尔定律也被随后的时间里集成电路的实际发展所证实。随着时间的推移，历史的发展，集成电路已从先前的中小规模集成电路阶段进入了特大规模集成电路和片上系统发展阶段。在工业界，目前对集成电路设计的要求已经进入对面积、速度和功耗等三方面影响的考虑，而之前只是单一地追求高密度和高性能。目前，随着高端芯片设计领域的便携式设备的普及，面积优化已经成为芯片设计的首要考虑问题。因此，集成电路面积优化已成为电路优化的一个重要因素，亟待我们去研究探索，它在集成电路设计中也起到了决定性的作用。1956年，一组线性错误检验码被I. S. Reed和D. E. Muller一起发现，这就是人们所说的Reed-Muller（RM）码。纵观历史，集成电路优化大多是在与/或/非运算的布尔逻辑的基础上设计的，并且布尔逻辑也已经有了它自己比较完善的自动化设计方法，而基于异或/与和同或/或运算的RM逻辑的CAD优化技术尚未成熟。与传统Boolean逻辑实现的电路相比，用RM逻辑实现的电路，如算术电路、奇偶校验电路、通信电路等在功耗、面积和速度以及可测试性等方面表现出了相当的优势1。因此，研究RM电路逻辑综合优化方法以实现快速有效的极性搜索是对目前以Boolean逻辑为主的电路设计方法的补充和完善。RM逻辑展开式有两种重要形式：一是固定极性RM(Fixed-Polarity Reed-Muller, FPRM)展开式，二是混合极性RM(Mixed-Polarity Reed-Muller, MPRM)展开式。固定极性RM展开式中，变量只能以原变量或反变量的形式出现；而在混合极性RM展开式中，变量可以以原变量的形式出现，也可以以反变量的形式出现，或者是以原变量与反变量同时存在的形式出现，相关研究已表明，在功耗、面积等方面的性能，混合极性RM电路的优化结果均优于固定极性RM电路。然而，混合极性RM电路的极性搜索空间较大，导致了它在性能优化的时间和空间复杂程度都高于固定极性RM电路。因此，在混合极性RM逻辑电路的优化理论和求解方法上急需新的突破。 粒子群优化(Particle Swarm Optimization, PSO)算法是继蚂蚁算法后的一种新兴的群体智能算法。它与遗传算法（Genetic Algorithm, GA）类似，都是基于群体迭代的启发式算法。但是它比遗传算法简单，在搜索中没有交叉和变异的操作过程，它是通过个体间的行为交互（个体通过群体中最好个体的经验和自身的经验去判断自身下一时刻的行为）。PSO算法需要调整的参数少，结构相对比较简单、精度高、收敛快并且易于实现，这些优点引起了学术界对它的重视，并且它的优越性也表现在解决一些实际问题中。目前我们的研究主要集中在连续数值优化领域，但是实际生活中许多优化问题都是在离散数值空间中，随着对算法的不断探索和改进，粒子群优化算法己经被证明能有效解决许多离散问题。 所以，我们可以通过发展MPRM逻辑电路优化技术，充实RM逻辑电路优化方法体系，快速高效地找到面积优化的最佳极性搜索。本课题研究正是从这一实际需求出发，在前人对粒子群算法研究的基础上，发展混合极性RM逻辑电路面积优化算法和混合极性转换算法，结合细菌觅食优化算法，改进PSO算法，将其应用于RM电路面积优化，以达到面积优化在混合极性RM逻辑电路上的应用。因此，本课题对集成电路面积优化的研究发展具有积极的意义。1.2 研究现状及其发展趋势目前，对于优化在RM逻辑电路上的应用，大多数是对固定极性RM逻辑电路的研究，对混合极性RM逻辑电路的研究甚少，存在这种现象主要原因有：1）面积优化的成本函数构造不合理；2）单一的优化目标；3）最佳极性搜索算法太过简单并且效率相对也比较低下；4）对于实现多输出逻辑函数的快速混合极性转换的难度比较大。但由于我们深入研究了固定极性RM逻辑电路面积优化以及基于智能算法的大规模固定极性RM逻辑电路优化，也为混合极性RM逻辑电路优化提供了很大帮助，可能在以后有希望把一些像粒子群算法、改进粒子群这样的智能优化算法和混合极性RM逻辑电路优化方法相结合，来找到混合极性RM逻辑电路的最佳极性，以实现面积的自动优化。1.3 主要内容安排1）通过对离散PSO算法和细菌觅食优化算法的研究，提出混合极性XNOR/OR电路的面积优化算法；2）根据混合极性XNOR/OR展开式的特点，改进快速列表技术并将其应用于混合极性XNOR/OR展开式的转换；3）结合离散二值PSO算法和机率转换法则，在离散三值粒子群优化算法的基础上，结合细菌觅食优化算法，改进PSO算法，并将其应用于MPRM电路的最佳极性搜索中，实现混合极性XNOR/OR电路面积最小化；4）通过实验验证该算法具有更快的收敛速度和更好的寻优效率。2 混合极性MPRM转换2.1 混合极性AND/XOR表达式首先，我们来讨论下混合极性与/异或的展开式。n个输入变量和m个输入变量的逻辑函数fc: BnB | 0cm-1按香农（Shannon）展开形式进行分解2，即得到Boolean逻辑最小项表达式，其中fc为， (1)式中，为或运算；最小项mi可用符号表示为；ai,c，mi在fc中出现与否决定了ai,c的出现形式，若mi出现，ai,c为1,若mi不出现，ai,c为0；下标i可用二进制数表示为i=(in-1in-2i0)2；当ik=0时，；当ik=1时，0km-1。同时，n个输入变量的逻辑函数f(xn-1, xn-2, , x0)有三种与/异或运算展开形式，见下式（2）、（3）和（4）所示，其中，若分别将和代入式（2）中，化简后可得到式（3）和式（4）。若按式（2）、式（3）和式（4）展开的逻辑函数，则可得到3n个不同的混合极性RM表达式；若按式（3）和式（4）展开的逻辑函数，则可得到2n个不同的固定极性RM表达式。可见，混合极性RM展开式中的变量可以同时以原变量和反变量的形式出现，固定极性RM展开式中的变量只能以单一的原变量形式或单一的反变量形式出现。因此，同一逻辑函数的混合极性RM表示形式比固定极性RM表示形式具有更简单的RM逻辑表达式。 (2) (3) (4)在f(xn-1, xn-2, , x0)中，极性区将3n个不同的混合极性RM表达式分开来。在这里我用P来表示混合极性RM表达式的极性，则P的范围为0P3n-1， P=(pn-1pn-2p0)3是P的三进制数表示形式。其中xk的极性用pk表示，且xk的AND/XOR运算展开形式将决定pk的值：当xk按式（2）展开时，pk=2。当xk按式（3）展开时，pk=0；当xk按式（4）展开时，pk=1。所以，fc: BnB | 0cm-1有3n个不同的混合极性RM表达式，即n个输入变量的逻辑函数有3n个混合极性，对应有3n个MPRM表达式。P极性下的混合极性RM表达式可表示为， (5)式中，为异或运算；i为与项，它可用用符号表示为；bi,c为与项系数，i在fc中出现与否决定了bi,c的出现形式，若i出现，则bi,c为1，若i不出现，则bi,c为0；如图1所示，由ik和pk共同决定。图1 与ik和pk的关系2.2 混合极性XNOR/OR表达式下面我们来讨论本课题要用到的混合极性XNOR/OR的展开式。n个输入变量逻辑函数f: XnX可用最大项展开式表示为8 (6)同时，n个输入变量的混合极性RM对应不同的极性有3n个，对应不同的混合极性XNOR/OR展开式也有3n个，则极性P下混合极性XNOR/OR展开式可表示为(7)式中，为XNOR运算；P为极性，其三进制数表示形式为P=(pn-1pn-2p0)3；i为下标，可用二进制数表示为i=(in-1in-2i0)2；，表示Si项是否在表达式中出现，若Si出现，则di为1，若Si不出现，则di为0；Si为OR项，可用符号表示为。混合极性XNOR/OR展开式中的变量可以以原变量的式出现，或者以反变量的形式出现，也可以同时以原变量和反变量的形式出现，极性P决定其出现形式。图2为pk和ik与Si中的出现形式的关系，0kn-1，其中xk的原变量用表示，的反变量用表示。若pk是 对应的极性，当pk=2时，的原变量和反变量同时出现；当pk=1时，以反变量出现；当pk=0时，以原变量出现。图2 与ik和pk的关系2.3 混合极性列表技术在n个输入变量的单输出逻辑函数中，传统列表行要表示最小项或与项系数下标(in-1in-2i0)2是否在逻辑函数中出现仅用列表行就可，其中in-1in-2i0为下标项。而在n个输入变量和m个输出变量的逻辑函数中，它们的情况有所不同，即在逻辑函数fm-1, fm-2, , f0中，项的系数下标(in-1in-2i0)2和最小项出现的情况有所不同。为了能表示(in-1in-2i0)2在fm-1, fm-2, , f0中的出现情况，可用om-1om-2o0来表示，即用一组用于表示输出函数出现情况与最小项或与项系数的有关项加入到传统的列表行中。则我们将来表示新的列表行，在新的列表行中，in-1in-2i0是否出现在fc中决定了oc的取值，0cm-1，若in-1in-2i0出现，则oc=1，若in-1in-2i0不出现oc=0。列表行可表示为MPRM表达式，也可以表示为最小项表达式，即若用混合极性RM表达式来表示列表行，则与项系数下标i用in-1in-2i0来表示，om-1om-2o0可以与bi,m-1bi,m-2bi,0一一对应，其中bi,c表示fc的MPRM系数；若用最小项表达式来表示列表行，那么最小项系数下标i可用in-1in-2i0来表示，om-1om-2o0可以与ai,m-1ai,m-2ai,0一一对应，其中fc的最小项系数用ai,c来表示。在列表技术表示MPRM表达式时，列表栏、极性和列表行有以下的对应关系：当列表栏为时，对应pk=2，则xk和出现在MPRM表达式中，列表行中当ik=1时，表示xk出现在此项中，当ik=0时，表示出现在此项中；当列表栏为时，对应pk=1，则出现在MPRM表达式中，列表行中当ik=1时，表示出现在此项中，当ik=0时，表示出现在此项中；当列表栏为xk时，对应pk=0，则xk出现在MPRM表达式中，列表行中当ik=1时，表示xk出现在此项中，当ik=0时，表示xk出现在此项中。而在表示最小项表达式时，列表栏为，列表行ik为1或0分别对应xk或出现在此项中。一般，列表技术在多输出逻辑函数中的应用可总结成两个步骤，即产生新的行和删除成对的列项。如果要将混合极性RM表达式（极性为P）和最小项表达式进行转换，如果用pk来表示P的三进制形式(pn-1pn-2p0)3中的第k位，则可以用以下三种情况来分析产生的新行，即一、如果pk=0时，那么在混合极性RM表达式中出现xk，如果出现即最小项，那么可用来表示列表行，由， (8)上式中，可用来表示在列表中的与项，那么表示产生的新行，原来就的列表行无变化；二、如果pk=1时，则出现在混合极性RM表达式中，如果最小项出现，则用来表示列表行，由， (9)上式中，可用来表示在列表中的与项，那么表示产生的新行，再将所有列表行中出现ik的项进行取反；三、如果pk=2时，便不会产生新的项，因为xk和出现在MPRM表达式中，那么AND项的表示方式和列表中的最小项相同。又因为在异或的运算当中，相同的项进行异或的结果等于0，所以我们要在原行和新行中找到下标项相同的列表行，删除它们当中的成对列项，然后将按位异或运算运用到两行中相同的关系项，如果我们算出来的结果不为0的话，那么我们可以把算出来的结果代替原来的行的关系项，并且去掉新的行，若所得到的结果等于0，则将原行和新行一并删除。3 粒子群优化算法概述 粒子群优化算法的产生来源于对简化社会模型的模拟。它是在鸟群、鱼群和人类社会的行为规律的启发下提出的。自然界中很多生物是以社会型群居形式生活在一起，如鸟群、鱼群等，在20世纪七八十年代一些科学家对鸟群或鱼群的群体行为进行了研究。最早提出粒子群算法的是由美国社会心理学家J.Kennedy和电气工程师R.C.Eberhart在1995年发表的有关粒子群的文章，为粒子群算法翻开篇章。早期受鸟类的群体行为的启发，并且在这基本思想上面进行建模和仿真，开发出粒子群算法。在此之前Frank Heppner研究发现鸟群的同步飞行这个整体的行为只是建立在每只鸟对周围的局部感知上面，而且并不存在一个集中的控制者。也就是说整个群体组织起来但却没有一个组织者，群体之间相互协调却没有一个协调者，而J.Kennedy和R.C.Eberhart的建模与仿真算法主要也是利用了生物学家Frank Heppner的模型。1975年，生物社会学家E.O.Wilson提出，从理论上讲，鸟类在觅食的过程当中，鸟类可以根据其他个体和之前鸟类的经验进行觅食。当食物不规则地分布在各个区域当中，这种觅食方式解决了食物竞争的缺点，给鸟类带来了巨大的好处。1988年，R.Boyd和P.J.Richerson在研究人类的决策过程时指出，自身和他人的经验是人类在作出决定过程当中使用的最重要的两类信息。即人类通过他人和自身的经验作出自己的决定。通过历史研究，证实了信息共享对群体发展发挥的重要性。同时这也是粒子群算法的基本核心思想。鸟类通过向其他优秀的鸟类学习，并与其他优秀的鸟类进行比较，吸收最优秀鸟类的经验。这种算法的实现导致了粒子群优化算法的产生。3.1 基本粒子群算法在D维空间中，粒子群算法将每个个体看作为一个没有体积和重量的粒子，在搜索空间中以某种速度飞行，并根据对自身和集体飞行经验的综合分析来动态调整速度。其中，每一个粒子都有一个被优化函数决定的适应度值，粒子的位置代表优化问题在搜索空间的可行解，飞行速度代表着粒子的搜索方向和步长9。在每一代中，粒子将跟踪两个极值：一个是群体的最优解，另一个是个体的最优解。现在我们设想在D维的搜索空间中，一个由M个粒子组成的群体以一定的速度飞行。那么粒子i在t时刻的状态属性设置如下(, )： 位置： ，分别代表搜索空间的下限和上限；速度： ，、分别代表最小和最大速度；个体最优位置：；全局最优位置：；则粒子在t+1时刻的位置通过下式来更新得到：(10)(11)其中，w为惯性权重，c1和c2为学习因子，分别代表了自我调整能力和向种群最优粒子的学习能力，r1和r2为均匀分布在0，1范围内的随机数。公式(10)主要通过三部分来更新粒子的速度：第一部分为粒子先前的速度乘一个权值（即惯性权重w）进行加速，表示粒子对当前自身运动状态的信任；第二部分为认知项，表示粒子对自身个体的思考（即粒子对自身以往的经历进行综合考虑以做出下一步的决策）；第三部分为社会项，表示粒子间信息、资源的共享和团队的合作。其具体算法实现流程如下：step1：初始化PSO算法中的要用到的参数（每个粒子的位置、速度等）；step2：根据适应度函数，计算得到适应度值；step3：比较粒子与最优值的适应度值，如果粒子的适应度值优于目前的个体最优值，那么就将这个值作为目前的最好位置；step4：比较粒子与种群中得最优值，如果粒子的适应度值优于目前的全局最优值，那么就将这个值作为目前的全局最好位置；step5：用公式(10)和公式(11)更新粒子的速度和位置；step6：如未达到迭代结束条件(通常为足够好的适应值或达到一个预设最大代数)，则返回step2。用更直观的的流程图表示如下：YN 开始 初始化 评价粒子 更新粒子 满足停止条件？ 结束 图3 PSO简易流程图3.2 离散三值PSO算法根据混合极性XNOR/OR电路展开式的特点，结合离散二值PSO算法，提出了离散三值PSO算法，该算法与基本粒子群算法不同之处在于每个粒子的每一位只有三个状态，分别是0态、1态和2态，所以采用三进制编码形式，并且它的取值服从正态分布,它的粒子运动方程与PSO算法也有很大区别，其粒子运动方程如下:(12)(13)(14)(15)从式（12）我们可以看出，它的速度公式形式基本不变，而从式（13）我们观察到，它的位置公式完全改变了，式中，、和只能取0、1或2，round()对括号内的数值进行四舍五入，其返回值为整数，集合数Q=3，被约束在0,2之间，为权值。速度不再是位置的步长，而是决定位置的一种概率，通过sigmoid函数和服从标准正态分布的随机数来约束位置，选中位置的概率与该位置离的距离成反比，并可以证明概率之和为1，即：。3.3 基于细菌趋化的改进粒子群算法PSOBC我们知道，种群都有各自的特点，即种群的多样性。它与许多算法关联都非常密切，如果种群失去它的多样性，将使出现早熟或者陷入局部最优的风险。在我们之前提到的粒子群算法当中，个体总是在向最优解靠近，不管是个体最优还是种群最优。所以在追寻这种最优的原则下，如果种群失去多样性，那么它将会出现上面提到的早熟等风险。其实，我们可以换一个角度来研究粒子群算法以解决上节提到的“风险”问题。如对细菌觅食的趋化现象的研究。趋化是指细菌根据周围的环境向有利于自身生长的环境移动，逃避不利的生长环境，其实就是我们所说的寻找最优的办法，不过它还会排斥最差的解。受细菌这种趋化行为的启发，我们将它应用于粒子群算法，即PSOBC，以解决标准粒子群算法中只存在吸引操作而没有排斥操作而产生的种群多样性失去的问题。3.3.1 PSOBC算法上节中，我们说到细菌趋化问题，本课题正是结合细菌的趋化现象，采用PSOBC算法，改进标准粒子群算法。PSOBC算法最主要的是吸引和排斥的过程，算法中吸引是选择最优解的过程，这时，粒子会向自身最优和群体最优位置靠拢，这个过程与标准粒子群算法完全一样，公式也一样。还有一个是排斥，它与吸引过程刚好相反，它会远离自身最差和群体最差位置。这里给出粒子的排斥过程的速度更新公式： (16)上面式子中，群体的历史最差位置用Wid 表示，群体最差位置用Wgworstd 表示。从上述的算法分析中我们可以看出，粒子在被自身最优和群体最优位置吸引的同时也会被自身最差和群体最差位置所排斥，这有利于粒子找到最佳位置，即避免了粒子陷入局部最优。种群的多样性也会随着算法的吸引、排斥过程进行适当地增减。这时会出现一个问题，即应该在什么时候执行吸引操作，又该在什么时候执行排斥操作呢？针对这个问题，本课题引入了diversity。即多样性的度量，其公式表示如下： (17) 其中，是第j个分量的平均值，Sij 是第i个粒子位置的第j个分量，N为维数，L为搜索空间最长对角线的长度，P为种群大小。 3.3.2 PSOBC算法实现步骤PSOBC具体算法实现流程如下：step1： 对一些主要参数，如种群规模，惯性权重，粒子速度范围vmin，vmax，多样性阈值dlow，dhigh等进行初始化；Step2：刚开始取迭代次数为零，当前模式为吸引模式；Step3：根据适应度函数，计算得到适应度值；Step4： 如果种群多样性小于等于多样性最低阈值，那么令模式为排斥模式，执行排斥操作；如果种群多样性大于等于多样性最低阈值，那么令模式为吸引模式，执行吸引操作Step5：如果模式为吸引模式，那么用公式（10）进行速度更新，用公式（11）进行位置更新；Step6：如果模式为排斥模式，那么用公式（12）进行速度更新，同样用公式（11）进行位置更新；Step7：更新Pid，Pgd，Wid，Wgd；Step8：如果当前的迭代次数达到了预先设定的最大次数tmax，则停止迭代，输出最优解，否则，t=t+1，转到步骤step3。4 TPSO算法在混合极性XNOR/OR电路上的应用关于混合极性XNOR/OR电路的极性优化，其实际是一种研究组合优化的问题，由于电路的很多目标值在极性空间的分布无规律可循，如功耗、面积和延时等，而又不能用数学规划法、分支定界法等传统优化理论来处理这个问题。结合离散PSO算法的思想设计了一种新型的编码机制，并将提出的TPSO算法应用于混合极性XNOR/OR电路的面积优化上。4.1 TPSO中粒子与极性的参数映射和适应度函数n个输入变量的逻辑函数具有3n个不同的混合极性，对应3n个不同的XNOR/OR展开式，我们在寻找个数最少的混合极性RM电路的同或和或的项数中，可以利用TPSO算法实现。将极性的三进制代码作为算法的编码，并与离散三值PSO算法中的位置相对应，电路的输入变量数确定粒子的搜索空间维数，则任一极性可表示为粒子i在t时刻的位置，0,1,2，0dn-1，其中n是混合极性XNOR/OR电路的输入变量数。在搜索过程中，离散三值PSO算法需要对种群的每个粒子通过适应度函数进行评价，以确定每个粒子的好坏。RM逻辑电路面积估计模型可用混合极性RM电路的同或和或的项数个数表示，而实际当中，一般都会出现很大的同或和或的项数。因此，适应度函数可用下式表示为(18)式中，和分别表示在粒子i的极性下MPRM电路中XNOR和OR的项数个数。4.2 速度与位置更新粒子的速度和位置可以根据公式(14)、公式(15)、公式(16)和公式(17)分别进行更新以得到新粒子，在这过程当中还要对速度进行限制，因为标准正态分布函数和sigmoid函数决定了离散三值PSO算法的位置为0、1或2的概率。在sigmoid函数作用,要使概率被限制在0.0025, 0.9975之间，只有设置才合适。所以设置。4.3 XNOR/OR电路的混合极性转换On-Set表示在XNOR/OR逻辑函数中所有值为0的系数的下标的集合，其式表示为On-Set= i | 0i2n-1(19)则MPRM展开式表示的On-Set为On-SetMPRM=i | 0i3n-1, di=0；最大项展开式的On-Set为On-SetMaxterms=i | 0i2n-1, ai,=0。XNOR/OR电路混合极性转换即为在已知On-SetMaxterms的条件下将其转换为极性P下On-SetMPRM的过程。借鉴固定极性转换上的快速列表技术思想，将其用于混合极性XNOR/OR电路的极性转换，从而提高极性转换速度。其基本转换流程用文字表述如下：step1：将所有最大项以二进制形式表示；step2：将所要求的极性转换成三进制形式，并与最大项中对应极性为1的位进行异或操作，得到新项，若极性位为0或2时，则不操作；step3：当极性位为0或1时，选择i个位为1的新项，以这些位为无关项，再产生所有2i-1个新项，并更新索引表中的项数，若极性位为2时，则保持不变；step4：重复步骤step3，直至操作完所有新项；step5：索引表中项数为奇数的项即为所求的XNOR/OR项。以三变量Boolean函数为例，现将此最大项展开式转换成极性19下MPRM展开式。New maxtermsNew terms of generation000011000,001,010111100,101,110 图4 产生新的最大项 TermsNumber of occurrence00020011010101111001101111011111 图5 索引表 首先，根据step2将每个最大项与201（极性19）进行异或操作得到新的最大项，如图4中第二列所示；再根据step3产生新项并建立索引表，如图5所示。最后，索引表中项数为奇数的项即为所求的XNOR/OR项，即得到极性19时的MPRM展开式： (20)4.4 算法描述将上文所述的TPSO算法应用在XNOR/OR电路的混合极性转换技术中，则所提算法的基本步骤如下：step1： 先读入PLA格式测试电路，再初始化各个参数，并计算初始种群的适应度值；Step2： 通过公式更新速度和位置以得到下一代粒子群；Step3： 调用混合极性转换技术，则可以得到每个个体所对应极性下的MPRM逻辑展开式，并据此获得混合极性RM电路的同或/或的操作项数，计算个体适应度值，再更新pid和pgbestd；Step4： 若达到最大迭代次数，则输出最优解结束，否则继续进化。上述算法过程的程序伪代码如图6所示： Begin Algorithm: Read_PLA(); /读入PLA标准电路 Initialize_Population(); /初始化种群 for(i=0;ipopulation_size;i+)for(j=0;jno_of_variables;j+)speedij=vmax*rdftfu(); /速度初始化，取vmax内的随机数for(i=0;ipopulation_size;i+)for(j=0;jno_of_variables;j+)bestij=positionij; /粒子最优位置初始化,用小写的population_sizeworstij=positionij;for(i=0;ipopulation_size;i+)fft(position,i);fitnessi=(1.0/no_of_xnor+1.0/no_of_or)*1000;speedkt=w*speedkt-c1*rdft()*(positionkt-worstkt)-c2*rdft()*(positionkt-G _Position_worstt); /速度更新x=(3/(1+exp(-(speedkt)+2*0.2*randn(0); /位置更新 positionkt=(int)(x+0.5); fft(int *pop_or_off,int kk_population) /调用fft技术localworst(k); /更新pid和pgbestdlocalbest(k);globalbest(PROCESS_INITIALIZE);If(iMAX_INTERATIVE_STEPS) /未达到最大迭代次数 i+;R