遗传算法与函数优化.DOC

1、第四章 遗传算法与函数优化4.1 研究函数优化的必要性：首先，很多实际问题进行数学建模后，可抽象为一个数值函数的优化问题。其次，便于系统、规范地研究测试遗传算法地性能。4.2 评价遗传算法性能的常用测试函数在设计用于评价遗传算法性能的测试函数时，必须考虑实际应用问题的数学模型中所可能呈现出的各种数学特性，以及可能遇到的各种情况和影响因素。这里所说的数学特性主要包括：连续函数或离散函数；凹函数或凸函数；二次函数或非二次函数；低维函数或高维函数；确定性函数或随机性函数；单峰值函数或多峰值函数，等等。下面是一些在评价遗传算法性能时经常用到的测试函数：(1) De Jong 函数 F1：这是一个简单的

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

3、小点，全局极小值为 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 Back Function）：该函数

4、共有六个局部极小点，其中(-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 测试函数F1F5。他采用了下面的一些研究方法：1

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

6、R1，测试函数为 F1）变异概率对在线性能的影响（优化策略为 R1，测试函数为 F1）经过仔细分析和计算，De Jong 得到了下述几条重要的结论：结论 1群体的规模越大，遗传算法的离线性能越好，越容易收敛。结论 2规模较大的群体，遗传算法的初始在线性能较差；而规模较小的群体，遗传算法的初始优化策略 R1，R2，R3 在基因损失方面的性能比较（测试函数为 F1）优化策略 R1，R2，R3 的离线性能比较（测试函数为 F1）优化策略 R1，R2，R3 的在线性能比较（测试函数为 F1）排挤因子对离线性能的影响（优化策略为 R5，测试函数为5）在线性能较好。结论 3虽然变异概率的增大也会增加群体的

7、多样性，但它却降低了遗传算法的离线性能相在线性能，并且随着变异概率的增大，遗传算法的性能越来越接近于随机搜索算法的性能。结论 4使用保留最佳个体模型或期望值模型的遗传算法比基本遗传算法的性能有明显的改进。结论 5对于广义交叉算子，随着交叉点数的增加会降低遗传算法的在线性能和离线性能。这些结论在遗传算法的开发研究和实际应用中具有重要的指导意义。4.4 多目标优化4.4.1 多目标优化问题的定义多目标优化问题一般可描述为下面的数学模型：式中，V-min 表示向量极小化，即向量目标 中的各个子目标函数都尽可能地极小化的意思。难点：在很多情况下，各个子目标有可能是相互冲突的，一个子目标的改善有可能会引

8、起另一个子目标性能的降低，也就是说，要同时使这多个子目标都一起达到最优值是不可能的，而只能是在它们中间进行协调和折衷处理，使各个子目标函数都尽可能地达到最优。【定义 4.4.1】：设 是多目标优化模型的约束集， 是多目标优化时的向量mRXpRxf)(目标函数， 。x21,)()(fxfkk),21(pk并且 )()(21xffkk),(k则称解 x1 比解 x2 优越。【定义 4.4.2】：设 是多目标优化模型的约束集， 是向量目标函数，若mRXpRxf)(，并且 x*比 X 中的所有其他点都优越，则称 x*是多目标极小化模型的最优解。x*由该定义可知，多目标优化问题的最优解 x*就是使向量目

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

10、优解也只由这些最优解所组成，再不包含有其他解。所以可以这么说，Pareto 最优解是多目标优化问题的合理的解集合。4.4.2 求解多目标优化问题的遗传算法几种主要的方法。1权重系数变化法对于一个多目标优化问题，若给其各个子目标函数 fi(x)，(i 1，2，p)，赋予不同的权重 wi(i1，2，p)，其中各 wi的大小代表相应子目标 fi(x)在多目标优化问题中的重要程度。则各个子目标函数的线性加权和可表示为：若以这个线性加权和作为多目标优化问题的评价函数，则多目标优化问题就可转化为单目标优化问题。权重系数变化法就是在这个评价函数的基础上，对每个个体取不同的权重系数，就可以利用通常的遗传算法来求出多目标优化问题的多个 Pareto 最优解。2并列选择法