1、“.....是第个染色体的适 应度值，是种群中所有染色体的适应度值之和。 用适应度比例法进行选择时，首先计算每个染色体的适应度，然后按比 例于各染色体适应度的概率进入交换匹配集的染色体，其具体步骤如下 计算每个染色体的适应度值 累加所有染色体的适应度值，得最终累加值，记录对 应于每个染色体的中间累加值 产生个随机数 选择其对应的中间累加值满足的染色体进入交换 集。 重复直到交换集中包含足够多的染色体数字串为止。 重复上述过程，直到交换集中包含足够多的染色体为止。显然，此法要 求染色体的适应度应为正值。请看下例 例种群包含个染色体，按适应度比例法选择进入交换集的过程示 于表及表......”。

2、“.....表可以看到，号染色体的选择概率最高，被选中的次数最多，其 他选择概率较低的染色体被选中的次数就少。当然，用适应度比例法进行选 择时，性能最坏的染色体也可能被选择，但概率极小，当种群长度较大时， 这种情况可以忽略不计。 交换 复制操作虽然能够从旧种群中选择出优秀者，但不能创造新的染色体， 因此，遗传算法的开创者提出了交换操作。它模拟生物进化过程中的繁殖现 象，优良品种，即在匹配集中任选两个染色体称为双亲的染色体随机 选择点或多点交换点位置，是染色体数字串的长度交换双亲 染色体交换点右边的部分，即可得到两个新的下代染色体数字串。也 就是说，交换操作能够创造新的染色体子孙染色体，从而允许测试在搜索 空间中的新点。交换也体现了自然界中信息交换的思想。请看下例 例从匹配集中取出的对染色体为 染色体 染色体集训队论文遗传算法的特点及其应用张宁 第页共页 随机产生的点交换位置是，交换染色体，中第位右边的部分 和......”。

3、“.....它以很小概率随机地改变遗传基因表示染色体的符号串的 位的值。在染色体以二进制编码的系统中，它随机地将染色体的个基 因由变成，或由变成。若只有选择和交换，而没有变异操作，则无法 在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而终 止进化过程，从而使解的质量受到很大限制。通过变异操作，可确保群体中 遗传基因类型的多样性，以使搜索能在尽可能大的空间中进行，避免丢失在 搜索中有用的遗传信息而陷入局部解，获得质量较高的优化解答。 简单的遗传算法运算示例 让我们从下面两个非常简单的例子来具体了解下简单遗传算法的各种操 作。虽然下面的例子都有更好处理方式，但为了深入了解遗传算法的各种操作， 还是从简单的例子入手 例计算机公司的经营策略优化问题 个计算机公司追求的目标是最高的利润，为达此目标，必须选择适当的经 营策略......”。

4、“..... 把问题的可能解表示为染色体数字串。因为有四个决策变量，而每新染色体值适应度目标函 数 和 平均 最大 从表可以看出，虽然仅进行了代遗传操作，但种群适应度的平均值及最 大值却比初始群有了很大提高，平均值由变到，最大值由 变到。这说明随着遗传运算的进行，种群正向着优化的方向发展。 遗传算法应用举例 例在子集和问题上的应用 子集和问题给定正整数集合和个整数，判定是否存在 的个子集使得中整数的和为。 例如，若，且， 则子集是个解。 设子集和问题的个实例为。其中，是个正整数的集合„， ，是个正整数。子集和问题要求判定是否存在的个子集，使得 。我们已知道该问题是个完全问题。在实际应用中，我们常遇 到的是最优化子集和问题......”。

5、“.....我们要找出的个子集，使得 其和不超过，但又尽可能接近于。例如，我们有辆载重车，其载重量不能 超过公斤。有个不同的箱子要用载重车来装运，其中第个箱子重公斤。 我们希望在不超过载重限制的前提下将载重车尽可能地装满。这个问题实质上就 是个最优化形式的子集和问题。 下面用遗传算法来解决 若集合中元素的个数为，每个元素只有两种可能属于或不属于。 因此我们可以用为二进制数来表示每个染色体。每位，若为则说明这个元 素不属于，若为则说明这个元素属于。 确定了问题的描述方式，我们只需随机取出染色体组成初始群体。接着，便 可以按前所述，进行选择交换以及变异运算。 我们将染色体所表示的子集的元素和与所给的差异记为适应度。 即令染色体的每位为，所表示元素的值为则 集训队论文遗传算法的特点及其应用张宁 第页共页 但是经过实践后发现由于适应度相对差异较小，使得适应度非常接近，难以 区分优秀的染色体，使得遗传进化变得非常缓慢，且可能为负值......”。

