文档介绍：兰州理工大学
硕士学位论文
遗传算法的种群退化分析及其抑制技术
姓名:马小科
申请学位级别:硕士
专业:计算机软件与理论
指导教师:张远平
20080520
摘要本文以求解固定费用运输问题的遗传算法为研究对象,分析遗传算法的种群退的重组算子导致种群退化,并从编码方式、运输网络各节点的供给和需求能力及整时间的高效算法。,证明了和——在抑制种群退化现象的显著优势。魑V秩和嘶耐ㄓ靡种萍际酢J笛楸砻鱅的抑制能力在大规模问题中具有显著性能,尽管谝种浦行⌒臀侍獾耐嘶芰Σ关键词:进化计算;遗传算法;种群退化现象:生成树;免疫算法;固定费用运化现象,研究种群退化的条件及其抑制技术。证明了基于矩阵编码的遗传算法篏体运输成本三个方面来判断种群退化的算法,这些算法的时间复杂度皆为多项式面证明了算法的变异算子不能抑制种群退化。提出了抑制由算法狦下,.—芄灰种艷狹算法所引发的种群退化现象,试验结果表明—的基于子树补充式单点交叉算子引发完全种群退化现象,并解析地给出了种群退化的发生概率,该概率正比于生成树的叶子节点数。提出了抑制生成树的叶子节点的算法狦篠永砺酆褪笛榱椒矫嬷っ髁为解决——蚐狦谇蠼饽芰τ胍种颇芰ψㄒ恍浴R肓嗣庖遗传算法:明显,但其应用范围大大拓展。本文最后还提出了进一步改进种群退化抑制技术和推广该技术应用领域的未来研究方向。输问题七篠跹硕士学位论文
,.,,瑅痳,—..,瓼琣閑瑃——孙,—,狦狤狦狤琣篹籫籹;—遗传锋法的种群退化分析及其抑制技术迳玞畁七琓遠瑆縮乞遫,.琣瑃甌Ⅱ卜,广.‘
硕士学位论文籪
弓/⒈:马小斜说明兰州理工大学学位论文原创性声明和使用授权日期:加彦年占月,乡日学位论文版权使用授权书原创性声明日期:弘对年‘月,;日本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有权中国科学技术信息研究所将本学位论文收录到《中国学位论文全文数据库》,并通日期:年耭弓日本人郑重声明:,,:保留并向国家有关部门或机构送交论文的复印件和电子版,,可以采用影印、.
第滦髀遗传算法的历史背景选择操作来生成新的种群,并逐步进化到最优或近似最优解。从而实现全局优化的果,阐述本文的研究方向,最后,介绍本文的研究内容和章节安排。统的新思想、新方法,比如早期的自动机理论就试图采用类似神经元的元素建设一种新型的的思维机器。很多学者对关于从生物进化和遗传的机理发展出适合现实世和模拟珂等,进行了开拓性的长期探索和研究,导致了以遗传算法篏徒婊:为代表的进化算法的形十分相似的概念与思想。但没认识到自然遗传方法可以转化成人工遗传算法。世生物进化过程是自然的、并发的、鲁棒的优化过程,优化目标是对环境的自适应。生物种群通过遗传复制和优胜劣汰的自然选择过程,使新种群达到适应环境的最佳状态,显示对自然环境的自适应能力和自身的优化能力。受进化论和遗传学的启发,进化计算使用基于种群的搜索技术,通过对当前种群进行基因重组、变异和目的。本章扼要回顾遗传算法的发展历史,概述遗传算法的基本结构和主要理论成世纪年代以来,科学家不断努力从生物学中寻找用于计算科学和人工系界复杂系统:芯考扑慵际跻蛔匀唤低车募算模型:进化算法:,进化策略篍成。现代遗传算法的发展主要归功于淌诩捌渫旅堑难芯俊甏琀在研究自然和人工系统的自适应行为时,认识到生物遗传和自然进化现象和人工自适应系统的相似关系,提出在研究和设计人工自适应系统时,可以借鉴生物遗传和进化机制。年,岢隽思嗫爻绦母拍,即利用群体进化模拟适应系统的思想。注意到在建立智能机器的研究中,不仅可以完成单个生物体的适应性改进,而且可以通过一个种群的多次迭带也可以取得非常好的适应效果。为了获得一个好的学习方法,仅单个策略的改进是不够的,采用多策略的群体繁殖往往可以产生显著的学习效果。尽管当时没有给出实现这些思想的具体技术,却引进了群体、适应值、选择、变异、交叉等基本概念。年,人也给出了类似的思想,但其重点是放在变异算子而不是重组算子。年,通过对跳棋游戏的研究,在其博士