新个体是：

t?1tt?XA??XB?(1??)XA ?t?1ttX??X?(1??)X?BAB

其中，α是一参数，它可以是一个常数，此时所进行的交叉运算称为均匀算术交叉；它可以是一个由进化代数所决定的变量，此时所进行的交叉运算称为非均匀算术交叉。

3．交叉算子与遗传算法的收敛型

遗传算法的收敛性不仅取决于编码，初始化群体，适应度函数，选择算子的设计，而且还取决于交叉算子和下面要提到的变异算子。但是，遗传算法的收敛性主要决定于作为其核心操作的交叉算子。交叉算子收敛性是遗传算法研究中最重要的课题之一。需要指出的是，交叉算子并未提供收敛性保证。

三、变异算子

变异操作的基本内容是对群体中的个体串的某些基因座上的基因值作变动。例如，基于字符集{0，1}的二值码串，变异操作就是把1变成0或者把0变成1。变异操作的步骤为：在群体中所有个体的码串范围内随机的确定基因座，然后以事先设定的变异概率对这些基因座的基因值进行变异。如下图所示：

图2.4 简单位变异

遗传算法引入变异的目的有两个：一个是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解临近值时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。这种情况下变异概率应取较小值，否则已经接近最优解的值会因为变异而遭到破坏。二是使遗传算法可以维持群体多样性，以防止出现早熟现象。

遗传算法中，交叉算子因为其全局搜索能力作为主要算子，变异算子因其局

部搜索能力作为辅助算子。遗传算法通过交叉和变异这一对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。

遗传算法在组合优化中有着许多重要而且成功的应用实例，这里只涉及到了最典型的旅行商问题(TSP问题)。旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中的著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 。即寻找一条最短的遍历n个城市的路径，或者说搜索整数子集X= {1,2,…,n}的一个排列，使得Td??d(vi,vi?1)?d(vi,vn)取最小值。其中d(vi,vi?1)表示城市i

i?1n?1到vi?1的距离。

TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

遗传算法求解可以得到问题的最优解，且算法简单，对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。我将用遗传算法来求解一个简单的TSP问题，其中基因是n个城市的排列顺序,适应度应该是城市之间的距离总和，将距离作为权值。算法求解的问题就是对总距离最小的访问城市的路径排序。得到最短访问路径适应函数的最优排序。

本例中，首先以十进制方式对遍历29个城市的次序排列进行编码，例如码串12345678表示从城市1开始，依次经过城市2，3，4，5，6，7，8，最后返回城市1的遍历路径，这是一种针对TSP问题的最自然的编码方式。其边权值如下所示：

/*

0 107 241 190 124 80 316 76 152 157 283 133 113 297 228 129 348 276 188 150 65 341 184 67 221 169 108 45 167

107 0 148 137 88 127 336 183 134 95 254 180 101 234 175 176 265 199 182 67 42 278 271 146 251 105 191 139 79 241 148 0 374 171 259 509 317 217 232 491 312 280 391 412 349 422 356 355 204 182 435 417 292 424 116 337 273 77 190 137 374 0 202 234 222 192 248 42 117 287 79 107 38 121 152 86 68 70 137 151 239 135 137 242 165 228 205 124 88 171 202 0 61 392 202 46 160 319 112 163 322 240 232 314 287 238 155 65 366 300 175 307 57 220 121 97 80 127 259 234 61 0 386 141 72 167 351 55 157 331 272 226 362 296 232 164 85 375 249 147 301 118 188 60 185 316 336 509 222 392 386 0 233 438 254 202 439 235 254 210 187 313 266 154 282 321 298 168 249 95 437 190 314 435

76 183 317 192 202 141 233 0 213 188 272 193 131 302 233 98 344 289 177 216 141 346 108 57 190 245 43 81 243 152 134 217 248 46 72 438 213 0 206 365 89 209 368 286 278 360 333 284 201 111 412 321 221 353 72 266 132 111 157 95 232 42 160 167 254 188 206 0 159 220 57 149 80 132 193 127 100 28 95 193 241 131 169 200 161 189 163 283 254 491 117 319 351 202 272 365 159 0 404 176 106 79 161 165 141 95 187 254 103 279 215 117 359 216 308 322 133 180 312 287 112 55 439 193 89 220 404 0 210 384 325 279 415 349 285 217 138 428 310 200 354 169 241 112 238 113 101 280 79 163 157 235 131 209 57 176 210 0 186 117 75 231 165 81 85 92 230 184 74 150 208 104 158 206 297 234 391 107 322 331 254 302 368 149 106 384 186 0 69 191 59 35 125 167 255 44 309 245 169 327 246 335 288 228 175 412 38 240 272 210 233 286 80 79 325 117 69 0 122 122 56 56 108 175 113 240 176 125 280 177 266 243 129 176 349 121 232 226 187 98 278 132 161 279 75 191 122 0 244 178 66 160 161 235 118 62 92 277 55 155 275 348 265 422 152 314 362 313 344 360 193 165 415 231 59 122 244 0 66 178 198 286 77 362 287 228 358 299 380 319 276 199 356 86 287 296 266 289 333 127 141 349 165 35 56 178 66 0 112 132 220 79 296 232 181 292 233 314 253 188 182 355 68 238 232 154 177 284 100 95 285 81 125 56 66 178 112 0 128 167 169 179 120 69 283 121 213 281 150 67 204 70 155 164 282 216 201 28 187 217 85 167 108 160 198 132 128 0 88 211 269 159 197 172 189 182 135 65 42 182 137 65 85 321 141 111 95 254 138 92 255 175 161 286 220 167 88 0 299 229 104 236 110 149 97 108 341 278 435 151 366 375 298 346 412 193 103 428 230 44 113 235 77 79 169 211 299 0 353 289 213 371 290 379 332 184 271 417 239 300 249 168 108 321 241 279 310 184 309 240 118 362 296 179 269 229 353 0 121 162 345 80 189 342 67 146 292 135 175 147 249 57 221 131 215 200 74 245 176 62 287 232 120 159 104 289 121 0 154 220 41 93 218 221 251 424 137 307 301 95 190 353 169 117 354 150 169 125 92 228 181 69 197 236 213 162 154 0 352 147 247 350 169 105 116 242 57 118 437 245 72 200 359 169 208 327 280 277 358 292 283 172 110 371 345 220 352 0 265 178 39 108 191 337 165 220 188 190 43 266 161 216 241 104 246 177 55 299 233 121 189 149 290 80 41 147 265 0 124 263 45 139 273 228 121 60 314 81 132 189 308 112 158 335 266 155 380 314 213 182 97 379 189 93 247 178 124 0 199 167 79 77 205 97 185 435 243 111 163 322 238 206 288 243 275 319 253 281 135 108 332 342 218 350 39 263 199 0

*/

