求解非线性规划问题的遗传算法设计与实现

破坏群体中的优良模式，对进化运算产生不利影响；若Pc过小，产生新个体的速度又较慢。我们为了获得较大的种群多样性，产生较多的新个体，Pc值取为0.8。

（4）变异概率Pm。变异操作是为了保证遗传算法具有局部搜索能力，同时也能保证群体多样性，抑制早熟现象。若Pm取值过大，虽然能够产生较多的新个体，但也可能破坏掉很多较好的模式，使得遗传算法的性能近似于随机搜索算法的性能；若Pm取值过小，则变异操作产生新个体的能力和抑制早熟现象的能力就会较差。这里由于是对每个基因座进行变异操作，为了保证变异效果，Pm取值较大，为0.2。

（5）终止代数T。为保证遗传算法能获得近似最优解，T取值为150。即遗传算法迭代150次停止，将得到的最佳个体作为最优解输出。

5.2 求解非线性规划问题的遗传算法程序设计

5.2.1 算法过程描述

由前面遗传算法的算法描述再结合本次毕业设计的实际情况，我们设计了以下的具体算法流程[3][9][16]。步骤如下：

（1）初始化遗传算法的运行参数：种群大小pop_size，每条染色体基因串长度length，交叉概率Pc，变异概率Pm，算法迭代次数T，当前迭代次数t。

（2）根据所给x的范围，种群大小，染色体长度，随机生成符合条件的初始种群A。 （3）将约束条件加入目标函数，确定适应度函数，计算适值e。 （4）对适值e从小到大排序，排序后的适值记为s，并记录变动情况l。

（5）根据排序结果把每一代最小适值赋给M，并记录局部最优值对应的位置（行），用1?length的行向量B表示。

（6）输出每次迭代t对应的局部极值位置B和局部最优值s(1)。 （7）计算累积概率。

（8）用转轮法进行选择运算。种群由A进化为A1。

（9）双点交叉实现交叉运算。实现遗传算法的第一次遗传运算，种群更新为A2。 （10）均匀变异实现变异过程。实现第二次遗传运算，种群更新为A3。 （11）更新种群，将A3赋给A。

（12）判断是否满足迭代结束条件。满足转（13），不满足转（3），继续迭代。 （13）对每代最小适值M排序，me为排序后的向量。 （14）输出最小适值Min，即为所求全局最优。

21

5.2.2 遗传算法程序流程图

22

图5-2 求解非线性规划问题的遗传算法程序流程图

5.2.3 遗传算法中所设计的辅助算法的设计

（1）随机数生成。程序中多处涉及到随机数的生成，像一开始初始种群的生成，后面的选择、交叉、变异的循环条件判断，都有用到。这里我们使用常用的rand函数。rand函数的作用是生成0～1之间的浮点型矩阵，通过对函数的简单运算可以生成我们想要的确定范围内的矩阵。

（2）累加函数cunsum。程序中计算累积概率部分，可以使用循环运算实现，但我们使用MATLAB中更便捷的函数cumsum直接计算元素累加，如a=[1 2 3 4]，则 cumsum(a)=[1 3 6 10]。

（3）上取整函数ceil。ceil()是向正无穷大舍入，如ceil(2.5)=3，配合rand函数可以随机生成一定范围内的整数。

（4）排序函数。因为我们所求是最小化问题，在庞大的种群和多次迭代过程中为方便找出局部最小值和全局最优值，我们可以对每次结果进行排序。sort函数实现按升序排序，如[s,l]=sort(e)，对e从小到大进行排序，s为排序后的矩阵，l为变动情况。

（5）选择函数。选择函数是为交叉操作从当前种群中选择两条染色体来进行交叉操作。我们采用转轮法（Roulette Wheel）来选择染色体。具体过程如下：

① 利用rand函数产生一个0～1之间的随机数r。

② 从第一条染色体起，将当前种群中各染色体的选择概率进行累加，当选择概率总和大于等于rand时停止。

③ 累加结束时的染色体（即概率之和刚好大于随机数rand的那条染色体）即为被选中的染色体。

23

6 算法的结果分析

6.1 概述

在以上算法分析设计的基础上，我们用MATLAB语言分别实现了求解非线性规划问题的遗传算法和外点罚函数法。本章我们通过运行实际的算法程序，通过对运行结果进行统计分析，比较两种算法各自的优越性。

6.2 结果比较

为了能直观地表现两种算法的实际执行结果，我们将两种算法的执行结果以图表的形式直观地表达出来。两种算法的计算结果如表6-1，6-2所示。

我们通过统计两种算法所得最优值的变化，来比较两种算法的收敛效果。为了充分比较两种算法收敛效果，我们对遗传算法分别采用大小为300和200的两个种群，惩罚函数法分别取初始惩罚因子M为10和1，两种算法分别执行算法10次，得到结果如表6-1所示。

表6-1 最优适值表 执行序号 1 2 3 4 5 6 7 8 9 10 种群300 703.678340 701.530725 702.253432 703.625196 698.693085 705.082156 714.335545 690.639063 694.401838 704.034177 遗传算法 种群200 689.693431 724.697202 707.968223 713.398107 717.147253 703.719043 704.113105 719.278202 692.633396 697.344160 惩罚函数法 初始惩罚因子M=10 711.150702 817.991629 762.156619 682.446767 784.342585 685.732024 736.895652 681.898495 684.731999 791.385667 初始惩罚因子M=1 737.210605 685.320941 749.302632 1497.284683 691.913655 711.150702 817.991629 762.156619 682.446767 784.342585 24