遗传算法起源于对生物系统所进行的计算机模拟研究。本章首先介绍遗传算法的特点、优缺点以及其他算法的比较,随后介绍遗传算法基本原理与方法:遗传算法正是依据生物进化中的“适者生存”规律的基本思想设计的。遗传算法在求解优化问题时,都是将实际问题的求解空间按一定的编码方式表现出来。遗传算法的主要步骤是:形成匹配集,按某种复制规则进行繁殖,若遗传代数(迭代次数)达到给定的允许值或其它收敛条件已满足时停止遗传;遗传算法的应用部分中,对遗传算法进行距离说明。

注脚

展开查看详情

1.遗传算法简介

2.1 遗传算法概述 2 遗传算法基本原理与方法 3 遗传算法的应用

3.1. 遗传算法概述 1.1 遗传算法的概念 遗传算法( Genetic Algorithm, GA ) 起源于对生物系统所进行的计算机模拟研究。 它是模仿自然界生物进化机制发展起来的随 机全局搜索和优化方法,借鉴了达尔文的进 化论和孟德尔的遗传学说。其本质是一种高 效、并行、全局搜索的方法,能在搜索过程 中自动获取和积累有关搜索空间的知识,并 自适应地控制搜索过程以求得最佳解。

4. 遗传算法操作使用 适者生存的原则 ,在潜在的解决方案种群中逐次产生一个近 似最优的方案。在遗传算法的每一代中,根 据个体在问题域中的适应度值和从自然遗传 学中借鉴来的再造方法进行个体选择,产生 一个新的近似解。这个过程导致种群中个体 的进化,得到的新个体比原个体更能适应环 境,就像自然界中的改造一样。

5.1.2 遗传算法的特点 遗传算法是一种借鉴生物界自然选择和 自然遗传机制的随机搜索法。它与传统的算 法不同,大多数古典的优化算法是基于一个 单一的度量函数的梯度或较高次统计,以产 生一个确定性的试验解序列;遗传算法不依 赖于梯度信息,而是通过模拟自然进化过程 来搜索最优解,它利用 某种编码技术,作用 于称为染色体的数字串,模拟由这些串组成 的群体的进化过程。

6.1.2.1 遗传算法的优点 ( 1 )对可行解表示的广泛性。 ( 2 )群体搜索特性。 ( 3 )不需要辅助信息。 ( 4 )内在启发式随机搜索特性。

7.( 5 )遗传算法在搜索过程中不容易陷入局部 最优,即使在所定义的适应度函数是不连续 的、不规则的或有噪声的情况下,也能以很 大的概率找到全局最优解。 ( 6 )遗传算法采用 自然进化机制来表现复杂 的现象,能够快速可靠地解决求解非常困难 的问题。 ( 7 )遗传算法具有固有的并行性和并行计算 的能力。 ( 8 )遗传算法具有可扩展性,易于同别的技 术混合。

8.1.2.2 遗传算法的缺点 ( 1 )编码不规范及编码存在表示的不准确性。 ( 2 )单一的遗传算法编码不能全面地将优化问题的约 束表示出来。考虑约束的一个方法就是对不可行解采 用 阈值,这样,计算的时间必然增加。 ( 3 )遗传算法通常的效率比其他传统的优化方法低。 ( 4 )遗传算法容易出现过早收敛。 ( 5 )遗传算法对算法的精度、可信度、计算复杂性等 方面,还没有有效的定量分析方法。

9.1.3 遗传算法与传统方法的比较 传统算法 遗传算法 起始于单个点 起始于群体 改善 改善 (问题特有的) (独立于问题的) 否 否 终止? 终止? 是 是 结束 结束

10.1.3.1 遗传算法与启发式算法的比较 启发式算法是通过寻求一种能产生可 行解的启发式规则,找到问题的一个最优解 或近似最优解。该方法求解问题的效率较高 ,但是具有唯一性,不具有通用 性,对每个 所求问题必须找出其规则。但遗传算法采用 的是不是确定性规则,而是强调利用 概率转 换规则来引导搜索过程。

