（计算机应用技术专业论文）群智能优化算法研究及其应用.pdf

群智能优化算法研究及其应用 摘要 优化算法是一门以数学为基础的、用来求解各种工程问题最优解的计算 机应用技术。优化算法是当前计算机领域的研究热点之一。作为优化算法的 重要内容之一的群智能优化算法越来越受到界内学者的关注，并已成为相关 学科的热点研究内容。因而作者进行群智能优化算法方面的研究具有一定的 现实意义。 本研究的主要内容和主要成果如下： ( 1 ) 第一章概述了群智能优化算法研究的目的、介绍了群智能优化算法的 研究现状。最后给出本硕士论文的组织结构和研究内容。 ( 2 ) 第二章提出了基于模拟渔夫捕鱼行为习惯的群智能优化算法一 种模拟渔夫捕鱼的寻优算法( s f o a ) 。该算法采用移动搜索、收缩搜索和加速 搜索三种搜索技术。初始时在搜索域中随机分布有若干个点，每个点看作一 个“渔夫”，每个“渔夫”通过移动、收缩和加速三种搜索方式在搜索空间中 独立开展寻优活动，以搜寻全局的最优解或最优点。 ( 3 ) 第三章提出了一种基于人工鱼群算法的机器人加工路径规划新方法。 该算法搜索效率高，能在较短时间内求得最优解，可满足机器人加工的实时 性要求。 ( 4 ) 第四章提出了一种a f s a 与s f o a 相结合的混合算法。该算法在优化初 期使用a f s a 搜索局部最优域，而在优化后期则使用s f o a 在优化前期所初步 确定的局部最优域中搜索最优解。该算法具有优化精度高、收敛速度快的特 点。 关键词：群智能优化算法模拟渔夫捕鱼算法人工鱼群算法机器人加 工路径规划 a b s t r a c t t h er e s e a r c ho ft h es w a r mi 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 ma n di t sa p p l i c a t i o n s a b s t r a c t o p t i m i z a t i o na l g o r i t h mi s ac o m p u t e ra p p li c a t i o nt e c h n o l o g yb a s e do n m a t h e m a t i c sa n db e i n gu s e dt os o l v et h eo p t i m a ls o l u t i o no fv a r i e t ye n g i n e e r i n g p r o b l e m s o p t i m i z a t i o na l g o r i t h mh a sb e e no n eo f a s t u d y i n gf o c u si nc o m p u t e r d o m a i n t h es w a r mi 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 ，a sb e i n go n eo fa n i m p o r t a n tp o r t i o no ft h eo p t i m i z a t i o na l g o r i t h m s ，h a sd r a w nt h es c h o l a r s a t t e n t i o ni nt h ec o m p u t e ra r e a s s om a k i n gas t u d yo nt h ea s p e c to ft h es w a r m i n t e l l i g e n to p t i m i z a t i o na l g o r i t h mh a sap r a c t i c a ls i g n i f i c a n c e t h em a i nw o r ka n dt h ec o r eo ft h i sd i s s e r t a t i o na r es u m m a r i z e da s f o l l o w i n g s ： ( 1 ) i nt h ec h a p t e r1 ，t h ep u r p o s ea n dt h es i g n i f i c a n c eo ft h er e s e a r c ho nt h e s w a r mi n t e l l i g e n to p t i m i z a t i o na l g o r i t h ma r es u m m a r i z e d ，a n dt h es i t u a t i o no f t h es w a r mi n t e l l i g e n to p t i m i z a t i o na l g o r i t h mi sd i s c u s s e d f i n a l l yt h es t r u c t u r e a n dt h ec o n t e n t so ft h i sd i s s e r t a t i o na r eg i v e n ( 2 ) i nt h ec h a p t e r2 ，an o v e lo p t i m i z a t i o na l g o r i t h mb a s e do ns i m u l a t i n gt h e b e h a v i o ra n dt h eh a b i to ff i s h e r f i s h i n gi sp r e s e n t e d t h i sa l g o r i t h mu s e dt h r e e s e a r c ht e c h n o l o g i e sw h i c ha r ec a l l e dm o v i n gs e a r c h ，r e d u c i n gs e a r c ha n d s p e e d i n gs e a r c h i nt h eb e g i n n i n g ，s o m ep o i n t sa r er a n d o m l yd i s t r i b u t e do v e rt h e g r a b b l i n gd o m a i n ，a n de v e r yp o i n to ft h e mi sr e g a r d e da sa “f i s h e r t h e ne v e r y f i s h e r o ft h e mi su s e dt os e a r c h h i m s e l f o p t i m u mp o i n t so rg l o b a lo p t i m u m s o l u t i o nt h r o u g h h i s ”m o v i n gs e a r c h ，r e d u c i n gs e a r c ha n ds p e e d i n gs e a r c h i n d e p e n d e n t l y ( 3 ) i nt h ec h a p t e r3 ，t h ep a t h p l a n n i n g s c h e m eb a s e do na r t i f i c i a l f i s h - s w a r ma l g o r i t h mi s p r e s e n t e d t h i sa l g o r i t h mi s e f f e c t i v ea n di tc a n a c h i e v et h eo p t i m a ls o l u t i o no v e ras h o r tp e r i o do ft i m e s oi tc a nm e e tt h e r e q u i r e m e n to fp r o m p t n e s si nt h em a c h i n i n gp a t hp l a n n i n g ( 4 ) i nt h ec h a p t e r4 ，ah y b r i da l g o r i t h mc o m b i n i n ga f s aa n ds f o ai s p r e s e n t e d t h es t r a t e g yo ft h i sa l g o r i t h mi st h a tt h ea f s ai su s e dt os e a r c ht h e l o c a lo p t i m u md o m a i ni nt h eb e g i n n i n g so f o p t i m u mp r o c e d u r e ，a n dt h es f o a i sf i n a l l ym a d eu s eo fd e t e r m i n i n gt h eg l o b a lo p t i m i z a t i o ni nt h el o c a lo p t i m u m d o m a i nf o u n db ya f s a t h eh y b r i da l g o r i t h ms h o w sa l le f f i c i e n t q u a l i t yi n s o l v i n gg l o b a lo p t i m i z a t i o np r o b l e m s k e y w o r d s ：s w a r mi n t e l l i g e n c e ；o p t i m i z a t i o n a l g o r i t h m ；a no p t i m i z a t i o n a l g o r i t h mo ns i m u l a t i n gf i s h i n g ；a r t i f i c i a lf i s hs w a r ma l g o r i t h m ；m a c h i n i n gp a t h p l a n n i n go f r o b o t i i i 论文独创性声明 本人郑重声明：所提交的学位论文，是本人在导师的指导下，独立撰写 完成的。除文中已经注明引用的内容外，本论文不含其他个人或其他机构已 经发表或撰写过的研究成果，也没有剽窃、抄袭等违反学术道德规范的侵权 行为。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标 明。本人愿意承担由本声明而引起的法律责任。 研究生签名：陈蒸棠 日萁i j ：；o o q 年占月f 日 论文使用授权声明 本人完全了解广西民族大学有关保留、使用学位论文的规定。学校有权 保留并向国家有关部门或机构送交学位论文的复印件和电子文档，可以采用 影印、缩印或其他复制手段保存、汇编学位论文。除在保密期内的保密论文 外，允许学位论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。 研究生签名： 导师签名： 陈走荣 砂碧 -，j， 铲 ，d i | | | j 吁 1 1 研究背景和目的 1绪论 优化技术是一种以数学为基础的、用来求解各种工程问题最优解或满意解的计算机应 用技术。当前，优化技术已经在工业、农业、国防、工程、交通、金融、化工、能源、通 信等诸多领域得到了广泛地应用。如在工程设计中，如何选择参数，既能保证设计方案达 到设计要求，又能保证工程设计达到最优状态；在资源分配中，怎样分配有限的资源，使 分配方案既能满足各方面的基本要求，又能获得较好的经济效益等等，所有这些都涉及到 优化技术问题。总之，利用优化技术可提高经济效益、提高系统的效率、降低系统的能耗 等。因此，优化技术在国民经济建设中具有广泛的应用前景n 】。 随着现代经济的迅速发展，优化计算已经成为相关部门亟待解决的问题。然而，基于 严格机理模型所得到的优化命题，通常具有大规模、强约束、非线性、多极值、多目标等 特性，而许多经典的优化算法却又无法解决这一问题。因而，寻求一种适合于大规模问题 的优化算法已经成为许多科技工作者急需解决的问题，也是从事计算机研究的学者们研究 的重点和主要研究方向之一。 人类在认知自然的实践中得到了启示：生物体和自然生态系统可通过自身的演化，使 许多高度复杂的优化问题得到完美地解决。作为生物界中最高级的动物人类，理所当 然地有能力模拟自然生态系统机制来求解复杂的优化问题。正是在这样的背景下，最近几 年，人们提出了与经典的数学规划原理截然不同的、通过模拟自然生态系统机制来求解复 杂优化问题的群智能优化算法n 吲。这为解决采用传统优化技术所无法解决的优化问题提供 了技术保证。群智能优化算法属于随机搜索算法，它具有较强的并行性，鲁棒性也比较好。 正因如此，群智能优化算法越来越受到人们的重视n 侧，并在许多领域得到了广泛的应用。 作者进行群智能优化算法的研究也正是基于这一背景而展开的。 1 2 研究现状 近几十年来，国内外学者通过研究或模仿群体生活的昆虫、动物的社会行为特征，提 出了一系列模拟生物系统中群体生活习性的群智能优化算法。其中较具代表性的群智能优 化算法主要有蚁群算法刮、微粒群优化算法n0 1 、蜂群算法n 2 1 3 1 、人工鱼群算法n 4 1 、混合 蛙跳算法n 引、人口迁移算法n6 1 7 1 等。1 9 9 1 年，意大利学者d o r i g om 等人通过模拟蚂蚁的 群体行为提出了蚁群算法阳刊( a n tc o l o n ya l g o r i t h m ，a c a ) ，并用于解决复杂的组合优化 问题。在静态组合优化中蚁群算法用来解决旅行商( t s p ) 问题、二次分配问题( q a p ) 、车间 作业调度问题( j s p ) 、车辆路线问题( v r p ) 等。在动态组合优化中，蚁群算法可应用于解决 路由问题、电力系统故障诊断、模糊系统、数据挖掘、聚类分析，以及设计无限响应数字 滤波器。蚁群算法在系统辨识、图像处理以及化学工程等方面也进行了相关的应用研究。 1 9 9 5 年，k e n n e d y 和e b e r h a r t 提出了微粒群优化算法n0 1 ( p a r t i c l es w a r mo p t i m i z a t i o n ， p s o ) 。微粒群算法可应用于非线性复杂约束规划、作业调度优化、经济分配和数据挖掘等。 在工程应用方面，微粒群算法在化学工程中用于化学过程的动态分析；在生物工程中用于 蛋白质序列h m m s 模型训练；环境工程中用于大气中臭氧层的预测；农业工程中的温室环 境温度预测控制以及用于光纤通信、电力系统优化和控制参数优化等。1 9 9 5 年，t h e r a u l a z 提出了蜜蜂通过与环境之间的信息交互实现安排工作的模型，即蜂群算法n 2 1 3 1 ( w a s p c o l o n ya l g o r i t h m ，w c a ) 。该算法可用于解决作业车间调度问题等。2 0 0 2 年，李晓磊等人 通过观察鱼类在水中游弋觅食的行为特点提出人工鱼群算法n 钔( a r t i f i c i a lf i s h - s w a r m a l g o r i t h m ，a f s a ) 。人工鱼群算法目前已用于组合优化、参数估计、p i d 控制器的参数整 定、神经网络优化等。2 0 0 3 年，e u s u f f mm 从群体青蛙的觅食特性中得到启发提出混合蛙 跳算法u 副( s h u f f l e df r o gl e a p i n ga l g o r i t h m ，s f l a ) 。混合蛙跳算法具有全局优化与局 部细致搜索的优点，可以用来优化连续问题和离散问题。可用于地下水管网优化设计、非 线性函数优化、旅行商问题、下料问题、齿轮问题等。2 0 0 3 年，周永华等人模拟人口迁移 机制提出人口迁移算法口6 ”1 ( p o p u l a t i o nm i g r a t i o na l g o r i t h m ，p m a ) 等等。 以上这些算法通常具有不依赖于函数性态、适用范围广和鲁棒性强等优点，但也存在 诸如收敛速度慢、早熟、优化结果不够理想等缺点。虽然国内外学者们提出了许多改进方 法或改进策略，但还不是很完善，还有待进一步改进。 1 3 主要研究内容 第一章简单介绍了本课题研究的意义和背景，并介绍了国内外相关研究的现状。 第二章提出了新的群智能算法一种模拟渔夫捕鱼的寻优算法。首先介绍了算法的 基本原理，其次给出了渔夫捕鱼模型及渔夫捕鱼的三种基本行为描述，最后给出该算法的 实现步骤以及算法分析和实验仿真。 第三章进行了人工鱼群算法用于解决机器人加工路径规划问题的研究：首先给出机器 人加工路径规划问题的简单描述，然后给出将人工鱼算法应用于解决该问题时的具体方 法。 第四章提出了基于人工鱼与捕鱼算法相结合的混合优化方法：首先利用a f s a 算法搜 索目标空间中的局部最优域，然后再利用s f o a 算法在前期确定的局部最优域中搜寻精确 解或最优解。 2 最后总结全文，并指出今后的研究方向。 1 4 本章小结 本章主要介绍了群智能优化算法产生的背景和研究现状，说明了进行群智能优化算法 研究的价值和意义，最后对本研究的组织结构及研究内容进行了概述。 2 1引言 2 一种模拟渔夫捕鱼的寻优算法 目前，不少的学者已经开展了基于模拟生物的某些行为或习性而提出的具有智能特征 的优化算法的研究，并取得了显著的成功。意大利学者d o r i g om 等人1 通过模拟蚂蚁的 群体行为提出了蚁群算法，使之能用来求解复杂的组合优化问题。美国数学家j o h n h o ll a n d 噜们在2 0 世纪6 0 年代提出了模拟大自然生物进化的遗传算法，它是一种随机搜索 的寻优算法。k e n n e d y 和e b e r h a r t n0 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 ) 。李晓磊等人n 们则基于模拟鱼群的游弋和觅食等行为而提出了 人工鱼群算法( a f s a ) 。总之，基于模仿生物的行为特征而提出的智能算法的研究，越来越 受到计算机界内学者的重视。 本章通过对渔夫撒网捕鱼的行为习惯的观察而提出了一种模仿渔夫捕鱼行为或习惯 的寻优算法，即一种模拟渔夫捕鱼的寻优算法( a no p t i m i z a t i o na l g o r i t h mo ns i m u l a t i n g f is h i n g ，s f o a ) 。 2 2 采用的策略和方法 2 2 1基本策略 渔夫在江面上撒网捕鱼的行为习惯：刚开始时很随意地选择江面上一点撤下鱼网，然 后又在当前下网点的前后左右再各撒一次网。另外，渔夫撒网捕鱼，总希望每次撒网能捕 捉到尽可能多的鱼。而水中鱼的密度越大，每次撒网能捕捉到的鱼也就越多。因而，渔夫 选择在何处撒网，是基于如下准则的：( 1 ) 哪处鱼的密度大，就在哪处下网；( 2 ) 何处鱼的 密度比较大，就移到何处去撒网。( 3 ) 若当前位置没有鱼或鱼的密度比较小，其将加速离 开当前作业区而另选地点。( 4 ) 如果发现当前自己所处的位置鱼的密度比较大，则采用收 缩撒网范围的办法，希望能“一网打尽。( 5 ) 相互之间避免相碰。 本章假设渔夫事先对作业区d 中鱼的分布情况一无所知，且作业区d 中鱼的分布情况 ( 即分布密度) 不因渔夫在d 中打鱼而发生改变。本章基于渔夫捕鱼行为习惯而提出了一种 模仿渔夫捕鱼行为特征的搜索方法：设在渔夫捕鱼作业区d ( 即搜索空间) 中随机分布有一 群渔夫，他们各自在d 中随机选取一点撒下鱼网。然后各个渔夫又在自己当前位置的前后 左右再各撒下一次网。各个渔夫依据自己所处的环境独立选择移动搜索、收缩搜索和加速 4 搜索。综上所述，本章提出的搜索方法主要采用移动搜索、收缩搜索和加速搜索三种方法。 设d = q 3 2 ”见为有限闭区域，x = ( 而，x 2 ，矗) d 为状态，寥，d ，= 【口，6 ，】， j = 1 ，2 ，刀，f ( x ) 为d 上连续的目标函数( 即水中鱼的密度度量函数) 。渔夫的目标就是 寻找厂( x ) 在d 中的最优点或最优值。 设初始时在d 中随机分布有七个渔夫，他们在d 中随机地选择一点下鱼网。设第f 渔夫 初始位置和初次下鱼网点为r = ( 而，n ，：n ，。f ) ) ( 我们将下鱼网点抽象为无体积的点， 用以表征问题的候选解) 。i 渔夫在初始位置只“的前后上下左右再各撤下鱼网一次，从而 得到其以点只o 为“中心”的撒下鱼网点集： q o = 。= ( t l ( 0 , t 2 n ，) x o ，n l j ( - ) x o ，n ，x o ，+ ，+ ，j = 1 , 2 ，栉) 。 其中x o j 。q ，一o ，+ o ，x o j n 一一q ，x o 订+ + q 。并且当x o = 哆时， 取卜= o 且什 q x o o ；当“= 乃时，取+ = o 且卜 x o j “一巳；当x o o q 且嘞“屯 时，则取，一 0 。第一个渔夫在点忍”的前后上下左右再各撒 下鱼网一次，得到一个撒下鱼网点集为 q o ( 1 ) = ( 1 - l ，2 - i ) ，( 1 - l ，2 ) ，( 1 - l ，2 + ，) ，( 1 , 2 一，) ，( 1 ，2 ) ，( 1 ，2 + ，) ，( 1 + ，2 一，) ，( 1 + ，2 ) ，( 1 + ，2 + ，) 。 图2 1 移动搜索示意图 5 x o 1 = ( 1 + ，2 + 1 ) 且f ( x o 1 ) ：z m 。a 甜x 。( x ) f ( p o 1 ) ，即k 1 处鱼的密度比咒 处高。 此时，第一位渔夫选择从位置圪”移到新位置暑1 = x o ，并以只”为新的“中心 ，重复前 面的步骤，以搜寻比点墨1 处鱼的密度还要高的点罡，。 ( 二) 收缩搜索。设经过若干次位置变动后，i 渔夫位于己。= ( 。n ，：n ，。f ) ) ( ，l = 0 ，i 1 一，m ，m = o 表示渔夫位于初始位置) ，黼= m ，。a 蟛x ，f ( x ) ( 己) ，其中 q 。= z 二。= ( ”，f 2 n ，；厶。) i ， n 一，n ，+ ，+ ) ，j = l ，2 ，栉) ，f = 1 ，2 ，k 。 则i 渔夫继续停在已o 处，并在当前位置己o ) 的前后上下左右再各撒下鱼网一次，这时 得到关于点。的另一个下鱼网点集为 q 。+ l = 以+ l 。= ( ，) 。 n 一一，n ，d + 口+ ) ，j = 1 ，2 ，疗) ， 其中；( 一= 口，；( + = 耐，”，0 m ：，；a x 瞄f ( x 2 ) ，则该渔夫选择继续停在位置忍2 处；若 f ( p o 2 ) x m 。a 嘣x ：，f ( x 2 ) = f ( x o 2 ) ，则该渔夫选择从位置晶2 移到新位置鼻2 = x o 2 、，并以露2 为新的“中心 ，重复前面的步骤或方法，进一步搜寻比点尼2 处鱼的密度更高的点层2 ，。 6 ( 三) 加速搜索。经过若干次位置变动后，i 渔夫位于点e d = ( ? ，：，x 。( o ) ，且 x m 。a 甜x f ( x ( 己。) ，厂( e ) 一m a x f ( x ) x q ：，x 曩。 ( 昂7 ) 且k 昂n ，扛1 ，2 ，k ，f 渔夫则从当前位置尼移动 到新位置暑。) = x o ( “，并以暑f ) 为新的“中心”，重复f j i 面的步骤或方法，以寻找鱼的密度比 点只，) 还要高的点最n 。设经过m 次操作之后( 其中m = 0 , i ，m ，m = o 表示渔夫位于初始 位置) ，七个渔夫的位置分别为己o = ( ，n ，：n ，) ，f = 1 , 2 ，k 。此时，i 渔夫在当前 位置艺o 的前后上下左右再撤下鱼网各一次，得到一个下网点集为 q 。n = x = ( ，t 2 ( 0 , - - , ) l 矿 n l 一，n ，。+ + ) ，j = 1 ，2 ，疗) 。 若f ( x m ) 2x m 。a 嘴x ，f ( x ) 厂( 乞，即f 渔夫找到比点已更优的点巴+ - n = 以n ，这时f 渔夫就从点己d 移到点乞+ 。n ，并按前面的方法继续在d 中展开搜索；若 厂( 己) 刀菇，f ( x ) ，则f 渔夫继续停在点己处，并在圪的前后上下左右再各撒下鱼网 一次，这时得到关于点名。的又一个下鱼网点集： q n 州= 以+ l = ( t l ( o , 2 n ，乙。) 10 。 n e ，n ，+ c + ，= 1 ，2 ，力 。 其中c 卜k 鸭，e + ) _ 口t + ，o a l ，口为收缩系数；若在己o 处连续进行收缩操作 次数达到了设定的阈值，但厂( 乞刀菇，f ( x “) 且( 巴 ，则停机并输出公告板记录。否则i 卜l ，转s t e p 2 。 8 o u t p u t ：最优解x + ，最优值匕。 2 3 性能分析 为了考察s f o a 算法的有效性，本章将s f o a 算法与c p s o 算法n 引、p s o 算法n 钔和g a 算 法乜们进行算法性能对比和分析。 2 3 1实验环境 实验选用操作系统为：w in d o w sx ph o m es p 3 ：硬件为：i n t e lc o r ed u et 2 0 5 0 、2 g b 内 存、s e a g a t ep a t a5 4 0 0 转8 0 g b 硬盘的p c 机；仿真软件为m a t l a b 2 0 0 7 a 。 2 3 2 测试函数 本章采用四个著名的b e n c h m a r k 问题n 羽，用于算法性能实验测试。具体函数如下： ( 1 ) g p - g o l d s t e i n - p r i c e ( 刀= 2 ) 岛( x ) = 1 + ( 五+ 恐+ 1 ，一1 4 五+ 3 可- 1 4 x 2 + 6 五屯+ 3 x 2 2 ) 】，一2 工。2 ，2 【3 0 + ( 2 五一3 x 2 ) 2 ( 1 8 3 2 + 1 2 2 + 4 8 艺一3 6 x , x ：+ 2 7 x 2 2 ) 】 该函数的全局最小值为3 ，最优点为( o ，一1 ) ，可行域内有4 个局部极小点。 ( 2 ) b r b r a n i n ( 刀= 2 ) 厶( x ) = ( 恐一毫当2 + 昙五一6 ) 2 + 1 0 ( 1 - 去) c 。s 五+ 1 。，五卜5 ，l 。 ，毛 。，1 5 】 该函数的全局最小值为0 3 9 8 ，共有三个最优点( q 1 4 2 ，1 2 2 7 5 ) 、( 3 1 4 2 ，2 2 7 5 ) 、 ( 9 4 2 5 ，2 4 2 5 ) 。 ( 3 ) r a r a s t r i g i n ( n = 2 ) 0 ( x ) = 五2 + x 2 2 一c o s l 8 x 1 一c o s l 8 x 2 ，一1 薯1 ，i = 1 ，2 该函数的全局最小值为- 2 ，最优点为( o ，o ) ，在可行域内大概有5 0 个局部极小点。 ( 4 ) s h - s h u b e r ( n = 2 ) 向( x ) = c o s ( + 1 ) x l + f ) c o s ( + 1 ) x 2 + f 】 ，- l o x l ，j c 2 l o 该函数的最小值为一1 8 6 7 3 0 9 ，有1 8 个全局最优点，同时有7 6 0 左右个局部极小点。 2 3 3 算法参数设置 s f o a 算法参数设置如下表2 1 。其中迭代次数最大阈值均取固定值n = 1 2 0 次，渔夫总 人数k = 1 0 人，连续收缩操作次数最大阈值c = 5 次，公告板未更新次数最大阈值u = 4 次，三 为步长，口为收缩系数。 9 表2 1s f o a 算法参数设置表 目标函数岛( 工)厶( x )屯( j )矗( 工) n = 1 2 0 ，k = 1 0 ，c = 5 ，n = 1 2 0 ，k = 1 0 。c = 5 。n = 1 2 0 。k = 1 0 ，c = 5 ，n = 1 2 0 。k = 1 0 ，c = 5 。 参数设置 u = 4 ，= o 6 ，口= 0 0 3u = 4 ，l = 0 5 口= 0 0 3u = 4 ，工= 0 3 ，口= 0 0 2u = 4 ，l = 0 3 ，口= o 0 2 而c p s 0 算法、p s o 算法及g a 算法中的迭代次数均设为2 0 0 0 次，其余参数的设置详细情 况见文献 1 8 。 2 3 4 评价指标 为了便于对比分析s f o a 算法与c p s o 算法n8 1 、p s o 算法n 们及g a 算法啪3 性能的优劣，我们 依据文献 1 8 中有关以上四个著名的b e n c h m a r k 问题的评价标准体系，选择以下四个指标： 平均最小函数值、标准偏差、成功率、平均有效评价次数，作为本次算法性能对比的评价 指标。若每次运行的最终结果在全局最优值的3 5 范围内，则称该次运行为“成功运行”， 并将本次运行所用的最少评价次数记录下来。成功率s r ( s u c c e e dr a t i o ) 和平均有效评价次 数a v e n ( a v e r a g ev a l i de v a l u a t i o nn u m b e r ) 定义如下n8 。： 艘：丝1 0 0 ( 2 1 ) n 1 a v e n ：二y r i ( 2 2 ) v 乞 其中为算法独立运行的总次数，v 为次独立运行中成功运行的次数，n i 为第i 次 成功运行所用的最少函数评价次数。 2 3 5 实验结果 由于c p s o 算法、p s o 算法、g a 算法和s f o a 算法都是随机搜索算法。为了避免随机性 对实验结果的影响，测试采取如下办法：各算法均独立运行5 0 次，以这5 0 次运行结果数据 的平均值作为该算法的最终测试结果。运行所得实验数据如下表2 2 和表2 3 ： 表2 2 平均最小函数值和标准偏差 目标函数 s f o ac p s o 1 8 1 p s o 1 8 1g a 五，( x ) 3 0 0 0 0 6 7 4 3 1 e - 2 8 3 0 0 0 0 5 0 2 5 l e 1 54 6 2 0 2 1 1 4 5 5 43 1 4 7 l 0 9 8 6 0 厶。( 工) 0 3 9 7 9 土2 16 5 5 e 3 0 0 3 9 7 9 3 3 6 4 5 e 1 60 4 9 6 0 0 3 7 0 30 4 0 2 l 0 0 1 5 3 k ( j ) - 2 0 0 0 0 01 9 9 4 0 0 0 2 4 8 一1 9 7 0 2 0 0 3 6 6一1 9 6 4 5 o 0 3 9 3 厶( x ) - 1 8 6 7 3 0 9 4 - 9 4 7 9 2 e 一2 7一1 8 6 7 2 7 4 0 0 2 1 8 一1 8 0 3 2 6 5 1 0 1 7 1 8一1 8 2 1 8 4 0 5 3 5 9 9 表2 3s r 和a v e n 比较 s f o ac p s o 1 8 1p s o 1 8 1 g a 【1 8 】 目标函数 s ra v e ns ra v e ns r a v e ns ra ：v e n 厶( x ) l o o5 7l o o1 9 29 8 1 3 9 79 85 3 6 厶( j ) 1 0 06 ll o o1 5 4 9 47 4 39 21 6 8 2 0 ( x ) l o o 7 29 86 5 31 0 01 1 6 08 4 2 3 8 矗( j ) 1 0 07 31 0 03 6 09 81 3 3 79 8 1 5 1 6 平均值 l o o6 6 9 9 5 3 4 09 7 51 1 5 9 9 39 9 3 1 0 其中，s f o a 算法的平均耗时( 秒) ：岛( x ) 为0 3 9 4 3 7 5 0 ，( x ) 为0 2 4 6 5 6 2 5 ，厶( 工) 为 0 6 2 0 3 1 2 5 ，届( x ) 为0 3 0 6 2 5 0 0 。而得到的s f o a 算法的迭代次数与进化曲线仿真图如图2 3 至图2 6 ： 选代次教 图2 3f 。a x ) 迭代次数一进化曲线图 选代次数 图2 5 厶( j ) 迭代次数一进化曲线图 选代次数 图2 4 厶( 工) 迭代次数一进化曲线图 选代次数 图2 6 矗( 工) 迭代次数一进化曲线图 而c p s o 、p s o 、g a 算法的迭代次数与进化曲线仿真图 1 8 如图2 7 至图2 1 0 所示： 迭代次数 图2 7 厶( x ) 迭代次数一进化曲线图 图2 8 ，腑( j ) 迭代次数一进化曲线图 2 3 6 对比分析 从表2 2 和表2 3 中的相关实验结果、图2 3 至图2 1 0 的迭代次数一进化曲线图，以 及迭代次数最大阈值( s f o a 迭代次数最大阈值是1 2 0 次，而c p s o 、p s o 及g a 的迭代次数 均设为2 0 0 0 次n 8 1 ) 中，可以得出：( 1 ) s f o a 算法的搜索质量均比c p s o 算法、p s o 算法和 g a 算法好得多。( 2 ) s f o a 算法效率高、稳定性强。s f o a 算法运行成功率为1 0 0 ，搜索到 全局最优值的精度均比c p s o 算法、p s o 算法和g a 算法高，标准差也是最小的。因而s f o a 算法效率高于c p s o 算法、p s o 算法和g a 算法。( 3 ) s f o a 算法收敛速度快。从平均有效评 价次数a v e n 和迭代次数一进化曲线图中可以看出，s f o a 算法的收敛速度均比c p s o 算法、 p s o 算法和g a 算法快得多。因而，我们得出结论：s f o a 算法的性能均比c p s o 算法、p s o 算法和g a 算法的性能好。 2 4 本章小结 本章提出了一种模拟渔夫捕鱼行为习惯的搜索算法。该算法具有搜索速度快、求解精 度高和不易陷入局部极值的优点，具有较好的全局搜索能力。实验结果表明，s f o a 算法对 于解决复杂函数的优化问题是非常有效的和可行的。 1 2 3 基于人工鱼群算法的机器人加工路径规划 3 1 引言 移动机器人加工路径规划是工业加工过程中，经常会涉及到的问题，它是一种高度复 杂的非线性优化问题，传统的优化方法有梯度法、枚举法、a 等图搜索法、人工势场法等。 其中梯度法易陷入局部最小点；图搜索法、枚举法不能用于高维的优化问题；势场法则存 在丢失解的部分有用信息的可能。此外，传统的优化方法在机器人加工路径规划这类复杂 非线性优化问题中缺乏足够的鲁棒性。”。虽然人们用改进的遗传算法来解决这类问题，但 文献 2 2 中只是从单一的点出发，去寻找最优的加工路径，并不是真正达到全局最优。 人工鱼群算法“”2 ”是一种基于模拟鱼群行为的随机搜索优化算法，通过鱼群中各个 体的局部寻优达到全局最优的目的。该算法最大的优势在于具有克服局部极值、取得全局 极值的能力。 本章将人工鱼群算法引入机器人) j n t 路径规划中，设计出了一种基于人工鱼群算法的 机器人加工路径规划算法，并与其它算法进行了仿真比较，实现了真正意义下的全局最优 加工路径。 32 机器人加工路径规划问题 针对机器人抛光路径规划问题，机器人工作环境1 如图3 1 所示，在带有局部划痕的 工件上工作，即以最短的路径将所有的划痕进行抛光处理。将图像经过二值化处理和网格 化处理后，分别得到二值化图( 图32 ) 和网格图( 图3 3 ) 。”个划痕分别对应一个不同 的目标起点和终点即： 日，斗且。，n ，_ n 。，一，几_ + n ，“一p 。 ，f _ l ，2 ， 其中，儿，“分别为第i 个划痕的起点和终点坐标值，因为划瘦的长度已经固定，“，n 之间的路径长度d ( “，“) 为回定值。 圈3 1 有划痕的灰度图 图32 二值化后的图像 图33 呵格化后的图像 t 3 机器人抛光路径规划问题可描述为：搜索整数集合= 1 ，2 ，以 ( n 的元素表示门个划 痕的编号) 的一个排列三( ) = 厶，f 2 ，厶) ( f f n ，表示第i 条划痕) ，使得与此排列对应 的抛光路径长度最短。其中 表示工作环境中有刀个划痕需要加工。l ( n ) 表示，z 个划痕的 一个随机排列。 3 3 求解机器人加工路径规划问题的人工鱼群算法 人工鱼群算法是一种新的基于动物行为的寻求全局最优的计算模式，通过模拟鱼群在 觅食时相互尾随到达食物点，依靠集体智慧聚集成群躲避敌害。下面对鱼群初始化、适应 度函数、人工鱼行为等进行具体的描述。 3 3 1人工鱼群初始化 第k 条人工鱼个体状态可表示为向量鼍= ( 五，x 2 ，矗) ，每条人工鱼状态就是一个潜在 的解。将以= ( ，x 2 ，) 代入到适应度函数中就可以计算出相应的食物浓度值。根据浓度 值的大小来衡量丘的优劣。 针对机器人加工路径规划问题，初始化的顺序为：先随机产生各个划痕加工的先后顺 序，然后随机生成加工各个划痕的两个端点的先后顺序，算作一条人工鱼。每一条人工鱼 表示为： 以：a j 盼一p i p n ，1 七脚，f ：1 2 1 一，刀 1 一 1 ) ) ，“， l 一，。一，l ，t 2 ， 其中，k 表示第k 条人工鱼；只表示第f 个划痕，鼠，p z ，p i ，见表示，2 个划痕的随机排 列；与只对应，表示划痕只两端加工的先后顺序，t 的取值为0 和1 ，分别表示加工的顺 序和逆序。依此，随机生成m 条人工鱼。 3 3 2 适应度函数的确定 算法的目的是求抛光路径三= d ( b ，竹) 的最小值，为便于仿真比较，这里设定适应 度函数为： ( 3 - 1 ) 式中，d ( 凤，玩) 是两个划痕之间的路径长度，是固定不变的值。此时，求解抛光路径三 的最小值就转化为求适应度函数( x ) 的最大值。 3 3 3 相关定义 在人工鱼个体模型的构造中，人工鱼的距离、邻域和中一t l , 位置这几个概念比较重要，