《dna遗传算法及其函数寻优应用》由会员分享，可在线阅读，更多相关《dna遗传算法及其函数寻优应用（5页珍藏版）》请在金锄头文库上搜索。
1、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
2、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计
3、算潜在的巨 大并 行性及待研究的问题。 L i p t o n 进一步论证了D N A计算可解决完全 性问题( : ) 。自 此， D N A计算引起了许多 学者尤其是计算 机科学家的兴趣， 目前其研究已涉及许多方面， 如D N A计算的能力( 通用性和时空复杂性) 、 模型和算法等( a 最近， 我们开始将D N A计算用于智能系 统的研究1. 常规遗传算法是从生命的遗传机理开发得到 的， 它是解 决复杂问 题的全 局优化算法. 虽然 遗传算法有优良的全 局搜索能力， 但由 于它是基于。 一1 编码模型的 遗传操作， 局部搜索解空 间时不是很有效， 且 个体的多 样性有时减少很快。 常规遗传
4、算法用于处 理实际问题， 尤其是处 理复杂的混淆的和多任务问题时不够灵活， 计算速度慢。 且常规遗传算法模型不可能 表达丰富 的遗传信息， 也不可 能反映遗传信息对生物体生长、 发育的调控作用。 从D N A计算角度看， 在 所有荃于进化机理的方法中， 遗传算法最 适合采用D N A来实现。 这是由 于在遗传算法中， 问 题最优解的搜索 是通 过对染色体的位串结构的个体采用交叉和变异操作， 不断 地产生个体而 获取的。 本文基于D N A的生物机理， 探讨D N A遗传算法的计算模型， 给出D N A遗传算法的结 构、 操作算子 及其用于 求解优 化间 题时的实现步城; 然后通过在函数寻优中的
5、应用来说明 其有 效性， 最后将 D NA遗传算法与常规遗传算法进行了比较。 2 D N A遗传算法的生物遗传学基础 国家自 招科学羞全项目( 6 9 8 7 4 0 3 8 ) 和上海市呀光计匆度目 2 3 5 生物的遗传和变异是生命的两项基本活动。 生物的性状遗传主要是通过染色体上的基因 传递给后代， 因 此基因是控制生物性状的遗传物质的功能 和结 构单位. 生物遗传的基本规律 有 分离规律、 自 由组合规律和墓因的连锁 和互换规律， 生物的变异有三种方式: 基因突变、 基因重 组和染色体变异. 基因突变是指基因内 部的化学变化; 基因 重组是控制不同 性状的基因的重新 组合; 染色体变异
6、是指在一定条件下， 染 色体的结 构和数目 发生的变化.生物的变异一般是不 定向的， 而自 然选择是定向的， 只有适应环境的变异类型才能生存下来并产生后代， 而那些与 环 境不相 适应的变异类型则被淘汰， 如 此一代代地不断进化. D N A是最主要的遗传 物质， 携带着生物的遗传信 息. D N A的基本元素 是核昔酸。 由于化 学结构的不同， 核普酸划分为4 类碱基: 腺嗦岭( A ) ， 鸟嗦岭( G ) , 胞啥咤( C ) 和胸腺啥咤( T ) , D N A由两条极长的核昔酸键组成， 这两条核昔酸键利用碱基之间的氢键而结合在一起， 形成 一条双股的螺旋结构， 且一 股中的 碱基序
7、列与另一 股中 的碱基序列互 补。 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遗传 算法的理论 为了 进一步
8、模拟生物的遗传机理和基因调控机理， 下面讨论一种基于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遗
9、传算法的假设来讨论其结构。 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遗传算法的任务是从
10、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链有更多 萦殖后代的 机会， 从而使优良 特 性得以遗传， 它体现
11、了自 然界适者生 存的思想。 ( 4 ) 交叉 对于选中的用于篆殖的每一对D N A链个体， 将其中部分内容进行互换， 交叉位置是随机 产生的. 通过交叉并凭借交叉点， 产生新的D N A链， 基因得以 极大地改变。 交叉是D N A遗传 算法的核心， 是最重要的遗传算子， 对搜索过程起决定作用， 体现了自然界信息交换的思想. 只 有不断地交叉， 才能不断地产生新的个体， 从而得到优秀个体. 交叉有单点交叉和多点交叉等多种方式。而多点交叉又有。 一点交叉和标准 交叉两种类 型。 在。 一点交叉中， 两点交 叉被证明 是， 一 点交叉的最优数目， 图1 给出了一个两点交叉的例 子. 标准交叉中，
12、 其后代个体是基于 一个随机产生 的交叉特征码， 从父代而产生。 如图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.匹亘 亘亘亚亚
13、二巫巫亚亚 回 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链个体，
14、 随机地选取某一位进行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 A
15、G 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 .