对此29个城市的访问，要求每个城市都只能访问一次，并且最后要回到原来出发的城市。将以上29个城市之间的代号和距离权值用一个的数组matrix[maxstring][maxstring]进行存储和初始化。

接着在此基础上定义适应度函数。适应度函数通常取路径长度Td的倒数，即，则适f?1/Td。如果结合TSP的约束条件（比如每个城市经过且只经过一次）应度函数可表示成为f?1/(Td???Nt)。其中Nt是对TSP路径不合法的度量（比如取Nt为未遍历的城市的个数），?为惩罚系数，可以是距离的倍数。

然后进行遗传算子的设计：以n个城市的遍历次序作为遗传算法的编码，因为在各种遗传操作中都隐含了TSP问题的合法性约束条件（例如，每个城市经过且经过一次），所以适应度函数取哈密而顿长度的倒数。 采用赌轮选择机制。一开始用随机方法产生初始群体。随着遗传算法的执行，则保留M个教优的个体作为群体。在每一代运算过程中，个体被选中的概率与其在群体中的相对适应度

成正比。 交叉方法采用改进的OX方法，这种方法的好处是，在两个父代串相同的情况下仍能产生一定程度的变异效果，这对维持群体内一定的多样化特性有一定的作用。变异方法采用“逆转”与下山方法相结合的操作，称为“进化逆转”，主要目的是改善遗传算法的局部搜索能力。在基本遗传算法操作中，交叉操作在可行解空间中动作范围较宽，步伐较大，导致变异操作受“选择”压力的作用，难以发挥局部搜索的功效。因此，在遗传算法框架中加入适当的、基于邻域的局部搜索机制，构成一种全局搜索和局部搜索相结合的优化搜索算法。下山方法就是一种很好的局部搜索方法。这里，定义一次“逆转”为进入一个解的邻居，则进化逆转就是一个单方向的（朝着改进方向的深度下山）和连续的“逆转”操作。若“逆转”使可行解的适应度提高，则继续执行逆转，如此反复直到适应度不再提高（这就是典型的下山过程）。这一操作可以得到较好的效果。

将此算法编程实现，可得到如下的算法描述和流程框图： TSP START

数据初始化与内存空间分配； gen = 0； 初始化路径群体； 适应度统计； 显示初始路径； do{

gen = gen + 1； 选择操作； 交叉操作； 变异操作； 适应度统计； 显示中间结果； }while(不满足停止条件)

将计算结果写入文件； 内存空间释放； END

实验分析

此问题即一个TSP问题,其中事件间相当于一个偏序集,解方法可以用递归和回溯法,时间复杂度比较复杂.用遗传算法求解时，问题是要得到基因的一个序列与前面的不同，所以要在基因进行交叉和变异之后要进行基因序列的休整，使得整个基因序列保持完整，休整方法就是对重复基因进行更换。用遗传算法求解问题时,很容易将问题限于局部忧化。

本程序代码在C-Free 3.5下编译通过，谢谢老师审阅！