论文部分内容阅读
摘 要：遗传算法具有"早熟收敛"的缺点，所以利用最速下降法对遗传算法进行改进。定义适当的适应度函数和子代个体的选择算子，结合遗传算法和最速下降法两者的长处，得到既有较快收敛性，又能以较大概率得到全局极值的新的用于连续函数全局优化的混合数值算法。数值计算结果表明了本文方法显著优于求解函数优化的遗传算法和最速下降法。
关键词：遗传算法 最速下降法 函数优化 适应度
Abstract：Genetic algorithm has the shortcoming of "premature convergence"，so using the steepest descent method to improve the genetic algorithm.A proper fitness function and a selecting operator for son generation are defined，a hybrid algorithm for global optimization of continuous function，combined the advances of both of genetic algorithm and steepest decent algorithm，is got with fast convergence and great probability for global optimization.The nuerical computing results shown that the method is distinctly superior to the genetic algorithm and steepest decent algorithm.
Keywords：genetic algorithm； steepest decent algorithm； function optimization ； fitness
1. 引言
遗传算法（Genetic Algorithm）是由美国Michigan大学J.Holland教授提出来的基于达尔文适者生存、优胜劣汰的进化原则，对包含可能解的群体反复使用遗传学的基本操作，使种群不断进化的一种优化算法。其主要优点是简单、鲁棒性强。但GA存在的问题是：在进化后期，群体包含的大多数个体的适应值接近最優解，以致实际上缺乏竞争，使选择过程变慢，当进化过程足够慢时，就进入“早熟收敛”状态。显然，这个状态对应的最优个体只是一个可行解，它也许不是全局最优点，甚至不是局部最优点。
综合以上GA存在的问题，本文采用最速下降法帮助离开“早熟收敛”状态。其基本思想是在每次迭代中增加一个最速下降算子，对群体中的任一个体进行一次微调。其结果是，算法可能跳出这个“早熟收敛”状态，而进入另一个“早熟收敛”状态，并且每一次迭代中，由于都要进行编码和解码的操作，将影响算法的收敛速度。作为一种尝试，本文把最速下降法与改进的GA相结合，提出一种新的混合优化算法。
2 基于最速下降法和遗传算法的函数优化混合数值算法
最速下降法的迭代路线呈锯齿形，求得的是局部最优解，我们可以利用它的局部性质，针对遗传算法的“早熟收敛”这一特点进行改进，使得遗传算法避免“早熟收敛”。
本文提出的混合算法如下：
1.随机产生初始父代群体并计算其适应度
2.对初始父代群体的每个个体进行编码
3.Repeat
4. 选择群体中两个个体以概率Pc进行编码、杂交、解码运算，将父代和子代都加入新的子代群体
5. 对新的子代群体中每个个体以概率Pm进行编码、变异、解码运算，将父代和子代都加入新的子代群体
6. 对新的子代群体中每个个体以概率Ps计算f（xk），并进行线性搜索xk+1=xk+λkdk，将子代取代父代加入新的子代群体
7. 对每个个体计算适应度，以既定的群体规模选择下一次繁殖的子代群体（适者繁值，不适者被淘汰）
8.Until（结束迭代逻辑条件满足）
2.1 适应度函数定义
由于待优化的函数f（x）的值可正可负，而适应度函数需恒为正。因此，本文的上述混合算法的适应度函数g（x）定义为当个体的函数值大于0时g（x）=f（x）；若个体的函数值不大于0时g（x）=0。这样就保证了个体的适应值均是大于0的。
2.2 线性搜索算子
为了加速遗传算法在连续可微函数全局优化问题上的收敛性，发挥传统数值优化算法在计算速度与计算精度上的优势，本文混合算法中嵌入了一个最速下降算子。该最速下降算子主要进行的是传统最速下降法中的线性搜索运算。
3.数值测试及结果分析
本节考虑如下连续可微函数的有限区间的全局极值问题
f=10*sin（5*x）+7*cos（4*x）；（0≤x≤10）
该函数极大值点在1.6和7.9附近取得，最值约为17。
3.1 单纯遗传算法和混合算法最值测试比较
由以下表4.1所示五组数据，可以看出遗传算法寻找最值，重复较多的次数才能找到接近真实最值的结果。而混合算法寻找最值重复较少的次数就找到接近真实最值的结果，并且其结果整体较遗传算法优。
3.2 结论及分析
本文利用遗传算法中杂交（crossover）算子、变异（mutation）算子和选择算子在全变量空间，以较大概率搜索全局极值的特点，以及函数数值优化中最速下降法收敛快、计算数值精度高的特点，给出了一个适用于函数数值优化的混合优化算法。
参考文献：
[1]孙文瑜，徐成贤，朱德通.最优化方法[M].北京：高等教育出版社，2010.07.
[2]马昌凤.最优化方法及其Matlab程序设计[M].北京：科学出版社，2010.
[3]袁亚湘，孙文瑜.最优化理论与方法[M].北京：科学出版社，1999.05.
[4]赵明旺.基于遗传算法和最速下降法的函数优化混合数值算法[J].系统工程理论与实践，1999.07.
[5]郭成，李连庆.遗传算法的Matlab7.0程序实现[J].江苏： 淮海工学院学报，2010.09.
[6]葛继科，邱玉辉，吴春明，蒲国林.遗传算法研究综述[J].计算机应用研究，2008.10.
[7]马永杰，云文霞.遗传算法研究进展[J].计算机应用研究，2012.04.
关键词：遗传算法 最速下降法 函数优化 适应度
Abstract：Genetic algorithm has the shortcoming of "premature convergence"，so using the steepest descent method to improve the genetic algorithm.A proper fitness function and a selecting operator for son generation are defined，a hybrid algorithm for global optimization of continuous function，combined the advances of both of genetic algorithm and steepest decent algorithm，is got with fast convergence and great probability for global optimization.The nuerical computing results shown that the method is distinctly superior to the genetic algorithm and steepest decent algorithm.
Keywords：genetic algorithm； steepest decent algorithm； function optimization ； fitness
1. 引言
遗传算法（Genetic Algorithm）是由美国Michigan大学J.Holland教授提出来的基于达尔文适者生存、优胜劣汰的进化原则，对包含可能解的群体反复使用遗传学的基本操作，使种群不断进化的一种优化算法。其主要优点是简单、鲁棒性强。但GA存在的问题是：在进化后期，群体包含的大多数个体的适应值接近最優解，以致实际上缺乏竞争，使选择过程变慢，当进化过程足够慢时，就进入“早熟收敛”状态。显然，这个状态对应的最优个体只是一个可行解，它也许不是全局最优点，甚至不是局部最优点。
综合以上GA存在的问题，本文采用最速下降法帮助离开“早熟收敛”状态。其基本思想是在每次迭代中增加一个最速下降算子，对群体中的任一个体进行一次微调。其结果是，算法可能跳出这个“早熟收敛”状态，而进入另一个“早熟收敛”状态，并且每一次迭代中，由于都要进行编码和解码的操作，将影响算法的收敛速度。作为一种尝试，本文把最速下降法与改进的GA相结合，提出一种新的混合优化算法。
2 基于最速下降法和遗传算法的函数优化混合数值算法
最速下降法的迭代路线呈锯齿形，求得的是局部最优解，我们可以利用它的局部性质，针对遗传算法的“早熟收敛”这一特点进行改进，使得遗传算法避免“早熟收敛”。
本文提出的混合算法如下：
1.随机产生初始父代群体并计算其适应度
2.对初始父代群体的每个个体进行编码
3.Repeat
4. 选择群体中两个个体以概率Pc进行编码、杂交、解码运算，将父代和子代都加入新的子代群体
5. 对新的子代群体中每个个体以概率Pm进行编码、变异、解码运算，将父代和子代都加入新的子代群体
6. 对新的子代群体中每个个体以概率Ps计算f（xk），并进行线性搜索xk+1=xk+λkdk，将子代取代父代加入新的子代群体
7. 对每个个体计算适应度，以既定的群体规模选择下一次繁殖的子代群体（适者繁值，不适者被淘汰）
8.Until（结束迭代逻辑条件满足）
2.1 适应度函数定义
由于待优化的函数f（x）的值可正可负，而适应度函数需恒为正。因此，本文的上述混合算法的适应度函数g（x）定义为当个体的函数值大于0时g（x）=f（x）；若个体的函数值不大于0时g（x）=0。这样就保证了个体的适应值均是大于0的。
2.2 线性搜索算子
为了加速遗传算法在连续可微函数全局优化问题上的收敛性，发挥传统数值优化算法在计算速度与计算精度上的优势，本文混合算法中嵌入了一个最速下降算子。该最速下降算子主要进行的是传统最速下降法中的线性搜索运算。
3.数值测试及结果分析
本节考虑如下连续可微函数的有限区间的全局极值问题
f=10*sin（5*x）+7*cos（4*x）；（0≤x≤10）
该函数极大值点在1.6和7.9附近取得，最值约为17。
3.1 单纯遗传算法和混合算法最值测试比较
由以下表4.1所示五组数据，可以看出遗传算法寻找最值，重复较多的次数才能找到接近真实最值的结果。而混合算法寻找最值重复较少的次数就找到接近真实最值的结果，并且其结果整体较遗传算法优。
3.2 结论及分析
本文利用遗传算法中杂交（crossover）算子、变异（mutation）算子和选择算子在全变量空间，以较大概率搜索全局极值的特点，以及函数数值优化中最速下降法收敛快、计算数值精度高的特点，给出了一个适用于函数数值优化的混合优化算法。
参考文献：
[1]孙文瑜，徐成贤，朱德通.最优化方法[M].北京：高等教育出版社，2010.07.
[2]马昌凤.最优化方法及其Matlab程序设计[M].北京：科学出版社，2010.
[3]袁亚湘，孙文瑜.最优化理论与方法[M].北京：科学出版社，1999.05.
[4]赵明旺.基于遗传算法和最速下降法的函数优化混合数值算法[J].系统工程理论与实践，1999.07.
[5]郭成，李连庆.遗传算法的Matlab7.0程序实现[J].江苏： 淮海工学院学报，2010.09.
[6]葛继科，邱玉辉，吴春明，蒲国林.遗传算法研究综述[J].计算机应用研究，2008.10.
[7]马永杰，云文霞.遗传算法研究进展[J].计算机应用研究，2012.04.