遗传算法

《遗传算法》由会员分享，可在线阅读，更多相关《遗传算法（31页珍藏版）》请在金锄头文库上搜索。

1、 遗传算法前 言 人类基因组计划启动于年。年月 日，来自美国、英国、日本、法国、德国和中国 的科学家绘制出人类基因组“工作框架图”。 年月日，参与人类基因组计划的六国科学家共 同宣布：人类基因组研究工作巳取得了实质性进展， 经辽初步测定和分析，人类大约有万到万个基因 ，这些基因包含了人类生长、发育、衰老、遗传病变 的全部遗传信息，巳为破译生命之谜奠定了坚实基础 。笫一章 生物的遗传与进化从地球上最早生命的出现到现在，经过了 多亿年的繁衍进化，今天的自然界巳物种繁多，形 态各异，姿彩万千。那么，是什么支配着地球上生 物这种发展变化进程的呢？主宰地球生物如此演化 的因素主要有两方面：一是生命物质自

2、身的遗传与 变异功能（内因）；二是自然界环境与资源的限制 （外因），使生存能力弱的生物遭到淘汰，而对自 然环境适应的生物得进化。也就是说，地球上生物 的发展与进化，是生命物质自身具有的功能与自然 界相互作用的结果，正是这种作用使地球上的生命 形式得到优化。 一、生物的遗传与变异“种瓜得瓜，种豆得豆”，这句话 反映了生物第一代和笫二代之间， 在形态、结构和生理功能上非常相 似，这就是遗传现象。子女像父母 ，但父母并不能把任何一个具体器 官直接传给孩子，父代与子代之间 传递的桥梁只能是精子和卵子细胞 中的染色体。（）染色体与 DNA 染色体（chromosomes ），顾名思义是一种可染色 （容易

3、被碱性染料染成深色 ）的物质，它是遗传物质的 载体，主要由人们称之为 DNA 的分子（见图） 及同它所附的蛋白质组成。 DNA 又称脱氧核糖核酸。研 究表明，NA分子的作用就 是携带和传递由“上一代”传下 来的遗传信息。 在人体数以亿计的细胞内 共有对（计条）染 色体，其中一对为性染色体 。图 DNA分子DNA是一种高分子化合物。年, 美国科学家沃森 和英国科学家克里克提出了 DNA 模型（如图所示）， 它是以两条螺旋般的长链交替相联作骨架, 以碱基对（A-T和C- G）作为横杠、以氢键作为联钩所构成的线状分子。五种碱基名 称和配对情况是：腺嘌呤A与胸腺嘧啶T配对，鸟嘌呤G和胞嘧 啶C配对，还

4、有尿嘧啶U。如果一个链是ATCGT，那么另一 条链就应该是TAGCA ，这称为碱基配对法。 如果碱基的 顺序排错了，或有缺失、增加等现象，都会造成遗传上的差错 ，引起疾病，甚至死亡。因为每三个碱基为一个信息单位（密 码）, 而一个 DNA上的碱基可多达几百万个，所以 DNA 上的信 息多得数不清。破译密码的竞赛中，美国的尼伦伯格博士走在前面。图 DNA 分子 的 “双螺旋” 结构沃森DNA的天才，美国 生物学家，与克里克 博士一起发现了DNA 的双螺旋结构。 年获得诺贝尔生 理学和医学奖。解读人类 DNA 密码（）基因（gene） 生物体的每种可遗传的功 能都涉及到 DNA 链上的一个 节段，

