（通信与信息系统专业论文）基于智能优化算法的tsp问题研究及应用.pdf

摘要 中文摘要 髑p ( t r a v e l i n g s a l e s m a n p r o b l e m ，旅行商问题) 是指给定n 个城市和各城市间 的距离，要求确定一条经过各个城市当且仅当一次的最短路线。它是一种典型的组 合优化问题，其最优解的求解代价是指数级的。已经证明t s p 问题是一个n p - h a r d 问题。 基于智能优化算法求解t s p 问题，是近年来刚刚兴起的热门课题。本文主要对 粒子群算法和遗传算法求解t s p 问题进行了研究。 1 在分析基本粒子群算法机理的基础上，引入了粒子个体极值的平均值，将其 与粒子个体极值和全局极值一起用于粒子速度更新中，提出了一种改进的粒子群算 法。仿真结果表明改进后的粒子群算法在收敛率和收敛速度等方面有明显的提高。 2 引入交叉算子和变异算子，对求解t s p 问题的粒子群算法提出了一种改进， 并用1 4 - t s p 和3 0 - t s p 问题对算法了测试，验证了改进算法的有效性。 3 利用遗传算法求解了旅行商问题，并实验分析了适应度函数、交叉概率和变 异概率在求解旅行商问题时，对算法性能的影响。 4 设计了山西省旅游线路优化决策系统，构造了山西旅游线路多目标优化模 型。在距离最短、时间最少和费用最低的多目标情况下，对部分旅游景点的线路进 行了优化，得到较满意的p a r e t o 最优解集 关键词：旅行商问题；粒子群算法；遗传算法；旅游线路优化 基于智能优化算法的t s p 问题研究及应用 a b s t r a c t i nt h et r a v e l i n gs a l e s m a np r o b l e m ( t s p ) w ea r eg i v e nnc i t i e st o g e t h e r w i t ht h ep a i r w i s ed i s t a n c e sb e t w e e ne a c ht w oc i t i e s t h eg o a li st of i n dt h e s h o r t e s tt o u rv i s i t se v e r ye i t ye x a c t l yo n c ea n di nt h ee n dr e t u r n st oi t s s t a r t i n gc i t y t h et s pi so n eo ft h em o s tf a m o u sp r o b l e m si nc o m b i n a t o r i a l o p t i m i z a t i o n t h ec o s tt or e s o l v et s pi se x p o n e n t i a la n di ti sp r o v e nt ob e n p h a r d i ti san e wh o ts u b j e c tr i s e di nr e c e n ty e a r st os o l v et s p 、i t l li n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s i nt h i sp a p e rw em a i n l ye x p a n dr e s e a r c ho np a r t i c l e s w a r u lo p t i m i z a t i o n ( p s o ) a n dg e n e t i ca l g o r i t h m ( ( 认) f o rt s p 1 an o v e li m p r o v e dp s oi sa d v a n c e di nt h i sp a p e r w ea n a l y z et h e m e c h a n i s mo fb a s i cp a r t i c l es w a r n lo p t i m i z a t i o na n dt h e ni n t r o d u c et h e a v e r a g eo fi n d i v i d u a l s e x t r e m ev a l u et ob a s i cp s ot ou p d a t et h ev e l o c i t yo f p a r t i c l e st o g e t h e rw i t hi n d i v i d u a le x t r e m ea n dg l o b a le x t r e m e t e s tr e s u l t i n d i c a t e st h a tt h ei m p r o v e dp s oa d v a n c e dd i s t i n c t l yi np e r f o r m a n c el i k e c o n v e r g e n c es p e e da n dc o n v e r g e n c e r a t e 2 a ni m p r o v e m e n tt op s oa l g o r i t h mf o rt s pi sp r o p o s e db yi n t r o d u c i n g e r o s s o v e ra n dm u t a t i o no p e r a t o r s w et e s tt h ea l g o r i t h mw i t l l1 4 - n o d et s p a n d3 0 - n o d et s pa n dt h ei m p r o v e da l g o r i t h mi sp r o v e nv a l i d 3 r e s o l v et s pw i t hg aa l g o r i t h ma n de x p e r i m e n t sa r ec o n d u c t e dt o a n a l y z et h ei n f l u e n c e s o ng aa l g o r i t h mf o rt s pb yf i t n e s sf u n c t i o n , c r o s s o v e rp r o b a b i l i t ya n dm u t a t i o np r o b a b i l i t y 4 w ed e s i g nt h eo p t i m i z a t i o na n dd e c i s i o nm a k i n gs y s t e mf o rs h a nx i t o u r i n gi t i n e r a c i e s ，c o n s t r u c tt h em u l t i o b j e c to p t i m i z a t i o nm o d e lf o rs h a h x i t o u ri t i n e r a c i e s s a t i s f y i n gp a r e t oo p t i m a ls o l u t i o n so ft o u r i n gi t i n e r a c i e s o p t i m i z a t i o nf o rs o m es i g h t sa r eo b t a i n e di nc o n d i t i o no fm u l t i - o b j e c to f s h o r t e s td m t a n c e 1 e a s tt i m ea n d1 0 w e s te x p e n s e i k e yw o r d s ：t r a v e l i n gs a l e s m a np r o b l e m ；p a r t i c l es w a r mo p t i m i z a t i o n ； g e n e t i ca l g o r i t h m ；t o u ri t i n e r a c yo p t i m i z a t i o n i x 承诺书 本人郑重声明：所呈交的学位论文，是在导师指导 下独立完成的，学位论文的知识产权属于山西大学。如 果今后以其他单位名义发表与在读期间学位论文相关 的内容，将承担法律责任。除文中已经注明引用的文献 资料外，本学位论文不包括任何其他个人或集体已经发 表或撰写过的成果。 学位论文作者( 签章) ：撤 2 0 07 年f 月n 日 1 绪论 1 1 课题背景 随着人们生活水平的提高，旅游越来越成为一种时尚，旅游者和旅行社都希望 通过合理的旅游线路来达到满足最大化，成本最小化的目的。一条成功的旅游线路 能为旅游者提供一次特定时空序列、心理感受都满意的旅游消费经历，也能为旅行 社减少成本，提高效率，同时又能带动旅游景区的建设和发展。因此，科学的旅游 线路设计与开发对于旅游业的发展起着至关重要的作用。 山西省地处黄河中游，是一个旅游大省。悠久的历史留下众多的文化古迹和独 具特色的民俗风情，加上复杂的地形地貌、河流山川形成的自然景观，有着丰富的 自然和人文旅游资源。怎样将旅游资源优势转化为产品优势和产业优势，全面提高 旅游效益，旅游线路的开发设计是一个非常重要的方面。山西已有许多旅行社以及 旅游网站，但是都较少涉及旅游线路优化决策、自助旅游等项目，因此对山西省旅 游线路优化问题进行研究并设计一个旅游线路优化决策系统势在必行，该系统的实 现将会对山西省的旅游业发展起到一定的促进作用。本课题在这样的背景下提出， 并由山西省软科学研究项目( 编号：0 5 1 0 2 0 3 ) 支持。 1 2 课题研究的目的和意义 t s p 问题是组和优化问题的典型代表，在实际工程中t s p 有许多应用，如电子 地图、电器布线、计算机联网等。其难于求解，但表述简单，易于理解，因此成为 研究者测试新算法的良好工具。t s p 问题已经被证明是一个n - p - h a r d 问题i l 】，虽然 许多著名的数学家为t s p 的求解苦苦探索了几个世纪，但自1 9 3 2 年正式提出以来 至今尚未找到非常有效的求解方法。l a u r i e r ej l 1 9 7 8 年提出了用人工智能方法求组 合优化问题的一种计算机语言和系统 2 1 ，为t s p 等组合优化问题提供了新的思路和 手段。此后，人工神经网络、遗传算法、模拟退火等方法相续出现，掀起了智能优 化算法研究的热潮，且在诸多领域得到成功应用。将智能优化算法用于求t s p 问题 的近似解也取得了较好的效果，它已经成为求解t s p 问题的一种常用方法。 旅游者在选择旅游线路时有着共同的意愿，主要表现为费用、时间、精力等成 本因素最小化，满足最大化，所以，旅游线路优化问题也是t s p 的一种，即以最少 时间、最少费用或最短路径为原则，或以其中两种或两种以上为原则，寻找最佳线 路。科学的旅游线路设计与开发对于旅游业的发展起着至关重要的作用。区域旅游 产品的表现、促销和旅游活动的组织大多是通过旅游线路的形式得以体现。在旅游 r 基于智能优化算法的t s p h i 题研究及应用 业竞争日趋激烈的今天，旅游线路作为旅游产品，其质量高低、特色体现对于区域 旅游的发展起着非常重要的作用。因此，旅游线路优化决策系统的设计与实现是区 域旅游发展中一项重要的内容，关系着区域旅游发展的成败。 山西省地处黄河中游，是一个旅游大省。悠久的历史留下众多的文化古迹和独 具特色的民俗风情，加上复杂的地形地貌、河流山川形成的自然景观，有着丰富的 自然和人文旅游资源。山西素有“中国古代艺术博物馆”、“文献之邦”的美 称，保留有全国百分之七十的地面古代建筑，列为国家重点保护的有5 0 处，省级 有4 0 0 多处【3 】。山西名山大川遍布，自然风光资源丰富优美，北岳恒山、壶1 ：3 瀑布 都是国家级风景名胜区。自然美景、历史文明、革命史迹和新时期建设成就，共同 构成了山西得天独厚、古今兼备、多姿多彩的旅游资源，整个山西可谓是一个旅游 类型效应、集聚效应、强度效应十分明显、颇具代表性的旅游区域。怎样将区域旅 游资源优势转化为产品优势和产业优势，全面提高区域旅游效益，旅游线路的开发 设计是一个非常重要的方面。 本课题的研究目的就是用智能优化算法研究t s p 问题，在此基础上结合山西省 旅游资源的实际情况，进行最佳路径优化，并实现山西省旅游线路优化决策系统， 而该系统的实现将会为山西省的旅游业发展起到一定的促进作用，具有较高的社会 效益和经济效益。 1 3 智能优化算法 自古以来，人类就力图根据认识水平和当时的技术条件，企图用机器来代替人 的部分脑力劳动，以提高征服自然的能力，这说明古代人们就有对人工智能的幻 想。人工智能的出现是人们长期以来探索能进行计算、推理和其他思维活动的智能 机器的必然结果，是由控制论、信息论、系统论、计算机科学、神经生理学、心理 学、数学和哲学等多种学科相互渗透的结果，是电子数字计算机的出现和广泛应用 的结果。 二十世纪五十年代英国数学家a m t u r i n g 提出的著名图灵机模型以及其后来的 电子数字计算机设计思想等关于“机器与思维”方面的论述为人工智能作出了杰出 贡献【4 】，但是图灵只是从其建立的计算机概念开始联想到智能机的概念，并没有对 真正意义的人工智能提出真正的设想闭。1 9 5 6 年夏季，人类历史上第一次人工智能 研讨会在美国的达特茅斯( d a r t m o u t h ) 大学举行，标志着人工智能学科的诞生嗍。 m i n s k y 和m c c a r t h y 的研究为其后的人工智能研究指明了方向川【引6 0 年代后，人工 2 智能进入高潮期，先后出现了符号处理语言原型、感知机、专家系统，并成立了国 际人工智能联合会。7 0 年代后半期，专家系统和知识工程在全世界迅速发展，机器 学习和人工神经网络的研究不断深入，进入人工智能发展的现代时期【9 】。 我国的人工智能研究起步较晚，1 9 7 8 年才将智能模拟纳入国家计划研究。1 9 8 4 年召开了智能计算机及其系统的全国学术讨论会，1 9 8 6 年将有关人工智能的项目列 入国家高技术研究计划，主要在定理证明、汉语自然语言理解、机器人及专家系统 方面设立课题，并取得一些初步成果【9 】。我国也先后成立中国人工智能学会、中国 计算机学会人工智能和模式识别专业委员会和中国自动化学会模式识别与机器智能 专业委员会等学术团体，开展这方面的学术交流。此外国家还着手兴建了若干个与 人工智能研究有关的国家重点实验室，这些都将促进我国人工智能的研究，为这一 学科的发展作出贡献。 智能算法是人工智能的一个研究领域。智能算法是一种通过模拟和利用自然界 中自然现象或生物体的各种原理和机理而开发的解决复杂问题的新方法。智能优化 算法作为智能算法的重要研究内容，不断呈现出新的智能工具，如遗传算法、蚁群 算法、粒子群优化算法等等。这些算法显示，通过模拟生物智能开发具有较高智能 的应用工具并对其进行理论与应用研究具有重要理论意义和现实意义。 智能优化算法通过模拟自然界生物系统无意识的寻优行为来寻找问题的解，具 有与线性规划、动态规划、构造型算法等传统优化算法不同的特点，遗传算法、蚁 群算法和粒子群优化算法是基于种群的智能优化算法，它们具有以下几个特点： ( 1 ) 它们具有自组织、自适应和自学习性，能够根据环境变化来自动发现环 境的特性和规律并通过不断学习提高适应性； ( 2 ) 它们具有隐含并行性，搜索过程同时从多个点出发，可同时搜索解空间 的多个区域，并相互交流信息，以获取所需性能； ( 3 ) 它们在优化过程中不依赖于优化问题本身的性质，只需要影响搜索方向 的目标函数和相应的适应度函数； ( 4 ) 它们对给定问题，可以产生许多的潜在解，最终选择可以由使用者确 定； ( 5 ) 它们是概率型的全局最优搜索算法，与完全的随机算法相比较，它们一 方面能在可行解空间进行全方位搜索，另一方面能在当前最优解附近进行更加精细 的搜索，因此它们能以更大的概率求得全局最优解。 基于智能优化算法的t s p 问思研究及应用 1 4 本选题领域内已有的研究成果 国外关于旅游线路的研究，可获得的资料十分有限，有些学者对旅游成本模型 和旅游定价问题进行讨论和研究，涉及到一些旅游线路问题。文献【1 0 】列出了一系 列内在于随机效用模型同时影响旅游成本模型的困难，文献 1 1 】已经证明无法准确 观测价格是空间参数呈现不确定性的一个原因，2 0 世纪6 0 年代末开始，出现了一 些从空间角度探讨旅游的各种结构模型，例如m a r i o t 曾提出连接永久居住地和旅游 中心的三种不同路径( 进入路径、返回路径和休闲路径) ；d p e a r c e l 9 8 7 年提出了 旅游流的概念，探讨了旅游者的空间运动模式。 国内旅游线路的研究较国外晚，2 0 世纪9 0 年代初至今，很多旅游地理学者在 区域旅游开发的基础上致力于旅游线路设计的研究，楚义芳等从空间尺度出发将旅 游线路划分为大尺度旅游线路和中小尺度旅游线路两类，她还指出无论周游型旅游 还是逗留型旅游者，其具体行为不外乎属于成本( 费用、时间、距离) 最小化行为 和非成本最小化行为( 即单纯的满足最大化行为) f 1 2 - 1 4 1 ，陈青光等在对单个景点开 发的基础上构造了旅游线路网络的观点，刘振礼、王兵提出了旅游线路设计的五大 原则。这些理论对旅游产品的开发起到了重要的指导作用，为旅游经济的发展作出 了重大贡献。 目前，我国已拥有3 0 0 0 多家具有一定咨询服务实力的旅游网站，为消费者提 供食、住、行、游、购、娱等方面的网上咨询服务，但总体上还处于旅游信息发 布、宣传和吸引网民的阶段，较少涉及旅游线路设计、自助旅游安排、网上虚拟实 景旅游等项目。我国大多数旅行社或其他旅游经营部门也很少具有旅游线路优化决 策系统。 我国关于旅游线路的研究有以下几个特点： ( 1 ) 个案研究多，通则性研究少；很多学者旅游线路设计研究都是针对某个省或 某个城市所作，通则性的研究很少，这也反映出我国旅游线路设计研究还处于起步 阶段。 ( 2 ) 规范性的定性研究多，定量研究少； ( 3 ) 宏观尺度的线路设计研究多，微观尺度线路设计较少；目前关于旅游线路设 计的研究中大多都是针对某个省或某个城市作的大尺度的旅游线路设计，很少涉及 景区内部线路设计的小尺度研究，这对旅游线路研究的全面性和完整性有不利影 响。 4 绪论 总之，我国的旅游线路研究成果较少，处于较低的水平，旅游线路的优化研究 更少，本文从旅游者的角度对山西旅游线路优化设计做了初步的研究，用智能优化 算法对山西几个景点作了多目标优化，这对山西省旅游业的进一步发展具有一定的 理论指导意义。 1 5 本论文采用的理论方法和主要研究内容 1 5 1 理论方法 ( 1 ) 粒子群算法 粒子群算法( p s o ) 是一种基于迭代的优化方法。进行优化时，粒子在一个1 1 维空间中搜索，每个粒子的位置对应于问题的一个解，粒子通过不断调整自己的位 置来搜索新解。每个粒子都能记住自己搜索到的最好解( 个体极值) ，记作，以 及整个粒子群目前搜索到的最优解( 全局极值) ，记作劈位置和速度的调整按照 以下公式进行： 矿k + l = 巧+ c l ( 彳一j ? ) + c 2 r 2 ( 茗一工? ) x ：“= x ：+ e ” 其中，c j 、c 2 为常数，用来调节个体极值和全局极值的相对重要性；、r 2 是 ( o ，1 ) 上均匀分布的随机数；彳，分别表示粒子第k 次迭代的个体极值点位置和 全局极值点位置。 p s o 的优点在于其简单，易于实现，需要调整的参数少。但是p s o 起步晚，正 处于研究的初期，p s o 求解t s p 问题与传统算法还有一定的差距。 ( 2 ) 遗传算法 遗传算法( g a ) 是一种通过模拟生物界自然选择和遗传机制的随机搜索算 法，其遗传操作和编码技术比较简单，主要操作有选择、交叉和变异。对于t s p 问 题，以1 1 个城市的一种排列作为一条染色体，随机构造若干条染色体构成初始种 群；然后根据适应度进行优胜劣汰的选择，每次繁殖由两个双亲产生一个子代：根 据一定的交叉算子和变异算子进行交叉和变异。以一定的迭代次数或某个到达条件 作为算法终止的条件。 g a 的搜索过程从问题解的一个集合开始，具有隐含并行搜索的特性，可大大 减少陷入局部最小的可能。但是对于大规模的t s p 问题，其搜索空间大，时间长， 往往会出现早熟收敛的情况；另外，g a 对初始种群很敏感，初始种群的选择常常 直接影响解的质量以及算法的效率。 基于智能优化算法舸璐p 问题研究及应用 本文选用以上两种方法进行t s p 问题研究，在实验中，针对算法的缺点进行改 进，对更好的求解t s p 问题有一定的意义，也能进一步提高g a 和p s o 算法的性 能。 1 5 2 主要研究内容 本文主要研究粒子群算法和遗传算法求解t s p 问题，具体内容如下： ( 1 ) 首先介绍粒子群算法的产生背景、算法流程以及算法参数等基础知识，然 后分析基本粒子群算法的思想和机理，引入种群平均信息对算法提出改进，并用非 线性连续函数对改进算法进行有效性测试。 ( 2 ) 简要介绍了t s p 问题的概念以及研究现状，阐述了粒子群算法求解t s p 问 题的原理，并引入交叉算子和变异算子对粒子群算法求解t s p 问题提出一种改进， 用1 禾t s p 和3 0 t s p 问题对改进算法进行了有效性测试。 ( 3 ) 对遗传算法中适应度函数、交叉概率、变异概率的设置进行实验和分析。 实验中，改变适应度函数等参数，用遗传算法求解1 4 - t s p 和3 0 t s p 问题，对比实 验结果，讨论了适应度函数、交叉概率、变异概率对算法性能的影响。 ( 4 ) 设计了山西省旅游线路决策系统并实现了部分功能。本文采用v b 6 0 为编 程语言，结合m a p x 5 0 控件，设计了友好的人机交互界面，合理规划和实现了系统 的各种模块，包括：电子地图管理模块、旅游景点介绍模块、交通信息管理模块、 和最佳旅游线路生成模块等。系统功能模块如下图所示。 图1 1 山西省旅游线路优化决策系统功能模块 图1 1 中，最佳线路生成模块要实现根据用户输入的起始点、终止点、交通工 具和优化目标等信息，用智能优化算法设计最佳旅游线路并输出方案供用户参考。 该模块需要对山西省的实际景点、宾馆、交通道路等各因素进行实际考察，由于条 6 件有限，本文只对旅游线路优化决策作理论上的探讨，即以时间、费用、距离中的 两个或三个指标为优化目标，用本文改进的p s o 算法进行多目标优化求取p a r e t o 最 优解集。 1 6 本章小结 本章介绍了课题“山西省旅游线路优化决策系统研究”的研究目的、意义以及 该领域的发展现状，并对智能优化算法作了概述，围绕山西省旅游线路优化决策系 统的设计与实现，提出了本文采用的理论方法和主要研究内容。 7 基于智能优化算法的t s p 问题研究及应用 2 基于种群平均信息的p $ 0 改进 2 1 概述 自然界中群居生物的各种生存行为表现出的群集智能正越来越受到人们的关 注，人工生命正是受到这种群体行为的启发而在计算机上构建其群体模型并将其应 用于现实生产生活中去解决一些复杂的组合优化问题。粒子群优化算法( p a r t i c l e s w a r mo p t i m i z a t i o n ，p s o ) 是一类基于群智能的随机优化算法，由j a m e sk e n n e d y 和r u s s e l le b e r h a r t 于1 9 9 5 年提出【”6 1 ，其基本思想源于对鸟群、鱼群等生物捕食 行为的简化社会模型的模拟。p s o 算法原理简单，需要调整的参数少，容易实现， 一经提出便引起了进化计算等领域学者们的广泛关注，短短几年时间在算法性能的 改进、算法的理论分析以及算法的应用等方面取得了大量的研究成果。 p s o 最初应用是神经网络训练，不仅训练网络的权重，还包括训练网络结构 1 7 1 嘲。p s o 还成功用于电气设备的功率反馈和电压控制9 】【2 0 】。近几年，p s o 在电 力系统中的应用也越来越广泛，例如，文献【2 1 】用p s o 对发电机组进行最小代价的 中长期规划( g e p ) ，文献 2 2 】、【2 3 将p s o 用于求解复杂最优潮流问题( o p f ) ， 文献 2 3 1 用基于可行保留策略和变异算子的改进p s o 求解最优潮流问题，算法结果 优于进化规划和常规p s o 算法。文献 2 4 1 、【2 5 1 将p s o 用于带阀点效应的经济负荷 分配问题的优化中，取得了较好的效果。此外，p s o 还在p i d 控制参数优化刚、电 容布局 2 7 1 、非线性磁场计算 2 a l 等非线性优化问题以及其他组合优化问题、决策调度 问题中得到成功应用 2 9 - 3 4 1 。 p s o 进行优化时，首先在可行解空间中随机产生初始种群，种群中每个个体都 为优化问题的一个解，这些个体称为“粒子”，粒子的适应值由与优化问题相关的 目标函数确定。粒子在多维空间中搜索时，根据对个体和集体的搜索经验的综合分 析来动态调整个体的搜索速度，通过个体问的竞争与协作实现复杂空间中最优解的 搜索。 与其他进化算法相似，p s o 也使用“种群”的概念来表示一组解空问中的个体 集合，并根据对环境的适应度将群体中的个体移动到较好的区域，p s o 也有一些其 它进化算法所不具备的特性，归纳如下： ( 1 ) p s o 没有使用进化算子，而是将个体看作多维搜索空间中的一个无体积无质 量的微粒，在搜索空间以一定速度飞行； 矗 基于种群平均信息的p s o 改进 ( 2 ) 粒子具有记忆功能，可以记忆自己曾经达到过得最优位置，保留局部个体和 全局种群的最优信息； ( 3 ) 粒子通过与种群问的交流来感知种群当前达到的最优位置； ( 4 ) 粒子按照两个显示的更新公式，综合考虑自己达到过的最优位置和种群达到 过得最优位置来调整自己的速度和位置。 2 2 基本p s o 算法 2 2 1 基本p s o 算法原理 p s o 算法中每个粒子根据自己的飞行经验和其他粒子的飞行经验来调整自己的 飞行。每个粒子在飞行过程所经历过的最好位置，就是粒子本身找到的最优解，称 为个体极值( ) ；整个群体所经历过的最好位置，就是整个群体目前找到的最 优解，称为全局极值( g 。) 。每个粒子都通过上述两个极值不断更新自己，从而产 生新一代群体。 设粒子的群体规模为，粒子当前的位置表示为舛= ( x ，t ，) ， 瞳，】，l s 行，厶和“。分别表示第疗维空问的上下边界；当前速度表示为 时= ( 诈，呓，砖) ，矿被钳位在最大值p 急= ( 1 盖哪，乞一，盍州) 和最小值 吐= ( ，1 0 ，吒叫) 之间，粒子的速度和位置更新方程如式( 1 ) 和式 ( 2 ) 所示【3 5 】： 矿”= 叫+ c l ( 彳一矸) + c 2 r 2 噼一矸) ( 1 ) 研“= 彤+ 矿1 ( 2 ) 而 v 工+ 1 谬 协 ， o 五 图2 1 粒子移动原理图 9 基于智能优化算法的t 趼问题研究及应用 其中，芹，e 分别表示粒子第七次迭代的个体极值点位置和全局极值点位 置。q 、c 2 为常数，称为学习因子，用来调节向尸f 和p g 方向飞行的最大步长；， 吒是( 0 ，1 ) 上均匀分布的随机数；式( 1 ) 中第一部分是粒子上一步的速度，表明粒 子目前的状态；第二部分是粒子对本身的思考，是认知部分，粒子通过对本身位置 的思考来调整自己下一步的速度和位置，这样可以是粒子有足够强的全局搜索能 力，避免陷入局部最小；第三部分表示粒子通过与其他粒子之间进行信息交流来更 新自己的下一步。 2 2 2 基本p s o 算法流程 基本粒子群算法的流程如下： 1 0 基于种群平均信息的p s o 改进 图2 2 基本p s o 算法流程 p s o 的流程可以分为初始化和迭代两步，具体描述如下： s t e p l ：初始化； s t e p l h 在允许的范围内随机产生粒子群中每个粒子的初始位置研； s t e p l 2 ：在允许范围内随机产生每个粒子的初始速度口； 基于智能优化算法自盯卵问题研究及应用 s t e p l 3 ：定义适应度函数f i a w a s 1 l ； s t e p l 4 ：计算最初的个体极值； s t e p l 5 ：计算最初的全局极值g h ； s t e p 2 ：进行迭代运算，更新粒子的速度和位置，直到符合停止条件。 s t e p 2 h 对每个粒子i ，寻找个体极值【f 】，如果f i t n e s s i 】 一触【订 则令【力= 群； s t e p 2 2 ：寻找全局极值g h ，即对任意粒子有f i t n e s s g , n 】a t n e s s i 】： s t e p 2 3 ：对每个粒子按照式( 1 ) 和式( 2 ) 更新其速度瞄和位置砰； s t e p 2 4 ：对每个粒子计算其适应度值f i t n e s s o ； s t e p 2 5 ：检验是否符合结束条件，如果当前的迭代次数达到了预定的最大次 数则停止迭代，输出最优解。 2 2 3 基本p s o 算法分析 影响p s o 性能的参数主要有种群规模、粒子最大速度、惯性权重、学习因子以 及终止条件等，针对不同的算法模型，要选取适当的控制参数以使算法性能达到最 优。 粒子种群规模的选择视具体问题而定，一般设置粒子数为2 0 - 5 0 就可以取得较 好的效果。不过对于多目标优化等比较难的问题，粒子数可以取到l o 帖2 0 0 个。 粒子的速度在搜索空间中每一维上都有一个最大速度限制值v 。，用来将粒子 的飞行速度控制在卜，v 嘣】范围内，决定问题空间搜索的粒度。如果，眦值太 大，则粒子会飞过最优解的位置；如果v m “值太小，则会降低粒子的全局搜索能 力。如果问题的搜索空问限定在【一，】，则通常设定，呱= 七， o 1 k s l 0 。 惯性权重影响粒子的飞行速度，缈较大则粒子以较大的步长进行全局探测， 较小则粒子的速度步长小，将进行精细的局部搜索。在搜索过程中，可以对m 进 行动态调整，即在算法开始时，给赋予一个较大值，随着搜索的进行逐渐减小 国，这样可以保证在算法开始时各粒子能在全局范围内探测到较好的位置；而在搜 索后期，较小的能够使粒子在极值点附近做精细的搜索，从而使算法更易于收敛 到全局最优解。一般国的取值范围为【o ，1 4 】，试验结果表明当取【o 8 ，1 2 】时， 算法收敛速度较快。 学习因子c i 调解微粒飞向自身最好位置方向的步长，c ，调节微粒向全局最好位 置飞行的步长，二者共同决定粒子个体经验和群体经验对粒子运行轨迹的影响，反 基于种群平均信息的p s o 改进 映粒子群之间的信息交流。如果【一v m ，虹】，则粒子只受群体经验影响，其收敛速 度更快，但容易陷入局部最优点；如果c 2 = 0 ，则微粒间缺乏信息交流，失去了种 群间信息共享，不容易得到最优解。s h i 和e b e r b a r t 建议 3 6 1 ，为了平衡随机因素的 作用，一般情况下设置c l = c 2 = 2 。 迭代终止条件一般设为最大迭代次数、计算精度或最优解的最大凝滞步数。 2 3 基于种群平均信息的p s o 模型 2 3 1 问题的提出 基本p s o 存在早熟收敛、容易陷入局部极小值等缺点，因此，研究者们对其作 了各种各样的改进，包括参数选择、拓扑改进、进化方程改进以及混合算法等。 基本p s o 的速度更新公式中包含粒子的个体极值和全局极值，粒子在进行搜索 时综合考虑自己的历史最佳位置和整个种群的当前全局最佳位置来调整下一步的速 度。种群中每个粒子与其他粒子之间的经验交流和信息共享程度在很大程度上影响 着该粒子探测到最优解的几率和速度，从而影响算法的性能。 基本p s o 算法中，对于全局极值不是粒子本身的粒子来说，即对砰， 华露，则该速度更新相当于该粒子与全局极值的粒子进行了一次信息交流；对 于本身就是全局极值的粒子，即孵= 彳= 露，则粒子只是通过对当前速度加权来 调整下一步的速度，亦即该粒子速度的更新没有利用到种群信息。因此，基本p s o 中每个粒子进行搜索时能够充分利用同伴的信息来调整速度和位置，这也是导致基 本p s o 容易早熟收敛、容易陷入局部极小值等缺点的因素之一。 为了增加种群中粒子间的经验交流，使无论舛= 彳= 芹还是彤辟，粒子 都能够与种群中其他粒子进行信息交流和共享，我们考虑对粒子速度更新公式进行 改进，并提出了以下的基于种群平均信息的粒子群算法。 2 3 2 一种基于种群平均信息的p s o 算法 基本粒子群算法的速度更新公式只利用了粒子的个体极值和全局极值。文献 3 7 1 在基本粒子群算法的基础上提出了一种改进的粒子群算法，即在基本粒子群算法的 速度更新公式中加入了第四项，如式( 3 ) 所示，其中，冠是在粒子群中随机选择 的一个粒子，岛为常数，r 3 为是( o 1 ) 上均匀分布的随机数。 巧“1 = 口彤+ q ( 彳一爿? ) + c 2 r 2 ( 嘭一工? ) + 巳( 肆一工? ) ( 3 ) 加入置项后，粒子进行速度更新时，除了利用粒子自身信息和种群最优值信息 外，还与另一个随机粒子进行交流，这必然对粒子容易陷入局部最优和早熟有一定 基于智能优化算法的t s p i 目题研究及应用 的抑制作用，但由于日是随机的，不能保证给舛带来向最优值靠近的有利信息， 所以可能会对粒子起到“误导”的作用。 本文对文献【3 7 】的第四项进行了改进，速度更新公式如式( 4 ) 所示。 巧”= 国k + q ( 异一爿? ) + 。j 吒( 茗一爿? ) + 岛吩( 片一x ? ) ( j 4 ) 其中，片为第七代所有粒子的个体极值的平均值，即学= 吉彳；c 3 为学习 扣l 因子，决定整个种群信息对该粒子的影响程度；弓为( o ，1 ) 上均匀分布的随机数。这 样，改进后的粒子群算法每次进行速度更新时，粒子除了对本身思考以及与另外一 个粒子( 每次的全局极值) 进行交流外，还考虑了整个种群的平均信息，该平均信 息为每个粒子个体极值的平均值，将会给粒子带来优良的信息，并且无论 砰= 彳= 茗还是矸譬，都保证粒子能够与种群进行信息共享，充分利用更多 的信息来调节自己的行为。 基于种群平均信息的p s o 算法步骤如下： s t e p l 初始化； s t e p l 1 ：在允许的范围内随机产生粒子群中每个粒子的初始位置舛； t s t e p l 2 ：在允许范围内随机产生每个粒子的初始速度口； s t e p l 3 ：定义适应度函数力 黜【习； s t e p l 4 ：计算最初的个体极值p h ； s t e p l 5 ：根据每个粒子个体极值计算最初个体极值平均值芹i s t c p l 6 ：计算最初的全局极值g h ； s t e p 2 ：进行迭代运算，更新粒子的速度和位置，直到符合停止条件。 s t e p 2 1 ：对每个粒子f ，寻找个体极值 f 】，如果伽跚【f 】 一f i t n e s s i 】 则令【刁= 矸； s t e p 2 2 ：计算个体极值的平均值劈= 寺彳i o i = l s t e p 2 3 ：寻找全局极值g ，即对任意粒子有f i t n e s s 【g h 】2 q t n e s s q ； s t e p 2 4 ：对每个粒子按照式( 4 ) 和式( 2 ) 更新其速度曙和位置研； s t e p 2 5 ：对每个粒子计算其适应度值l i t n e s s i 】； s t e p 2 6 ：如果符合结束条件则输出结果，停止迭代；否则跳至s t e p 2 1 。 基于种群平均信息的体。改进 2 3 3 函数优化实验及结果分析 为验证本文所提方法的性能，我们选择了以下4 个测试函数来进行优化测试， 并将测试结果与文献 3 7 】进行比较。 ( 1 ) z o ) = 薯2 ( 一l o o g x ， 1 0 0 ) f f i l s p h e r e 函数，单峰，在葺= 0 时达到极小值d 量3 3 s 4 e l 。 图2 - 3 二维s p h e r e 函数图像 ( 2 ) 五( 功= ( # - a c o s ( 2 ，r x + ) + a ) ( - 5 1 2 x ，5 1 2 ) i = l r a s t r i c m 函数，在玉= o ( 扛l 2 ，玎) 时达到全局极小点， 在 s = “( - 5 1 2 ，5 1 2 ) ，i = i 2 ，h ) 范围内大约存在1 0 n 个局部极小点，仿真中，彳取 l o 口7 3 删。 图2 4 二维r a s t r i g i n 函数图像 ( 3 ) 石：妻# 砌一n n 。嘶o ) + 1 ( 枷而 6 0 0 ) i = ld g r i e w a n k 函数，全局极小在而= oo = l ，2 ，一) 时达到1 3 量3 搏4 0 】。 基于智能优化算法的t s p 问题研究及应用 图2 5 二维c r d e w a a k 函数图像 c 4 ，工e 功= 。s 一；：蒜c 一- ，而， s c h a f f e r 函数，全局极大点是( o ，o ) ，在距离全局极大点大约3 1 4 的范围内存在 无限多的次全局极大点，函数强烈震荡的性态使其很难全局最优化【3 5 1 。 图2 6 二维s c h a f f e r 函数图像 测试中，公式( 3 ) 及公式( 4 ) 两种方法的最大收敛代数均为2 0 0 0 ，粒子个数 均为2 0 ，其它参数的设置见表2 1 ，其中公式( 3 ) 的参数与文献【6 】一致。每个函 数两种方法各测试了4 0 次，结果如表2 2 、表2 3 、表2 4 和表2 5 所示。其中，平 均值反映误差：收敛率为达到最优值的次数与总次数之比；平均收敛代数反映收敛 速度。 从表2 2 可知，对于s p h e r e 函数，与公式( 3 ) 相比，公式( 4 ) 的精度更高， 收敛率也非常理想，达到了1 0 0 ，公式( 4 ) 的收敛速度比公式( 3 ) 高出将近2 倍。从图2 7 可知，公式( 3 ) 的误差在维数超过2 5 后明显增加，而公式( 4 ) 则保 持误差为0 不变。 基于种群平均信息的p s o 改进 表2 1 参数设置 参数公式( 3 )公式( 4 ) 墨兰：! 璺也皇竺鱼墼型亟笪墨些墼! 量盔鎏壅塑! 鲤! 项目公式( 3 )公式( 4 ) 项目公式( 3 )公式( 4 ) 表2 4g r i e w a n k 函数测试结果比较( 最大速度为6 0 0 ) 基于智能优化算法的t s p 问题研究及应用 表2 5s c h a f f e 函数测试结果比较( 最大速度为1 0 0 ) 公式( 3 )公式( 4 ) 图2 7s p h e r e 函数误差随维数变化曲线 图2 8r a s t r i g i n 函数收敛代数随维数变化曲线 1 8 基于种群平均信息的p s o 改进 图2 9g r i e w a n k 函数收敛率随维数变化曲线 表2 3 中r a s t d g i n 函数以及表2 4 的c n i e w a n k 函数均为连续多模态函数，数值 结果显示，在同样的条件下，对于r a s t r i g i n 函数，公式( 3 ) 不能收敛到全局最优 值0 ，对g r i e w a n k 函数虽然能够找到最优值0 ，但是收敛率很低。对这两个函数， 公式( 3 ) 的速度和精度都比公式( 4 ) 低。另外，表2 3 的标准差较大，说明对 r a s t r i g i n 函数两种方法都不是很稳定，但公式( 4 ) 比公式( 3 ) 稳定。由图2 8 知，公式( 3 ) 的收敛代数比公式( 4 ) 超出近3 0 0 代，即公式( 4 ) 的收敛速度比 公式( 3 ) 快将近一倍；图2 9 中两种方法的收敛率对比很明显，公式( 3 ) 的收敛 率一直为0 ，即无论维数如何变化，公式( 3 ) 都无法搜索到c n - i e w a n k 函数的最优 值0 ，而公式( 4 ) 的收敛率随着维数的增加，开始时有些大幅度的振荡，1 5 维以 后逐渐趋于平稳，收敛率保持在9 0 n , 4 以上。 表2 5 为2 维s c h a f f e 函数，对该函数的实验表明，从收敛率、收敛速度和精度 三方面来看，公式( 3 ) 均不如公式( 4 ) 好。 由此可见，在算法精度、收敛速度以及收敛率等方面，本文所提出的算法都优 于文献【3 7 】的算法，尤其是对于连续多模态函数其性能更是高出了许多。 2 4 本章小结 粒子群算法是近十年来才发展起来的新颖的基于群体智能的随机优化算法，它 简单易懂，容易实现，在许多领域都得到了广泛应用。本文详细介绍了基本p s o 的 原理、算法流程，对p s o 的参数进行了分析，并利用粒子群的平均信息对粒子速度 基于智能优化算法自n s p 问题研究及应用 更新公式进行改进，提出了一种改进的粒子群算法，仿真结果表明，它在函数优化 方面具有精度高、收敛速度快等特点，尤其是对连续多模态函数，这些特点更加明 显。 基于髓。求解t s p 向最 3 基于p s o 求解t s p 问题 3 1 概述 旅行商问题( t r a v e l i n g s a l e s m a n p r o b l e m ，t s p