内容发布更新时间 : 2025/7/12 3:04:36星期一 下面是文章的全部内容请认真阅读。
新个体是：
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