5、现代分子遗传学把一个 有特定遗传功能的 DNA 节段 称为一个基因 (gene )。 基因 才是控制生物遗传的物质单元 。“基因”好比是一部天书中一 个一个的单词,如眼睛基因、 鼻子基因等等。而每个基因 又含有成百上千的碱基，“碱 基”好比是组成单词的字母,每 三个碱基组成一个密码,它们 在染色体上有次序地排列，排 列次序代表遗传密码信息。图为氨基酸的密码 。图 以性染色体里的基因为例，见图母亲的性染色体 中由 特定的 X(1) 和 X(2) 基因组成，父亲 的性染色体由 特定的 X(m) 和 Y 基因组成 。两个染色体的结合 是这两对基因竞争后 的产物，竞争的 结局 可能是 X(1),X(m

6、) (女)，X(1),Y ( 男)，X(2),X(m) ( 女)，X(2),Y ( 男)，这一对新的结合物为 子代的一对性染色体 。由此可见，生男生 女并不由母亲决定， 而是由父亲的基因Y 随机决定的。女性男性子 代X(1)X(2)X(m)Y? ?图 性别基因的竞争（）变异现象 作为遗传物质的基因及其所含的核苷酸 （每个核苷酸里有一个碱基）分子序列不是 永远不变的，常常会发生某一个核苷酸变更 或移位，而使基因发生性质上的变化。称这 种基因结构的变化为变异(mutation)。例如, 在 人体数以亿计的细胞中，有一个至少由 个所谓原始致癌基因组成的“小集团”，这些 原始致癌基因一旦遇到辐射、吸入

7、某些化学 物质，或其他环境方面的影响，就会发生突 变，或者过分活跃，开始无节制地分裂，并 且在人体内不断地转移、扩散，贪婪地吞噬 人体的养分，直到病人死亡。二、生物的进化 世纪年代， 英国博物学家达尔文，综 合了许多世纪以来科学和 实践的成就，提出了“自 然选择学说”，不仅说明 物种是可变的，而且对生 物的适应性作出了正确的 解释。生物在发展过程中 ，只有能适应环境的生物 才能生存下来，并产生后 代；而那些与环境不相适 应的生物就被淘汰（简称 优胜劣汰）。生物是在自 然条件的作用下，从简单 到复杂，从低等到高等， 逐渐变化形成的。（）自然选择（）进化的基本过程 以循环圈的群体为起点，经过竞争后

8、，一部分群体被淘汰 而无法再进入这个循环圈，而另一部分则成为种群。种群通过 婚配或杂交（物种间的远缘杂交和品种间的近缘杂交）的作用 产生子代群体（简称子群）。进化的过程中，可能因为基因变 异而产生新的个体，这时子群成长为新的群体而取代旧群体。 在新的一个循环过程中，新的群体将替代旧的群体而成为循环 的开始。 群体种 群竞争婚配子群变异淘汰的群体三、生物遗传与进化对组合优化问题的启发 （）组合优化问题的描述组合优化问题可以形象地用二元集 (S, f) 描述,其中S 是 解空间，它是由一切可能的解组成的有限集，f 是目标函数 。组合优化问题是在 S 中找到一个解, 使得其目标函数值达 到最小 (或

9、最大)。如果一个组合优化问题 (S,f) 的目标函数在S上只有一 个最小 (或最大值)，则称为凸情况。在这种情况下可以用 任何梯度下降(或上升)方法找到最优解,但在大多数情况下 ，目标函数在 S 上存在多个极值点，此时称为非凸情况。 在优化计算时，这些局部极值点为全局寻优带来困难。因 为在开始时没有任何朝向最优解的提示信息，所以只能从 某一初始状态开始去搜索。如果在这种情况下仍采用梯度 搜索方法，很可能使系统陷入局部极值点。(2) 遗传算法的基本思想遗传算法是模仿生物遗传与进化过程而 得出的一种随机优化方法，对非线性、多极 值的寻优问题是一种有效方法。遗传算法先 对问题的可行解 (近似解) 进

10、行编码，表示成 “染色体”,再由随机方法产生一群“染色体”组 成初始种群，它们对应的的目标函数值大小 视为生物种群的优劣，通过适应度构成优胜 劣汰、适者生存的“自然环境”,种群通过杂交 、交换、变异等不断演化，产生新的更加优 良的种群。这样经过若干代的进化，最后求 得适合问题的全局最优解。第二章 遗传算法 1962年，美国 Michigan大学 John H.Holland 教授发 现，按照类似活的有机体的自然选择 (selection) 、杂交 (crossover)和变异(mutation)的自然进化(natural evolution)方式, 编制的计算机程序能够解决复杂的优化 问题,

