离散变量多群体演化算法的研究

《离散变量多群体演化算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南京邮电大学硕士研究生学位论文第一章绪论遗传算法是基于“适者生存，优胜劣汰”的生物进化原理而发展起来的一种高效的全局随机搜索技术，最早由美国密执安大学的Holland教授提出，后来人对遗传算法的数学理论和搜索机理又进行了补充研究，并成功求解了多个领域的优化问题。遗传算法中，待优化的矢量称为个体（染色体），多个个体组成一个种群，通过选择、交叉、变异三种遗传操作使种群不断进化。首先针对问题的优化目标，设计一个合理的评价函数，它的好坏对算法的优化结果和求解效率有很大影响。所有个体进行统一评价后，利用选择算子挑选出部分评价值高的个体作为父本繁衍下一代，即遵循选取概率与个体适应值成正比关系的

2、原则，使优秀的父本生成的下一代种群在整体上优于当前代。常用的选择算子有轮盘赌选择、随机遍历抽样、局部选择、截断选择、锦标赛选择等等，根据具体的优化问题挑选不同的算子。选中的个体放入交配池，按照概率进行交叉操作。交叉率的设置对于算法性能至关重要，过大容易破坏已形成的优良基因结构以致难以找到最优解，过小进化过程缓慢不利于算法收敛，根据经验交叉率通常设置在0.6~0.9之间。未能交叉的父体则直接复制进入下一代。交叉类似于生物进化过程中的有性繁殖，将两个父体的部分基因结构进行互换重组而形成两个新的个体，它是遗传算法产生新个体的主要方式，交叉后产生的新个体将取代父体种群数保持不变。变异运算引

3、入新的基因引导算法进行全局搜索，它是产生后代的另一种途径，类似于生物进化中的无性繁殖。对交叉后的个体按照概率执行变异操作，变异率通常设在0.01~0.1之间，因为太大的变异率会使算法趋于完全随机搜索而无法收敛，过小的变异率又因为种群多样性不够而进入早熟收敛。随机地指定变异个体的某个基因位作为突变点，对该点上的基因值按照一定规则调整。对二进制变异来说，该点值原为0的变为1，为1的变为0。而实值变异则根据运算式，将当前值向范围上界或下界方向随机调整。至此就完成了一次进化过程，形成了新一代种群。若该种群中的某个个体及其适应值满足问题设定的目标条件，则输出该个体并停止迭代，否则继续进行下一

4、轮的遗传操作及终止条件判断，如此重复直至达到最大迭代次数强行终止。[14][15](2)粒子群算法粒子群算法是1995年由Eberhart博士和Kennedy博士提出的一种群智能算法，源于对鸟群和鱼群觅食行为的研究，对复杂的连续优化问题具有良好的优化效果。1997年他们又提出了粒子群算法的二进制版本，这样应用又延伸到离散变量领域。由于PSO原理简单、程序实现简洁、参数少且容易调节而得到人们的青睐，已经在诸多领域实现了应用，并不断有人提出其新的改进版本。5南京邮电大学硕士研究生学位论文第一章绪论粒子群算法中把研究对象看成一个个“粒子”，该粒子具有位置和速度两个属性。位置矢量的每一维对

5、应着问题中待优化的各个参量，速度与位置同维数，它是运行中得到的一个中间矢量。粒子群算法区别于其他演化算法的一个特点就是每个粒子具有记忆功能，记录着自己迄今为止搜索到的最优位置，以及整个种群目前找到的最优位置，分别称为个体极值和全局极值，在每次迭代中，粒子就通过跟踪这两个极值来更新自身的速度和位置。对于当前种群中的每个粒子，其速度更新由三部分组成：①当前速度与惯性权重的乘积，这表示粒子的运动习惯。惯性权重一般设在0.4~0.9之间，大则利于全局寻优，小则倾向于局部搜索。通常做法是先将惯性权重设在最大值0.9，然后随着迭代次数的增加逐渐衰减到0.4，即先进行大范围搜索确定最优解所在区域

6、，接着慢慢地在最优解周围进行精细搜索以提高获得解的精度；②自身位置与个体极值的差乘上学习因子及比例系数，这项表示粒子的认知能力，即往日的经验对现在行为的指导作用；③自身位置与全局极值的差乘上学习因子和比例系数，该项表征粒子的协同合作能力，即同伴的经验对自身行为也具有重要的指导意义。这三部分累加便得到了粒子的更新速度，②③项中的学习因子一般设为2。之后更新速度加上当前的位置即得到粒子的更新位置。用评价函数对更新后的所有粒子进行评价，根据适应值情况对各粒子的个体极值进行更新，并将所有粒子中最优的个体极值与当前全局极值相比，若个体极值的适应度更好，则对应粒子的位置成为新的全局极值。通过这

7、样一代代地更新，整个种群的粒子逐渐向着全局最优解的方向靠拢，直至满足某种截止条件算法终止，最后的全局极值即为算法找到的最优解。[16](3)差分演化算法1995年由Storn和Price两位学者提出的差分演化算法是一种新兴的群智能并行搜索技术，算法的初衷只是用于求解切比雪夫多项式问题，但后来尝试求解复杂的多维函数并获得了成功，由此证明差分演化算法具有通用性，能用于各类优化问题的求解。与其他算法相比，DE能自动收缩具有极优的全局收敛能力，已被广泛应用到众多工程实践和科学