利用遗传算法求解函数的最大值

1、利用遗传算法求解函数的最大值蒋赛 赵玉芹1 遗传算法的基本原理遗传算法是模拟生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种重要形式。遗传算法与传统数学模型截然不同，它为那些难以找到传统数学模型的难题找出了一个解决方法。同时，遗传算法借鉴了生物科学中的某些知识，从而体现了人工智能的这一交叉学科的特点。遗传算法是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制条件的约束，不需要有先验条件。其搜索过程是从问题解的一个随机产生的集合开始的，而不是从单个个体开始的，具有隐含并行搜索特性，也就大大减少可陷入局部极小值的可能。

2、在解决可能在求解过程中产生组合爆炸的问题时会产生很好的效果。遗传算法需选择一种合适的编码方式表示解, 并选择一种评价函数用来每个解的适应值, 适应值高的解更容易被选中并进行交叉和变异, 然后产生新的子代。选择、交叉和变异的过程一直循环 , 直到求得满意解或满足其他终止条件为止。算法的运行过程具有很强的指向性, 适合众多复杂问题的求解。具体操作步骤如下：1）初始化种群；2）计算种群上每个个体的适应度值；3）按由个体适应度值所决定的某个规则选择将进入下一代的个体4）按概率PC进行交叉操作5）按概率PC进行变异操作6）若没有满足某种停止条件，则转步骤2），否则进入下一步；7）输入种群中适应度值最优的

3、染色体作为问题的满足解或最优解本例运用遗传算法求解函数优化的问题2 遗传求解举例（Rosenbrock函数的全局最大值计算）2.0 求解函数介绍 函数f(x1,x2) = 100 (x21-x2)2 + (1-x2)2是非凸函数，又称Rosenbrock函数，是由De Jong提出的，现已成为测试遗传算法的标准函数。该函数在极小值附近沿曲线x2=x12有陡峭的峡谷，很容易陷入局部极小，它的全局最小点是(1，1)，最小值是0.该函数有两个局部极大点， 分别是: f(2.048, -2.048)=3897.7342 和 (-2.048,-2.048)=3905.9262其中后者为全局最大值点。如图

4、所示：21 算法流程图 下面介绍求解该问题的遗传算法的构造过程：第一步：确定决策变量及其约束条件。 s.t. -2.048 xi 2.048 (xi=1,2)第二步：建立优化模型。 max f(x1,x2) = 100 (x21-x2)2 + (1-x1)2第三步；确定编码方法。 用长度为l0位的二进制编码串来分别表示二个决策变量x1,x2。lO位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x1,x2的定义域离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。从离0000000000(0)到1111111111(1023)之间的二进制编码。再将分别表示

5、x1和x2的二个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。例如 X：0000110111 11011 10001 就表示一个个体的基因型。第四步：确定解码方法。 解码时先将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2，依据前述个体编码方法相对定义域的离散化方法可知，将代码yi转换为变量xi的解码公式为：Xi= 4.096 ´ yi/1023-2.048 (i=1,2)例如，对前述个体 X： 0000110111|11011 10001 它由这样的

6、两个代码所组成：y1= 55 y2 = 881经上式的解码处理后，得到： x1= -1.828 x2= 1.476 第五步：确定个体评价方法。由式 f(x1,x2) = 100 (x21-x2)2 + (1-x1)2 可知，Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，并且不再对它作其他变换处理，即有： F(x) = f(x1,x2)第六步：设计遗传算子。选择运算使用比例选择算子;(1) 选择算子或复制算子从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。(2) 最常用和最基本的选择算子： 比例选择算子。

7、(3) 比例选择算子：指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。(4) 执行比例选择的手段是轮盘选择。轮盘法的基本精神是：个体被选中的概率取决于个体的相对适应度： pi = fi / Sfi ( i=1,2,M ) 式中 pi个体i被选中的概率；fi个体i的适应度； Sfi群体的累加适应度。显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。交叉运算使用单点交叉算子(1) 交叉算子作用 通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正是有了交换操作，群体的性态才多种多样。(2) 最常用和最基本单

8、点交叉算子。(3) 单点交叉算子的具体计算过程如下： . 对群体中的个体进行两两随机配对。 若群体大小为M，则共有 M/2 对相互 配对的个体组。 . 每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为l ，则共有(l-1)个可能的交叉点位置。 . 对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。单点交叉运算的示例如下所示:、A；10110111 00 A：10110111 11B：00011100 11 B：00011100 00交叉概率 Pc=MC/M式中 M群体中个体的数目； Mc群体中被交换个体的数

9、目。变异运算使用基本位变异算子。基本位变异算子是最简单和最基本的变异操作算子。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因位上的原有基因值为0，则变异操作将该基因值变为1，反之，若原有基因值为1，则变异操作将其变为0。基本位变异因子的具体执行过程是： . 对个体的每一个基因位，依变异概率pm指定其为变异点。 . 对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替从而产生出一个新的个体。基本位变异运算的示例如下所示：A：1010 1 01010 基本位变异 A1010 0 01010 变异点变异概率变异是针对个体的某一个或某一些基因位上的基因值执

10、行的，因此变异概率pm也是针对基因而言，即：Pm=B(M*L)式中 B每代中变异的基因数目； M每代中群体拥有的个体数目 l个体中基因串长度。第七步：确定遗传算法的运行参数。对于本例，设定基本遗传算法的运行参数如下：群体大小: M80 终止代数: T200交叉概率： pc0.6 变异概率： pm0.001遗传算法迭代次数：MAXGA=333 实验结果4总结传统的搜索方法由于其应用的局限性,在某些情况下可能搜索到局部最优点，而不能达到全局最优点。利用遗传算法搜索函数最优点的方法极大地提高了搜索全局最优点的准确性，有效地避免了组合爆炸地产生。因此，遗传算法在求解复杂的优化问题中具有广泛的应用前景。5 实验难点和重点 本次实验的重点在于三个方面，一是