11、这类新的优化方法就是遗传算法 ( Genetic Algorithm), 简称 GA，又称基因算法。一、 遗传算法的实施步骤步骤 对研究的变量或对象进行编码（建立字符 串与可行解之间的联系）,并随机地建立一个初始群体 。步骤 计算群体中诸个体的适应度(个体优劣尺 度)。步骤 执行产生新群体的操作，包括：(a) 选择 。将适应度高的个体选择到新群体中,删 除适应度低的个体；(b) 杂交 。随机选出个体对, 进行片段交叉换位 ,产生新个体对； (c) 变异。随机地改变某个体的某个字符,而得到新个体 。 步骤 根据某种条件判断计算过程是否可以结束,如果 不满足结束条件,则返回到步骤,直到满足结束条件

12、为止。在后面的几段里,将根据遗传算法的步骤, 介绍执行中的某 些细节。（）编码与初始群体将优化问题可行域内的试探解(可行解)设计成字符串(视 为染色体)的工作称为 编码(encoding)。字符串每个位置上的 元素代表基因，每个基因记录了解中某个分量的遗传信息。编码的形式分三种：当优化问题的变元(单变量或多变量) 取值是实数时，采用实数编码 (即字符串的每个位置上都取实 数 )，这是一种最常用的编码形式。如果优化问题是单变量且 变元的取值是整数时,或者当变元是开关型的多变元(指变元的状态只取两种情况)时，则采用0/1二进制编码。这种编码形式 虽然简单但对于实变量(特别是多实变元)的问题，二进制

13、编码 会限制解的精度和搜索空间，而编码太长又会导致计算量太大, 因此二进制编码在工程计算中应用并不广。如果是符号型变元 (指变元的状态只是一些事物名称, 如职业变元的状态是由公务 员、教师、医生、工人等组成 )，一般采用整数编码，即字符 串的每个位置上用整数序号，k；k。以后我们 将在附录中作一介绍。现以实数编码为例，详细说明如下：设有最小化问题min f(X) (2-1)a(j)x(j)b(j) 式中，X=(x(1),x(p) 为优化变量向量，a(j),b(j) 为x(j)的变 化区间，f 为目标函数(假设其值为非负)。这里采用实数编码 ，即利用如下线性变换x(j)=a(j)+r(j)( b

14、(j)-a(j) ), (j=1,2,p) (2-2)把初始变化区间a(j),b(j)中的第个优化变量x(j)对应到0,1 区间上的实数 r(j)=0.I(j,1) I(j,2) I(j,m)。在GA中称r(j)为 基因，而 I(j,k) ( k=1,2,m ) 取中任一个整数, 它相 当于生物学中的 碱基。把个优化变量对应的基因串 ( r(1),r(2),r(p) ) 即 ( 0.I(1,1)I(1,m), 0.I(2,1)I(2,m), , 0.I(p,1)I(p,m) ) 称作 染色体，或个体。经过编码，所有优化变量 x(j) 的取值范围都统一为 0,1，这样，遗传算法只对个体 (染色体

15、) 施行各种遗传操 作，而不是对优化变量 x(j) 本身，从而简化了计算。当编码方式被确定后，遗传算法要求先选择一组初始 群体(设群体规模为 n, 规模越大，越容易搜索到全局最优 解），即生成 n 组0, 1区间上的均匀随机数, 每组 p 个， 即r(i,j)j=1,2,p; i=1,2,n, 可以排成一个 np 矩阵r(1,1) r(1,2) r(1,p) r(n,1) r(n,2) r(n,p) A=称为群体矩阵，矩阵每一行都代表一个染色体 (个体), 将矩 阵元素 r(i,j) 代入式(2-2)得优化变量值 x(i,j) , 再经式 (2-1) 得到相应的目标函数值 f(i) （i=1,2,n ）。把它们从小到 大排序，对应的个体也跟着排序 (在不作声