6、“.....才可以适合本题的要求。 令为当前群体中所有染色体适应度的最大值 所以适应度为。 选择时可以用前面所介绍的适应度比例法，但采用随机方式，可能会出现随 机，使得优秀的染色体没有子孙。因此，在这里我们对选择方法作下改进， 采用确定性选择法，使得选择不依靠随机的好坏，先计算群体中每个串的生存概 率然后计算期望复制数，式中为群体中染色 体的数目。根据值的整数部分给每个染色体串分配个复制数，而按的小 数部分对群体中的染色体串排序，最后按排列的大小顺序选择要保留到下代的 染色体串子孙。 接着可以进行交换运算，交换运算与前述相同，不过若进行单点交换有可能 使得两个染色体在交换时产生的差异过大，使得遗传变得不稳定，优秀的染色体 不能遗传到下代。因此可以采用多点交换，不过本题中只需进行两点交换即可， 其实两点交换与单点交换是类似的。 设有两个父辈染色体和 设两个交换点选择如下 则两点交换运算就是交换染色体和染色体，两个交换点之间的部分......”。

7、“.....可进行变异运算，变异运算时，只需注意变异概率的取值， 至于具体算法如前面所述。 在本题中的些数值不妨取值如下 种群长度染色体个数 选择概率 变异概率 结束条件当前最优解在代遗传后仍未改变，或已取到最优解 例在旅行商问题求解中的应用 设存在个城市，表示城与城之间的距离现在要求条 遍历所有个城市，且不走重复路的最短路径最短哈密尔顿圈。 这是个典型的排列顺序问题，属于完全问题。传统解法诸如限界剪 枝法，或是最小支撑树算法，对此都并不太奏效或是运算速度上的缺陷，或是 解的质量上的缺陷。下面我们试着用遗传算法来解决这道题目。 我们先采用十进制编码，每个染色体由按定顺序排列的个城市的序号组集训队论文遗传算法的特点及其应用张宁 第页共页 成，表示条可能的旅行路径，其中每个基因表示个城市。染色体的长度为， 解空间为,。适应度为条旅行路径对应的距离，路径越短的染色体适应度越 高。例如，取，城市代号为，......”。

8、“.....把最小化优化目标函数变换为以最大值为目标的适 应度函数，可以如下定义  其中为可以取为进化过程中路径长度的最大值，或者为了保证为正 而预先设定为个与种群无关的常数。 下面介绍具体算法 首先我们由城市数目，可以确定染色体长度为，染色体的基因代码由城 市编码组成。但是，我们仍须确定种群长度变异概率等参数。这些参数都由人 为确定，与算法无关，可暂时不考虑，讨论完算法后，可再行确定具体数值。 随机组合成染色体，每个染色体须表示条哈密尔顿回路，生成初始种群。 然后分别计算每个染色体的适应度，按适应度比例法选择染色体到交换集。不 过，我们也可以考虑下改进后的选择方法。 适应度比例法实现简单，缺点是选择过程中最好的染色体可能在下代产生 不了子孙，可能发生随机。因此我们可以采用择优选择法，即对于群体中最 优秀适应度最高的染色体不进行交换和变异运算......”。

9、“.....以免交换和变异运算破坏种群中的优秀解答。这种方法可加快局部搜索速 度，但又可能因群体中优秀染色体的急剧增加而导致搜索陷入局部最优解。同时， 我们也可以采用确定性选择法，使得选择不依靠随机的好坏，先计算群体中每个 串的生存概率然后计算期望复制数，式中为 群体中染色体的树木。根据值的整数部分给每个染色体串分配个复制数， 而按的小数部分对群体中的染色体串排序，最后按排列的大小顺序选择要保 留到下代的染色体串子孙。 完成选择运算后，可以进行交换运算。但是，此处的交换运算不同于前，须 改进原有的交换运算，具体做法如下 因为两个染色体，若进行简单的交换运算，可能会使得染色体所表示路径中 会重复经过同城市，即同染色体中的两个基因有着相同的城市编号。这就造 成了染色体不再表示条哈密尔顿回路，因此须改进交换运算。 我们可以采用部分匹配交换运算。它先用随机均匀分布方法在欲交换 两父染色体串中各产生两个交换点，把这两点之间的区域定义为匹配区域......”。