智能优化方法课程论文.doc

智能优化方法课程论文基于食物链捕食模式的三种群协作遗传算法实验侯树卫1.实验目的通过编程实现基于食物链捕食模式的三种群协作遗传算法，对函数进行优化，将其与标准的遗传算法优化效果进行对比分析，得出一定的结论。同时，在试验过程中学习熟悉遗传算法。2.技术方案在遗传算法基础上，进一步模拟自然界的生物进化过程。自然界生物的进化还受到食物链的影响，被捕食和获取食物直接影响生物进化过程。设想，有三个初始种群，按捕食和食物间的一定关系进行协作，会对遗传算法优化效果有一定提升。算法的流程如下：1. 采用实数编码，设置变异参数、种群数量等，生成三个初始种群；2. 计算适应度；3. 进入迭代：（1） 处理第三个种群：第三个种群中所有适应度坏于第二种群平均适应度的个体，作为食物被第二种群分配；删除作为食物的个体。按一定选择方式选择父代，交叉产生子代，进行变异；（2） 处理第二个种群：按一定方式分配由第三种群获取的食物，食物低于一定值的个体死亡，作为第一种群食物，同时，对第二种群中适应度坏于第一种群平均适应度的个体，也作为第一种群食物，作为食物的个体删除。按一定选择方式选择父代，交叉产生子代，进行变异；（3）处理第一个种群： 按一定方式分配由第三种群获取的食物，食物低于一定值的个体死亡、删除。然后，按一定选择方式选择父代，交叉产生子代，进行变异。（4）每个种群中的最好个体替代最差个体；所有种群中的最好个体分别替代每个种群中的最差个体。（5）计算适应度；（6）继续循环直至满足终止条件；4.输出优化的结果，算法结束。 算法采用的交叉方式为多点交叉，即随机选择一半的位串，在父代间交叉。采用的变异方式有：以位串平均值为准按比例上下随机浮动；以位串平均值为准，以取值范围一定比例随机上下浮动；以位串平均值为准，按方差上下随机浮动；以最每代最好个体位串值为准，按同样方式上下随机浮动以及高斯变异。算法中的交叉系数a，变异系数pm、种群规模等根据算法运行情况调整。 3.实验结果及分析通过相同数量个体下，分三种群协同进化和单种群进化进行对比。其他参数相同，个体总数为150。三个种群捕食关系为：pop1吃pop2，pop2吃pop3。在迭代代数为300，变异概率为0.3，交叉系数a为0.1参数下，对测试函数一进行优化，分别运行五次。最后的优化结果如下：classicga1: 3.515301e-017 classicga1: 4.811999e-017 classicga1: 6.306604e-018classicga1: 8.110289e-018 classicga1: 1.177726e-017foodchain1: 1.795252e-025 foodchain1: 1.803103e-025 foodchain1: 1.019144e-024foodchain1: 7.066503e-025 foodchain1: 1.062899e-024classicga2: 2.393638e-029 classicga2: 9.651748e-030 classicga2: 1.393717e-029classicga2: 3.456894e-029 classicga2: 2.568764e-029foodchain2: 1.739845e-026 foodchain2: 1.724897e-027 foodchain2: 5.407059e-026foodchain2: 2.292180e-025 foodchain2: 1.241327e-026classicga21: 1.513442e-022 classicga21: 4.744149e-022 classicga21: 7.380783e-023classicga21: 1.037500e-023 classicga21: 1.369897e-022foodchain21: 4.817046e-028 foodchain21: 9.183365e-029 foodchain21: 2.496357e-028foodchain21: 5.246736e-029 foodchain21: 3.771595e-029classicga22: 1.906018e-003 classicga22: 2.668078e-004 classicga22: 4.903648e-004classicga22: 9.686630e-005 classicga22: 1.767192e-004foodchain22: 2.749719e-004 foodchain22: 1.397267e-003 foodchain22: 1.435156e-005foodchain22: 2.618383e-005 foodchain22: 4.022535e-004其中：classicga代表一般的遗传算法，foodchain代表采用食物链的算法；序号1代表交叉方式为串位直接互换，变异方式为以位串平均值为准按比例上下随机浮动，种群间捕食方式为被捕食群体中低于捕食群体中最优个体适应度两倍。序号2在1基础上改变种群间捕食方式为被捕食群体中低于捕食群体平均适应度。序号21代表在2基础上改变交叉方式为实数交叉方式，按一定系数变化取值交叉；序号22代表在21基础上，改变变异方式为高斯变异。通过以上数据可以明显看出，在这几种方法下，分三种群按食物链方式竞争对提高结果的收敛速度有一定作用。然后对序号1算法加入同样的小于平均适应度淘汰机制，分析结果发现，其收敛速度快于加入食物链的方法。由此可知，采用的新方法的收敛性介于序号1的不淘汰方法和序号2的单种群淘汰方法之间。 对函数六进行优化，结果如下：foodchain2: 5.044213e+000 foodchain2: 2.965453e+000 foodchain2: 2.358099e+000foodchain2: 4.605018e+000 foodchain2: 5.390974e+000classicga2: 4.876047e+000 classicga2: 4.968353e+000 classicga2: 4.537115e+000classicga2: 5.672532e+000 classicga2: 5.952916e+000classicga1: 5.056437e+000 classicga1: 6.804616e+000 classicga1: 6.561508e+000classicga1: 6.528788e+000 classicga1: 5.657101e+000对函数十二进行优化，结果如下：foodchain2: 7.671139e-001 foodchain2: 7.902732e-001 foodchain2: 8.036008e-001foodchain2: 5.243947e-001 foodchain2: 3.423643e-001classicga2: 1.360849e+000 classicga2: 1.145134e+000 classicga2: 1.337375e+000classicga2: 1.063871e+000 classicga2: 5.237828e-001classicga1: 1.184714e+000 classicga1: 1.161197e+000 classicga1: 1.477536e+000classicga1: 1.053585e+000 classicga1: 1.279836e+000三种群的方法在这两个函数的优化中，结果明显较好，这说明三种群食物链的优化方法在一些复杂问题的优化效果上要好于单种群的优化方法。分析其原因，可能是由于基于食物链模式的三种群协作方式之间互相制约，各种群分工协作的结果。假设，pop2的平均适应度较高，则pop3种群淘汰率较高，从而使pop3在这一代就有较高的收敛性，同时由于pop3淘汰的多，pop2从pop3获取的食物足够多，种群中个体保存数量就越多，保证了pop2的种群多样性，有效的保证了对全局最优的搜索能力，在这种情况下，如果pop1平均适应度较低，食物不足，淘汰率就多，则pop1也具有较高收敛性，如果pop1平均适应度较高，则依然可以保证食物，使pop1具有保持种群多样性的能力。同时三个种群协作，更方便对每个种群使用不同的交叉和变异方式，以适应不同优化问题收敛和全局搜索要求。下面是对基于食物链模式的三种群协作方式的交叉变异方式改进后对其他一些函数进行优化的效果。4.对其他测试函数的优化考虑测试函数一：，这个测试函数具备最优值为零，最优解为零，各位最优解相同三个特点，这都属于特殊情况，我把这个函数改进后，变为：，这样最优解就变为（1,2，n）。通过搭配不同种群的高斯变异方式，t=exp(-gen/100);bound=avival;avival+dom*0.5;-0.5*ones(1,bn);newpop(1:popnum,1:bn)=gaussian_mutation(newpop(1:popnum,1:bn),pm,bound)%对种群三以最优五个个体的每个位串值的平均值为中心，以取值范围为范围作高斯扰动；if gengenmax/3,bound=dom*0.5;-0.5*ones(1,bn);newpop(popnum+1:3*popnum,1:bn)=gaussian_mutation(newpop(popnum+1:3*popnum,1:bn),pm,bound); 对种群三以最优个体的每个位串值为中心，以取值范围为范围作高斯扰动；elsebound=pop(minnum,1:bn);pop(minnum,1:bn)+dom*0.5;-0.5*ones(1,bn)*t;高斯扰动范围缩小做微调newpop(popnum+1:3*popnum,1:bn)=gaussian_mutation(newpop(popnum+1:3*popnum,1:bn),pm,bound);end求取最优值及最优解，迭代900次，运行五次结果如下（函数文件名foodchaincom24）：1.000535e+000 1.998628e+000 3.000666e+000 4.000945e+000 5.001641e+000 6.000294e+000 6.999452e+000 8.000164e+000 9.000570e+000 1.000036e+001 1.099905e+001 1.199995e+001 1.300082e+001 1.399802e+001 1.500093e+001 1.600051e+001 1.700028e+001 1.799789e+001 1.900130e+001 2.000036e+001 2.100041e+001 2.200032e+001 2.300085e+001 2.399982e+001 2.499926e+001 2.599957e+001 2.700049e+001 2.799936e+001 2.900011e+001 2.999928e+001; 2.296092e-005 1.002224e+000 2.002033e+000 3.001367e+000 4.002296e+000 5.000156e+000 6.001793e+000 7.000312e+000 7.995894e+000 9.000350e+000 9.999528e+000 1.099928e+001 1.200283e+001 1.299962e+001 1.400113e+001 1.499935e+001 1.599913e+001 1.699754e+001 1.799837e+001 1.900324e+001 2.000215e+001 2.100106e+001 2.200003e+001 2.300063e+001 2.400119e+001 2.499679e+001 2.599951e+001 2.700105e+001 2.800199e+001 2.900191e+001 2.999735e+001; 1.008800e-004 9.990165e-001 1.999304e+000 3.001063e+000 3.998800e+000 4.998648e+000 5.998688e+000 6.999040e+000 8.001043e+000 9.000862e+000 9.999494e+000 1.100214e+001 1.200157e+001 1.300057e+001 1.399932e+001 1.500144e+001 1.599825e+001 1.699841e+001 1.799913e+001 1.900108e+001 2.000166e+001 2.099951e+001 2.199858e+001 2.300092e+001 2.400042e+001 2.500057e+001 2.600022e+001 2.700224e+001 2.800206e+001 2.900018e+001 2.999864e+001; 4.559174e-005 1.000033e+000 1.996500e+000 3.002602e+000 3.996413e+000 4.999589e+000 6.000232e+000 7.000290e+000 8.001422e+000 8.999821e+000 9.999805e+000 1.100030e+001 1.199946e+001 1.300123e+001 1.399840e+001 1.500007e+001 1.600063e+001 1.700107e+001 1.800117e+001 1.899913e+001 1.999869e+001 2.100021e+001 2.200184e+001 2.299782e+001 2.399848e+001 2.500212e+001 2.600059e+001 2.700049e+001 2.799884e+001 2.900005e+001 2.999946e+001; 6.133224e-005 9.992472e-001 2.001992e+000 3.002017e+000 4.001626e+000 5.001180e+000 5.999469e+000 6.999992e+000 8.002034e+000 8.999343e+000 9.997772e+000 1.100076e+001 1.200237e+001 1.300078e+001 1.399838e+001 1.499815e+001 1.600067e+001 1.699794e+001 1.800656e+001 1.899641e+001 1.999765e+001 2.099964e+001 2.200039e+001 2.299993e+001 2.400217e+001 2.500194e+001 2.599802e+001 2.699596e+001 2.799808e+001 2.900101e+001 3.000285e+001; 1.432954e-004最优解误差范围在0.001左右，最优值误差数量级为0.00001。下面将函数一继续一般化，修改为+100，对函数的交叉选择方式改进为：t=exp(-gen/100);expfit=pop(1:popnum,bn+1)/t;expfit=expfit-min(expfit)+t;sumprob1=cumsum(expfit.(-1);即将适应度除以一个随代数逐渐缩小的参数t，以避免基数100对选择概率的影响。迭代900次，运行五次结果如下（函数文件名foodchaincom25）：9.998908e-001 2.001862e+000 2.998627e+000 4.000609e+000 4.998313e+000 6.003926e+000 7.013799e+000 8.000208e+000 8.998694e+000 9.987354e+000 1.099934e+001 1.199782e+001 1.300931e+001 1.400508e+001 1.499532e+001 1.600194e+001 1.699809e+001 1.799425e+001 1.899915e+001 1.999884e+001 2.099686e+001 2.199790e+001 2.299295e+001 2.400756e+001 2.499779e+001 2.600469e+001 2.699157e+001 2.800146e+001 2.900168e+001 2.999311e+001; 1.000008e+002 1.000405e+000 2.000193e+000 2.999447e+000 4.000421e+000 5.000631e+000 5.999752e+000 6.999878e+000 7.999913e+000 8.999680e+000 9.999722e+000 1.099965e+001 1.199982e+001 1.299980e+001 1.399972e+001 1.500005e+001 1.599948e+001 1.700047e+001 1.800020e+001 1.900026e+001 1.999991e+001 2.099974e+001 2.199995e+001 2.300057e+001 2.400062e+001 2.500002e+001 2.599987e+001 2.700019e+001 2.800061e+001 2.900019e+001 3.000011e+001; 1.000000e+002 1.000371e+000 2.000307e+000 2.999670e+000 3.999934e+000 4.999903e+000 5.999740e+000 6.998994e+000 8.000190e+000 9.000611e+000 1.000056e+001 1.099992e+001 1.199978e+001 1.300022e+001 1.400027e+001 1.499978e+001 1.599997e+001 1.699981e+001 1.800011e+001 1.900037e+001 2.000053e+001 2.099966e+001 2.200001e+001 2.299989e+001 2.400020e+001 2.499993e+001 2.600020e+001 2.699987e+001 2.800044e+001 2.899989e+001 3.000030e+001; 1.000000e+002 9.999186e-001 1.999828e+000 3.000088e+000 3.999592e+000 5.000686e+000 6.000030e+000 7.000279e+000 7.999719e+000 8.999861e+000 1.000037e+001 1.099919e+001 1.199925e+001 1.300029e+001 1.400086e+001 1.499924e+001 1.600028e+001 1.700016e+001 1.799982e+001 1.899993e+001 2.000010e+001 2.099967e+001 2.199927e+001 2.300063e+001 2.399989e+001 2.500000e+001 2.599983e+001 2.700068e+001 2.800028e+001 2.900048e+001 2.999964e+001; 1.000000e+0021.000108e+000 1.999725e+000 2.999225e+000 4.000051e+000 4.999727e+000 6.000210e+000 7.000090e+000 8.000274e+000 8.999705e+000 9.999894e+000 1.100028e+001 1.199974e+001 1.299992e+001 1.399983e+001 1.500024e+001 1.600013e+001 1.700030e+001 1.799966e+001 1.899939e+001 2.000041e+001 2.099965e+001 2.199996e+001 2.299994e+001 2.399938e+001 2.499970e+001 2.599979e+001 2.700010e+001 2.800011e+001 2.899926e+001 3.000017e+001; 1.000000e+002可见优化结果误差在0.0001以下。而且变异和交叉随代数变化的参数t一致，以方便调节。通过调节参数t和迭代代数gen，此方法可以很好的优化一些局部最优解就是全局最优解的函数优化问题。通过对20个函数进行测试，使用参数t=exp(-gen/100)，可以对函数1、2、4、6、7、9、11、12、13、14、16、17达到较好的优化效果，而且改变最优解位置和最优解值都不会影响算法的优化效果。对函数f15、f5，算法易陷入局部最优，说明算法的全局搜索能力有待改进。 对函数f15，用同样的食物链方式采用了不同的交叉变异方式编写程序进行优化。优化十次的结果如下：1.580438e-001 2.416381e+000 1.078715e+000 8.662021e-001; 6.724240e-0041.928463e-001 1.909046e-001 1.231885e-001 1.358267e-001; 3.074866e-0041.591676e-001 2.289273e+000 1.021616e+000 8.343526e-001; 6.626680e-0042.286899e-001 -4.116399e-001 3.164739e-016 -1.866079e-001; 4.460175e-0041.923051e-001 2.071334e-001 1.280509e-001 1.431971e-001; 3.079842e-0041.927640e-001 1.928847e-001 1.237368e-001 1.366991e-001; 3.074943e-0041.831855e-001 6.207852e-001 3.077401e-001 3.061440e-001; 4.131947e-0041.731852e-001 1.148033e+000 5.222885e-001 4.907948e-001; 5.264242e-0041.820283e-001 6.640751e-001 3.200571e-001 3.223491e-001; 4.233988e-004可见陷入局部最优的概率较大，只有0.3的概率找到最优解。但是，在实验中发现三种群可变化的策略和参数较多，由于时间所限，许多策略尚未进行尝试，相信通过一些收敛性能较好和全局搜索能力较好的策略的组合，可以找到适应欺骗性较大的测试函数的三种群遗传算法。此外，使用函数文件foodchaincom25算法对测试函数f11优化，100维时结果：-5.303419e-003 3.184086e-003 5.078061e-003 -1.035811e-003 -6.275223e-003 1.774169e-003 1.958596e-002 -1.909631e-002 1.452854e-002 2.293981e-002 4.937595e-002 4.363609e-003 4.587579e-002 7.476464e-002 -2.940075e-002 6.176152e-003 -1.014093e-002 6.389616e-003 -5.630374e-002 3.148974e-002 -1.057264e-003 3.378027e-002 -1.846562e-002 -1.333515e-003 -1.240639e-002 -2.892952e-002 7.345833e-002 -5.537798e-004 1.822834e-002 -1.558020e-002 -8.429851e-003 -5.129757e-002 1.126087e-001 -4.487050e-002 2.677885e-002 -3.358620e-002 1.173082e-001 7.128365e-002 3.848273e-002 -4.918911e-002 -4.089758e-002 -2.531578e-002 2.920673e-002 2.629595e-002 2.222572e-003 -7.647061e-003 2.406584e-003 -1.028581e-001 1.151639e-001 5.422928e-003 2.981802e-002 -2.300380e-002 -9.223894e-002 -5.512438e-002 5.443842e-002 -3.194004e-002 -4.042654e-003 9.004926e-002 1.652899e-001 -3.858518e-003 2.465630e-001 6.704669e-002 -4.405554e-002 -1.259725e-001 -1.760053e-002 1.262368e-002 -9.280966e-002 -1.630268e-001 -8.242919e-002 -4.789286e-002 3.153895e-003 9.889429e-003 -7.148740e-003 -1.218854e-001 7.968106e-002 -1.109885e-002 3.132322e-002 1.435489e-001 -1.412229e-001 -4.497986e-003 -1.108524e-001 -3.126451e-001 1.300540e-001 -1.155248e-001 -2.635043e-001 -6.189265e-002 3.030999e-001 4.341387e-002 -4.042581e-002 1.424756e-002 1.144918e-001 2.699507e-001 2.908979e-001 2.505504e-001 -6.239794e-002 1.968862e-002 -2.214921e-001 1.380143e-001 -2.511483e-001 2.074968e-001; 7.800256e-003。 1000维时结果：1.4447。每一位数据见电子文档。5.结论通过上述对基于食物链模式的三种群协作遗传算法的实验，说明该方法具有较大的灵活性，可以通过不同的策略组合调整算法的性能，从而使其在许多函数的优化问题上效果由于单种群的遗传算法。在实验中，尝试了一些策略的组合，但许多的方法组合并未尝试，例如均匀变异、边界变异、非均匀变异、柯西变异，二进制编码，同样三种群的差分演化，三种群群体规模不同和交叉选择的一些其他方法等等，而且算法并没有在实际的优化问题上进行测试，因此，对该算法效果还没有认识充分，需要进一步的实验。论文中一定存在许多问题，请批评指正，谢谢。6.参考文献【1】曾孝平,张晓娟,李勇明 多子群协同链式智能体遗传算法分析重庆大学学报 第31 卷第7 期2008 年7 月【2】喻海飞1, 汪定伟2食物链算法及其与实编码遗传算法性能比较研究系统工程理论与实践第6 期 2007 年6 月7.附录课程论文相关的matlab文件有：适应度计算fit.m，高斯变异gaussian_mutation.m，不同方式的算法文件：calassicgacom1.m, calassicgacom2.m, calassicgacom21.m, calassicgacom22.m,foodchaincom1.m, foodchaincom2.m, foodchaincom21.m, foodchaincom22.m, foodchaincom25.m,minfunction15以及1000维的数据文件1000维结果。函数文件foodchaincom25matlab源代码：function foodchain25; clearclcbn=30; popnum=50; genmax=900; pm=0.3; dom=200; a=0.1; gen=1; inpop=dom*(rand(3*popnum,bn+1)-0.5*ones(3*popnum,bn+1);for i=1:3*popnum, inpop(i,bn+1)=fit(inpop(i,1:bn);end minfit1,minnum1=min(inpop(1:popnum,bn+1);minfit2,minnum2=min(inpop(popnum+1):2*popnum,bn+1);minfit3,minnum3=min(inpop(2*popnum+1):3*popnum,bn+1);minnum=minnum1 popnum+minnum2 2*popnum+minnum3;minshu=inpop(minnum,:); pop=inpop;while(gen=mean2, newpop(i,:)=10000*ones(1,bn+1); food2=food2+1; endendif food2=45,expfit=pop(2*popnum+1:3*popnum,bn+1)/t;expfit=expfit-min(expfit)+t; sumprob3=cumsum(expfit.(-1); for m=(2*popnum+1):2:3*popnum,i=1;r=rand;while(i=popnum)if r=(sumprob3(i)/sumprob3(popnum), fanum=i+2*popnum; i=10000;%endi=i+1;end%r=rand;i=1;while(i=popnum)if r=mean1, food1=food1+1; newpop(i+popnum),:)=10000*ones(1,bn+1); endendfor i=(sur2+1):popnum, newpop(i+popnum),:)=10000*ones(1,bn+1);end% if food1=45,% sumprob2=cumsum(pop(popnum+1):2*popnum,bn+1).(-1);% sumprob=cumsum(prob.*prob.*prob);expfit=pop(popnum+1:2*popnum,bn+1)/t;expfit=expfit-min(expfit)+t; sumprob2=cumsum(expfit.(-1); for m=(popnum+1):2:2*popnum,i=1;r=rand;while(i=popnum)if r=(sumprob2(i)/sumprob2(popnum), fanum=i+popnum;i=10000;endi=i+1;end%r=rand;i=1;while(i=popnum)if r=(sumprob2(i)/sumprob2(popnum), monum=i+popnum;i=10000;endi=i+1;end% son=pop(fanum,:);dau=pop(monum,:);for j=1:(bn/2), changepoint=ceil(bn*rand); son(changepoint)=a*pop(monum,changepoint)+(1-a)*pop(fanum,changepoint); dau(changepoint)=a*pop(fanum,changepoint)+(1-a)*pop(monum,changepoint);endnewpop(m,:)=son;newpop(m+1,:)=dau;end% for l=1:bn,tenfitmax,tenfitnum=sort(newpop(popnum+1):2*popnum,bn+1);k=0;for m=1:5, tenfit(m,l)=pop(tenfitnum(m),l); sumval=k+pop(popnum+tenfitnum(m),l); k=sumval;endavival(l)=sumval/5;tenfit(:,l);tenstd(l)=std(tenfit(:,l),1); end else newpop(popnum+1):2*popnum,:)=dom*(rand(popnum,bn+1)-0.5); end minavifood1=1; sur1=fix(food1/minavifood1); sortfit1,sortfitnum=sort(pop(1:popnum,bn+1);for i=1:sur1, newpop(i,:)=pop(sortfitnum(i),:);endfor i=(sur2+1):popnum, newpop(i,:)=10000*ones(1,bn+1);end % sumprob1=cumsum(pop(1:popnum,bn+1).(-1);% sumprob=cumsum(prob.*prob.*prob);expfit=pop(1:popnum,bn+1)/t;expfit=expfit-min(expfit)+t; sumprob1=cumsum(expfit.(-1); for m=1:2:popnum,i=1;r=rand;while(i=popnum)if r=(sumprob1(i)/sumprob1(popnum), fanum=i;i=10000;endi=i+1;end%r=rand;i=1;while(i=popnum)if r=(sumprob1(i)/sumprob1(popnum), monum=i;i=10000;endi=i+1;end% son=pop(fanum,:);dau=pop(monum,:);for j=1:2, changepoint=ceil(bn*rand); son(changepoint)=a*pop(monum,changepoint)+(1-a)*pop(fanum,changepoint); dau(changepoint)=a*pop(fanum,changepoint)+(1-a)*pop(monum,changepoint);endnewpop(m,:)=son;newpop(m+1,:)=dau;end%minfit1,minnum1=min(pop(1:po