安康学院 学年论文（设计） 题目_____________________________________________ 学生姓名_______________ 学号_____________________________ 所在院（系）_______________________________________ 专业班级__________________________________________________ 指导教师_____________________________________________ 年月曰
基于粒子群优化算法的图像分割 （作者：） （） 指导教师： 【摘要】本文通过对粒子群优化算法的研究，采用Java编程，设计出一套用于图像分割的系统。 基于粒子群优化算法的图像分割系统，可以将一幅给定的图像进行分割，然后将分割结果保存。图像分割的目的是将感兴趣的区域从图像中分割出来，从而为计算机视觉的后续处理提供依据。图像分割的方法有多种，阈值法因其实现简单而成为一种有效的图像分割方法。而粒子群优化（PSO）算法是一类随机全局优化技术，它通过粒子间的相互作用发现复杂搜索空间中的最优区域缩短寻找阈值的时间。因此，基于粒子群优化算法的图像分割以粒子群优化算法为寻优工具，建立具有自适应和鲁棒性的分割方法。从而可以在最短的时间内，准确地确定分割阈值。 关键词：粒子群优化（PSO，图像分割，阈值法，鲁棒性 Abstract T his paper based on the particle swarm optimizati on algorithm, desig ns a set of system for image segme ntati on using Java program min g. Image segme ntati on system based on particle swarm optimizati on algorithm, the image can be a given segmentation, and then the segmentation results would be saved. Image segmentation is the purpose of the interested area from the image, thus providing the basis for the subsequent processing of computer vision. There are many methods of image segmentation, threshold method since its simple realization, becomes a kind of effective method in image segmentation. Particle swarm optimization （PSO） algorithm is a stochastic global optimization technique; it finds optimal regions of complex search spaces for threshold time shorte ned through the in teractio n betwee n particles. Therefore, particle swarm optimization algorithm of image segmentation based on particle swarm optimization algorithm based on optimizati on tools; establish segme ntati on method with adaptive and robust. Therefore, it is possible for us in the shortest possible time to accurately determ ine the segme ntati on threshold. Key word s: PSO, image segmentation, threshold method, robust. 1引言 1.1研究的背景和意义 技术的不断向前发展，人们越来越多地利用计算机来获取和处理视觉图像信息。据统计，人类
第37卷第4期河北工业大学学报2008年8月V ol.37No.4JOURNAL OF HEBEI UNIVERSITY OF TECHNOLOGY August2008 文章编号：1008-2373(2008)04-0055-05 改进的粒子群优化算法 宋洁，董永峰，侯向丹，杨彦卿 （河北工业大学计算机科学与软件学院，天津300401） 摘要粒子群优化算法是一种基于群体的自适应搜索优化算法，存在后期收敛慢、搜索精度低、容易陷入局部极 小等缺点，为此提出了一种改进的粒子群优化算法，从初始解和搜索精度两个方面进行了改进，提高了算法的计 算精度，改善了算法收敛性，很大程度上避免了算法陷入局部极小．对经典函数测试计算，验证了算法的有效性． 关键词粒子群优化算法；均匀化；变量搜索；初始解；搜索精度 中图分类号TP391文献标识码A A Modified Particle Swarm Optimization Algorithm SONG Jie,DONG Yong-feng,HOU Xiang-dan,Y ANG Yan-qing (School of Computer Science and Engineering,Hebei University of Technology,Tianjin300401,China) Abstract Particle Swarm Optimization Algorithm is a kind of auto-adapted search optimization based on community. But the standard particle swarm optimization is used resulting in slow after convergence,low search precision and easily leading to local minimum.A new Particle Swarm Optimization algorithm is proposed to improve from the initial solution and the search precision.The obtained results showed the algorithm computation precision and the astringency are im- proved,and local minimum is avoided.The experimental results of classic functions show that the improved PSO is ef- ficient and feasible. Key words PSO；average；variable search；initial solution；search accuracy 0引言 粒子群优化（Particle Swarm Optimization，PSO）算法是一种基于群体的随机优化技术，最早在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart[1]共同提出，基本思想源于对鸟群觅食行为的研究．PSO将每个可能产生的解都表述为群中的一个微粒，每个微粒都具有自己的位置向量和速度向量，和一个由目标函数决定的适应度，通过类似梯度下降算法使各粒子向适应度函数值最高的方向群游．该算法控制参数少、程序相对简单，因此在应用领域表现出了很大的优越性．由于PSO算法容易理解、易于实现，所以PSO算法发展很快．目前，多种PSO改进算法已广泛应用于函数优化、神经网络训练、模式识别、模糊系统控制以及其他的应用领域． 许多学者对PSO算法进行研究，发现其容易出现早熟、最优解附近收敛慢等现象，并提出了一些改进方案，例如自适应PSO算法、混合PSO算法、杂交PSO算法等[2-4]．因此，本文从初始解和收敛精度两个角度出发对PSO算法进行了改进，提高了算法的计算精度，有效的改善了算法的优化性能． 1基本PSO算法 PSO算法是一种基于群体的随机优化技术，基本思想源于对鸟群觅食行为的研究．通过对鸟群飞行时经常会突然改变方向、散开、聚集，但整体总保持一致性，个体与个体间鸟群好像在一个中心的控制 收稿日期：2008-04-17 基金项目：河北省自然科学基金（F2006000109） 作者简介：宋洁（1967-），女（汉族），副教授．
东南大学 硕士学位论文 移动机器人完全遍历路径规划算法研究 姓名：胡正聪 申请学位级别：硕士 专业：机械电子工程 指导教师：张赤斌 20080403
第一章绪论 第一章绪论 １．１移动机器人的发展史 社会的主体是人类，历史的推动者是人类，伟大的人类运用自己的智慧不断创造伟大的发明，不断推动社会的发展。邓小平同志说过：“科技是第一生产力。”生产力是社会发展的动力，所以人类推动社会发展就是要致力于发展生产力，致力于发展科技。人类不断发展生产力来提高自身认识自然、改造自然、得到自己所需物质的能力，这种能力的进化由最初的运用双手、简单工具、发展到运用畜力、发展到运用简单机器、发展到运用自动化设备、还会发展到我们无法想象的未来。 机器人就是生产力发展的产物。机器人的概念最早是在１９２０年的科幻小说中提出的，而早期的机器人如１９３９年美国纽约世界博览会上展出的西屋电气公司制造的家用机器人Ｅｌｅｋｔｒｏ和１９５６年美国人乔治?德沃尔制造出的世界上第一台可编程的机器人都是一些实用价值不高的机器人，它们是现代机器人的雏形。上世纪６０年代，由于传感器和计算机技术的发展及应用，兴起了全世界第二代机器人的研究热潮，并向人工智能进发。１９６８年，美国斯坦福研究所公布了他们研发成功的机器人Ｓｈａｋｅｙ。它带有视觉传感器，能根据人的指令发现并抓取积木。Ｓｈａｋｅｙ可以算是世界第一台智能机器人，它拉开了第三代机器人研发的序幕。到了上世纪８０年代，发达国家都组建各种机器人研究机构，尤其是以美国为代表的国家将机器人的研究列入了军事发展计划，带动各国把机器人的研究推上了高潮，日本和欧洲各国都成立了各自的机器人研究中心和规划了自己的研究计划。进入９０年代后，机器人的应用领域除了工业和军事外，还涉及到了服务和娱乐领域，以日本本田公司的ＡＳＩＭＯ人型机器人和索尼公司的ＡＩＢＯ娱乐机器人为代表的机器人展示了机器人领域各方面的先进研究成果。在欧洲，２００２年丹麦ｉＲｏｂｏｔ公司推出了吸尘器机器人Ｒｏｏｍｂａ，它能避开障碍，自动设计行进路线，还能在电量不足时，自动驶向充电座。Ｒｏｏｍｂａ是目前世界上销量最大、最商业化的家用机器人。２００６年６月，微软公司推出ＭｉｃｒｏｓｏＲＲｏｂｏｔｉｃｓＳｔｕｄｉｏ，机器人模块化、平台统一化的趋势越来截明显，比尔?盖茨预言：“家用机器人很快将席卷伞球。” 图１．１丹麦ｉＲｏｂｏｔ公司推出的吸尘机器人Ｒｏｏｍｂａ［
对于函数f=x*sin(x)*cos(2*x)-2*x*sin(3*x)，求其在区间[0,20]上该函数的最大值。 ?初始化种群 已知位置限制[0,20],由于一维问题较为简单，因此可以取初始种群N 为50，迭代次数为100,当然空间维数d 也就是1。 位置和速度的初始化即在位置和速度限制内随机生成一个N×d 的矩阵，对于此题，位置初始化也就是在0~20内随机生成一个50×1的数据矩阵，而对于速度则不用考虑约束，一般直接在0~1内随机生成一个50×1的数据矩阵。 此处的位置约束也可以理解为位置限制，而速度限制是保证粒子步长不超限制的，一般设置速度限制为[-1,1]。 粒子群的另一个特点就是记录每个个体的历史最优和种群的历史最优，因此而二者对应的最优位置和最优值也需要初始化。其中每个个体的历史最优位置可以先初始化为当前位置,而种群的历史最优位置则可初始化为原点。对于最优值，如果求最大值则初始化为负无穷，相反地初始化为正无穷。 每次搜寻都需要将当前的适应度和最优解同历史的记录值进行对比，如果超过历史最优值，则更新个体和种群的历史最优位置和最优解。 ?速度与位置的更新
速度和位置更新是粒子群算法的核心，其原理表达式和更新方式如下: 每次更新完速度和位置都需要考虑速度和位置的限制，需要将其限制在规定范围内，此处仅举出一个常规方法，即将超约束的数据约束到边界（当位置或者速度超出初始化限制时，将其拉回靠近的边界处）。当然，你不用担心他会停住不动，因为每个粒子还有惯性和其他两个参数的影响。 代码如下： clc;clear;close all; %% 初始化种群 f= @(x)x .* sin(x) .* cos(2 * x) - 2 * x .* sin(3 * x); % 函数表达式figure(1);ezplot(f,[0,0.01,20]); N = 50; % 初始种群个数 d = 1; % 空间维数 ger = 100; % 最大迭代次数 limit = [0, 20]; % 设置位置参数限制 vlimit = [-1, 1]; % 设置速度限制 w = 0.8; % 惯性权重 c1 = 0.5; % 自我学习因子 c2 = 0.5; % 群体学习因子 for i = 1:d
一、粒子群算法概述 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，1995 年由Eberhart 博士和kennedy博士提出，源于对鸟群捕食的行为研究。该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。粒子群算法在对动物集群活动行为观察基础上，利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得最优解。 PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个”极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 二、算法原理 粒子群算法采用常数学习因子，及惯性权重，粒子根据如下的公式更新自己的速度和位置。 V ki=ωk V i?1i+c1r1(Q bi?Q k?1i)+c2r2(Q bg?Q k?1i)Q ki=Q k?1i+V ki 三、算法步骤 1、随机初始化种群中各微粒的位置和速度； 2、评价个粒子的适应度，将各粒子的位置和适应度储存在各微粒的pbest（Q bi）中，将所有pbest中适应度最优的个体的位置和适应度存储在gbest（Q bg）中。 3、更新粒子的速度和位移。 V ki=ωk V i?1i+c1r1(Q bi?Q k?1i)+c2r2(Q bg?Q k?1i)Q ki=Q k?1i+V ki 4、对每个微粒，与其前一个最优位置比较，如果较好，则将其作为当前的最优位置。 5、比较当前所有的pbest和上一迭代周期的gbest，更新gbest。 6、若满足停止条件（达到要求精度或迭代次数），搜索停止，输出结果，否则，返回2。
第5期(总第156期) 2009年10月机械工程与自动化 M ECHAN I CAL EN G I N EER I N G & AU TOM A T I ON N o 15 O ct 1 文章编号:167226413(2009)0520194203 机器人路径规划方法的研究 李爱萍,李元宗 (太原理工大学机械工程学院,山西 太原 030024) 摘要:路径规划技术是机器人学研究领域中的一个重要部分。目前的研究主要分为全局规划方法和局部规划方法两大类。通过对机器人路径规划方法研究现状的分析,指出了各种方法的优点及不足,并对其发展方向进行了展望。 关键词:机器人;全局规划;局部规划中图分类号:T P 242 文献标识码:A 收稿日期:2009201207;修回日期:2009204218 作者简介:李爱萍(19792),女,山西晋中人,在读硕士研究生。 0 引言 路径规划技术是机器人学研究领域中的一个重要 部分。机器人的最优路径规划就是依据某个或某些优化准则(如工作代价最小、行走路线最短、行走时间最短等),在其工作空间中找到一条从起始状态到目标状态的最优路径。根据对环境信息的掌握程度不同,路径规划可分为:①全局路径规划:环境信息完全已知,根据环境地图按照一定的算法搜寻一条最优或者近似最优的无碰撞路径,规划路径的精确程度取决于获取环境信息的准确程度;②局部路径规划:环境信息完全未知或部分未知,根据传感器的信息来不断地更新其内部的环境信息,从而确定出机器人在地图中的当前位置及周围局部范围内的障碍物分布情况,并在此基础上,规划出一条从当前点到某一子目标点的最优路径。 1 全局规划方法111 栅格法 栅格法是目前研究最广泛的路径规划方法之一。该方法将机器人的工作空间分解为多个简单的区域(栅格),由这些栅格构成一个显式的连通图,或在搜索过程中形成隐式的连通图,然后在图上搜索一条从起始栅格到目标栅格的路径。一般路径只需用栅格的序号表示。但栅格的划分直接影响其规划结果,如果栅格划分过大,环境信息储藏量小,分辨率下降,规划能力就差;栅格划分过小,规划时间长,而且对信息存储能力的要求会急剧增加。112 可视图法 可视图法中的路径图由捕捉到的存在于机器人一 维网络曲线(称为路径图)自由空间中的节点组成。路径的初始状态和目标状态同路径图中的点相对应,这样路径规划问题就演变为在这些点间搜索路径的问题。要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,即直线是“可视的”。然后采用某种方法搜索从起始点到目标点的最优路径,搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。该法能够求得最短路径,但需假设忽略机器人的尺寸大小,使得机器人通过障碍物顶点时离障碍物太近甚至接触,并且搜索时间长。113 拓扑法 拓扑法将规划空间分割成具有拓扑特征的子空间,根据彼此的连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。拓扑法的基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。其优点在于利用拓扑特征大大缩小了搜索空间,其算法的复杂性仅依赖于障碍物数目,在理论上是完备的;而且拓扑法通常不需要机器人的准确位置,对于位置误差也就有了更好的鲁棒性。缺点是建立拓扑网络的过程相当复杂,特别是在增加障碍物时如何有效地修正已经存在的拓扑网是有待解决的问题。 114 自由空间法 自由空间法采用预先定义的广义锥形或凸多边形等基本形状构造自由空间,并将自由空间表示为连通图,通过搜索连通图来进行路径规划。自由空间的构
一种移动机器人的路径规划算法 作者：霍迎辉，张连明 (广东工业大学自动化研究所广州510090 文章来源：自动化技术与应用点击数：1419 更新时间：2005-1-24 摘要：本文提出一种移动机器人路径规划最短切线路径算法。依据此算法，机器人能顺利地避开障碍物到达目标位置，其原理简单，计算快捷，容易实现。仿真结果验证了它的有效性和实用性。 关键词：移动机器人；路径规划；机器人避障 1引言 移动机器人路径规划问题是指在有障碍物的工作环境中寻找一条恰当的从给定起点到终点的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物［1］。 障碍环境中机器人的无碰撞路径规划［2］是智能机器人研究的重要课题之一，由于在障碍空间中机器人运动规划的高度复杂性使得这一问题至今未能很好地解决。路径规划问题根据机器人的工作环境模型可以分为两种，一种是基于模型的路径规划，作业环境的全部信息都是预知的；另一种是基于传感器的路径规划，作业环境的信息是全部未知或部分未知的。 对机器人路径规划的研究，世界各国的专家学者们提出了许多不同的路径规划方法，主要可分为全局路径和局部路径规划方法。全局路径规划方法有位形空间法、广义锥方法、顶点图像法、栅格划归法；局部路径规划方法主要有人工势场法。这些方法都各有优缺点［3］，也没有一种方法能够适用于任何场合。 本文提出一种最短切线路径的规划方法，其涉及的理论并不高深，计算简单，容易实现，可供侧重于应用的读者参考。下面将详细介绍该算法的基本原理，最后给出仿真实现的结果。 2最短切线路径算法 2.1算法基本原理 (1)首先判断机器人和给定的目标位置之间是否存在障碍物。如图1所示，以B代表目标位置，其坐标 为(x Ｂ，y Ｂ ），以R、A分别代表机器人及障碍物，坐标为(x Ｒ ，y Ｒ )、(x Ａ ，y Ａ )。Ｒr和Ra表示机器人和障 碍物的碰撞半径，也就是说在其半径以外无碰撞的危险。这里对碰撞半径的选择作出一点说明，碰撞半径越小，发生碰撞的危险度越大，但切线路径越短；碰撞半径越大，发生碰撞的危险度越小，但同时切线路径越长。要根据实际情况和控制要求来确定碰撞半径。若机器人与目标位置之间不存在障碍物，机器人可走直线直接到达目标位置，此时的直线方程可由两点式确定：
遗传算法与机器人路径规划 摘要：机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。 关键词：路径规划；移动机器人；避障；遗传算法 Genetic Algorithm and Robot Path Planning Abstract: Robot path planning research is a very important area of robotics, it is also a combine point of artificial intelligence and robotics. For the mobile robot, it need to be worked by certain rulers（e.g time optimal），and find a best movement path in work space. Robot path planning can be modeled that in the course of robots able to avoid the obstacles from the initial position to the target location,and it ruquire to work under ertain constraints. Genetic algorithm used in path planning is very common, when planning the path ,it use the information of map ,and have high eficient in actual. Key words: Path planning,mobile robot, avoid the obstacles, genetic algorithm 1路径规划 1.1机器人路径规划分类 （1）根据机器人对环境信息掌握的程度和障碍物的不同，移动机器人的路径规划基本上可分为以下几类： 1，已知环境下的对静态障碍物的路径规划； 2，未知环境下的对静态障碍物的路径规划； 3，已知环境下对动态障碍物的路径规划； 4，未知环境下的对动态障碍物的路径规划。 （2）也可根据对环境信息掌握的程度不同将移动机器人路径规划分为两种类型： 1，基于环境先验完全信息的全局路径规划； 2，基于传感器信息的局部路径规划。 （第二种中的环境是未知或部分未知的，即障碍物的尺寸、形状和位置等信息必须通过传感器获取。） 1.2路径规划步骤 无论机器人路径规划属于哪种类别，采用何种规划算法，基本上都要遵循以下步骤： 1, 建立环境模型，即将现实世界的问题进行抽象后建立相关的模型； 2, 路径搜索方法，即寻找合乎条件的路径的算法。 1.3路径规划方法
第25卷第7期V ol.25No.7 控制与决策 Control and Decision 2010年7月 Jul.2010移动机器人路径规划技术综述 文章编号:1001-0920(2010)07-0961-07 朱大奇,颜明重 (上海海事大学水下机器人与智能系统实验室，上海201306) 摘要:智能移动机器人路径规划问题一直是机器人研究的核心内容之一.将移动机器人路径规划方法概括为:基于模版匹配路径规划技术、基于人工势场路径规划技术、基于地图构建路径规划技术和基于人工智能的路径规划技术.分别对这几种方法进行总结与评价,最后展望了移动机器人路径规划的未来研究方向. 关键词:移动机器人；路径规划；人工势场；模板匹配；地图构建；神经网络；智能计算 中图分类号:TP18；TP273文献标识码:A Survey on technology of mobile robot path planning ZHU Da-qi,YAN Ming-zhong (Laboratory of Underwater Vehicles and Intelligent Systems，Shanghai Maritime University，Shanghai201306, China．Correspondent：ZHU Da-qi，E-mail：zdq367@https://www.doczj.com/doc/048472564.html,) Abstract:The technology of intelligent mobile robot path planning is one of the most important robot research areas.In this paper the methods of path planning are classi?ed into four classes:Template based,arti?cial potential?eld based,map building based and arti?cial intelligent based approaches.First,the basic theories of the path planning methods are introduced brie?y.Then,the advantages and limitations of the methods are pointed out.Finally,the technology development trends of intelligent mobile robot path planning are given. Key words:Mobile robot；Path planning；Arti?cial potential?eld；Template approach；Map building；Neural network; Intelligent computation 1引言 所谓移动机器人路径规划技术,就是机器人根据自身传感器对环境的感知,自行规划出一条安全的运行路线,同时高效完成作业任务.移动机器人路径规划主要解决3个问题:1)使机器人能从初始点运动到目标点;2)用一定的算法使机器人能绕开障碍物,并且经过某些必须经过的点完成相应的作业任务;3)在完成以上任务的前提下,尽量优化机器人运行轨迹.机器人路径规划技术是智能移动机器人研究的核心内容之一,它起始于20世纪70年代,迄今为止,己有大量的研究成果报道.部分学者从机器人对环境感知的角度,将移动机器人路径规划方法分为3种类型[1]:基于环境模型的规划方法、基于事例学习的规划方法和基于行为的路径规划方法;从机器人路径规划的目标范围看,又可分为全局路径规划和局部路径规划;从规划环境是否随时间变化方面看,还可分为静态路径规划和动态路径规划. 本文从移动机器人路径规划的具体算法与策略上,将移动机器人路径规划技术概括为以下4类:模版匹配路径规划技术、人工势场路径规划技术、地图构建路径规划技术和人工智能路径规划技术.分别对这几种方法进行总结与评价,展望了移动机器人路径规划的未来发展方向. 2模版匹配路径规划技术 模版匹配方法是将机器人当前状态与过去经历相比较,找到最接近的状态,修改这一状态下的路径,便可得到一条新的路径[2,3].即首先利用路径规划所用到的或已产生的信息建立一个模版库,库中的任一模版包含每一次规划的环境信息和路径信息,这些模版可通过特定的索引取得;随后将当前规划任务和环境信息与模版库中的模版进行匹配,以寻找出一 收稿日期:2009-08-30；修回日期:2009-11-18. 基金项目:国家自然科学基金项目(50775136)；高校博士点基金项目(20093121110001)；上海市教委科研创新项目(10ZZ97). 作者简介:朱大奇(1964?),男,安徽安庆人,教授,博士生导师,从事水下机器人可靠性与路径规划等研究；颜明重(1977?),男,福建泉州人,博士生,从事水下机器人路径规划的研究.
基于粒子群优化算法的神经网络在农药定量构效关系建模中的应用 张丽平 俞欢军3 陈德钊 胡上序 (浙江大学化工系,杭州310027) 摘 要 神经网络模型能有效模拟非线性输入输出关系,但其常规训练算法为BP 或其它梯度算法,导致训练时间较长且易陷入局部极小点。本实验探讨用粒子群优化算法训练神经网络,并应用到苯乙酰胺类农药的定量构效关系建模中,对未知化合物的活性进行预测来指导新药的设计和合成。仿真结果表明,粒子群优化算法训练的神经网络不仅收敛速度明显加快,而且其预报精度也得到了较大的提高。关键词 粒子群优化算法,神经网络,定量构效关系 2004201204收稿;2004207225接受 本文系国家自然科学基金资助项目(N o.20276063) 1 引 言 药物定量构效关系(QS AR )是研究药物生理活性和药物分子结构参数间的量变规律并建立相应的 数学模型,进而研究药物的作用机理,从而用于预测未知化合物的生物活性,探讨药物的作用机理,指导新药的设计和合成,在药物和农药的研究与设计中已经显示出广阔的应用前景1。以往QS AR 的建模方法大多基于统计原理,局限于线性模型,只进行简单的非线性处理,由此所建立的模型很难契合实际构效关系,并且其处理过程都比较繁琐2。神经网络通过学习将构效关系知识隐式分布在网络之中,适用于高度非线性体系。 在药物QS AR 中采用神经网络(NN )始于20世纪80年代末3,此后得到迅速的发展,目前已发展为除多重线性回归和多元数据分析之外的第3种方法4。通常多层前传网络采用BP 算法,通过误差反传,按梯度下降的方向调整权值。其缺点是可能陷入局部极小点,且对高维输入收敛速度非常缓慢。 粒子群优化算法(particle swarm optimization ,PS O )是K ennedy 等5源于对鸟群、鱼群和人类社会行为的研究而发展的一种新的进化型寻优技术。PS O 已成为进化寻优算法研究的热点,其最主要特点是简单、收敛速度快,且所需领域知识少。本实验拟将该方法初始化前传神经网络为苯乙酰胺类农药建立良好适用的QS AR 模型。 2 苯乙酰胺类农药的Q SAR 问题 苯乙酰胺类化合物是除草农药,其除草活性与其分子结构密切相关。所有的N 2(12甲基212苯乙基)苯乙酰胺都可用相应的羧酸酰胺通过霍夫曼反应生成。N 2(12甲基212苯乙基)苯乙酰胺的基本结构式为 : 其中X 为Me 、F 、Cl 、OMe 、CF 3和Br 等,Y 为Me 、Cl 、F 和Br 等,由不同的X 和Y 取代基可构成不同的化合物。常用以下7个理化参数描述化合物的分子组成和结构:log P 、log 2P (疏水性参数及其平方项)、 σ(电性效应参数)、E s (T aft 立体参数)、MR (摩尔折射度),1χ、2 χ(分子连接性指数)。于是这类化合物的QS AR 就转化为上述理化参数与除草活性间的关系。为研究这种关系,选用具有代表性的50个化合物, 他们的活性值取自文献1,见表1。 第32卷2004年12月分析化学(FE NXI H UAX UE ) 研究报告Chinese Journal of Analytical Chemistry 第12期1590～1594
浅谈粒子群算法改进方法 【摘要】本文介绍了粒子群算法的基本概念及粒子群算法的训练过程，分别从基本进入、改变惯性因子、改变收缩因子三个方面对其进行优化改进。 【关键词】粒子群;进化方程;惯性因子;收缩因子 1.粒子群算法综述 二十世纪九十年代，美国的社会心理学家James Kennedy和电气工程师Russell通过对自然界的鸟群进行觅食的行为进行观察和研究，提出了模仿鸟群行为的新型群体智能算法——粒子群（Particle Swarm Optimization，PSO）算法。 粒子群算法与其它进化类算法十分相似，同样也是采用“群体”与“进化”的概念，同样也是依据粒子的适应值大小进行操作。而与之不同的是，粒子群算法不像其它进化算法那样，对于每个个体使用进化算子，而是将每个个体看作是在一个n维搜索空间中的没有重量没有体积的微粒，并在搜索空间中以一定的速度进行飞行。该飞行速度这个个体的飞行经验和群体的飞行经验来进行动态的调整。 2.粒子群算法实现的步骤 这里将基本粒子群算法的训练过程描述如下： （1）首先将初始化方程作为依据，将该粒子群体的随机位置和速度进行初始化设置; （2）计算粒子群中每个粒子的适应度值; （3）将该粒子群中每个粒子的适应值与其经历过的最好位置Pi的适应值进行比较，如果好，将它作为当前的最好位置; （4）将该粒子群体中每个粒子的适应值与所有粒子经历的最好位置Pg的适应值进行比较，如果好，将它作为当前的全局最好位置; （5）以粒子群进化方程为依据，进化粒子的速度及位置; （6）如果没有达到设置的结束条件或达到一个设置的最大迭代次数，则返回到第二步，否则结束。 3.粒子群算法进化方程的改进 3.1 基本粒子群算法进化方程的分析
收稿日期:2009-12-13 基金项目:国家自然科学基金资助项目(60674021) 作者简介:卢 峰(1982-),男,辽宁抚顺人,东北大学博士研究生;高立群(1949-),男,辽宁沈阳人,东北大学教授,博士生导师 第32卷第9期2011年9月东北大学学报(自然科学版)Journal of Northeastern U niversity(Natural Science)Vol 32,No.9Sep.2011 基于改进粒子群算法的优化策略 卢 峰,高立群 (东北大学信息科学与工程学院,辽宁沈阳 110819) 摘 要:为提高传统粒子群算法的搜索速度和搜索精度,提出了一种改进的自适应粒子群优化算法 将正则变化函数和慢变函数引入传统位置更新和速度更新公式当中,形成两种新的更新机制:搜索算子和开发算子 在算法运行的初始阶段,种群中大部分个体将按照搜索算子进行更新,搜索算子将有助于种群遍历整个解空间;随着迭代次数的增加,按照搜索算子进行更新的个体将逐渐减少,而按照开发算子进行更新的个体将逐渐增多,开发算子将有效地克服陷入局部最优解的问题 通过典型测试函数的仿真实验,新算法在加快收敛速度同时,提高了算法的全局搜索能力 关 键 词:进化算法;粒子群算法;全局优化;慢变函数;自适应 中图分类号:T G 273 文献标志码:A 文章编号:1005 3026(2011)09 01221 04 Novel Optimization Mechanism Based on Improved Particle Swarm Optimization L U Feng ,GAO L i qun (School of Information Science &Engineering,Northeaster n U niv ersity,Shenyang 110819,China.Corresponding author :LU F eng,E mail:feng.lu.lf @g https://www.doczj.com/doc/048472564.html,) Abstract :To accelerate searching speed and optimization accuracy of traditional PSO,an improved particle swarm optimization (PSO )algorithm w as presented.Regularly vary ing function and slow ly varying function were introduced in the position and velocity update formula.New mechanisms such as explorative operator and exploitative operator are formulated.At the beginning,most elements will be updated by explorative operator in the entire search space sufficiently.Within the iterations,more and more particles w ill be handled by ex ploitative operator,which are useful to overcome the deceptions of multiple local optima.It can be seen from the simulation results of the standard benchm ark test functions that the proposed algorithm not only accelerates the convergence process,but also improves g lobal optim ization ability. Key words:evolutionary algorithms;particle sw arm optimization;global optimization;slow ly v arying function;self adaptive 20世纪90年代初,产生了模拟自然生物群体行为的优化方法,被称为群智能优化方法 Dorigo 等人通过模拟蚂蚁的寻径行为,提出了蚁群优化算法(ant colony optimization)[1] ;Eberhart 等人基于对鸟群、鱼群的模拟,提出了粒子群优化算法(particle sw arm optim ization )[2] 作为一种群智能优化方法的代表,粒子群算法通过个体间的协作来寻找最优解,每个个体都被赋予一个随机速度并在整个解空间中搜索,通 过个体之间的合作与竞争来实现个体进化 由于粒子群优化算法运算简单,易于实现,具有良好的解决非线性、不可微和多峰值复杂优化问题的能力,已被广泛应用于科学和工程实际领域[3-5] 但是,粒子群优化算法是根据全体粒子和自身的搜索经验向着最优解的方向进化,在进化后期收敛速度将变得缓慢,同时算法在收敛到一定精度时,容易陷入停滞,无法继续进化更新,因此,存在早熟和陷入局部极值点的现象
多机器人路径规划研究方法 张亚鸣雷小宇杨胜跃樊晓平瞿志华贾占朝 摘要：在查阅大量文献的基础上对多机器人路径规划的主要研究内容和研究现状进行了分析和总结，讨论了多机器人路径规划方法的评判标准，并阐述了研究遇到的瓶颈问题，展望了多机器人路径规划方法的发展趋势。 关键词：多机器人；路径规划；强化学习；评判准则 Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multi robot.Then discussed the criterion of path planning research for multi robot based large of literature.Meanwhile,it expounded the bottleneck of the path planning research for multi robot，forecasted the future development of multi robot path planning. Key words:multi robot；path planning;reinforcement learning;evaluating criteria 近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI研究大致可以分为DPS（distributed problem solving）和MAS（multi agent system）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点,而路径规划研究又是其核心部分。 机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果[1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、Dempster Shafer 证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划