资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
2 0 0 0中 国 按 刹 与 决 策 学 术 年 会 论 文 集 D N A遗传算法及其函数寻优应用 丁永生任立红邵世垃 ( 东华大拿信意科学与技术学映上梅2 0 0 0 5 1 ) 摘 要恭于生 物D N A结构和遗 传信患流程, 提出一种析软的 墓于D N A编码方法的遗传算 法.给出了D N A遗 传算法的结构, 讨 论了D N A遗传算法的 操作算子, 并通过在函教中 寻优的 例子来说明其有效性. 最后将D N A遗传算法和常舰遗传算法进行了 比较, 指出了D N A遗传算 法的优点, DN A编码方法较常规遗传算法的二进制编码更适合复杂知识的表达。 关健词D NA结构, D N A绮码, 遗传算法, 函教寻伏 1 引言 生命遗传和变异的物质基础是遗传物质的主 要载体 染色体. D N A则是染色体重要的 组成部分, 它在染色体里含量和结构相对稳定, 能够自 我复制, 前后 代可以保持一定的连续性 和变异。 在生物技术方面, D N A ( 基因) 芯片 技术随着“ 人类 基因组计划” 研究的发展应运而生, 它 是进年来在高科技领域内出现的最具时代特征的重大进展. 可以说, D N A芯片为基于D N A 的智能系统应用于许多 实际问题莫定了硬件基础.从计算角度讲, A d l e m a n 首次用实验显 示 了D N A用于计算的 可能 性1j, 指出了D N A计算潜在的巨 大并 行性及待研究的问题。 L i p t o n 进一步论证了D N A计算可解决完全 性问题( : ) 。自 此, D N A计算引起了许多 学者尤其是计算 机科学家的兴趣, 目前其研究已涉及许多方面, 如D N A计算的能力( 通用性和时空复杂性) 、 模型和算法等( a 最近, 我们开始将D N A计算用于智能系 统的研究1. 常规遗传算法是从生命的遗传机理开发得到 的, 它是解 决复杂问 题的全 局优化算法. 虽然 遗传算法有优良的全 局搜索能力, 但由 于它是基于。 一1 编码模型的 遗传操作, 局部搜索解空 间时不是很有效, 且 个体的多 样性有时减少很快。 常规遗传算法用于处 理实际问题, 尤其是处 理复杂的混淆的和多任务问题时不够灵活, 计算速度慢。 且常规遗传算法模型不可能 表达丰富 的遗传信息, 也不可 能反映遗传信息对生物体生长、 发育的调控作用。 从D N A计算角度看, 在 所有荃于进化机理的方法中, 遗传算法最 适合采用D N A来实现。 这是由 于在遗传算法中, 问 题最优解的搜索 是通 过对染色体的位串结构的个体采用交叉和变异操作, 不断 地产生个体而 获取的。 本文基于D N A的生物机理, 探讨D N A遗传算法的计算模型, 给出D N A遗传算法的结 构、 操作算子 及其用于 求解优 化间 题时的实现步城; 然后通过在函数寻优中的应用来说明 其有 效性, 最后将 D NA遗传算法与常规遗传算法进行了比较。 2 D N A遗传算法的生物遗传学基础 国家自 招科学羞全项目( 6 9 8 7 4 0 3 8 ) 和上海市呀光计匆度目 2 3 5 生物的遗传和变异是生命的两项基本活动。 生物的性状遗传主要是通过染色体上的基因 传递给后代, 因 此基因是控制生物性状的遗传物质的功能 和结 构单位. 生物遗传的基本规律 有 分离规律、 自 由组合规律和墓因的连锁 和互换规律, 生物的变异有三种方式: 基因突变、 基因重 组和染色体变异. 基因突变是指基因内 部的化学变化; 基因 重组是控制不同 性状的基因的重新 组合; 染色体变异是指在一定条件下, 染 色体的结 构和数目 发生的变化.生物的变异一般是不 定向的, 而自 然选择是定向的, 只有适应环境的变异类型才能生存下来并产生后代, 而那些与 环 境不相 适应的变异类型则被淘汰, 如 此一代代地不断进化. D N A是最主要的遗传 物质, 携带着生物的遗传信 息. D N A的基本元素 是核昔酸。 由于化 学结构的不同, 核普酸划分为4 类碱基: 腺嗦岭( A ) , 鸟嗦岭( G ) , 胞啥咤( C ) 和胸腺啥咤( T ) , D N A由两条极长的核昔酸键组成, 这两条核昔酸键利用碱基之间的氢键而结合在一起, 形成 一条双股的螺旋结构, 且一 股中的 碱基序 列与另一 股中 的碱基序列互 补。 A和T配对, C和G 配对。 每个染色体是一段双股螺旋的D N A , A, T , C 和G在核昔 酸中的排列序列的多 样性构成 了丰富的 遗传信息. 从计算角度看, D N A计算模型可考虑如下: 单股D N A可表达为4 字母的集合E ( A , T , C , G ) , D N A串可作为译码信息, 酶可看作在D N A序列上的计 算.不同的酶用于不同的 操作 算子. 对D N A可施加分子水平上的作, 这可 使D N A计算模型建立在形式表达划A, T , C , G ? 且对其进行分子操作的基础上。 3 D N A遗传 算法的理论 为了 进一步模拟生物的遗传机理和基因调控机理, 下面讨论一种基于D N A编码的遗传 算法 。 3 . 1 D N A遗传算法的假设 D N A遗传算法是在D N A编码遗传模型 基础上进行遗传操作的.该模型基于以 下假设: DD N A链是由A , T , C 和G组成的一个固定( 或可变) 长度的字符串, 其中每一位都具有 有限数目的等位基因。 2 ) D N A群体中有有限条D NA链。 3 ) 每一条D N A链有一个相应的适应度, 表示该D N A链生存与复制的能力。 适应度为大 于。 的实数, 适应度越大, 表示其生存能力越强。 3 . 2 D N A遗传算法的结构 本节基于以 上D N A遗传算法的假设来讨论其结构。 D N A 遗传算法的 结构与常规遗传算 法的结构类似。下面具体说明D N A遗传算法求解问 题时的具体步骤。 ( 1 ) 初始化及 D N A链编码 使用, 个具有任意D N A链的个体组成初始世代群 体P ( z ) . 一个D N A链由4 种碱基A, G , C , T的结合体构成, 它可以 表示多 个基因. 在D N A遗传算法初始化时, 待解决问题的设计 参数通过 4 字符集X( A, T, C, G 编码以形成染色体, 即D NA链。D NA编码是一个关键的环 节, D N A链的长短将直接影响向题求解的梢度 和收敛速度。 D N A遗传算法的任务是从D N A 群体出发, 模拟进化过程, 最后选择出优秀的群体 和个 体, 满足求解问 题的优化要求. ( 2 ) 评价 按编码规则, 将 D NA群体 P( t ) 中每一个 D N A链的密码子所对应的参数值用于求解问 2 3 6 题, 并按某一标准计算其评价函数 人.若其评价函数较大, 表示该DN A链有较高的适应度. ( 3 ) 选择 按一定的概率 P , 从D NA群体P(t) 中选出.个 D NA链个体, 作为双亲用于繁殖后代, 产生新的 个体加入到下一代尸 (t + 1 ) 。 选择的目 的是使 适应度大的D N A链有更多 萦殖后代的 机会, 从而使优良 特 性得以遗传, 它体现了自 然界适者生 存的思想。 ( 4 ) 交叉 对于选中的用于篆殖的每一对D N A链个体, 将其中部分内容进行互换, 交叉位置是随机 产生的. 通过交叉并凭借交叉点, 产生新的D N A链, 基因得以 极大地改变。 交叉是D N A遗传 算法的核心, 是最重要的遗传算子, 对搜索过程起决定作用, 体现了自然界信息交换的思想. 只 有不断地交叉, 才能不断地产生新的个体, 从而得到优秀个体. 交叉有单点交叉和多点交叉等多种方式。而多点交叉又有。 一点交叉和标准 交叉两种类 型。 在。 一点交叉中, 两点交 叉被证明 是, 一 点交叉的最优数目, 图1 给出了一个两点交叉的例 子. 标准交叉中, 其后代个体是基于 一个随机产生 的交叉特征码, 从父代而产生。 如图2 所示, 若某一位贵上交叉特征码为。 , 则其后 代的碱荃不变。 反之, 其后代的碱墓由双亲互换得到, 也 就是说, 所产生的后代个体是父代个体碱基序列的混合。 T G AG ( CI G TA G TA C GA TAC ( ; T AG A T, 二“ , T G AG C C GT AG T AC GA T AC G TA G AT.-. 文叉点:AG TA TG A AC T GC A C G CC OT AC T A C T二 AGT ATG A AcT GC ACG ccG TAc T Ac T.匹亘 亘亘亚亚二巫巫亚亚 回 Q。交X特征码 T G A G c c l A c T G c A C C C c A C G T AGAT T G A A T G c C c T G T A c G ATA T A T A G c T. A G T AI G AIG T A G T A c C A I G T A c T AcT :人 G T G G C A A T A G c A c G 仁 c G C G C T A A T.” 圈1两点 交又的 例子图2 标准交又的例子 ( 5 ) 变异 以一定的概率 尸 .从D NA群体 尸(t十1)中随机选取若干个 D N A链个体, 对于选中的 D NA链个体, 随机地选取某一位进行D NA链中孩基序列的变化。 D NA链中的变化有孩基的 替换、 缺失和嵌入. 碱荃的替换指染色体中某个碱基或多个碱基从一种状态跳变到另 一种状 态. 碱墓的替换有两种, 一种是转换变异: 嗦岭替 代嗓岭, 啥咤替代喻咤, 如T变为C ; 另一 种 是颠换变异: 嗦岭被嗦岭或咯睫替代, 如T变为A或G , C 变为G或A , 图3 是一个染色体中 的一 个碱基由T 一 A的变异例子。 碱基的缺失与嵌人又称框构转移变异, 即一个或多 个碱签缺 失或嵌入, 再重新组合。 T G AG 右 心C G TA GT A C GA T AC G T A(玉 A 了” “ GT G AG G C C G T A GT AA C GAT A!C TA G AT. 0令 交异。例位 :T G AG 心C C G TA GT A C GA AA C G TA G AT“ 二GT G AG G C C G A TA G CA AT GA TC TA G AT. 图3 点变异的例子(T一A )图 侧位的例子 ( 6 ) 倒位 以 一定的概率尸 。 从D N A群体尸(t +1)中随机选取若干个D N A链个体, 对于选中的 D N A链个体, 随机地选取某两位置, 将它们之间的碱墓顺序进行倒位。 倒位的目的是试图找到 有好的进化特性的墓因顺序。 倒位 操作是可 选的, 根据问 题的需要而定。 图4 给出了 倒位操作 的一个例子. (7) 循环操作 2 3 7 对产生的新一代D N A群 体返回 第( 2 ) 步, 再进行评价、 选择、 交叉、 变异和倒位. 如此 循环 往复, 使群体中个体的 适应度和平均适应度不断提高, 直 到最 优个体的适应度达到某一限值或 最优个体的适应度和群体的平 均适应度不 再提 高, 则迭代过程收敛, 算法结束。 4 D N A遗传算法在函数寻优中的应用 为了验证 D N A遗传算法的有效性 , 我们 将其用于一些函数寻优中。例如, 函数f ( x ) 二 1 0 + 1 / ( x-0 .
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号