毕业论文移动版

在传统算法中，例如排序算法通过诸如快速排序、冒泡排序等排序方法来优化问题，搜索算法则是通过索引等方法，而进化算法仿佛是打开了新世界的大门，首次将大自然的生存法则运用到现实的优化问题中。进化算法的三大发展方向上，进化策略和进化规划都主要强调对于子代的选择上，从最初问题得到初级最优解，再由初级最优解一步步迭代直至终极最优解，这与动态规划有异曲同工之处，虽然很大程度上降低了时间复杂度，但是它们与动态规划都有相似的缺陷，那就是，往往最终的结果极有可能是局部最优而并非是我们所要的全局最优。相较于遗传算法近乎完备的基础理论知识，另外两者的理论储备也或多或少在很大因素上束缚了二者的发展。遗传算法相对于前两者更强调对父代的选择，在父代到子代的遗传过程中，遗传方式使用了交叉、变异操作来反复改变父代个体的多样性，这样的操作无疑大大降低了算法收敛到局部最优解的可能性，所以在进化算法的发展过程中，遗传算法取代进化策略和进化规划成为进化算法的主流就是大势所趋了。

遗传算法由于借鉴了遗传学的部分原理，因此，诸如染色体、基因、基因位点也被用来指代相关参数。例如，染色体表示用二进制编码的问题的其中一解，基因（用0或1代表）表示的是个体，通过基因位点可获得对应个体的值。遗传算法的基本思路是，用二进制编码问题的所有解得到N个染色体，用适应度函数分别计算每个染色体的适应度值，然后开始进

行选择操作。假设第i个染色体的适应度值为(i=1,2,…,N),那么在选择操作中，我们常常引入选择概率进行此操作，我们先要计算每个染色体的选择概率(i=1,2,…,N),

       i=(1,2,…,N)

选择概率作为一种表示方法可以很直观看出，概率低的染色体在接下来的操作中被选择的概率要明显小于概率高的染色体。在得到选择概率后随机选择多个个体组成新的群体，其规模大小保持不变，接下来开始交叉操作。就像生物界中物种进化的重要因素是基因的重组和变异，而交叉操作就是遗传算法的重中之重。在交叉操作中，我们通过交叉概率从当前个体中随机任取相应个目标个体，然后再随机选取交叉点，最后两两染色体的基因编码再根据交叉点互换位置进而得到新的染色体，其余的保持原样。经过选择和交叉操作确实可以产生具有最高平均适应度值的种群，但是也同时会陷入局部最优解的问题，因此，除了交叉和选择操作，遗传算法引入了变异操作使其避免收敛至局部最优解，并维持种群个体不断更新变化。变异操作引入了变异概率，变异概率的值对算法的搜索能力有很大影响，往往不能过大也不能过小。因此根据变异概率我们可以凭此判断所有个体中哪些染色体是否需要变异，需要进行变异的个体我们会任意地选择其基因位然后开始相关操作。虽然遗传算法的效率比传统的优化算法低，有效的控制参数难以确定，但遗传算法对之后的研究者影响深远，应该说，后来的DE算法的发展更多受到了遗传算法的影响。

粒子群优化算法[3]（Particle Swarm optimization,PSO）作为进化算法的一种，是一种通过模拟鸟类群体的觅食活动发展的并行的群智能算法。在一个空间内，一群鸟儿在寻找一块食物，它们都不清楚食物的具体位置，唯一可以确定的是这些鸟儿知道那块食物离自己有多长距离。所以，粒子群优化算法的主要思想就是，在当前最优解的附近区间内不断去搜索问题的全局最优值。粒子群算法的操作比遗传算法要简单，它通过不断改变粒子的位置来取代遗传算法的变异和交叉过程，同时算法会记录下初始最优位置和每个粒子的历史最优位置，速度因子被引入作为每个粒子改变方向和距离的决定因素。可以看出，粒子群算法中每个粒子是根据当前自己的最优解和整个种群的种群的最优解来选择靠拢，这种选择往往是单向的不像遗传算法是均匀的，但是，这样的好处是其收敛至全局最优解的效率比遗传算法要高。 (责任编辑：qin)