11.1.3.2 遗传算法与爬山法的比较 爬山法是直接法、梯度法和 Hessian 法的 通称。爬山法首先在最优解可能存在的地方 选择一个初始点,然后通过分析目标函数的 特性,由初始点移到一个新的点,然后再继 续这个过程。爬山法的搜索过程是确定的, 容易产生局部最优解;而遗传算法是随机的。 其主要差别为:

12.( 1 )爬山法的初始点仅一个,由决策者给出 ;遗传算法的初始点有多个,是随机产生的 。 ( 2 )爬山法由上一个点产生一个新的点;遗 传算法在当前的种群中经过交叉、变异和选 择产生下一代种群。对同一问题,遗传算法 花费的机时少。

13.1.3.3 遗传算法与穷举法的比较 穷举法就是对解空间内的所有可行解进行 搜索,但是通常的穷举法并不是完全穷举法 ,即不是对所有解进行尝试,而是有选择地 尝试,如动态规划法、限界剪枝法。对于特 殊的问题,穷举法有时也表现出很好的性能。 但一般情况下,对于完全穷举法,方法简单 可行,但求解效率太低;对于动态规划法、 限界剪枝法,则鲁棒性不强。相比较而言, 遗传算法具有较高的搜索能力和极强的鲁棒 性。

14.1.3.4 遗传算法与盲目随机法的比较 与上述的搜索法相比,盲目随机搜索法有 所改进,但是它的搜索效率仍然不高,并且 只有解在搜索空间中形成紧致分布时,它的 搜索才有效。而遗传算法为导向随机搜索方 法,是对一个被编码的参数空间进行高效搜 索。

15. 经上面的探讨,可以看到遗传算法与传统 优化方法在本质上有着不同之处,主要有以 下几点: ( 1 )遗传算法搜索种群中的点是并行的,而 不是单点。 ( 2 )遗传算法并不需要辅助信息或辅助知识 ,只需要影响搜索方向的目标函数和相应的 适应度。 ( 3 )遗传算法使用 概率变换规则,而不是确 定的变换规则。 ( 4 )遗传算法工作使用 编码参数集,而不是 自身的参数集(除了在实值个体中使用 )。

16. 2. 遗传算法基本原理及方法 2.1 遗传算法的基本思想 遗传算法正是依据生物进化中的“适者生存”规 律的基本思想设计的,它把问题的求解过程模拟为 群体的适者生存过程,通过群体的一代代的不断进 化(包括竞争、繁殖和变异等)出现新群体,相当 于找出问题的新解,最终收敛到“最适应环境”的个 体(解),从而求得问题的最优解或满意解。

17. 遗传算法在求解优化问题时,都是将实际问题的求解空 间按一定的编码方式表现出来,即对解空间中的各个解进行 编码。所谓解的编码就是把各个解用 一定数目的字符串(如 “0” 和“ 1” )表示。字符串中的每一位数称为遗传基因,每 一个字符串(即一个解的编码)称为一个染色体或个体。个 体的集合称为群体。遗传算法的寻优过程就是通过染色体的 结合,即通过双亲的基因遗传、变异和交配等,使解的编码 发生变化,从而根据“适者生存”的规律,最终找出最优解。 表 2-1 列出了生物遗传的基本概念在遗传算法中的体现。

18. 表 2-1 遗传算法一般由编码与解码、适应度函数、遗传算子和 控制参数等四个部分组成。 1 ) 由设计空间向遗传算法编码空间的映射称为编码;由编 码空间向设计空间的映射称为解码。用 遗传算法求解优化问题 时,必须先建立设计变量与染色体之间的对应关系,即确定编 码和解码的规则。这样在遗传算法中,其优化问题求解的一切 过程都通过设计解的编码与解码来进行。

19.2 ) 适应度函数是用 以描述个体适应环境的程 度,也是生物进化中决定哪些染色体可以产 生优良后代(适者生存)的依据。一般是, 个体的适应度函数值越大,则个体性能越好 ,生存可能性越大;反之,若个体的适应度 函数值越小,则个体的性能越差,越有可能 被淘汰。

