2.5　MATLAB仿真实例

例2.1　用标准遗传算法求函数f（x）=x+10sin（5x）+7cos（4x）的最大值，其中x的取值范围为［0，10］。这是一个有多个局部极值的函数，其函数值图形如图2.2所示，其MATLAB实现程序如下：

解：仿真过程如下：

（1）初始化种群数目为NP=50，染色体二进制编码长度为L=20，最大进化代数为G=100，交叉概率为Pc=0.8，变异概率为Pm=0.1。

（2）产生初始种群，将二进制编码转换成十进制，计算个体适应度值，并进行归一化；采用基于轮盘赌的选择操作、基于概率的交叉和变异操作，产生新的种群，并把历代的最优个体保留在新种群中，进行下一步遗传操作。

（3）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。

优化结束后，其适应度进化曲线如图2.3所示，优化结果为x=7.8567，函数f（x）的最大值为24.86。

MATLAB源程序如下：

例2.2　计算函数的最小值，其中个体x的维数n=10。这是一个简单的平方和函数，只有一个极小点x=（0，0，…，0），理论最小值f（0，0，…，0）=0。

解：仿真过程如下：

（1）初始化种群数目为NP=100，染色体基因维数为D=10，最大进化代数为G=1000，交叉概率为Pc=0.8，变异概率为Pm=0.1。

（2）产生初始种群，计算个体适应度值；进行实数编码的选择以及交叉和变异操作。选择和交叉操作采用“君主方案”，即在对群体根据适应度值高低进行排序的基础上，用最优个体与其他偶数位的所有个体进行交叉，每次交叉产生两个新的个体。在交叉过后，对新产生的群体进行多点变异产生子群体，再计算其适应度值，然后和父群体合并，并且根据适应度值进行排序，取前NP个个体为新群体，进行下一次遗传操作。

（3）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。

优化结束后，其适应度进化曲线如图2.4所示，优化后的结果为x=［0.0003 -0.0037 0.0069 -0.0000 -0.0020 0.0001 -0.0009 0.0056 0.0052 0.0003］，函数f（x）的最小值为1.24×10-4。

MATLAB源程序如下：

例2.3　旅行商问题（TSP）。假设有一个旅行商人要拜访全国31个省会城市，他需要选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。对路径选择的要求是：所选路径的路程为所有路径之中的最小值。

全国31个省会城市的坐标为［1304 2312；3639 1315；4177 2244；3712 1399；3488 1535；3326 1556；3238 1229；4196 1004；4312 790；4386 570；3007 1970；2562 1756；2788 1491；2381 1676；1332 695；3715 1678；3918 2179；4061 2370；3780 2212；3676 2578；4029 2838；4263 2931；3429 1908；3507 2367；3394 2643；3439 3201；2935 3240；3140 3550；2545 2357；2778 2826；2370 2975］。

解：仿真过程如下：

（1）初始化种群数目为NP=200，染色体基因维数为N=31，最大进化代数为G=1000。

（2）产生初始种群，计算个体适应度值，即路径长度；采用基于概率的方式选择进行操作的个体；对选中的成对个体，随机交叉所选中的成对城市坐标，以确保交叉后路径每个城市只到访一次；对选中的单个个体，随机交换其一对城市坐标作为变异操作，产生新的种群，进行下一次遗传操作。

（3）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。

优化后的路径如图2.5所示，其适应度进化曲线如图2.6所示。

MATLAB源程序如下：

例2.4　0-1背包问题。有N件物品和一个容量为V的背包。第i件物品的体积是c（i），价值是w（i）。求解将哪些物品放入背包可使物品的体积总和不超过背包的容量，且价值总和最大。假设物品数量为10，背包的容量为300。每件物品的体积为［95，75，23，73，50，22，6，57，89，98］，价值为［89，59，19，43，100，72，44，16，7，64］。

解：仿真过程如下：

（1）初始化种群数目为NP=50，染色体基因维数为L=10，最大进化代数为G=100。

（2）产生二进制初始种群，其中1表示选择该物品，0表示不选择该物品。取适应度值为选择物品的价值总和，计算个体适应度值，当物品体积总和大于背包容量时，对适应度值进行惩罚计算。

（3）对适应度进行归一化，采用基于轮盘赌的选择操作、基于概率的交叉和变异操作，产生新的种群，并把历代的最优个体保留在新种群中，进行下一步遗传操作。

（4）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。

优化结果为［1 0 1 0 1 1 1 0 0 1］，1表示选择相应物品，0表示不选择相应物品，价值总和为388。其适应度进化曲线如图2.7所示。

MATLAB源程序如下：