所在的位置：数据库 >> 学习资料 >> 机器人算法专题介绍3

机器人算法专题介绍3

DECACO算法的设计DECACO算法均能较好较快地完成规划任务，优化精度高、搜索速度快、算法的鲁棒性较强、算法的复杂度适中，充分证明了该算法在解决移动机器人路径规划问题上的有效性。1.信息素更新策略本文设计的DECACO算法采用具有信息素下限的ACOgb,min算法，不过更新策略有所不同。DorigoM提出的ACOgb,min算法仅对最优蚂蚁进行更新，如果仅采用全局最优蚂蚁进行信息素更新，在算法初期，算法的收敛速度较快，但陷入局部最优的可能性也随之增加;如果仅对当前最优蚂蚁进行更新，算法能保持较好的多样性，但收敛速度又不够理想。因此，我们试想，能否将这两种更新策略以一种合理的方式进行结合，得到更好的效果呢?本章正是致力于寻求这样一种交替策略，在种群的进化迭代过程中交替更新当前最优蚂蚁和全局最优蚂蚁的信息素，以改进算法的性能。由FWACO算法的分析可知，种群迭代过程大致分为两个阶段:算法未停滞阶段和算法停滞阶段。在算法未停滞阶段，为了确保算法的收敛速度，全局最优蚂蚁更新的概率应大些;而随着算法进入停滞阶段，应逐步加大当前最优蚂蚁的更新概率，以确保算法的多样性，避免算法陷入局部最优。这是一种概率型的交替策略，每一阶段都有二者的共同作用，故能同时兼顾算法的收敛速度和多样性。此公式的意义是:在停滞门限以前，以固定概率q0更新当前最优蚂蚁的信息素;当达到停滞门限以后，可以认定算法已陷入局部最优，此时为使种群保持较好的多样性，应加大当前最优蚂蚁更新信息素的概率。因此，相比单纯更新当前最优蚂蚁或全局最优蚂蚁的更新策略，这样的交替更新策略，其全局优化能力更强，同时在算法初期会有较快的收敛速度。2.具有差分进化特性的信息素更新因此，将DE算法中的变异交叉操作引入到信息素更新过程中，增加信息素更新中可利用的信息量，进而增强蚂蚁种群内部间的交流协作。具体过程如下:3.混沌扰动上述设计可在一定程度上防止算法陷入局部最优，但任何随机方法均不能从根本上消除陷入局部最优的可能性，因此，当算法出现长时间停滞时，引入才能有效跳出局部最优的搜索算法是合理的。鉴于前文关于混沌搜索算法的分析，本方法引入混沌搜索算法。由于混沌的引入，原来的有利信息可能会被淹没;所以实施混沌扰动时，应确认算法确实己陷入局部最优。因此，可以适当扩大切入点的选取，c∈增量处理公式为[1,+∞)其值可根据具体问题而定。4.新的评价函数蚁群算法中，仅以路径长度最短为路径评价准则来评价可行路径;这种近似的处理是以牺牲真实性为代价来换取问题处理的简洁性。而DECACO算法除将路径长度作为核心指标外，同时还将路径平滑程度和路径节点的危险程度两个指标纳入到评价函数中。5.DECACO的算法流程具有差分进化特性的混沌蚁群优化算法的程序流程如图5.5所示。差分进化混沌蚁群优化算法差分进化(DE)算法是一种基于群体差异的启发式随机搜索算法，该算法是R.Storn和K.Price为求解Chebyshe多项式而提出的。其本质是通过个体间的变异、交叉、选择操作达到协同进化的目的，其原理简单、受控参数少、随机并行、全局最优、具有记忆最优个体的能力、全局收敛能力和鲁棒性均较强。1.算法改进的总体描述基本蚁群算法除了具有并行、正反馈、强鲁棒、全局最优等特点外，另一个显著的优势就是易与其他算法融合，达到优势互补，提高性能的目的，因此，本章从算法混合的角度出发，研究对基本蚁群算法的改进。由分析可知，蚁群算法易陷入局部最优，症结所在就是信息素更新环节;蚁群算法中无论是最优蚂蚁还是全体蚂蚁的信息素更新，只是单一地应用了全局路径信息，蚂蚁个体间的信息交流不够，种群间的协作性没有充分体现出来，因而不利于算法预防和跳出局部最优。因此，改进的思路是:算法初期在保证一定的收敛速度前提下尽可能地引导蚂蚁探索新的区域，使蚂蚁能遍历整个解空间;算法后期达到一定的收敛精度，随着蚁群聚集程度越来越大，算法易陷入局部最优，此时应引导蚂蚁逃离局部最优区，以进一步提高算法的收敛精度。差分进化(DE)算法是一种基于群体差异的启发式随机搜索算法，该算法是R.Storn和K.Price为求解Chebyshe多项式而提出的。其本质是通过个体间的变异、交叉、选择操作达到协同进化的目的，其原理简单、受控参数少、随机并行、全局最优、具有记忆最优个体的能力、全局收敛能力和鲁棒性均较强。近年来在多目标优化问题、复杂的约束优化计算、高性能聚类分析、非线性优化控制、神经网络优化、集成电路设计、多传感器信息融合等方面得到了广泛地应用。对比分析DE和AS两种算法的特点，可以发现:DE算法具备特有的记忆能力，使其可以动态地跟踪当前的搜索情况，随时调整其搜索策略，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适宜于求解一些利用常规的数学规划方法无法求解的复杂环境下的优化问题;而AS算法具有算法简单、搜索能力强等特点。因此，考虑充分利用两种算法各自的优势，将两种机制有机地结合起来，取长补短;本章设计了具有差分进化特性的混沌蚁群优化(DECACO)算法。即:应用DE算法来进行信息素的更新，同时对可能出现的停滞现象，适当时刻在信息素更新过程加入混沌扰动因子，以此来增强算法的逃逸能力。2.差分进化算法简介差分进化算法也是模拟自然界生物进化机制的一种仿生智能算法;从数学角度看，差分进化算法是一种随机搜索算法，而从工程学角度看，它是一种自适应的迭代寻优过程。算法的基本思想是从某一随机产生的初始群体开始，通过把种群中任意两个个体的向量差加权后按一定的规则与第三个个体求和来产生新个体;然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的适应度值优于与之相比较的个体的适应度值，则在下一代中用新个体取代旧个体，否则旧个体仍保存下来。通过不断的迭代计算，保留优良个体，淘汰劣质个体，引导搜索过程向最优解逼近[]。归纳起来，差分进化算法具有如下优点:(1)算法通用，不依赖于问题信息;(2)算法原理简单，易于实现;(3)群体搜索，具有记忆个体最优解的能力;(4)协同搜索，具有利用个体局部信息和群体全局信息指导算法进一步搜索的能力;(5)易于与其他算法混合，构造出具有更优性能的算法。简单的差分进化算法中，选择、交叉和变异这三种基本差分操作是算法的基础;构成差分进化算法的主要要素有个体适应度评价、差分操作和参数设置。(1)适应度函数在差分进化算法中，差分操作主要通过适应度函数（fitnessfunction)的导向来实现，它是用来评估个体相对于整个群体的优劣的相对值的大小。通常根据具体问题定义适应度函数。(2)差分进化算法的三种差分操作差分进化算法的基本操作和遗传算法类似，只是两种算法的操作算子顺序不同，差分进化算法的操作顺序是变异、交叉、选择。(3)差分进化算法的运行参数差分进化算法有四个运行参数:群体大小n、迭代代数t、变异因子η，交叉概率因子CR。这四个参数对差分进化算法的求解结果有着确定性的影响。3.差分进化算法的具体过程差分进化算法通过种群内个体间的合作与竞争来实现对优化问题的求解，其本质是一种基于实数编码的具有保优思想的贪婪遗传算法，其算法原理与遗传算法十分相似。DE算法中的选择策略通常为贪婪策略，而交叉操作方式与遗传算法也大体相同，但在变异操作方面使用差分策略，即利用种群中个体间的差分向量对个体进行扰动，实现个体变异。DE的变异方式，有效地利用了群体的分布特性，可提高算法的搜索能力，避免遗传算法变异方式不足的缺点。其具体执行过程为。（1）初始化:为了建立优化搜索的初始点，种群必须被初始化。通常寻找初始种群的一个方法是从给定边界约束内的值中随机选择。在DE研究中，一般假定对所有随机初始化种群均符合均匀概率分布。即:(c)选择操作:交叉、变异后，如果试验矢量的适应度优于目标矢量的适应度，则用试验矢量取代目标矢量而形成下一代，该操作被称为选择。4.差分进行算法流程模糊自适应窗口蚁群优化算法的设计基于参数模糊自适应调整策略的窗口蚁群优化（FWACO）算法，该算法利用模糊控制实现α、β、(1-p)三参数的优化，在合理分布初始信息素的同时，通过引入节点活跃度的概念实现信息素的有效更新；提高了算法初期的搜索速度、避免算法陷入局部最优，在很大程度上改善了算法的性能。1.算法改进的总体描述基本蚁群算法（AS）具有并行、正反馈、强鲁棒、全局最优等优点，但蚁群算法的全局寻优性要求蚁群搜索过程具有很强的随机性，而蚁群算法的快速收敛性又要求蚁群搜索过程具有较髙的确定性；两者对蚁群算法性能的影响是密切相关的，二者既矛盾又相关。因此，蚁群算法自身不可避免地具有搜索速度慢、易陷入局部最优的缺点。此外，基本蚁群算法中五个基本参数中，信息素启发因子α、期望启发因子β和信息素残留度(1-P)对算法性能起着决定性的作用，它们的优化组合直接影响着算法寻优能力的优劣，。但是目前关于三个参数的设置依然是凭借经验，缺乏清晰严密的理论指导；已有的关于参数自适应方面的研究，或是利用其他算法（例如GA）进行优化，或是利用简单的解析式进行调整，前者过于复杂，后者调节又过于粗糖。鉴于此，本章提出了一种基于参数模糊自适应调整策略的窗口蚁群优化（FWACO）算法。该算法利用模糊控制实现α、β、(1-p)三参数的优化，在合理分布初始信息素的同时，通过引入节点活跃度的概念实现信息素的有效更新；提高了算法初期的搜索速度、避免算法陷入局部最优，在很大程度上改善了算法的性能。最后在二维栅格环境和三维栅格环境下进行了多种类型的仿真研究，仿真结果表明该算法收敛速度快，能在较短时间内找到一条最优或近似最优的安全可行路径。2.模糊自适应窗口蚁群优化算法的设计根据以上分析，参数模糊自适应窗口蚁群优化算法的总体设计方案为：（1）实现参数优化：针对α、β、(1-p)三个参数，设计模糊自适应控制器，实现算法参数的优化。（2）建立动态窗口：为蚂蚁建立动态搜索窗口，减小蚂蚁单步搜索的任务量。（3）初始信息素的启发式分布：为每只蚂蚁建立近邻城市表，同时加入混纯信息，据此进行信息素的初始分布，以加快算法初期的搜索速度。（4）提出节点活跃度的概念：为有效避免陷入局部最优，提出节点活跃度的概念，以此作为未来信息指导蚂蚁进行解的构造和信息素的更新。（5）信息素的启发式更新：信息素更新中，只有接近当前最优的蚂蚁才进行信息素更新；同时信息素更新时综合考虑全局信息、局部信息及城市活跃度等因素。参数自适应模糊控制器的设计在基本蚁群算法的α、β、(1-p)、Q、m五个基本参数中，m依具体问题的规模n定，一般取m=n，Q对算法的影响取决于α、β、(1-p)三参数的优化组合，一般不做特殊考虑。那么，对算法性能有着决定性影响的就是α、β、(1-p)三个参数，这三个参数的优化组合直接关系到算法寻优性能的优劣。目前，如何合理地设置这三个参数也是一个亟待解决的问题。模糊具有灵活、无约束、完全非解析的特点，适合于解决多親合、非线性的参数优化问题；模糊控制不依赖于控制对象的数学模型、鲁棒性好、简单实用，已广泛地应用到图像识别、语言处理、自动控制、故障诊断、信息检索、地震研究、环境预测、楼宇自动化等学科和领域，并且渗透到社会科学和自然科学许多分支中，在理论研究和实际运用上都取得了引人注目的成果。因此，本章提出了一种简洁快速的参数模糊自适应方法，以期在一定程度上提高算法的性能。根据算法设计的需要，现作如下定义：为了方便随后的叙述，现将算法中所涉及的变量及其意义加以说明，如表4.1所示。根据蚁群算法的原理和特点，模糊自适应控制器的设计大致可分为两个阶段：算法未出现停滞阶段和停滞阶段；针对两个阶段的不同特点，分别设计相应的模糊控制器Fuzzy1和Fuzzy2。模糊自适应控制器的整个过程如下：（1）当种群能搜索到更优解时，由模糊控制器Fuzzy1优化参数α和β，而此时（1-p）保持初始值不变。（2）当种群不能搜索到更优解，但连续停滞代数还没有达到停滞门限Nplateau时，算法参数保持不变。也就是说，当种群不能搜索到更优解，但算法未停滞时，算法参数保持不变。（3）当种群不能搜索到更优解，同时连续停滞代数也已达到停滞门限Nplateau时，由模糊控制器Fuzzy2优化参数α、β和（1-p）以使算法逃出局部最优。即：当种群不能搜索到更优解，且算法已停滞时，由模糊控制器优化Fuzzy2优化α、β和（1-p）三参数。根据参数在算法中的作用，参数模糊自适应控制器的具体设计过程如下：（1）模糊控制器Fuzzy1的设计在此阶段算法能持续找到更优解，α、β和（1-p）三参数调节的主要依据就是算法的收敛速度及算法当前的进化程度。模糊控制器Fuzzy1的作用就是通过调节参数使算法在保证收敛速度的同时预防陷入局部最优。模糊控制器Fuzzy1将整个算法的进化过程大致分为三个阶段根据每个阶段收敛速度的不同来实时调整α、β参数；在力求收敛速度最快的同时，尽可能地预防陷入局部最优。具体过程如下：算法初期：此时算法的寻优能力EXP较小，说明算法还有提速的空间，应该加大信息素的正反馈作用。即：应增大信息素启发因子α，且增大的幅度应大一些；增大的幅度应随寻优能力EXP的增加而相应地减小，以避免收敛过快出现停滞。算法初期各路径信息素整体差异不大，故将期望启发因子β设置为最大，以保证算法初期平均收敛速度较快。算法中期：此阶段中，算法陷入局部最优的风险较大，除需增强寻优能力外，还应注意预防算法陷入局部最优。因此，信息素启发因子α增大的幅度应随寻优能力EXP的增加而相应地减小，α增大的平均水平要比算法初期小。此时，期望启发因子β值应相应地减少，以加强算法的随机性和多样性，防止算法陷入局部最优。算法末期：此时算法陷入局部最优的风险最大，因此，必须以预防算法陷入局部最优为首要任务。所以，信息素启发因子α增大的幅度应随寻优能力EXP的增加而相应地减小，α增大的平均水平要比算法中期还小。此阶段β值应进一步地减小，以保持算法的多样性，防止算法陷入局部最优。最终制定出了模糊控制器的模糊规则，如表4.2所示。釆用重心法进行解模糊过程。（2）模糊控制器Fuzzy2的设计如前所述，当种群不能搜索到更优解，且算法已停滞时，由模糊控制器Fuzzy2来优化参数α、β和（1-p）。因此，设计Fuzzy2时，蚁群在连续Nplateau代内已不能搜索到更优解，可以认定算法以最大可能陷入局部最优；则模糊控制器Fuzzy2的作用就是通过调节参数使算法逃离局部最优，确保算法能找到最优解。因此，模糊控制器Fuzzy2以算法的停止程度BOG为输入变量，输出变量是参数α、β和（1-p）。输入变量的论域划分为｛PS,PMS,PM,PMB,PB｝，即：｛0,0.25,0.5,0.75,1｝隶属度函数选择三角函数和高斯函数，相应的量化因子为kBOG=1:输出变量α和β的论域划分均为｛NB,NMB,NM,NMS,NS｝，即：｛-1,0.75,0.5,0.25,0｝，隶属度函数选择高斯函数，而输出变量(1-p）的论域划分为｛PS，PMS,PM,PKB,PB｝，、即｛0，0.25,0.5,0.75,1｝，隶属度函数选择高斯函数。则，相应的输出结果的表达式为：动态搜索窗口的设计由表4.4可知，城市规模小于等于时，MAXYC10；当城市规模≤0时，MAXYC20；且此时PC,=1的概率基本上为50%以上。也就是说对于每一个城市C，选择由该城市为起点的最短边的概率很大，如果从离其最近的MAXYC个城市中选择一个作为近邻城市，而不是从剩余所有城市中任选一个，也必然可以找到最优解。这将大大缩小搜索空间，节省搜索时间，提高收敛速度。为不失一般性，可对MAXYC进行适当地放大处理:初始信息素的合理分布蚁群算法在初始化时，各条路径上的信息素取值相同，使得在算法初期蚂蚁以相等的概率选择路径，这样蚂蚁很难在短时间内从大量的杂乱无章的路径中找出一条较好的路径;所以，算法初期，蚂蚁搜索量大，收敛速度较慢。因此，为加快算法初期的收敛速度，替换信息素等值均匀分布法，在信息素的初始分布中加入启发式信息。本章的具体做法是:根据当前城市路径相对长度的局部信息进行信息素的初始分布，同时加入混沌分量进行微调，以防止算法陷入局部最优。将混沌的遍历性、随机性、初值敏感性和混沌扰动算子引入蚁群算法，有效避免搜索过程陷入局部最优，弥补蚁群算法的不足，提高解的多样性和全局寻优能力。其中，μ为控制参量，μ∈[3.56,4]。当μ=4,0△λ1时，Logisti完全处于混沌状态，其输出实际上相当于一个[0,1]之间的随机输出;此时系统在[0,1]之间具有遍历性，且其中的任一状态不会重复出现。再以此随机产生n个[0,1]上的初始值，分别赋给函数的每一维自变量，并利用全排列构造的理论，将每个混沌量对应于一条路径，从而产生大量的路径，从中选择较优的路径，使这些路径留下信息素(与路径长度和成反比)，各路径的初始信息量就不相同了，在此基础上，蚂蚁再进行路径的选择。混沌具有精致的内在结构，具有随机性、遍历性及规律性等特点，对初始条件极为敏感，能在一定范围内其自身规律不重复地遍历所有状态;利用混沌运动的这些性质进行优化搜索比其它随机搜索更具优越性。节点活跃度的概念在基本蚁群算法中，状态转移概率仅仅取决于历史信息τ0和当前信息ηij；因此，路径的选择缺乏未来信息的指导，使得算法易陷入局部最优。因此，本章提出节点活跃度的概念。全局信息素更新在基本蚁群算法中，种群完成一次迭代后，所有蚂蚁都进行信息素更新。这不能充分体现最优解的指导作用，同时劣质解的信息又会干扰下一次种群迭代;此外，信息素更新时仅利用全局信息(路径长度)进行指导更新，指导信息不完全。本章的改进策略是:仅对接近最优解的部分较优蚂蚁进行信息素更新，在更新时加入更多启发式信息，综合考虑全局信息、局部信息和节点活跃度等因素，充分利用有利信息快速收敛、逃出局部最优。新的评价函数在基本蚁群算法中，以规划路径的时空最优为优化准则来评价可行路径，即要求路径的长度最短。这种近似处理是以牺牲真实性为代价来换取问题处理的简洁性。而FWACO算法除将路径长度作为核心指标外，同时还将路径平滑程度和路径节点的危险程度两个指标纳入到评价函数中。(1)路径长度路径长度的数学表达式如下:(2)平滑程度如图4.4所示，θi是连接可行点Pi-1和Pi间线段的延长线与连接转向点Pi和Pi+1的线段之间的夹角，即偏转角。在栅格环境中，θi∈[0,π]，则θi越小，表明路径越平滑，机器人路径跟踪时的消耗也就越小。所有路段的偏转角之和就构成了路径平滑程度的整体描述，该项作为经济性的评价条件。3)节点危险程度节点危险程度用节点邻域中的栅格节点的相对数目来表示，此数目越大，说明该节点所处位置越危险;反之则越安全。在路径规划时，为了确保机器人行进的安全性应尽量选择危险指数低的栅格，而应尽量避开危险指数高的栅格。也就是说，从路径安全性的角度考虑，机器人应该尽量选择安全的栅格行进。危险指数的示意图如图4.5所示。4.模糊自适应窗口蚁群优化算法的算法流程具有模糊自适应特性的窗口蚁群优化算法FWACO的程序流程如图4.6所示。基于肤色统计的手势分割算法肤色统计的手势图像分割算法不用穿戴任何手势分割辅助设备，对人类自然手图像就能进行手势分割,而且手势分割的速度较快快,是目前广大从事手势识别研究者用到的最多的手势分割算法之一。基于肤色统计的手势分割算法通过对手势图像中各个像素点的统计计算，进而将手势图像从其所在的复杂背景中分离出来。1.算法总体框架该算法根据人体肤色在YCb’Cr’色彩空间中能将亮度Y和色度Cb，Cr进行分离，肤色在色彩空间Cb，Cr轴上的变化随光照条件不同变化很小的特性，将手势图像从复杂的背景中提取出来；随后利用形态学滤波将转化得到的二值图进行滤波，消除背景噪声的影响，然后提取分布手势分布区域边界轮廓，最后利用最小二乘法拟合，精确提取出手势图像。2.手势肤色在YCb’Cr’彩色空间的统计由于色度值在YCbCr空间中总是与亮度值Y存在着一定的非线性关系的依赖性，为了消除这种依赖性，采用非线性分段色彩变换的方法得到色彩空间YCb’Cr’,其方法如下所示：公式中Ci表示Cb、Cr，Ki=，Kh=，Ymin、Ymax是肤色聚类区域的最小值和最大值，Wch=46.97，WLch=23，WHcb=14，Wcr=38.76，WLcr=20，WHcr=10。然后通过椭圆拟合，如果得到的像素点在椭圆内部，则认为是肤色像素，否则则是背景像素点。通过此方法对图像进行分割虽能消除色度对亮度的依赖，但该方法的应用背景需要大量的数据库资料，不是个每个特定的设像装备。为此本文为解决此缺点，提出了利用最小二乘法进行拟合的肤色统计分割算法。3.最小二乘法拟合的手势分割算法根据YCb’Cr’色彩空间的基本方法是对特定设备的肤色统计结果，进过非线性转换后道道Cb’Cr’在色彩空间的肤色色素点的分布结果，把手势图像转换成二值图像，然后在手势图像上找到肤色像素点分布的边界点，最后利用最小二乘法将边界点进行拟合，从而将手势图像从复杂背景中分割出来。其基本思路是：首先在待测的手势图像上选择一个矩形区域作为样本点，利用公式一将像素点先转化成YCbCr色彩空间，然后通过非线性转换，得到YCb’Cr’色彩空间，利用肤色在YCb’Cr’空间Cb’Cr’色度聚类的特性将手势图像转换成二值图像。由于干扰的存在，图像在离聚类区域较远的区域存在一些离散点，需要通过形态学方法来去除图像中的离散点。最后利用八邻域搜索的方法提取二值图像中手势图像边界点的坐标集合S。根据提取得到的手势图像边界点的参考坐标集合点集合，通过最小二乘发最小化参考点与选定窗口的最小距离，并与设定的阈值相比较，小于设定阈值的为手势图像，其他为背景图像。最小二乘发的曲线方程为：其中x、y为参考点坐标，A、B、C、D、E、F为最小二乘法后得到的拟合参数。4.实验结果与分析本文的实验使用了市场上普通的摄像头在室内光照、复杂的背景下拍摄手势图像用手势分割实验，获得的手势对比结果如图所示。由实验结果可以看出，利用肤色统计的方法在普通摄像头下不同光照条件下可以准确地分割手势图像，且不受光照和环境中相同颜色的影响较小，检测准确，实时性比较高。

来源：萝卜库