毕设-李良良.doc

毕业论文(设计)
论文(设计)题目:改进粒子群算法求解TSP问题
系别:
计算机与信息科学系
专业:
网络工程
学号:
2008107407
姓名:
李良良
指导教师:
易云飞
讲师
时间:
2012年6月
河池学院
毕业论文(设计) 开题报告
系别:计算机与信息科学系专业:网络工程
学号
2008107407
姓名
李良良
论文(设计)题目
改进粒子群算法求解TSP问题
命题来源
教师命题□学生自主命题□教师课题
选题意义(不少于300字):
旅行商问题(TSP)又名货郎担问题,是一个典型的NP难题。其数学描述非常简单,但却无法找到一个确定的算法在多项式时间内求解TSP 问题,另一方面很多研究领域出现的复杂优化问题可以被抽象概括为TSP问题加以求解,因此找到能够有效解决TSP 问题的方法,在理论上和实际应用中都很有价值。
本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义,使粒子群算法适合于求解TSP问题,并采用贪心算法的思想每一步都取局部最优。这样产生的初始种群全局最优值已经比较接近问题的解,因此可以节省搜索时间,提高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷,引入了适合于求解TSP问题的基于球隙迁移的改进措施,克服了PSO算法易陷入局部最优的缺陷。
作为一类组合优化问题的代表,TSP问题在实际工程中有许多应用,如计算机联网、物流等行业中的车辆调度优化、电力系统配电网络重构、城市管道铺设优化、交通导航、电气布线、电子地图、VLSI单元布局、X射线结晶学问题等。
研究综述(前人的研究现状及进展情况,不少于600字):
在我国,在粒子群优化算法的研究则是刚刚起步,深入的研究和应用还很少, PSO算法的研究还有大量的研究工作要做。主要的研究方向有下面几个方面:
(l)粒子群算法的改进
标准粒子群算法主要适用于连续空间函数的优化问题,如何将粒子群算法应用于离散空间优化问题,特别是一类非数值优化问题,将是粒子群算法的主要研究方向。另外,充分吸引其他进化类算法的优势,以改进PSO算法存在的不足也是值得研究的问题。
(2)粒子群算法的理论分析
到目前为止,PSO算法的分析方法还很不成熟,存在许多不完善之处。如何利用有效的数学工具对PSO算法的运行行为、收敛性以及计算复杂性进行分析也是目前的研究热点之一。
(3)粒子群算法与其他进化算法的比较研究
目前,进化算法的研究在理论和应用两方面都得到迅速发展,效果显著。其中研究的比较成熟的有遗传算法、蚁群算法等,而粒子群算法是一个新兴的群体智能算法,目前己成为进化算法的一个重要分支,如何从多方面比较各种算法从而得到各自的特长和不足,如何吸引其他进化类算法的优势来弥补PSO算法的不足也是当前研究的热点之一。
(4)粒子群算法的应用
算法研究的目的是应用,如何将PSO算法应用于更多领域,同时研究应用中存在的问题也是值得关注的热点。
研究的目标和主要内容(不少于400字)
基本粒子群算法的速度进化方程由认识和社会两部分组成,如何实现全局搜索能力与局部搜索能力的平衡是一个重要的研究方向。PSO算法极易陷入局部极值,如何保证其在陷入局部最优时,能够及时“跳出”,继续进行全局搜索,对于提高其寻优性能有着至关重要的影响。球隙迁移算法中,发现局部极小(开采)和克服局部极小(勘探)这两个过程互不影响,并能防止其陷入已经发现的局部极小,这样就避免了不必要的重复探索,提高了性能。在解决TSP问题时,基于球隙迁移的策略克服了易陷入局部最优的缺陷,它不但能保证及时的“跳出”,同时,还能有效地回避历史上已经发现的多个局部极小。
初始种群的产生借鉴贪心算法(Greedy Algorithm)的思想,每一步都取局部最优。由于旅行商问题为一个循环回路,所以可以选择任意一个城市作为起始城市。采用贪心算法的思想,随机选择一个城市作为出发城市,并始终选择距离当前城市最近的城市作为下一个遍历城市,直到所有城市均被遍历后直接连接到出发城市即可。可以利用这个贪心算法得到近似最优循环序列,产生一定规模的初始种群。
PSO算法在连续空间优化问题上已经取得了很好的效果,但是将其应用在TSP等离散优化问题中还是一种尝试。因此用改进的PSO算法有效的求解TSP问题,在整个组合优化领域和实际工程中都有着重要影响和实际意义。
拟采用的研究方法
a)查找并阅读相关资料,了解基本的内容,利用需求分析文档,对整个系统有个初步的架构。
b)搜寻实验用的文件文档集和研究过程中用到的各种工具软件。
c)根据已有的资料形成基本的思想。
d)采用MyEclipse 。
研究工作的进度安排
2011