2。2 遗传算法的基本工作流程

遗传算法就是将问题转化为染色体来解决，生成一组染色体，将它们放在问题环境里根据适者生存的法则，挑选适应该问题环境的染色体进行复制（reproduction）、交叉（crossover）、变异（mutation）等操作产生新的个体，构成新的染色体群，对当中的染色体进行循环操作， 直到获得一个最能够适应环境的染色体个体为止，求得问题最优解。其基本步骤如下。

（1）确定编码方案

（2）确定适应度函数

（3）选取合适的参数

（4）设计遗传算子

（5）限定终止条件

需要注意的有以下几个方面：

1、编码策略：有二进制编码、实数编码和符号编码等，以二进制编码为代表，是最早使用也是最简单的一种编码方式，但由于字符串的长度与问题所要求的求解精度相关，导致在使用二进制编码时会产生一些问题：例如在连续函数离散化时映射有误差，编码串长度短时，精度达不到要求，反之虽可以提高精确度，但会使搜索空间加大;而且它不反映所求问题的特定知识，不便开发针对性的遗传算子。

为改进二进制编码，从而提出实数编码，就是在一定范围内取实数来代表个体对应的基因值，其个体的编码长度由变量数目决定；符号编码是将染色体中的基因值都以有一定代码意义的符号，形成一个符号集，对车间调度问题，TSP和车辆路径优化问题具有广泛的应用价值。

2、适应度函数：遗传算法就是通过对个体适应度的评价来表现目标函数的使用，从而计算出所求问题的目标函数值，以此就可以获得下一步的搜索信息。所以对评价个体的适应度至关重要，常用的方法有两种：原始适应度函数、标准适应度函数。前者直接以问题的目标函数 为个体适应度值，后者由于不同的选择策略，所要求的适应度函数值也不同，例如 对极小化问题，标准适应度可这样定义 ，其中 为充分大的正数， 为目标函数， 为适应度函数。

3、遗传算法的选择使用：通过遗传算法使用选择对个体取优和淘汰，适应度高的延续下去，反之淘汰。不同的选择策略对下一代中的上一代的遗传因子的分配关系会造成很大的影响，即选择压力的大小，选择压力大的最优个体复制数目多，算法收敛快，但会出现过早收敛；反之可以使群体保持多样性，收敛到全局最优的概率大，缺点就是收敛速度比较慢。

1）精英个体保留策略[6]：就是把适应能力强的个体留下来，直接复制进入下一环节。

2）适应度值比例方法[7]：个体选择概率:  ，  是种群中第  个个体给定的适应度值；  为种群规模，将一个圆盘分成若干份，通过参照点随机的落在圆形上，进行选择。具体实现过程：在区间 生成随机数  ,若  ，则选择个体  , 。来*自-优=尔,论:文+网www.youerw.com

3）排列选择方法[7]：在事先了解每个个体的适应能力后，根据适应能力的大小进行个体排序。将概率表发放给个体，确定个体选择几率的大小。其选择概率与适应度值无直接关系。

4）交叉：指将两个个体的部分基因交换，再重新组合排列，从而得到新个体的过程。常见交叉操作有均匀交叉、模拟二进制交叉、单点交叉和两点交叉等。

1、均匀交叉：先随机生成一个二进制串，遇上一代同等的宽度，并以此为模范，将两个父代个体进行交叉，获得两个新的下一代。

2、模拟二进制交叉：在组合优化或离散优化时个体是一个排列，每个基因值必须且只能出现的次数固定，为确保交叉后个体需设计相应的交叉算子，现在有很多交叉算子，如部分映射交叉PMX、次序交叉OX、循环交叉CX、基于位置的交叉PX、优先保存交叉PPX等。