（机械设计及理论专业论文）基于机器视觉的机构运动学和动力学分析系统研究.pdf

摘要 摘要 在机器工业中，机构是组成各种机械系统的基础，因此机构学的研究一直是 机械领域中的研究重点。机构的运动分析，就是对机构的位移、速度和加速度进 行分析。无论是分析研究现有机械的工作性能，还是优化设计新机构，机构运动 分析都是十分重要的。 基于机器视觉的检测技术以其快速、精确、柔性高等特点在国外得到了深入 研究和广泛应用，在国内也越来越受到重视。 本文提出了基于机器视觉的机构运动学和动力学的分析系统，根据实际工程 的需要，选择了合适的硬件，搭建了机器视觉系统，并给出了系统软件的结构及 其工作流程。在先进的开发平台上，利用现有的软件，配置相关的硬件，采用固 定时间拍摄机构运动的图像，通过数字图像处理技术，实现对机构运动学和动力 学相关参数的检测，为企业提供准确机构运动和动力学参数。 由于机构工作环境的影响以及成像系统的自身限制，所获取的图像会存在一 定的噪声，影响图像分析的结果，所以必需进行图像的预处理。图像的预处理是 图像处理的关键步骤，它直接关系到图像处理后续环节中的准确性以及正确率。 所以研究图像预处理的根本目的在于提取信息，将有用的部分作为前景与背景进 行有效的区分开来。 本文首先介绍最新的优化算法竞选算法的基本思想，实现过程和特点，并使 用验证函数对竞选算法进行验证。 其次，概述了图像增强和图像分割的定义和意义以及其发展现状和趋势，并 在此基础上提出了基于竞选算法的自适应图像增强和图像分割的设想，经实验证 明，取得良好的效果。 再次，本文采用基于竞选算法的自适应图像增强和图像分割方法，作为基于 机器视觉的机构运动学和动力学的分析验证系统的图像预处理算法，并设计出该 验证系统，能准确提供机构运动学和动力学的相关参数，本程序采用v a 嘶o 在 w i n x p 环境下编译，完成实现了上述的各种算法。为了验证各种算法的性能和效 果，本文对系统进行了实验。实验结果表明，该系统达到了预期目标。 在论文最后，对整个论文的工作进行了总结，并指出了进一步研究探索的方 向。 广东工业大学工学硕士学位论文 关键字：竞选算法；图像分割：机器视觉；图像增强 a b g m c a b s t r a c t i nt h ed e v e l o p m e 恤o f i n 蜘，m e c h = m sj st h eb a s i co f m a c h i ms y s t e m ，s o m e c i 场面鲫笛i sa l w a y st h em o s ti m p o r t a n t p 矾o f t h e 如血蚰y a 】 1 a 岍；i so f m e c h a n i s m s i st oa n a l y z en 砖d i 叩妇n 瑚m 叫o c i t ya n da c c e l e l - a 6 0 no f m h a n i s m s n om a t t d 证 a n a l 酒n g t h e m e c h a n i s m s ，o rd e s i 跳l l c w m h a i l i 知够，x m l y s i s o f m e c h a n i s m s i s t h e m o s t i m p o r t a n t p a n t h em 鞠飙脚跚1 e mb a s e d0 1 1n m c h i n ev i s i o ni sd 盈髓咖e i i s 雠w i t hr a p i d ，l l j 曲 p i l ，2 i s i o n a n d f l e x i b i l i t y i t h a s b e e n s t u d i e d a n d a p p l i e d w i d e l y a t h o m e a n d a b r o a d n 凼p a s s a g ei n t r o d u c e das y s t e mt h a ta n a l y z e ( h ek i n e i i l a f i ( 笃a n dk j l 甜c 8o f m e c h a m m mb a s e d m a c l 池v i s i o ma l lt h ep a r eo f ( h em a c h i n ev i s i o ns y s t e ma r c c h o s e n a n d a s s e m b l e d b y n e e d t h es t z l c t m o f t h e m a c h i n e v i s i o n s y s t e m a n d t h e f l o w c h a l to ft h es o l 6 t w a r ei s 画v e r l t h ep l a t f o r mw i t ha d v a n c e ds o i t w a r ca n dh a r d w a r ei s u s e dt os h o o ts o r l i n l a g 髂a b o u tt h es y s t e mi ni n t e r v a l i tw i l l p r o v i d ea 酗 如暖嘲m 舶1 删晦o fn 1 d n 跚衄矗璐a n d 菇n 鲥璐o fm k m i c c 咖塔t o1 h ea 恤印d 辩 t h r o u g hd i 酉t a li m a g cp l o s s i i 培 t h e r em - ei n e v i t a b l eal o to f n o i s e si nd 埒i m a g 鹳t h a t 瓣a c q u i r e d b y 曲曙c 越r 啪，i t w i l l a f f e c tn l cr e s u l to fi m a g es o a l y s i ss oi m a g ep i 争p i d 积妇n gi s e d 。d h i m g e p r 争n o c 蛐j st h ei m f l g cp r o c e s s i n ge s s e n t i a ls t e p ，i t 蜘妇t ol h ea c c u r a c yo f 恤f o l l o w i n gi n l a g ep d s s i i 培，a n dt h ep r o p o 船o f i n 噙g ep r e - p r o c e s 她i st og e tt h e f o r e g r o u n d w h i c h w a s u s e f u l f o r m t h e b a c l q i r o u n & f i r s t i ti n l r o d u c ef i l eb * d s i ci d e a 、p r o c e s s i n ga n da d v a m a g eo fl l l ee l e c t i o n a l g o r i t l a 【i l s e c o n d ，i t 飘n n n 嘶z et h ed e f i n i t i o n 、 i m a g ee n h a n c e m e n ta n di m a g es e g m e f l t a t i o n ，t h e nu s ee l e c t i o na 】9 0 f i l h nt oo p t m = l t t a d a p 位v e i m a g e a n d i m a g es e g m e n t a f i o l l t h i r d ，t h e s y s t e m o = t a n a l y s i s t h e l d n e * m a f i c s a n d k i n e t i c s o f 蛐b a s e d o n m a c l = 血l ev i s i o nw i l ll 聊t h em e t h o do fl 醇h 萼e l e c t i o na l g o r i 岫at o0 l 妯| i l i z et h et h e a d a p t i v ei m a g ee n h a n c e m e n t a n di m a g es e g m e n t a t i o na si 俘i n = g ep r e - p r o c e s s 啦，a n d m 广东工业大学工学硕士学位论文 i sd e s i g n e d i tw i l lp r o v i d ee x a c tm e a s u r e m e n t so ft h ek i n e m a t i c sa n dk i n e t i c so f m e c h a n i s m s i ti sp r o g r a r m n i n g0 1 1t h ew i n d o wx pp l a t f o r mw i t hp r o g m n n n ct o o lo f v i s u a lc + + 6 0 i no r d e rt ov a l i d a t ea l la l g o r i t h m sa n dt ! zs y s t e ma b o v e ，e x p m m e n 姆 戤p c d 伽讽低唧s h o w s 帆船s y s 咖m 眺雠r 蚓s o f 啦妇s i s a t h s t ，t h e a u t h o r s i d e a s a n d a d v i c c s t o e x t e n d s t u d y a g i 吼 k 眄w o r d ：e l e c t i o na l g o r i t h m ；m a c h i n e v i s i o n ；i m a g es e g m e n t a t i o n ；i m a g e e n h a n c e m e n t 广东工业大学工学硕士学位论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表达了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有 申请学位论文与资料若有不实之处，本人愿意承担切相关责任，特此声明。 闭烀 曼健 口移杜 鬈咖 鬈似 弘 第一章绪论 自从1 8 世纪末工业革命，人类踏入机器工业的文明时代，机械工业占据主要 地型”。而在机械工业的领域中，机械机构一直起着十分重要的作用。随着机器 自动化的迅速发展，机械机构的应用范围越来越广，机构学成为一门独立的学科， 走进学术的殿堂。 一个多世纪以来，世界各国科研人员投入了极大的精力，对机构进行大量的 研究，取得优秀的成果。无论是过去还是未来，机构对机械工业的生产和发展有 极重要的意义。在机器工业中，机构是组成各类型机械系统的基础，例如活塞发 动机中的连杆机构，各种纺织机械中的卷绕机构、印刷机械中的凸轮机构等，因 此机构学一直是机械领域中的研究重点。 1 _ 2 机构运动分析 机构运动分析是分析研究现有机械系统的工作性能和优化设计新机构中十分 重要的一环。 机构的运动分析的定义是对机构的位移、速度和加速度进行运动学和动力学 分析。机构运动分析研究的内容，是在已知原动件的运动规律的条件下，分析研 究现有机构中各构件上各节点的位移、轨迹、速度和加速度，以及这些构件的角 位移、角速度和角加速度。这些运动参数，是分析、评价现有机构的工作性能的 重要指标，同时它也是综合优化设计新机构的基本依据。 通过对位移( 包括轨迹) 的分析，可以确定机构上的构件运动所需的空间，避 免各个构件在运动中发生相互干涉；影响机构的正常运作而且还可以确定各个构 件的行程位置，考查构件或构件上某节点能否实现预定位置变化的要求，能否满 足工作的需要。 通过对速度的分析，可以得到机构中各构件的速度随时间变化而变化的情况， 从而确定是否满足工作要求。同时速度分析也是机构的加速度分析和受力分析的 广东工业大学工学硕士学位论文 前提条件。 对机构加速度的分析，是计算机构惯性力不可缺少的前提条件。机构的动载 荷或惯性力随着时间变化的大小变化，关系到机构的运动强度、振动等动力学性 能。特别在高速机械中，加速度分析将显得十分重要。 1 3 机构的运动分析方法 机构运动分析的方法有三种，分别为：图解法、解析法和实验i 去f 习。在这三种 基本的方法中，图解法形象直观，能提供一些物理形象和相互关系一般应用于 比较简单的机构，例如平面机构来说。从机构开始使用到1 9 5 0 年，进行机构分析 几乎都使用图解法。使用图解法作图相当复杂，需要对机构的一系列位置进行运 动分析时，对每一个位置需要作图分析，工作重复而且精度不高。无法满足现代 科学技术发展需要。常用的图解法有速度瞬心法和矢量方程图解法等，它们也有 不同的地方。利用瞬心法对某些平面机构，特别是平面高副机构，能比较简便的 进行速度分析。缺点是，对比较复杂的机构来说，如多杆机构，则由于瞬心数目 过多，因而将使速度分析问题变得十分复杂，而且有时有些瞬心的位置往往位于 图面之外，致使求解产生困难。另外，利用速度瞬凸法只能对机构进行速度分析， 而当需要对机构进行加速度分析时，速度瞬心法就无能为力。矢量方程图解法依 据的基本原理，是理论力学中的运动合成原理在对机构进行速度和加速度分析 时，首先要根据运动合成原理，来列出机构运动的矢量方程，然后再根据该方程 进行作图求解。这种方法需要列出矢量方程，对于复杂机构杆件，有些点的矢量 方程复杂而不容易列出，这样对于进步作图求解形成了障碍。 解析法的基本方法是把机构中已知的尺寸参数和运动变量与未知的运动变量 之间的关系用数学式表达出来，然后对数字式进行求解。因此，解析式一旦列出， 则机构在各位置时的运动变量的计算就很便捷了，而且可获得很高的计算精度， 能推广到解空间机构f 司题。同时还可把机构分析问题和机构综合问题联系起来， 便于进行更深入的研究。缺点是解析法得到的只有表达式，不像图解法那样直观 形象的看出机构的运动轨迹，而且在分析复杂机构和多自由度机构时，常常难以 建立有关的解析数学模型，而且得到表达式也比较复杂，计算工作量也很大。近 十多年来，各种新的解析方法不断涌现，这里介绍其中的两种解析法。 2 第一章绪论 节点逼近法，是一种用数值法求解连杆机构运动问题的通用方法。此方法是 把连杆机构作为由若干矢量构成的封闭图形，然后通过对每一个节点的迭代逼近， 逐步求得满足给定精度的数值解。 吴方法是七十年代数学机械化思想的倡导者吴文俊院士提出，这种方法是一 种对非线性方程组进行代数求解的方法，这个方法能准确判定一个非线性联立方 程组有无解答，是否无穷多解，以及在恰有有限多个解时，可求出这些解答的全 部而无增无漏。这种方法也称为数学机械化方法，因为它有一个机械化的计算程 式，按照此程式的步骤，每个非线性联立方程组都可以在有限步内得到解决。 实验法，顾名思义，就是进行实验，同时使用相关的仪器对机构的相关数据 进行检测，直接从实验中获得机构运动学和动力学数据。用实验法进行设计的过 程中，使用传统的手工绘图方法来完成机构简图的绘制任务，用移动透明纸来确 定机构铰接点的位置，用三角板等测量工具来完成澳4 量任务，不仅费时，费力， 而且由于存在分度误差，作图误差，对准误差和测量误差以及由这些误差所产生 的误差累积效应，常常使得设计精度难以提高，设计过程多次重复的现象时有发 生。因此，减小用实验法进行机构设计过程的各种误差，提高该方法的设计精度 和设计效率是一个不容忽视的问题。 实验法最常用的方法是结合传感器的检测方法，该方法是使用各种传感器测 量相关数据，要完成机构运动学和动力学的参数检测，需要使用位移传感器测量 节点的位移，使用速度传感器测量节点的速度，还需要角速度传感器，加速度传 感器，角加速度传感器，力传感器等，优点是测量精度高，缺点是测量效率低， 测量设备昂贵。 针对实验法现有存在的缺点，本文在实验法基础上，提出基于机器视觉的机 构运动和动力学的验证系统，对运动机构进行高精度、高分辨率的图像或视频采 集，然后通过图像处理，实现对机构运动学和动力学相关参数的快速检测，缺点 是精度不高，适合对精度要求不高的场合，如对机构作定量分析。 1 4 机器视觉简介 人类在漫长的生产实践中，发明创造了许多机器来辅助或代替人类完成生产 实践活动 3 1 。人们一直在努力使机器能模仿人类的功能来感知外部世界，从而能 广东工业大学工学硕士学位论文 更有效地帮助人们来减轻劳动强度。 人类对外部世界的感知主要是通过视觉、触觉、听觉和嗅觉等感觉器官来完 成，但其中约8 0 的信息是由视觉获取的。视觉对于人类和许多高级动物来说是 一种极为重要的能力。因此，要使机器能够更好的为人类服务，给机器赋予视觉 功能是非常必要的。随着科技的进步，计算机己经可以模仿人类大脑的部分活动， 相机也能像人类的眼睛一样捕捉外部的世界。- - f 研究如何让机器拥有类似人类 视觉功能一样的科学也应运而生了，这就是机器视觉。 机器视觉是研究用相机和计算机来模仿人的眼睛和大脑完成对目标的识别、 跟踪和测量等任务的科学。通俗地说，就是用机器代替人眼来做测量和判断。它 的工作过程大致为：首先，使用相机将被摄取目标转换成图像信号，传送给专用的 图像处理系统，图像系统对这些图像中包含的信息进行处理和计算：然后计算机根 据处理的结果做出判断或决毙最后将控制信号传送给执行机构。机器视觉的特点 是自动化、客观、非接触和高精度，与一般意义上的图像处理系统相比，机器视 觉强调的是精度和速度，以及工业现场环境下的可靠性。 作为一门新生的科学，机器视觉显示出了强大的生命力。人们从2 0 世纪5 0 年代开始研究二维图像的统计模式识别，6 0 年代r o b e m 开始进行三维机器视觉 的研究，7 0 年代中期，m r r 人工智能实验室正式开设机器视觉课程，舳年 代初期开始了全球性的研究热潮，机器视觉获得了蓬勃发展，新概念、新理论不 断涌现。伴随着计算机技术的不断提高和图像处理与传输技术的日益成熟，机器 视觉在生产实践中的应用也加快了步伐。现在机器视觉已经广泛地用于工业、农 业、军事、航空、医学等领域中。同时，机器视觉在理论研究上也取得了很大的 发展，现在机器视觉涉及了多门学科，包括光学、机械、图像处理、计算机图形 学、模式识别、人工智能、人工神经网络等。 1 4 i 机器视觉检测 本机构运动学和动力学系统是基于机器视觉相关理论的，依靠其图像处理的 相关理论，实现运动学和动力学参数的快速检测1 4 1 。机器视觉检测技术是一种以 现代光学为基础，融光电子学、计算机图像学、信息处理等科学技术为一体的现 代检测技术。随着计算机技术和光电技术的发展，机器视觉检测技术得到了飞速 4 第一章绪论 的发展和广泛的应用。 与传统测量方法相比，视觉测量技术有着独特的优越性。首先从成本考虑， 由于传统的测量方法的速度慢，效率低而且投入的人力资源也多，所以成本高。 第二，视觉测量技术有效地扩展了人了自身的视觉能力，它利用光电成像技术对 所得的图像进行处理，通过选择合适的镜头，可以对不同尺寸大小的零件进行测 量，极大地扩大了测量的范围。第三，视觉测量技术利用了计算机及各种软件功 能进行图像处理，有效地避免了人眼读数等因素造成的误差，减少了重复性测量 的误差和仪器本身形成的误差，有利于提高精度。最后，由于测量系统本身的特 性，测量过程自动化程序提高，提高了检测的效率。 1 5 优化算法应用于图像处理 优化理论所研究的问题是讨论的是如何在搜索范围内中找出最优值，以及怎 样找出最优僧q 。这类问题广泛存在于图像处理与分析系统的技术领域。近年来， 随着计算机广泛应用于数字图像处理技术，使优化算法成为求解图像问题的有力 工具，而优化算法也是各图像处理系统最核心、最保密的部分，所以研究优化算 法应用于图像处理是必要的。 目前最优化理论应用范围涉及了图像技术的方方面面，例如图像重构、图像 恢复、图像增强、图像边缘检测、图像配准、图像分割和图像编码等。刘梅、刘 慧念、刘伟东等人的文章中提出了采用人工神经网络映射图像重构过程非线性特 性的方法。在相机参数已知的情况下，用后向误差传播( b p ) 神经网络融合从不同 角度对同一景物重复拍照得到的多帧低分辨率图像的冗余信息，重构得到较高分 辨率的图像 6 1 。汪建在文章中论述了基于遗传算法的图像恢复方法，提出了将模 拟退火法和遗传算法相结合求解图像非线性最优化问题的算法见改进的算法提 高了进化速度和全局寻优的能力，从而提高了图像的复原度。蒋定定、王贵霞、 等人的论文将遗传算法引入红外图像增强，使用缈 图像的参数模型将图像增强 转化为参数的优化呷。实验结果表明，该方法是种有效的图像增强方法。m o r s e 等人把动态规划应用于边缘检测，首先检测出图像的局部不连续性，再用串行搜 索法将它们连成边界，从而实现目标的边缘检测唧。唐健等人提出一个适当的适 配度函数以评定传感器图像间的映射参数，并在此基础上采用遗传算法、模拟退 广东工业大学工学硕士学位论文 火、遗传模拟退火算法等随机优化方法解决此优化问题，从而达到自动配准传感 器图像的目自q 【埘。吴薇等人文章中用种基于免疫调节机制的免疫遗传算法求解 最大熵准则下图像的一组最佳分割阈值，不仅提高了运算速度【l “。肖嵩等人提出 种联合信源信道编码的速率分配方案，针对渐进图像的速率分配问题建立了数 学模型，对模型的求解进行了简化，并采用拉格朗日乘数法，在满足一定的约束 条件下实现了速率的最优化分配l 忸。 从上面例子，可以得到个结论，许多图像处理的问题最终归结到个最优 化问题。通过对图像处理问题进行分析研究，建立数学模型。将所得的最优化问 题进行整理和变换，使之成为易于求解的形式，选择适当的优化理论方法，进行 分析，计算结果 1 6 论文选题的目的与意义 鉴于机构在机械工业发挥着重大的作用，机构运动分析是研究机械性能的重 要组成部分。通过对机构运动分析，可以了解已有机构的运动特性，便于合理有 效的使用现有的各种机械，或者根据机构的性能对某些机械提供改进设计的有关 数据，使机构在改型时有所遵循，在设计新机构方面，进行机构的运动分析，是 设计师检查机构是否符合设计要求的必要步骤，通过分析得到的有关数据，才能 确实说明新机构满足设计要求，或者是否尚存在不足，依此为据改进设计方案， 修改原设计从以上几个方面，可以看出机构运动分析的重要性和必要性。 随着计算机技术迅猛发展，计算机图聊图像处理能力日益增强。计算机辅助 设计又使机构学发展到个新阶段，它把机构设计理论方法和参数选取等设计者 的智慧与计算机系统所具有的强大逻辑推理、分析判断、数据处理、运算速度、 二维、三维图形显示等功能结合起来，可以用人机对话方式，简便、直观、快速、 最优的完成设计任务，已成为现代机构设计的主要手段。 因此，结合计算机图像处理技术，对机构运动分析进行研究，一直是机构学 中较为重要的研究课题。因此，利用现有图像处理技术，研究出简单、直观、快 速的方法是本课题的研究目标。 6 1 7 文章的主要研究内容 1 综述竞选算法的理论基础、特点，及其应用。 2 分析了现有的图像增强和图像分割方法。 3 针对现有的图像增强和图像分割方法存在的缺陷，分析了一些结合竞选算 法的图像增强和图像分割算法。 4 针对图解法、解析法和实验法现有的缺点，结合机器视觉检测技术高效快 速的优点，本课题主要研究采用基于机器视觉技术的实验方法，这方法既继承了 实验法的优点，同时在一定程度上避免了实验法效率低的缺点。 7 广东工业大学工学硕士学位论文 2 1 引言 第二章竞选算法 优化是科学研究和应用技术中都经常遇到的问题。随着科学技术的迅速发展， 现代系统的规模越来越大，结构日趋复杂，约束条件不断增多，非线性日益严重， 同时由于测量的不准确性，系统动力学的不确定性等固有的因素的存在，在这些 系统的研究中存在着大量的经典优化方法所不能有效求解的问题。w o l p e i t 和 m 蚓瑚d y 在1 9 9 7 年提出并严格论证了无免费午餐定理( n of r e e l u n c h t h e o r e m s ) ， 简称为n f l 定理【“。n f l 定理的简单表述为：对于所有可能的问题，任意给定两 个算法a 、a t ，如果a 在某些问题上表现比a t 好( 差) ，那么a 在其他问题上的表现 就一定比a 差( 好) 。也就是说，任意两个算法a 、a 对所有问题的平均表现度量 是完全一样的。n f l 定理否定了寻找一个万能的通用最佳算法的可能性，等效地， n 】璇理肯定了针对特定的优化问题，一定存在着相对最适用优化算法的必然性。 因此，探索新型的优化算法将始终是一项有科学意义和实用价值的工作。 人们对自然界和人类社会及其表现出各种行为、特征和规律迸行模拟，产生 了一些对现代科学技术发展有着重要影响的新兴学科和技术，如模仿生物行为而 建立的仿生学、借鉴人体信息处理机制的人工神经、效仿大脑思维方式的模糊系 统等。在优化理论和方法研究上，人们通过模拟自然界和人类社会的各种行为、 特征和规律，提出了一些具有优秀搜索能力的现代优化算法，如模仿物种进化的 竞选算法、模拟金属冷却过程的退火算法、模拟蚂蚁觅食过程的蚁群算法、模拟 鸟类或鱼群觅食行为的粒子群算法、模拟动物记忆功能的禁忌搜索算法、基于免 疫学原理的免疫算法等。 竞选是人类社会的一项重要活动，竞选人通过一系列竞选行为，以期望获得 选民们的最大支持。竞选人通过对选民们的抽样调查来估算当前支持情况，并以 此来决定下一步竞选行动。为了获得选民们的更高支持，竞选人总是趋向具有较 高威望选民的位置。竞选是竞选人追求选民们的最大支持；而优化是从问题的求 解域中寻找出最优解，两者在过程上和原理上都存在着一定相似性。可以想象， 竞选过程中应该蕴涵着一种优化思想和机制，可以借鉴这一思想和模拟这一机制 而建立个新型的优化算法。 2 2 竞选算法的基本原理 设想存在着这样一种竞选机制：多个竞选人在选民中进行竞选。竞选人能够 对一定范围内的选民产生影响，竞选人对选民的影响随着竞选人与选民之间的距 离的增加而逐渐减小。竞选人的威望越高，他的影响范围也就越大，当超过一定 的极限距离后竞选人对选民的影响降低为零；假设社会结构是不均衡的，选民的 威望不尽相同，因此对竞选人的支持也不相同；每一个选民都受到多个竞选人的 影响，选民要根据竞选人对他影响的大小按比例分配他的支持；通过对选民的抽 样调查获取各个竞选人的被支持情况。为了保证调查的准确性和全面性，以竞选 人所在位置为均值按正态分布的概率生成局部调查样本，在整个选民范围内按均 匀分布的概率生成全局调查样本。这样，计算某个竞选人对有限数量抽样调查选 民的影响和抽样调查选民对该竞选人的支持，就可以估算出该竞选人的被支持情 况。竞选人可能对多个选民产生影响，因此也就会获得多个选民的支持。个抽 样调查选民对某个竞选人的支持占该竞选人获得总支持的比例，就是个抽样调 查选民对该竞选人的贡献。将每个抽样调查选民的位置坐标与其贡献相乘后求和， 得到的位置坐标就是该竞选人支持重心，即抽样调查得出的该竞选人具有更高威 望的位置。 在上面描述的竞选机制中，如果将竞选人比喻成“船”，选民想象成“水”， “船”出于对更高“水”面的追求，根据抽样调查结果不断调整自身位置，以得 到更高的威望。可以看出，竞选人对不同距离的抽样调查选民的影响是不同的， 威望不同抽样调查选民可供分配的的支持量也不相同，因此个抽样调查选民分 配给不同竞选人产生的支持的也不相同。这样，虽然是同一批抽样调查选民，对 不同竞选人产生的支持的贡献是完全不同的，因此也就有不同的支持萤d ，引导 着竞选人向最适合自己的位置移动。从效果上看，这样的竞选机制将引导着竞选 人向着距离自己较近的、具有较高威望的抽样调查选民方向移动，以获得具有更 高威望的位置。 9 广东工业大学工学硕士学位论文 2 3 竞选算法 竞选是竞选人通过一系列竞选活动以获得最大的支持，而优化是从问题的众 多可行解中寻找出最优解，两者在过程上存在着定的相似性。可以想象，竞选 过程中蕴涵着一种优化思想和机制，可以借鉴这一思想和模拟这一机制而建立一 个新型的优化算法，将它称为竞选算法。 在竞选算法中，将解空间想象成选民，将当前解想象成竞选人。选民，既可 行解所对应的函数值称为选民的威望，竞选人。即当前解所对应的函数值称为竞 选人的威望。 1 1 1 2 - 1 抽样调歪选民分布 f i g 哦2 - 1 丑埒d i s n 协i t i o n o f v o i 矗 下面以竞选算法的一个计算循环为例，介绍竞选算法的搜索过程。在示例计 算中使用3 个竞选人，记为g ( f 2 l ，2 ，3 ) ，在图中以十字符号标志：使用1 6 - ? 啥 局抽样调查选民巧( ，= l ，2 ，1 6 ) ，以空心圈符号标志，其位置坐标记为 。_ ( 歹2 l ，2 ，1 6 ) ；每个竞选人周围使用4 个局部抽样调查选民 ( i - 1 ，2 , 3 ；j = t , 2 ，3 ，4 ) ，以实心圆符号标志，其位置坐标记为 4 ( f 2 l ，2 3 ；，2 l ，2 , 3 ，4 ) ：图中的实心点示意选民。以后约定，抽样调查选民的 单数字下标”表示全局抽样调查选民，逗号分开的两数字下标“l ，j ”表示局 部抽样调查选民，第一个数字表示在第“f ”个竞选人周围，第二个数字表示在 第“j ”个局部顺序号。 首先计算竞选人的威望。在竞选算法中，竞选人，即当前解所对应的函数值 称为竞选人的威望，因此，直接由目标函数计算竞选人的威望，即 量= k ) 其中，气表示竞选人c f 的威望，厂( + ) 是目标函数，是竞选人g 的位置坐 械忙1 2 ，3 ) 。可以计算出竞选人q 、c 2 和g 的威望乇、乞和乞 计算竞选人的影响范围。竞选人的威望越高，他的影响范围也就越大，当超 过一定的极限距离后竞选人对选民的影响降低为零。因此，可以采用下面的规律 建立竞选人的威望与影响范围之间的关系 民= 等( 一) + p p ”一“。 【2 1 ) 其中，表示竞选人e 的影响范围；和矗是最大和最小竞选人影响 范围，是算法的两个参数；和j k 是当前竞选人中的最大威望和最小威望， = 胍( 墨，忍，吃) ，= m i n ( p c 。，吃，吃) 。也可以将和设为相 同，即采用固定的竞选人影响范围。可以计算出竞选人q 、g 和g 的影响范围 飞、和。 厂乐工业丈掌工学硕士学位论文 计算竞选人的局部抽样调查均方差。竞选人的威望越高，竞选算法采用较小 的局部抽样调查范围，以使算法快速地稳定收敛于局部最优解。因此，可以采用 下面的规律建立竞选人的威望与局部抽样调查均方差之间的关系 2 一瓦1 , g - f m i n ( 一) 。 其中，表示竞选人c f 的局部抽样调查均方差；仃如和a h 一是最大和最小 竞选人局部抽样调查均方差，是算法的参数，需要在计算前进行设置；也可以将 口赢和a 赢设为相同，即采用固定的竞选人局部抽样调查均方差。可以计算出竞 选人q 、g 和c 的影响范围、和 生成全局抽样调查选民。在可行解中，使用均匀分布产生全局抽样调查选民， 均匀分布记为“( x 一，x 一) ，其概率密度函数为 ，。一j 士毛m j 工( x ) = 一6 “一一” 【0 其他 ( 2 3 ) 其中，j 一和分别是可行解区域的下限和上限。可由下面的m a t l a b 语言 代码实现： 2 r a n d ；p ：生 o ，1 】区间上的服从均匀分布的随机数 r a n d 是m a t l 曲提供的产生【o ，1 1 区间上的服从均匀分布的随机数的函数 2 2 + “x m a x 一一) ；将随机数映射到【，m 】区间上 因此，可由均匀分布产生全局抽样调查选民 勃= “( ，) 可以计算出全局抽样调查选民即、吁、瑶。 生成局部抽样调查选民。在竞选人周围，使用正态分布产生局部抽样调查选 民。正态分布记为n ( ，c r 2 ) ，其概率密度函数为 斛去唧 - 簪卜m g 御 其中，是均值，c r 2 是均方差。可由下面的m 甜a b 语言代码实现： u l2 加，耐；产生【o ，l 】区间上的均匀分布的随机数 u 22 r a n d ；产生i o ，1 】区间上的均匀分布的随机数 z = - 2 1 n ( “1 ) - s i n ( 2 x u 2 ) ：产生服从标准正态均匀分布n ( o 1 ) 的随机数 z = “+ o z ：产生服从正态均匀分布n 似，c r 2 ) 的随机数 因此，可由正态分布产生局部抽样调查选民 飞= nk ，吒) ， 可以计算出竞选人q 、c 2 和g 的局部抽样调查选民、巧、，巧j 、 k j 、k j 、k j 和巧，、巧j 、巧。 计算竞选人与抽样调查选民之间的距离。竞选人与抽样调查选民之间的距离 或 d c ? j = r j j = k 一_ l ( 2 固 其中，2 k 竞选人q 与抽样调查选民巧之间的距离这里，巧泛指全局和局 广东工业大学工学硕士学位论文 部抽样调查选民，例如，竞选人c l 与全局抽样调查选民巧之间的距离是b ， 竞选人c 1 与局部抽样调查选民k ，：之间的距离是。可以计算出所有竞选人与 所有抽样调查选民之间的距离。 计算竞选人对抽样调查选民的影响。竞选人可以其影响范围内的选民产生影 响。竞选人q 对抽样调查选民的影响为 f j 堕尼 f c n 2 、 r c t i qj ， 【 o 其他 ( 2 刀 其中是竞选人c l 对抽样调查选民巧的影响，巧泛指全局和局部抽样调 查选民。此处假设竞选人对选民的影响按线性规律衰减。也可以采用非线性规律 衰减的。如 f c 2 警卜民嘞 o 其他 ( 2 8 ) 例如，竞选人c l 可以影响到全局抽样调查选民巧、巧、k 、巧和局 部抽样调查选民巧，- 、巧、巧j 、巧，、k j ，对他们的影响分别是 黾 “， 生二垒p 警吃、孚吃、平吃、警尼和警乇、 警乞、半吃、警量、牛气俐阍以 获得其他竞选人对其影响范围内的抽样调查选民产生的影响。一个抽样调查选民 可能受到多个竞选人的影响，例如全局抽样调查选民嵋同时受到竞选人c l 、c 2 和 g 的影响，全局抽样调查选民巧同时受到竞选人c l 和c 2 的影响，局部抽样调查 选民同时受到竞选人c 1 和c 2 的影响。 计算选民受到的总影响。个选民可能受到多个竞选人的影响，他所受到的 总影响是所有竞选人对他影响之和 矗= 其中表示选民巧的总影响。例如，抽样调查选民巧同时受到竞选人c l 和 c 2 的影响。可以计算出所有抽样调查选民受到的总影响。 计算选民的威望。直接由目标函数计算选民的威望，即 吃= 厂h ) 其中乇表示选民巧的威望，厂( ) 是函数，勺是选民巧的位置坐标。可以 计算出抽样调查选民的威望。 计算选民自产生的支持。选民能产生的支持正比于他的威望，比例系数会在 以后的运算约去，因此直接用选民的威望来表示选民能产生的支持。 抽样调查选民根据各个竞选人对他影响的大小按比例进行分配他的支持。一 个抽样调查选民可能受到多个竞选人的影响，选民要根据竞选人对他影响的大小 按比例分配他的支持。抽样调查选民k ，分配给竞选人的支持为 = 孚昂 g 9 ) 其中墨q 表示抽样调查选民巧对竞选人q 的支持。例如，全局抽样调查选民 广东工业大学工学硕士学位论文 k 受到竞选人c l 、c 2 和g 的影响，他能产生的支持& 要分配给竞选人c l ，c 2 rq = 警旦乇q = 粤乇屯g = 号生乇 和b ，分别为 1 k 、 1 k 和 4 ；局部抽样调 查选民嵋，：受到竞选人c l 和c 2 的影响，他能产生的支持& ；要分配给竞选人c 1 和 别为鲁气和& 雨2 等气俐恻分骥惴黼 选民对竞选人的支持。 计算竞选人获得的总支持。一个竞选人可能得到多个抽样调查选民的支持， 竞选人获得的总支持为 2 其中表示竞选人c i 获得的总支持，求和对所有对竞选人c l 的支持。例如， 竞选人q 可以得到全局抽样调查选民巧、巧、k 、巧和局部抽样调查选 民、巧，：、巧j 、巧，、屹j ，的支持，竞选人c l 获得的总支持 2 黾q + 屯q + c i + 吒q + 屯g + & ，c l + & 矗+ & 五+ & 局+ 同样，可以计算出其他竞选人获得的总支持和屯。 计算抽样调查选民对竞选人的贡献。抽样调查选民对竞选人的贡献是某个选 民对一个竞选人的支持占该竞选人的总支持的比例，由下式计算 鲁 叫。， 第二章竞选算法 其中，蛾q 表示抽样调查选民巧对竞选人q 贡献。例如，全局抽样调查选 民列竞选人g 的贡献为 钱q = 誓 一 屯q = = _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ - _ _ - _ _ _ _ _ ；_ _ _ _ - i - _ 。_ _ _ - _ _ _ _ - - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ i _ - & q + 屯g + q + 屯c i + 强c l + 而+ + & 扣+ 屯q 同样可以计算出所有抽样调查选民对所有竞选人的支持的贡献。 计算竞选人的支持萤d 。抽样调查选民对竞选人的贡献就是引导竞选人向着 该抽样调查选民所在方向移动的权重。抽样调查选民对某一竞选人的贡献与该抽 样调查选民的位置坐标相乘后求和，计算出个新的位置坐标，将它称为该竞选 人的抽样调查支持萤b ，即 琵= 其中，4c j 表示竞选人的抽样调查支持重心。例如，竞选人的支持萤d 为 噶2 绒q 飞+ 线q 电+ q k + 哦q + 鲅q + 钱一+ 钆q + + + 。 竞选人的支持萤心是通过抽样调查获得的与竞选人较近的、具有较高威望的 抽样调查选民位置，因此竞选人的下步的竞选地点应该就是支持重心的位置。 如此循环直至搜索最优解为止。 在计算过程中，为了加快搜索速度和跳出局部最优解，比较抽样调查选民的 威望与竞选人的威望，如果抽样调查选民的威望高于竞选人的威望，高威望抽样 调查选民将参选而成为竞选人，而低威望竞选人被淘汰。 广东工业大学工学硕士学位论文 2 4 竞选算法的计算流程 竞选算法的计算流程如下： 0 设置算法的参数； 1 生成竞选人的初始位置： 2 计算初始竞选人的威望； 3 计算竞选人的影响范围： 4 生成全局和局部调查选民样本： 5 计算抽样调查选民的威望 6 计算竞选人与调查选民之间的距离； 7 计算竞选人对调查选民的影响： 8 计算调查选民受到的总影响； 9 分配调查选民对竞选人的支持： 1 0 计算竞选人获得的总支持； l l 计算调查选民对竞选人的贡献： 1 2 计算竞选人的支持重心，作为竞选人的下位置； 1 3 计算竞选人在新位置的威望； 1 4 比较全局抽样调查选民与竞选人的威望： 1 5 判断是否满足要求，否则返回步骤3 ，进行下一循环的计算。 2 5 竞选算法的检验 现使用遗传算法的测试函数对竞选算法进行验算，以证明竞选算法是否可行。 1 ) f 1i 磁( s p h c r ef u r o r ) m i n 石( x ) = # 。1 g 1 2 ) 其中，薯【- 5 1 2 ，s 1 2 ，i = l 2 ，n 。 f 1 函数是普通的平方和函数，具有一个最小值在，- - ( o , o , ，o ) ，此时 第二章竞选算法 厂f ) = o 。 在计算中取以= 4 ，竞选人个数为4 ，局部抽样调查选民数为3 ，全局抽样调 查选民数为6 ，局部抽样的正态分布的方差为o 0 2 ，距离定义为位置之差的绝对 值。 ( c ) 匿2 2 f 1 解和目标值收敛过程 蛳2 - 2 啦c c 师哪脚西f l 图2 - 2 ( a ) 、c o ) 、( c ) 、( 骱别为五，而，毛，的收敛过程，从图中可以看 到它们的值速度收敛到数值0 。 ( 2 ) f 2 函数( i t o s 朗撇f i i r l c t i o n ) 广东工业大学工学硕士学位论文 椭，( 工) = 1 0 0 + 1 - 薯) 2 + ( 而一1 ) 2 8 1 ( 2 1 3 ) 其中，五卜2 0 4 8 ，2 0 4 8 1 ，i = l ，2 ，。 f 2 函数是非凸的单峰函数，其极值呈病态难以极小化，全局最小值在 ，= ( 1 ，1 ，1 ) ，此时八x ) = o 。 在计算中取雄。2 ，竞选人个数为4 ，局部抽样调查选民数为3 ，全局抽样调 查选民数为1 2 ，局部抽样的正态分布的方差为0 0 1 2 ，距离定义为位置之差的绝 对值。 ( c ) 图2 - 3f 2 解和目标值收敛过程 图2 - 3 ( a ) 、c o ) 、( c ) 分别为薯，恐，毛，五的收墩过程，从图中可以看到它 们的值速度收敛到数值1 。 2 6 小结 本章介绍了竞选算法的基本思想，基本原理和计算的步骤。竞选算法和遗传 算法有很多共同之处。两者都随机初始化种群，而且都使用评估值来评价系统， 而且都根据评估值来进行一定的随机搜索。竞选算法与遗传算法的信息共享机制 是很不同的。在遗传算法中，染色体互相共享信息，所以整个种群的移动是比较 均匀的向最优区域移动。在竞选算法中，距离当前解距离近的信息以大权重传给 下一循环，属于集中式的信息流动，整个搜索更新过程可能以更快的速度收敛。 通过使