计算智能专业课程设计粒子群优化算法求解旅行商问题Matlab实现.doc
《计算智能专业课程设计粒子群优化算法求解旅行商问题Matlab实现.doc》由会员分享,可在线阅读,更多相关《计算智能专业课程设计粒子群优化算法求解旅行商问题Matlab实现.doc(11页珍藏版)》请在咨信网上搜索。
1、摘要:TSP是一个经典NPC问题。本文首先介绍旅行商问题和粒子群优化算法基础概念。然后结构一个基于交换子和交换序1概念粒子群优化算法,经过控制学习因子和、最大速度,尝试求解旅行商问题。本文以中国31个省会城市为例,经过MATLAB编程实施对旅行商问题求解,得到了一定优化程度路径,是粒子群优化算法在TSP问题中利用一次大胆尝试。关键字:TSP问题;粒子群优化算法;MATLAB;中国31个城市TSP。粒子群优化算法求解旅行商问题1. 引言1. 旅行商问题概述旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题货郎担问题,是数学领域中著名问题之一。假设
2、有一个旅行商人要造访n个城市,她必需选择所要走路径,路径限制是每个城市只能造访一次,而且最终要回到原来出发城市。路径选择目标是要求得路径旅程为全部路径之中最小值。TSP问题是一个组合优化问题,其描述很简单,但最优化求解很困难,若用穷举法搜索,对N个城市需要考虑N!种情况并两两对比,找出最优,其算法复杂性呈指数增加,即所谓“指数爆炸”。所以,寻求和研究TSP问题有效启发式算法,是问题关键。2. 粒子群优化算法概述粒子群优化算法(Particle Swarm optimization,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是经过模拟鸟群觅食行为而发展起来一个基于群体协作随机搜索
3、算法。通常认为它是群集智能 (Swarm intelligence, SI) 一个。它能够被纳入多主体优化系统(Multiagent Optimization System, MAOS). 粒子群优化算法是由Eberhart博士和Kennedy博士发明。PSO模拟鸟群捕食行为。一群鸟在随机搜索食物,在这个区域里只有一块食物。全部鸟全部不知道食物在那里。不过她们知道目前位置离食物还有多远。那么找到食物最优策略是什么呢。最简单有效就是搜寻现在离食物最近鸟周围区域。PSO从这种模型中得到启示并用于处理优化问题。PSO中,每个优化问题解全部是搜索空间中一只鸟。我们称之为“粒子”。全部粒子全部有一个由被
4、优化函数决定适应值(fitnessvalue),每个粒子还有一个速度决定她们翱翔方向和距离。然后粒子们就追随目前最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解),然后经过迭代找到最优解,在每一次叠代中,粒子经过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到最优解,这个解叫做个体极值pBest,另一个极值是整个种群现在找到最优解,这个极值是全局极值gBest。另外也能够不用整个种群而只是用其中一部分最优粒子邻居,那么在全部邻居中极值就是局部极值。3. 粒子群优化算法求解旅行商问题旅行商问题是一个经典、易于描述却难于处理组合优化问题,而且是一个NP完全难题,其可能路径数目和城市数
5、目n是成指数型增加,对n个城市而言,可能路径总(n-1)!。伴随n增加,路径数将按数率急剧增加,即所谓“指数爆炸”,所以通常极难正确地求出其最优解,所以寻求出其有效近似求解算法就含相关键理论意义。而粒子群优化算法是处理复杂问题有效方法,自然也能应用于处理旅行商问题。PSO模拟鸟群捕食行为。一群鸟在随机搜索食物,在这个区域里只有一块食物。全部鸟全部不知道食物在那里。不过她们知道目前位置离食物还有多远。那么找到食物最优策略是什么呢。最简单有效就是搜寻现在离食物最近鸟周围区域。2. 粒子群算法基础思想21. 粒子群优化算法基础原理一个由个粒子(Particle)组成群体(Swarm)在维搜索空间中以
6、一定速度飞行,每个粒子在搜索时,考虑到了自己搜索到历史最好点和群体内(或领域内)其它粒子最好点,在此基础上进行位置(状态、也就是解)改变。第个粒子位置表示为:第个粒子速度表示为:,第个粒子所经历历史最好点表示为:群体内(或领域内)全部粒子所经历过最好点表示为:。通常来说,粒子位置和速度全部是在连续实数空间内进行取值,粒子位置和速度依据以下方程进行改变 其中,为惯性权重。和称为学习因子(Learning Factor)或加速系数(Acceleration Coefficient),通常为正常数。学习因子使粒子含有自我总结和向群体中优异个体学习能力,从而向自己历史最优点和群体内或领域内历史最优点靠
7、近。和通常等于2。,是在区间内均匀分布伪随机数。粒子速度被限制在一个最大范围内。 当把群体内全部粒子全部作为领域组员时,得到粒子群优化算法全局版本;当群体内部分组员组成领域时得到粒子群优化算法局部版本。局部版本中,通常有两种方法组成领域,一个是索引号相邻粒子组成领域,另一个是位置相邻粒子组成领域。粒子群优化算法领域定义策略又能够称为粒子群领域拓扑结构。12. 粒子群优化算法步骤3. 粒子群优化算法关键组成要素1. 群体大小是个整型参数。当很小时候,陷入局优可能性很大。然而,群体过大将造成计算时间大幅增加。而且当群体树木增加至一定水平时,再增加将不再有显著作用。当=1时,PSO算法变成基于个体搜
8、索技术,一旦陷入局优,将不可能跳出。当m很大时,PSO优化能力很好,可是收敛速度将很慢。2. 学习因子和学习因子使粒子含有自我总结和向群体中优异个体学习能力,从而向群体内或领域内最优点靠近。和通常全部等于2,不过也可能有其它取值。不过通常等于,而且范围在0和4之间。3. 最大速度:最大速度决定粒子在一次迭代中最大移动距离。较大,探索能力增强,不过粒子轻易飞过最好解。较小时,开发能力增强,不过轻易陷入局优。有分析和试验表明,设定作用能够经过惯性权重调整来实现。所以现在试验基础上使用进行初始化,将设定为每维变量改变范围,而无须进行细致选择和调整。4. 惯性权重智能优化方法运行是否成功,探索能力和开
9、发能力平衡是很关键。对于粒子群优化算法来说,这两种能力平衡就是靠惯性权重来实现。较大惯性权重使粒子在自己原来方向上含有更大速度,从而在原方向上飞行更远,含有愈加好搜索能力;较小惯性权重使粒子继承了较少原方向上速度,从而飞行较近,含有愈加好开发能力。经过调整惯性权重能够调整粒子群搜索能力。5. 领域拓扑结构全局版本粒子群优化算法将整个群体作为粒子领域,速度快,不过有时会陷入局优;局部版本粒子群优化算法将索引号相近或位置相近个体作为粒子领域,收敛速度慢一点,不过极难陷入局部最优。显然,全局版本粒子群优化算法能够看作局部版本粒子群优化算法一个特例,立即整个群体全部作为领域。6. 停止准则通常使用最大
10、迭代次数或能够接收满意解作为停止准则。7. 粒子空间初始化很好地选择粒子初始化空间,将大大缩短收敛时间。这是问题依靠。3. 粒子群算法求解旅行商问题步骤粒子群优化算法即使成功地应用于连续优化问题中,而在离散上研究和应用还极少,尤其是用PSO处理TSP问题是一个新研究方向2。最初PSO是用来处理连续空间问题,为了适合求解TSP问题,大家对算法进行了多种改善。本文采取王岚3重新定义PSO运算符号和规则,引入交换子和交换序概念,结构一个特殊PSO用于求解TSP方法。先对这种改善PSO进行简略介绍:定义1 设n个城市TSP问题解序列为S=(ai),i=1,2,n.定义交换子SO(i1,i2)为交换解S
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 智能 专业课程 设计 粒子 优化 算法 求解 旅行 问题 Matlab 实现
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【二***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【二***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。