·452· 智能系统学报 第6卷 (P2)及变异率(Pm)如式(2)所示，其中Pa和Pml为 1.0 1.0 原始交叉率和变异率，N为分解后的染色体个数，实 09 08A 验中N等于3.分析式(2)可知，并行进化时交叉率 0.6 906 和变异率都增大了，不过这与简单地增大原染色体 的交叉、变异率不同.分解染色体后，整条染色体不 0.4 12345×100.4 1234x10 是发生某一种定义好的变异，它可以以不同的概率 进化代数 进化代数 发生一点变异、两点变异及三点变异，其概率由式 (a)进化过程1 b)进化过程2 (3)可得，且它们是由限定在不同染色体区域的变 1.0 1.0r 异组合而成，不过对于分解后的某一区域只可能在 一代遗传过程中发生一次变异，这样避免了变异过 ,0.8 0.8 别 度集中而保证了全局的最优及高效的进化速度，同 月0.6 0.6 时保留了不同部分独立进化的性能优势.整条染色 体的某一位在一代遗传中也只可能发生一次变异， 0.4 1 2345×10 0.4 1 23410 进化代数 进化代数 这样不会出现变异抵消的情形.对于交叉的分析，其 (c进化过程3 (d)进化过程4 情况与变异相同，其一次、两次及三次交叉概率由式 图2任意4次进化曲线 (4)可得.由式(3)、(4)可知，从一点变异到三点变 Fig.2 Arbitrary four evolution curves 异概率依次降低，从一次交叉到三次交叉概率依次 1.3基于染色体分解的并行进化 增加. 由图2可以看出在随机产生初始种群的基础 上，在200~500代电路可以进化成功.文献[4]提 Pa=(2）41-2产=1-1-y 出了一种将整个系统划分成多个子系统进行进化的 方法，以提高进化性能.参考其划分电路的思想，考 e=ka-产=1-4- 虑将整个电路编码后的染色体进行分解.这样不仅 (2) 可以使系统进行并行的进化，而且每个进化的染色 体长度会大大减少 实验中染色体采用基于PLA的编码方法，故 (3) 可以将染色体中与或非门进行分离，由于每个与门 的入口都对应一个非门，故与门和非门的数量相同， Pne3 =Pm 其对应染色体长度也相等，剩下的既为或门染色体 实验中与非门编码长度为28位，或门编码也为28 Pa - 位.每一代进化时，各段染色体独立进行交叉、变异 (4) 等运算，进化参数相同.而进行适应度计算时应用分 解的逆运算过程将染色体进行合并，组成完整的染 P23=p2. 色体而进行评估及选择，合并时采用顺序合并，即将 编号相同的染色体进行合并. 分别采用改进前和改进后的进化方法各自进行 与文献[4]中分解法不同的是这里的分解对象 了20次试验，统计了其进化成功所用的代数，结果 为整条染色体，且不是以电路功能进行模块化的划 如表1所示.由进化结果可以看出，在20次进化试 分，这样避免了进化时对电路尤其对复杂电路划分 验中，采用逻辑门分离的方法每一次进化所需的代 的工作，进化时各染色体之间也不是毫无关联的独 数都小于改进前进化所需的代数，而在平均代数上 立进化，而是共同参与适应度计算和父代选择， 并行进化比改进前减少了84.1代，平均速度提高了 对于整条染色体，并行进化方法下的交叉率 32.25%