多点正交交叉的遗传算法精要.ppt

多点正交交叉的遗传算法 基本遗传算法的不足 遗传算法是一种基于自然选择和生物进化机制的智能优化算法，由于它具有非常多的优点，所以被广泛应用于各个领域。但是基本的遗传算法（简称GA）同时存在着许多的缺点和不足：适用范围不是非常广，很容易出现“早熟”收敛，而且局部有哪些信誉好的足球投注网站能力差，收敛速度很慢。 针对基本遗传算法的不足采取多点正交交叉的遗传算法 正交试验： 正交试验设计(Orthogonal experimental design)是研究多因素多水平的一种设计方法，它是根据正交性从全面试验中挑选出部分有代表性的点进行试验，这些有代表性的点具备了“均匀分散，齐整可比”的特点，正交试验设计具有高效率、快速、经济等特点。将该技术引入到遗传算法中，可以改善遗传算法的局部有哪些信誉好的足球投注网站能力和收敛速度 。 正交试验的原理： 在实际问题中 试验往往是多因素多水平的，如果对每个因素的每个水平都相互搭配进行全组合试验，然后从所有的搭配方案中找出最优方案，则总的试验次数将会爆炸式地增长，利用正交表的均匀分散性和整齐可比性，来安排多因素多水平试验，可以实现对试验方案的最优设计。 正交表可以为： A是一个nxm矩阵，它的第 j 列的元素为由数1,2, …tj,(j=1,2, ,m) 所构成，它的任两列中同行元素所构成的元素对是一个完全对，而且每对出现的次数相同，则A称是正交表。简记为Ln(t1xt2x…xtm)=Ln(t^m )，n为试验数，m为因素数，t为水平数。这里所谓的完全对是指，有两组元素 A1，A2，… Ar 与B1， B2，…Bs把rxs个元素对(A1 ，B1 )，(A1，B2 )，…(A1，Bs)，(A 2，B1），(A2，B2 )，(A2 ，Bs )，(Ar，B1 )，(Ar，B2)，(Ar ，Bs)，叫做由元素 A1，A2，…Ar 与B1，B2，…Bs 所构成的完全对 。 正交表有下列性质 (1)它的任两个元素都构成有相等重复的完全试验，但是一般来说，却不能构成有 m 个因素的完全试验 。 (2)在第 i ，j 两列所构成的水平对中，每个水平对都重复出现n/（ti*tj）次，其中 n 为试验数。 (3) 每一列中各水平出现的次数相同。如第j列中，每个水平都出现n/tj次( j=1，…m)。下表是一个简单的正交表L4(2^3)，它用来安排3因素2水平试验，表中X、Y和Z代表3因素；数字1和2代表因素的2个不同的水平，从表中可知因素的2^3种组合就只要4重组合进行试验。 实验次数/实验因素数 X Y Z 1 1 1 1 2 1 2 2 3 2 1 2 4 2 2 1 多点正交交叉算子 在多点交叉运算中，其交叉组合有多种方式存在，且随着交叉点的增多，组合方式的数量将会爆炸式地增长 为了解决这个问题，采用正交多点交叉算子，通过正交表安排多点交叉运算，以保证交叉运算后能够得到优良染色体，提高遗传算法的局部有哪些信誉好的足球投注网站能力和收敛速度。 定义 1： 设染色体进行N-1点交叉运算，则交叉的染色体 子串的个数为N，将这N个子串看成N个因素。 定义 2 ：将染色体的每一个交叉子串设置为同一水平，这样两个染色体的交叉运算，就是一个N因素2 水平试验。 定义 3 ：用N因素2水平正交试验表安排染色体的子串交叉 得到2^N个新染色体，通过适应度函数选取两个适应度最大的作为子代染色体，进入下一次进化算法，该生成子代 染色体的过程是多点正交交叉算法。 例如：设一个长度为24的染色体，如进行2点交叉运算，则要交叉的染色体子串为3，将染色体1的每一个子串设置为水平1，染色体2的每一个子串设置为水平2，如下表所示，这样2点交叉运算就成为一个二水平三因素的试验。 水平/因素 X Y Z 染色体1 110101110染色体2 200101011但因素间可能会有交互作用，一个二水平三因素的试验 可用正交表 L8(2^7)来安排试验,将L8 (2^7)表中的水平用 -1和1来表示，在下表中的7个8维向量相互正交，且第1列和第2列的元素相乘是第3列，第1和第4列的元素相乘是第5列，第2和第4列的元素相乘是第6列，从试验设计的角度，若将因素X和Y分别放在第1、2列，则它们的交互作用 X*Y反映在第3列,所以该列不能再排其他因素 否则主效应与交互效应将混在一起，二者都无法估计，考虑因素间可能会有交互作用的一个二水平三因素的试验一个设计方案。 序号 1 2 3 4 5 6 7 因素 X Y X*Y Z X*Z Y*Z 该方案中，每个主效应和交互效应各占1列，但在试验 安排时，只需要 X、Y、Z所在的第1、第2、第4列、将该3列的2个水平换算成实际的水平 ，得到遗传算法的