遗传算法与函数优化

《遗传算法与函数优化》由会员分享，可在线阅读，更多相关《遗传算法与函数优化（14页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章 遗传算法与函数优化遗传算法与函数优化4.1 研究函数优化的必要性：首先，对很多实际问题进行数学建模后，可将其抽象为一个数值函数的优化问题。由于 问题种类的繁多，影响因素的复杂，这些数学函数会呈现出不同的数学特征。除了在函数是 连续、可求导、低阶的简单情况下可解析地求出其最优解外，大部分情况下需要通过数值计 算的方法来进行近似优化计算。其次，如何评价一个遗传算法的性能优劣程度一直是一个比较难的问题。这主要是因为 现实问题种类繁多，影响因素复杂，若对各种情况都加以考虑进行试算，其计算工作量势必 太大。由于纯数值函数优化问题不包含有某一具体应用领域中的专门知识，它们便于不同应 用领域中

2、的研究人员能够进行相互理解和相互交流，并且能够较好地反映算法本身所具有的 本质特征和实际应用能力。所以人们专门设计了一些具有复杂数学特征的纯数学函数，通过 遗传算法对这些函数的优化计算情况来测试各种遗传算法的性能。4.2 评价遗传算法性能的常用测试函数在设计用于评价遗传算法性能的测试函数时，必须考虑实际应用问题的数学模型中所可 能呈现出的各种数学特性，以及可能遇到的各种情况和影响因素。这里所说的数学特性主要 包括：连续函数或离散函数；凹函数或凸函数；二次函数或非二次函数；低维函数或高维函数；确定性函数或随机性函数；单峰值函数或多峰值函数，等等。下面是一些在评价遗传算法性能时经常用到的测试函数：

