免费论文
收费论文
发表论文
我要投稿
设为首页 招标网
联系我们
经济学|管理学|法学|计算机|医学|教育|文学|政治|艺术|哲学|更多 经济学|管理学|法律|计算机|医学|教育|文学|政治|艺术|哲学|更多
 论文搜索
  推荐服务: 论文发表 收费论文
期刊论文格式
毕业论文格式
期刊论文范文
毕业论文范文
论文致谢
毕业论文答辩
开题报告
论文选题
英文摘要书写
关于一种基于基因库和多重搜索策略求解TSP的遗传算法
作者:陈 静 杨小帆 曾 智  时间:2009/11/18 12:48:00  来源:论文天下论文网

  论文关键词:旅行商问题  遗传算法  基因库  多重搜索策略

  论文摘要:TSP是组合优化问题的典型代表,该文在分析了遗传算法的特点后,提出了一种新的遗传算法(GB—MGA),该算法将基因库和多重搜索策略结合起来,利用基因库指导单亲遗传演化的进化方向,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际TSP库中多个实例的测试,结果表明:算法(GB—MGA)加快了遗传算法的收敛速度,也加强了算法的寻优能力。

  TSP(traveling salesman problem)可以简述为:有n个城市1,2,…,n,一旅行商从某一城市出发,环游所有城市后回到原出发地,且各城市只能经过一次,要求找出一条最短路线。TSP的搜索空间是有限的,如果时间不受限制的话,在理论上这种问题终会找到最优解,但对于稍大规模的TSP,时间上的代价往往是无法接受的。这是一个典型的组合最优化问题,已被证明是NP难问题,即很可能不存在确定的算法能在多项式时间内求到问题的解[1]。由于TSP在工程领域有着广泛的应用,如货物运输、加工调度、网络通讯、电气布线、管道铺设等,因而吸引了众多领域的学者对它进行研究。TSP的求解方法种类繁多,主要有贪婪法、穷举法、免疫算法[2]、蚂蚁算法[3]、模拟退火算法、遗传算法等。

  遗传算法是一种借鉴生物界自然选择和遗传机制的随机化搜索算法,其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息[4]。遗传算法主要包括选择、交叉和变异3个操作算子,它是一种全局化搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。遗传算法虽然不能保证在有限的时间内获得最优解,但随机地选择充分多个解验证后,错误的概率会降到可以接受的程度。

  用遗传算法求解TSP能得到令人满意的结果,但是其收敛速度较慢,而且种群在交叉算子作用下,会陷入局部解。采用局部启发式搜索算法等,虽然能在很短的时间内计算出小规模城市的高质量解,一旦城市规模稍大就容易陷入局部最优解。因此,为了能够加快遗传算法的收敛速度,又能得到更好的近似最优解,该文采纳了文[5]中杨辉提出的基因库的想法,并结合文[6]中Cheng-Fa Tsai提出的多重搜索策略思想,使用单亲演化与群体演化相结合的方式来求解TSP问题。该文根据文[7]中最小生成树MST(minimum cost spanning tree)的应用,由MST建立TSP的基因库,保存有希望成为最优解的边,利用基因库提高初始群体的质量进行单亲演化,然后利用改进后的交叉算子和的多重搜索策略进行群体演化。

  1 单亲演化过程

  现有的大多数演化算法在整个演化过程中所涉及的基因,大多来源于个体本身,个体质量的高低决定了算法的全局性能,如果群体中初始个体的适应度都较差,肯定要影响算法的收敛速度,对于规模稍大的TSP尤其明显[8]。该文为了克服上述弱点,首先利用普里姆算法求出TSP中最小生成树,并将各个MST中的每一条边都保存在一个n*(n-1)方阵里面,就构成了一个基因库,在生成初始群体的时候尽量使用基因库中的基因片段,来提高整个初始群体的适应度,从而提高算法的效率。

  1.1 TSP编码表示

  设n个城市编号为1,2,…,n,为一条可行路径,Pk=Vk1Vk2…Vkn为一条可行路径,它是1,2,…,n的一个随机排列,其含意是第k条路径起点城市是Vk1,最后一个城市是Vkn,则第k条环路的总长度可以表示为:

  

[1] [2] [3] [4] [5] [6]  下一页

 3000万硕士、博士、期刊论文全文下载  论文发表:快速、低价、优质
提供60万硕士论文、10万博士论文、2700万期刊论文全文下载服务,助您一臂之力! 十年的论文发表经验,快捷的论文发表服务,保证所发表的杂志均为正规合法的期刊,收费同行最低!
[本文关键字] 旅行商问题 遗传算法 基因库 多重搜索策略
[版权说明]《关于一种基于基因库和多重搜索策略求解TSP的遗传算法》论文版权属于作者本人,您可以参考本论文进行论文创作,但不得抄袭、复制!本站免费论文主要来源于用户投稿(投稿网址),如果涉及到侵权问题,请联系lunwentianxia_card@163.com删除。
  遗传算法论文  
·求解不可微函数优化的一种混合遗传算法
·一种启发式频率分配算法
·基于遗传算法的平面叶栅多目标优化设计
·加速遗传算法在边坡稳定分析中的应用
·遗传算法在试题组卷中的应用
 
  推荐期刊投稿
·今日山西
·临床心血管病杂志
·大气科学
·安徽冶金科技职业学院学报
·数码世界
·贵州畜牧兽医
·黑龙江财会
·体育成人教育学刊
·氨基酸和生物资源
·计算机应用
 
·广东交通
·俄罗斯文化评论
·中国腐蚀与防护学报
·母婴世界
·计算力学学报
·装备维修技术
·消防科学与技术
·内江师范学院学报
·临床和实验医学杂志
·组合机床与自动化加工技术
 
·亚非纵横
·武钢技术
·鱼雷技术
·高等教育研究学报
·轧钢
·机械制造文摘-焊接分册
·办公室业务
·表面活性剂工业
·继续教育研究
·数学小灵通(5-6年级版)
   免费论文
公共管理 | 法学 | 理学 | 医药学
政治 | 社会学 | 文学 | 艺术 | 哲学
工学 | 计算机 | 文化 | 英语论文
经济学 | 财政 税收 | 证券金融
管理学 | 会计审计 | 工商管理 | 教育
财务管理 | 论文写作指导 | 应用文
   收费论文
马列毛邓 | 哲学宗教 | 社会科学
政治法律 | 军 事 | 经 济
文化科学教育体育 | 语言文字
文学 | 艺术 | 历史地理 | 自然科学
数理化 | 天文 | 生物科学 | 医药卫生
农业科学 | 工业技术 | 交通运输
航空航天 | 环境安全
   浏览历史

联系论文网 | 收费论文 | 发表论文 | 论文翻译 | 友情链接 | 全部分类 | 网站地图 | 期刊导航
版权所有 2008-2018 论文天下 www.lunwentianxia.com 京ICP备08104503号
.2978516