第0章智能算法及其应用
第10章 智能算法及其应用
10.1遗传算法的基本原理 遗传算法简称GA(Genetic Algorithms)是1962 年由美国Michigan2大学的Holland教授提出的模拟自 然界遗传机制和生物进化论而成的一种并行随机搜索 最优化方法。 遗传算法是以达尔文的自然选择学说为基础发展 起来的。自然选择学说包括以下三个方面：
10.1 遗传算法的基本原理 遗传算法简称GA（Genetic Algorithms）是1962 年由美国Michigan大学的Holland教授提出的模拟自 然界遗传机制和生物进化论而成的一种并行随机搜索 最优化方法。 遗传算法是以达尔文的自然选择学说为基础发展 起来的。自然选择学说包括以下三个方面：
(1)遗传：这是生物的普遍特征，亲代把生物信息交给子代， 子代总是和亲代具有相同或相似的性状。生物有了这个特征， 物种才能稳定存在。 (2)变异：亲代和子代之间以及子代的不同个体之间的差异， 称为变异。变异是随机发生的，变异的选择和积累是生命多样 性的根源。 (3)生存斗争和适者生存：具有适应性变异的个体被保留下来， 不具有适应性变异的个体被淘汰，通过一代代的生存环境的选 择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种
（1）遗传：这是生物的普遍特征，亲代把生物信息交给子代， 子代总是和亲代具有相同或相似的性状。生物有了这个特征， 物种才能稳定存在。 （2）变异：亲代和子代之间以及子代的不同个体之间的差异， 称为变异。变异是随机发生的，变异的选择和积累是生命多样 性的根源。 （3）生存斗争和适者生存：具有适应性变异的个体被保留下来， 不具有适应性变异的个体被淘汰，通过一代代的生存环境的选 择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种
遗传算法将“优胜劣汰，适者生存”的生物进化 原理引入优化参数形成的编码串联群体中，按所选择 的适应度函数并通过遗传中的复制、交叉及变异对个 体进行筛选，使适适应度高的个体被保留下来，组成 新的群体，新的群体既继承了上一代的信息，又优于 上一代。这样周而复始，群体中个体适应度不断提高， 直到满足一定的条件。遗传算法的算法简单，可并行 处理，并能到全局最优解
遗传算法将“优胜劣汰，适者生存”的生物进化 原理引入优化参数形成的编码串联群体中，按所选择 的适应度函数并通过遗传中的复制、交叉及变异对个 体进行筛选，使适适应度高的个体被保留下来，组成 新的群体，新的群体既继承了上一代的信息，又优于 上一代。这样周而复始，群体中个体适应度不断提高， 直到满足一定的条件。遗传算法的算法简单，可并行 处理，并能到全局最优解
遗传算法的基本操作为： (I)复制(Reproduction Operator) 复制是从一个旧种群中选择生命力强的个体位串产生新种群 的过程。具有高适应度的位串更有可能在下一代中产生一个或多 个子孙。 复制操作可以通过随机方法来实现。首先产生01之间均匀 分布的随机数，若某串的复制概率为40%，则当产生的随机数在 0.401.0之间时，该串被复制，否则被淘汰。 (2)交叉(Crossover Operator)
遗传算法的基本操作为： （1）复制（Reproduction Operator） 复制是从一个旧种群中选择生命力强的个体位串产生新种群 的过程。具有高适应度的位串更有可能在下一代中产生一个或多 个子孙。 复制操作可以通过随机方法来实现。首先产生0~1之间均匀 分布的随机数，若某串的复制概率为40%，则当产生的随机数在 0.40~1.0之间时，该串被复制，否则被淘汰。 （2）交叉（Crossover Operator）
复制操作能从旧种群中选择出优秀者，但不能创造新的染色 体。而交叉模拟了生物进化过程中的繁殖现象，通过两个染色 体的交换组合，来产生新的优良品种。 交叉的过程为：在匹配池中任选两个染色体，随机选择一点 或多点交换点位置；交换双亲染色体交换点右边的部分，即可 得到两个新的染色体数字串。 交权体现了自然界中信息交换的思想。交叉有一点交叉、多 点交叉、还有一致交叉、顺序交叉和周期交叉。一点交叉是最 基本的方法，应用较广。它是指染色体切断点有一处，例：
复制操作能从旧种群中选择出优秀者，但不能创造新的染色 体。而交叉模拟了生物进化过程中的繁殖现象，通过两个染色 体的交换组合，来产生新的优良品种。 交叉的过程为：在匹配池中任选两个染色体，随机选择一点 或多点交换点位置；交换双亲染色体交换点右边的部分，即可 得到两个新的染色体数字串。 交杈体现了自然界中信息交换的思想。交叉有一点交叉、多 点交叉、还有一致交叉、顺序交叉和周期交叉。一点交叉是最 基本的方法，应用较广。它是指染色体切断点有一处，例：
A:1011001110>1011000101 B:0010100101>0010101110 (3)变异(Mutation Operator) 变异运算用来模拟生物在自然的遗传环境中由于各种偶然 因素引起的基因突变，它以很小的概率随机地改变遗传基因 (表示染色体的符号串的某一位)的值。在染色体以二进制编 码的系统中，它随机地将染色体的某一个基因由1变为0，或由 0变为1。若只有选择和交叉，而没有变异，则无法在初始基因 组合以外的空间进行搜索，使进化过程在早期就陷入局部解而 进入终止过程，从而影响解的质量。为了在尽可能大的空间中 获得质量较高的优化解，必须采用变异操作
B : 001010 0101 001010 1110 A:101100 1110 101100 0101 （3）变异(Mutation Operator) 变异运算用来模拟生物在自然的遗传环境中由于各种偶然 因素引起的基因突变，它以很小的概率随机地改变遗传基因 （表示染色体的符号串的某一位）的值。在染色体以二进制编 码的系统中，它随机地将染色体的某一个基因由1变为0，或由 0变为1。若只有选择和交叉，而没有变异，则无法在初始基因 组合以外的空间进行搜索，使进化过程在早期就陷入局部解而 进入终止过程，从而影响解的质量。为了在尽可能大的空间中 获得质量较高的优化解，必须采用变异操作
10.2遗传算法的特点 (1)遗传算法是对参数的编码进行操作，而非对参数本身，这 就是使得我们在优化计算过程中可以借鉴生物学中染色体和基 因等概念，模仿自然界中生物的遗传和进化等机理； (2)遗传算法同时使用多个搜索点的搜索信息。传统的优化方 法往往是从解空间的单个初始点开始最优解的迭代搜索过程， 单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜 索过程局限于局部最优解而停滞不前。遗传算法从由很多个体 组成的一个初始群体开始最优解的搜索过程，而不是从一个单 一的个体开始搜索，这是遗传算法所特有的一种隐含并行性， 因此遗传算法的搜索效率较高
10.2 遗传算法的特点 （1）遗传算法是对参数的编码进行操作，而非对参数本身，这 就是使得我们在优化计算过程中可以借鉴生物学中染色体和基 因等概念，模仿自然界中生物的遗传和进化等机理； （2）遗传算法同时使用多个搜索点的搜索信息。传统的优化方 法往往是从解空间的单个初始点开始最优解的迭代搜索过程， 单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜 索过程局限于局部最优解而停滞不前。遗传算法从由很多个体 组成的一个初始群体开始最优解的搜索过程，而不是从一个单 一的个体开始搜索，这是遗传算法所特有的一种隐含并行性， 因此遗传算法的搜索效率较高
(3)遗传算法直接以目标函数作为搜索信息。传统的优化算法 不仅需要利用目标函数值，而且需要目标函数的导数值等辅助 信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换 来的适应度函数值，就可以确定进一步的搜索方向和搜索范围， 无需目标函数的导数值等其他一些辅助信息。遗传算法可应用 于目标函数无法求导数或导数不存在的函数的优化问题，以及 组合优化问题等。 (4)遗传算法使用概率搜索技术。遗传算法的选择、交叉、变 异等运算都是以一种概率的方式来进行的，因而遗传算法的搜 索过程具有很好的灵活性。随着进化过程的进行，遗传算法新 的群体会更多地产生出许多新的优良的个体
（3）遗传算法直接以目标函数作为搜索信息。传统的优化算法 不仅需要利用目标函数值，而且需要目标函数的导数值等辅助 信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换 来的适应度函数值，就可以确定进一步的搜索方向和搜索范围， 无需目标函数的导数值等其他一些辅助信息。遗传算法可应用 于目标函数无法求导数或导数不存在的函数的优化问题，以及 组合优化问题等。 （4）遗传算法使用概率搜索技术。遗传算法的选择、交叉、变 异等运算都是以一种概率的方式来进行的，因而遗传算法的搜 索过程具有很好的灵活性。随着进化过程的进行，遗传算法新 的群体会更多地产生出许多新的优良的个体
(5)遗传算法在解空间进行高效启发式搜索，而非盲目地穷举 或完全随机搜索； (6)遗传算法对于待寻优的函数基本无限制，它既不要求函数 连续，也不要求函数可微，既可以是数学解析式所表示的显函 数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范 围较广； (7)遗传算法具有并行计算的特点，因而可通过大规模并行计 算来提高计算速度，适合大规模复杂问题的优化
（5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举 或完全随机搜索； （6）遗传算法对于待寻优的函数基本无限制，它既不要求函数 连续，也不要求函数可微，既可以是数学解析式所表示的显函 数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范 围较广； （7）遗传算法具有并行计算的特点，因而可通过大规模并行计 算来提高计算速度，适合大规模复杂问题的优化