3、(1)De Jong 函数 F1：这是一个简单的平方和函数，只有一个极小点f1(0, 0, 0)0。(2)De Jong 函数 F2：这是一个二维函数，它具有一个全局极小点f2(1，1) = 0。该函数虽然是单峰值的函数， 但它却是病态的，难以进行全局极小化。(3)De Jong 函数 F3：这是一个不连续函数，对于区域内的每一个点，它都取全局极小值0 . 5,12. 5ix。30),(543213xxxxxf(4)De Jong 函数 F4：这是一个含有高斯噪声的 4 次函数，当不考虑噪声的影响时，它具有一个全局极小值 f4(0，0，0)0。(5)De Jong 函数 F5：这是一个多峰值函

4、数，它总共有 25 个局部极小点，其中有一个是全局极小点，全局极 小值为f5(-32，-32)0.998。(6)Shaffer 函数 F6：该函数在其定义域内只具有一个全局极小点f6(0，0)0。(7)Shaffer 函数 F7：该函数在其定义域内只具有一个全局极小点f7(0，0)0。(8)Goldstein-Price 函数：该函数在其定义域内只具有一个全局极小点f(0，-1)3。(9)Shubert 函数：这是一个多峰值函数，在其定义域内它总共有 760 个局部最小点，其中的 18 个点是全 局最小点，全局最小值为f-186.731。(10)六峰值驼背函数（Six-hump Camel B

5、ack Function）：该函数共有六个局部极小点，其中(-0.0898，0.7126)和(0.0898，-0.7126)为全局最小 点，最小值为f(-0.0898，0.7126) f(0.0898，-0.7126) -1.031628。(11)带有复杂约束条件的函数(之一)：该函数的全局最小点为：f(1，1，1，1，1，1，1，1，3，3，3，1) = -15。(12)带有复杂约束条件的函数(之二)：该函数的全局最大点为：f(1，0，0) = 2.471428。4.3 De Jong 的研究结论De Jong 用来进行函数优化问题研究的研究对象是前面所介绍的 De Jong 测试函数 F1

6、F5。他采用了下面的一些研究方法：1编码方法用二进制编码符号串来表示个体。2算法的影响参数群体大小 M；交叉概率pc； 变异概率pm； 代沟 G。3算法种类(子代群体复制策赂)R1：基本遗传算法(比例选择、单点交叉、基本位变异)；R2：保留最佳个体模型；R3：期望值模型；R4：保留最佳期望值模型；R5：排挤因子模型；R6：广义交叉模型。群体规模对等位基因损失的影群体规模对等位基因损失的影 响（优化策略为响（优化策略为 R1，测试函，测试函 数为数为 F1）群体规模对离线性能的影响群体规模对离线性能的影响 （优化策略为（优化策略为 R1，测试函数，测试函数 为为 F1）群体规模对在线性能的影响群

7、体规模对在线性能的影响 （优化策略为（优化策略为 R1，测试函数，测试函数 为为 F1）变异概率对等位基因损失的影变异概率对等位基因损失的影 响（优化策略为响（优化策略为 R1，测试函，测试函 数为数为 F1）变异概率对离线性能的影响变异概率对离线性能的影响 （优化策略为（优化策略为 R1，测试函数，测试函数 为为 F1）变异概率对在线性能的影响变异概率对在线性能的影响 （优化策略为（优化策略为 R1，测试函数，测试函数 为为 F1）优化策略优化策略 R1，R2，R3 在基因在基因 损失方面的性能比较（测试函损失方面的性能比较（测试函 数为数为 F1）优化策略优化策略 R1，R2，R3 的离线

8、的离线 性能比较（测试函数为性能比较（测试函数为 F1）经过仔细分析和计算，De Jong 得到了下述几条重要的结论：结论 1群体的规模越大，遗传算法的离线性能越好，越容易收敛。结论 2规模较大的群体，遗传算法的初始在线性能较差；而规模较小的群体，遗传算法的初始 在线性能较好。结论 3虽然变异概率的增大也会增加群体的多样性，但它却降低了遗传算法的离线性能相在线 性能，并且随着变异概率的增大，遗传算法的性能越来越接近于随机搜索算法的性能。结论 4使用保留最佳个体模型或期望值模型的遗传算法比基本遗传算法的性能有明显的改进。结论 5对于广义交叉算子，随着交叉点数的增加会降低遗传算法的在线性能和离线性

9、能。这些结论在遗传算法的开发研究和实际应用中具有重要的指导意义。4.4 多目标优化多目标优化问题一般可描述为下面的数学模型：优化策略优化策略 R1，R2，R3 的在线的在线 性能比较（测试函数为性能比较（测试函数为 F1）排挤因子对离线性能的影响排挤因子对离线性能的影响 （优化策略为（优化策略为 R5，测试函数为，测试函数为 5）式中，V-min 表示向量极小化，即向量目标中的各个子目标函数都尽可能地极小化的意思。多目标优化问题的难点在于，在很多情况下，各个子目标有可能是相互冲突的，一个子 目标的改善有可能会引起另一个子目标性能的降低，也就是说，要同时使这多个子目标都一 起达到最优值是不可能的

10、，而只能是在它们中间进行协调和折衷处理，使各个子目标函数都 尽可能地达到最优。多目标优化问题的最优解与单目标优化问题的最优解有着本质上的不同，所以为了正确 地求解多目标优化问题，必须对其最优解的概念进行定义。定义：设是多目标优化模型的约束集，是多目标优化时的向量目标函mRX pRxf)(数， 。XxXx21,)()(21xfxfkk), 2 , 1(pkL并且)()(21xfxfkk), 2 , 1(pkL则称解x1比解x2优越。定义：设是多目标优化模型的约束集，是向量目标函数，若，mRX pRxf)(Xx *并且x*比 X 中的所有其他点都优越，则称x*是多目标极小化模型的最优解。由该定义可

11、知，多目标优化问题的最优解x*就是使向量目标函数f(x)的每一个子目标函 数都同时到达最优点的解，如图所示。显然，在大多数情况下*多目标优化问题的最优解是 不存在的。定义：设是多目标优化模型的约束集，是向量目标函数，若，mRX pRxf)(Xx 并且不存在比更优越的x，则称为多目标极小化模型的 Pareto 最优解，或称为非劣解。xx由该定义可知，多目标优化问题的 Pareto 最优解仅仅只是它的一个可以接受的“不坏” 的解，并且通常的多目标优化问题大多都具有很多个 Pareto 最优解，如图所示。由上述三个定义可知，着一个多目标优化问题存在最优解的话、则这个最优解必定是 Pareto 最优解

12、，并且 Pareto 最优解也只由这些最优解所组成，再不包含有其他解。所以可 以这么说，Pareto 最优解是多目标优化问题的合理的解集合。求解多目标优化问题的遗传算法对于如何求多目标优化问题的 Pareto 最优解，目前已经提出了多种基于遗传算法的求 解方法。下面介绍其中几种主要的方法。1权重系数变化法对于一个多目标优化问题，若给其各个子目标函数fi(x)，(i1，2，p)，赋予不 同的权重wi(i1，2，p)，其中各wi的大小代表相应子目标fi(x)在多目标优化问题中 的重要程度。则各个子目标函数的线性加权和可表示为：若以这个线性加权和作为多目标优化问题的评价函数，则多目标优化问题就可转化

13、为单 目标优化问题。权重系数变化法就是在这个评价函数的基础上，对每个个体取不同的权重系 数，就可以利用通常的遗传算法来求出多目标优化问题的多个 Pareto 最优解。2并列选择法并列选择法的基本思想是：先将群体中的全部个体按子目标函数的数目均等地划分为一 些子群体，对每个子群体分配一个子目标函数各个子目标函数在其相应的子群体中独立地 进行选择运算，各自选锋出一些适应度较高的个体组成一个新的子群体，然后再将所有这些 新生成的子群体合并为一个完整的群体，在这个完整的群体中进行交叉运算和变异运算，从而生成下一代的完整群体，如此这样 不断地进行“分割并列选择合并。过程，最终可求出多目标优化问题的 Pa

14、reto 最 优解。这种方法很容易产生个别子目标函数的极端最优解，而要找到所有目标函数在某种程度 上较好的协调最优解却比较困难。3排序选择法排序选择法的基本思想是：基于“Pareto 最优个体”的概念来对群体中的各个个体进行 排序，依据这个排列次序来进行进比过程中的选择运算从而使得排在前面的 Pareto 最优 个体将有更多的机会遗传到下一代群体中。如此这样经过一定代数的循环之后，最终就可求 出多目标优化问题的 Pareto 最优解。这里所谓的 Pareto 最优个体，是指群体中的这样一个或一些个体，群体中的其他个体 都不比它或它们更优越。需要说明的是，在群体进化过程个所产生的 Pareto

15、最优个体并不 一定就对应于多目标优化问题的 Pareto 最优解。当然，当遗传算法运行结束时，我们需要 取排在前面的几个 Pareto 最优个体，以它们所对应的解来作为多目标优化问题的 Pareto 最 优解。对群体中的所有个体进行 Pareto 最优个体排序的算法是：算法 ParetoIndividual设置初始序号 r = 1。求出群体中的 Pareto 最优个体，定义这些个体的序号为 r从群体中去掉 Pareto 最优个体并更改序号 r = r+1。转到第步，直到处理完群体中的所有个体。由上述 Pareto 最优个体排序算法可知，排序选择法仅仅度量了各个个体之间的优越次 序，而未度量各个

16、个体的分散程度，所以它易于生很多个相似的 Pareto 最优解，而难于生 成分布较广的 Pareto 最优解。4共享函数法求解多目标优化问题时，一般希望所得到的解能够尽可能地分散在整个 Pareto 最优解 集合内，而不是集中在其 Pareto 最优解集合内的某一个较小的区域上。为达到这个要求， 可以利用小生境遗传算法的技术来求解多目标优化问题。这种求解多目标优化问题的方法称 为共享函数法，它将共享函数的概念引入求解多目标优化问题的遗传算法中。在利用通常的遗传算法求解最优化问题时，算法并未限制相同个体或类似个体的数量。 但当在遗传算法中引入小生境技术之后，算法对它们的数量就要加以限制，以便能够产生出 种类较多的不同的最优解。对于某一个个体 X 而言，在它的附近还存在有多少种、多大程度 相似的个体，这是可以度量的，这种度量值称之为小生境数(Niche Count)。小生境数有很