20.3 ) 遗传算子包括复制(或选择)算子、交配算子和 变异算子。复制算子是根据个体的优劣程度决定在 下一代是被淘汰还是被复制(即个体继续存在,子 代保持父代的基因)。交配是指两个相互配对的染 色体按某种方式相互交换其部分基因而生产两个新 的个体。变异是将个体编码字符中的某些基因用 其 他等位基因来替换,从而生成一个新的染色体。这 三个算子一般都按一定的种群复制(或选择)概率 、交配概率和变异概率随机地进行,造成遗传中的 子代和父代的差异。 4 ) 算法的控制参数包括种群的规模 M 、交配率 Pc 和变异率 Pm 。

21.2.2 遗传算法的计算步骤 计算步骤  用 遗传算法求解工程优化设计问题的基本步骤如下 :  1 ) 确定寻优参数,进行编码。编码时先要设置编 码长度;  2 ) 随机产生一组初始解(即个体)组成初始种群。 初始种群中个体的数目称作初始种群的规模;  3 ) 计算种群中各个个体的目标函数值及其相应的 适应度函数值;

22.4 ) 形成匹配集。根据种群中各个染色体的 适应度函数值,采取一定的选择方法,从种 群中选出适应值较大的个染色体(其中有些 染色体是重复的),称这个染色体的集合即 为匹配集。这一过程即为选择操作。  5 ) 按某种复制规则进行繁殖。由匹配集中 的个染色体繁殖产生个新的染色体,得到一 个新的种群。繁殖方法主要有两种:交叉和 变异。  6 )若遗传代数(迭代次数)达到给定的允 许值或其它收敛条件已满足时停止遗传,否 则返回步骤 3 )。

23.上述遗传算法的计算过程可用 下图表示。 遗传算法流程图

24. 目前,遗传算法的终止条件的主要判据有以下几 种: 1 ) 判别遗传算法进化代数是否达到预定的最大 代数; 2 ) 判别遗传搜索是否已找到某个较优的染色体 ; 3 ) 判别各染色体的适应度函数值是否已趋于稳 定、再上升否等。

25.2.3 遗传算法实现的几个技术问题  2.3.1 编码  编码是应用 遗传算法时要解决的首要问题,同 时编码方法在很大程度上决定了如何进行群体的遗 传进化运算以及遗传进化运算的效率。因此编码是 设计遗传算法时的一个关键步骤。  1 ) 编码方法  由于遗传算法应用 的广泛性,迄今为止人们已 经提出了很多不同的编码方法。总的来说,这些编 码方法可以分成三大类:二进制编码方法、浮点数 编码方法和符号编码方法。 

26. 二进制编码方法是遗传算法中最常 用 的一种编码方法,它使用 的编码符号集是 由二进制符号 0 和 1 所组成的符号集 {0,1}, 它所构成的个体基因是一个二进制编码符号 串。二进制编码方法编码、解码操作简单易 行,交叉、变异等操作便于实现。

27. 所谓浮点数编码方法,是指个体的每个基 因值用 某一范围内的一个浮点数来表示,个体的编 码长度等于设计变量的个数。因为这种编码方法使 用 的是设计变量的真实值,所以浮点数编码方法也 叫真值编码方法。与二进制编码法相比,浮点数编 码方法更适合表示范围较大的数和较大空间的遗传 搜索。而且便于遗传算法与经典优化方法的混合使 用 ,改善了遗传算法的计算复杂性,提高了运算效 率。

28. 符号编码方法是指个体染色体编 码串中的基因值取自一个无数值含义,而 只用 代码含义的符号集。这个符号集可以 是一个数字序号表,如 {1 , 2 , 3 , 4, …} ;也可以是一个字母表,如 {A,B,C,D,…} 等。对于使用 符号编码方法 的遗传算法,一般需要认真设计交叉、变 异等遗传运算的操作方法,以满足问题的 各种约束要求,这样才能提高算法的搜索 性能。

29.2 ) 编码串长度  使用 二进制编码来表示个体时,编 码串长度的选取与问题所要求的求解精度 有关;使用 浮点数编码来表示个体时,编 码串长度与决策变量的个数相等;使用 符 号编码来表示个体时,编码串长度由问题 的编码方式来确定;另外,也可使用 变长 度的编码来表示个体。