DNA遗传算法的研究及其在指派问题中的应用

《DNA遗传算法的研究及其在指派问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TPl8密级：(秘密、机密、绝密)学校代码：10057研究生学号：08834007DNA遗传算法的研究及其在指派问题中的应用DNAgeneticalgorithmresearchanditsapplicationtotheassignmentproblem专业名称：计算机应用技术指导教师姓名：李孝忠教授研究生姓名：任吉栋申请学位级别：工学硕士论文提交日期：2011年2月论文课题来源：自选项目学位授予单位：天津科技大学天津科技大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究工作所取得的成果。除文中特别加以标注引用的

2、内容外，本论文不包括任何其他个人或集体己经发表或撰写的成果内容，也不包括为获得天津科技大学或其它教育机构的学位或证书而使用过的材料。对本文研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：住左椽日期：矽Jf年多月JJ6日知识产权和专利权保护声明本人郑重声明：所呈交的论文是本人在导师具体指导下并得到相关研究经费支持下完成的，其数据和研究成果归属于导师和作者本人，知识产权单位属天津科技大学；所涉及的创造性发明的专利权及使用权完全归天津科技大学所有。本人保证毕业后，以本论文数据和资料发表论文或使用论文

3、工作成果时署名第一单位仍然为天津科技大学。本人完全意识到本声明的法律后果由本人承担。作者签名：钍唁梳日期：弘『

4、年岁月伯日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，同意公布论文的全部或部分内容，允许论文被查阅和借阅。本人授权天津科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密Il(请在方框内打“寸’)，在年解密后适用本授权书。本学位论文属于不保密臣几请在方框内打cc√，，)。作者签名

5、：名专槠。日期：导师签名：日期：移巴垆f，年，；月／二日／【年歹月膨日摘要DNA(Deoxyribonucleicacid)计算是一种模拟生物分子结构并借助于分子生物技术进行计算的新方法。目前DNA计算还处于起步阶段，本身还有很多理论和实际问题需要解决。遗传算法是一种模拟生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，在搜索最优解方面有独特的优势。DNA计算与遗传算法两者天生就具有某种必然的联系，可以互相借鉴。由于生物DNA计算的局限性，遗传算法可以作为DNA计算进行复杂优化问题求解的桥梁。从DNA计算角度看，在所有基于进化机理的方法中，遗传

6、算法最适合采用DNA来实现。基于DNA计算的遗传算法，可以进一步模拟生物的遗传机理和基因调控机理，同时改进了DNA计算和遗传算法，具有更好的应用前景。本文将DNA计算思想和遗传算法相结合，围绕研究DNA计算的实现以及提高遗传算法的搜索效率、局部搜索能力及克服早熟收敛等核心问题，研究DNA遗传算法。并在此基础上提出了一种基于优秀基因片段思想的改进DNA遗传算法，将这段基因片段提取出来并将它遗传到后代中，可以加快收敛速度。给出了DNA遗传算法的结构，讨论了选择、交叉和变异算子的具体操作。最后本文将改进后的DNA遗传算法应用到指派问题最优解的求解中，提出了具

7、体的编码和详细的算法步骤，并对一个具体实例进行了仿真实验，证明了改进后的DNA遗传算法具有收敛速度快和较好的全局搜索能力，初步验证了该算法的有效性和实用性。关键词：DNA计算；遗传算法；指派问题ABSTRACTDNA(Deoxyribonucleicacid)computationisanewmethodsofsimulatingbimolecularstructureandconductedbymeansofmolecularbiologicaltechniques．DNAcomputationiscurrentlystillinitsinfancy

8、,therearemanytheoreticalandpracticalissuestoberesolved．Geneticalgorithmisacomputationmodel，whichsimulatesthenaturalselectionandthegeneticmechanismofthebiologicalevolution．Ithasauniqueadvantageinthesearchoftheoptimalsolution．BothofthemhaveadefinitelinkandtheyCalllearnfromeachothe

9、r．ForthelimitationsoftheDNAcomputation，genetica