文档介绍：摘要遗传算法是模拟自然环境中生物的遗传和进化过程而形成的一种优化算法。它具有全局搜索能力、隐并行性、鲁棒性、操作简单等特点,常被用于解决一些传统优化方法难以解决的问题。旅行商问题亲楹嫌呕煊蛑幸桓龅湫偷腘难问题,它陈述起来简单,求解却很困难。但旅行商问题的求解不仅为其他算法提供了思想方法平台,同时也被广泛地应用于交通、物流、大规模生产、基因测序等领域,具有较高的理论和应用价值。本文主要针对对称型芯苛薚的遗传算法求解,主要工作如下:⒔岷下眯猩涛侍獾奶氐悖杓屏艘桓鲂碌囊糯ń徊嫠阕樱诖嘶∩咸岢⒄攵砸焕嗵厥獾拇蠊婺B眯猩涛侍猓紫龋岢隽艘恢中碌木劾嗖呗裕距离较近的点聚成一类,从而将大规模的;H舾筛鲂」婺N侍猓黄浯危出了一种类的连接方法;最后,构造了求解这类特殊的大规模旅行商问题的有效⒍蕴岢龅乃惴ń辛耸的D馐笛椋贸隽私衔@硐氲慕峁得髁吮疚所设计算法的有效性。关键词:旅行商问题遗传算法交叉算子聚类了一种新的遗传算法,并且证明了算法的收敛性。算法。
,甋————————————————————————————————————————————————————一瑀瑂..,,琹—.、琣,·琓甌瓹..瓼,
导师签名:牛本人签名:—立耻本人签名:至蹬本学位论文属于保密,在一年解密后适用本授权书。西安电子科技大学学位论文创新性声明关于论文使用授权的说明期翌生三:日期塑:;日期丝:秉承学校严谨的学分和优良的科学道德,本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢中所罗列的内容以外,论文中不包含其他人已经发表或撰写过的研究成果;也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说申请学位论文与资料若有不实之处,本人承担一切的法律责任。本人完全了解西安电子科技大学有关保留和使用学位论文的规定,即:研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件,允许查阅和借阅论文;学校可以公布论文的全部或部分内容,可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证,毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。C艿明并表示了谢意。论文在解密后遵守此规定
第一章绪论引言遗传算法的产生和发展进成为近代科学发展的显著特点之一。遗传算法正是从大自然的杰作——生物进旅行商问题琓蔷涞淖楹嫌呕侍猓币是一个难问题】。它的历史由来已久,到目前,有关旅行商问题的研究有了很大进展,但该问题仍然未能得到彻底解决。当城市规模不断增大,可供选择的路线数目是呈指数级增长的,一般很难精确地求出其最优解,因而找出有效的近似求解算法就显得很有意义。遗传算法晏岢龅摹一种新型的、模拟自然界中生物进化过程的随机搜索方法。由于遗传算法不受搜索空间的限制性假设的约束,因此不必要求诸如连续性、可导性和单峰等假设【浚并且具有全局优化,隐并行性,鲁棒性等特点,在求解用传统方法难以求解的复杂问题’,如组合优化、模式识别、计算机网络优化等,显示出良好的性能和效果。人们已经开始应用遗传算法来求解大规模的旅行商问题【浚⑶业玫搅艘恍令人满意的结果。遗传算法已经成为求解旅行商问题的有效工具,本文进一步研究用遗传算法求解旅行商问题。世纪年代以来,科学家努力从生物学中寻找用于计算机科学和人工系统的新思维、新方法和新途径,生命科学与工程科学相互交叉、相互渗透、相互促化论中得到的灵感和启迪【浠舅枷胧荄酆蚆囊糯怠进化论最核心的是自然选择学说【小K衔#锝且桓龌郝变化过程,物种不是被创造出来的,而是自然选择的必然结果。“物竞天择,适者生存”。生物要想生存下来,就必须进行生存斗争。斗争是多方面的,有种内斗争、种间斗争以及生物与无机环境间的斗争。只有适应性强的个体才能在斗争中存活下来,并且有更多的机会将有利变异传给后代;而不适应斗争环境、具有不利变异的个体将面临淘汰。把这种在生存斗争中适者生存、不适者淘汰的过程称为自然选择。遗传学说最重要的是基因遗传原理【】。他认为遗传以密码方式存在于细胞中,并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特,怯蒍
方法,提出了遗传算法的基本定理——模式定理,为遗传算法的发展奠定了理论殊性质。所以,每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰,适应性高的基因结构现代遗传学和细胞学的研究表明】,生物的遗传物质主要保存在染色体中,染色体由脱氧核糖核酸偷鞍字首槌桑换蛟蚴侵感幸糯畔⒌腄序列,是控制性状的基本遗传单位。基因可以精确的复制,也可以发生突变,并可以通过控制蛋白质的合成而控制生物的性状。生物体自身通过对基因的复制和交