ScholarMate
English简体中文繁體中文
客服热线:400-1616-289
登录注册
学位论文

遗传算法的研究与应用 ——基于3PM交叉算子的退火遗传算法及应用研究

王银年*
2009-8-1
21阅读
引用收藏
分享

摘要

遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。它的研究历史比较短,早期是一种试图解释自然系统中生物的复杂适应过程入手,模拟生物进化的机制来构造人工系统的模型。近年来世界范围形成的进化计算热潮,计算智能已作为人工智能研究的一个重要方向,以及后来的人工生命研究兴起,使遗传算法受到广泛的关注。鉴于遗传算法存在着收敛速度慢或易出现“早熟”现象,本文对遗传算法进行改进,针对TSP问题提出贪心3PM交叉算子,同时对模拟退火算法进行改进,并将改进后的两种算法相结合,形成一种基于3PM交叉算子的模拟退火遗传算法(GCBSAGA)。主要研究工作如下:首先介绍了遗传算法国内外的研究现状,以及现有的遗传算法与模拟退火算法相结合的现有情况。其次,在阐述遗传算法基本概念、原理、方法、步骤的基础上,针对巡回旅行商问题(TSP)提出一种基于3PM交叉算子的模拟退火遗传算法(GCBSAGA)。在新算法中,一方面,对遗传算法进行了改进,先改进了它的构架,再引入判断搜索效率的条件,一旦搜索效率下降,便终止遗传算法,这样便保留了遗传算法前期全局高效的搜索,屏弃了后期搜索能力低的毛病。然后又提出了一种新的交叉算子―—贪心3PM交叉算子,这种算子不但考虑到了城市位置的关系,更重要的是考虑到了城市之间边的关系。采用三个父代产生子代的方法,能够得到更优的边信息,而且采用双向轮转的方法,使子完全地继承了父代的边的信息。而且对产生的子代还进行退火选择,从而将温度这一概念加入到遗传算法中,这样使子代基本不会出现退化现象。通过实验也可以看出,贪心3PM交叉算子收敛速度非常快,搜索能力极高。另一方面,对模拟退火算法进行改进,它使用的初始解就是遗传算法结束后得到的全局较优解,即对全局较优解进行独立退火,这样使得原本盲目搜索的模拟退火算法固定在有希望的区域里搜索,大大提高了搜索效率。模拟退火算法使用的初始温度也是遗传算法结束后的温度,这样高温时使用遗传算法,发挥它高效的全局搜索能力,低温时使用模拟退火算法,发挥它强大的局部搜索能力。然后选用国际公认的TSP库的数据进行测试,找到了比TSP库提供的最优解更优的解,证明了新算法的有效性。最后把新算法运用到配送和回收一体化的车辆路径问题这一实际问题中,并且针对问题的特殊性加入了编码解码机制,通过实验和对比验证了GCBSAGA算法在解决此类问题时的高效性。

学科与关键词

关键词
遗传算法退火选择模拟退火算法巡回旅行商问题贪心3PM交叉算子
相关
加载中…
  • 基于特征进化的混合遗传算法
    林冬梅; 王东计算机应用与软件, 2009, (04): 246-248.
  • 混合遗传算法解决单目标旅行商问题的研究
    袁成林大众科技, 2013, (06): 4-6.
  • 遗传算法的探究与应用——以高校排课系统为例
    李行; 包仁义; 金秋之; 宋智洋计算机光盘软件与应用, 2013, (08): 135-136.
查看全部 →

学位信息

颁发单位
江南大学
学位
硕士
答辩日期
2009-08-01

作者

  • 王

    王银年 (通讯) (第一作者)

登录解锁更多功能

  • 收藏这篇,随时在“我的 · 收藏”找回
  • 认领你的成果,生成推广素材
  • 关注作者获取最新成果
  • 加入项目组、协同写作
注册 / 登录

产品服务

  • 科研之友
  • 创新城
  • 科创云

服务支持

  • 帮助中心
  • 隐私政策
  • 服务条款

联系方式

在线客服:【】
客服热线:400-1616-289
电子邮箱:support@scholarmate.com

关注或下载科研之友

微信二维码
微信公众号
客户端下载二维码
下载客户端
科研成果科研人员科研机构科研动态爱瑞思软件

©2026 深圳市科研之友网络服务有限公司

公安备案图标粤公网安备 44030502000213
粤ICP备 16046710 号粤B2-20110417