（机械制造及其自动化专业论文）工业机器人最优轨迹规划研究.pdf

硕 j 学何论文 摘要 最优轨迹规划是机器人最优控制问题之一，实际上，规划就是一种问题的求解 技术，即从某个特定问题的初始状态出发，通过构造一系列操作步骤，使之达到 解决该问题的目标状态。 机器人的轨迹规划的策略中，与工作效率相关的时间最优算法是最早被提出 来的。其目的是为了通过最大化机器人的操作速度而最小化机器人总的运行时间。 能量最优指标在工业应用中也是很重要的性能指标，因为它不仅可以产出出光滑 的轨迹从而使轨迹更容易跟踪，而且还能减少机器人结构的压力。在能量资源有 限的情况下，这个性能更是重要。除了这两种性能指标外还有诸如，跃度最小、 速度和加速度最小、可操作度等性能指标，但是没有人将这些指标全部考虑，本 问就是通过使用多目标函数将以上的时间、能量、跃度性能指标加权考虑，从而 达到以上所有性能指标的特性。 本文的主要的内容如下： ( 1 ) 对多目标优化问题进行了研究，并提出了使用两种进化算法一差分进化 算法和基于精英策略的非支配排序的遗传算法来解决多目标优化的问题。 ( 2 ) 在对机器人的运动学和动力学进行研究的基础上，建立机器人运动学和 动力学方程，最后以斯坦福机器人为例，建立起其机器人模型。 ( 3 ) 加权考虑机器人的时间、能量、跃度性能指标，建立一个多目标函数一 代价函数。 ( 4 ) 采用了三次样条曲线来拟合关节轨迹，并推导了该样条的曲线和约束方 程。 ( 5 ) 结合斯坦福机器人为例，分别采用差分进化算法和基于精英策略的非支 配排序遗传算法以代价最小为优化目标，求解机器人的运动轨迹，并对结果进行 对比。 关键词：最小代价轨迹规划：工业机器人；三次样条曲线；设计指标；优化设计 a b s t r a c t t h eo p t i m a lt r a j e c t o r yp l a n i n gi so n eo ft h ep r o b l e mo ft h eo p t i m a l c o n t r 0 1 i n f a c t ，p l a n n i n gi sat e c h n o l o g yt os o l v eap r o b l e m ，t h a ti ss t a r t i n ga tt h ei n i t i a l w i t ha s e r i e so fo p e r a t o r s ，g e tt h et a r g e ts t a t u s ，c a ns o l v et h ep r o b l e m a m o n g t h e s es t r a t e g i e so nt r a j e c t o r yp l a n n i n gf o ri n d u s t r i a lr o b o t s ，w i t hr e l a t i o n t ot h ew o r k i n ge f f i c i e n c y ，t i m e o p t i m a lt r a j e c t o r yp l a n n i n go f r o b o t ，i sr a i s e df i r s t i t s a i mi sm i n i u mt h em o t i o nt i m e p l a n n i n go fr o b o t t r a j e c t o r yu s i n ge n e r g e t i cc r i t e r i a p r o v i d e ss e v e r a la d v a n t a g e s o nt h eo n eh a n d ，i ty i e l d ss m o o t ht r a j e c t o r i e se a s yt o t r a c ka n dr e d u c et h es t r e s s e st ot h ea c t u a t o ra n dt ot h em a n i p u l a t o rs t r u c t u r e m o r e o v e r ，s a v i n ge n e r g ym a yb ev e r yi m p o r t a n ti ns e v e r a la p p l i c a t i o n s ，s u c ha st h o s e w i t hal i m i t e dc a p a c i t yo ft h ee n e r g ys o u r c e w i t h o u tt h et w o c r i t e r i a ，t h e r ea r ej o i n t j e r ka n dj o i n ta c c e l e r a t i o n sa n dt h em a n i p u l a b i l i t ym e a s u r e b u tn o n eo fl i t e r a t u r e s c o n s i d e r e da l lt h ec r i t e r i a i nt h i sp a p e r ，w ec o n s i d e ra l lt h eo b j e c t i v ef u c t i o n si na c o m b i n e dm a n n e rt og e ta l lt h eb e n e f i t s t h i sp a p e ri so r g a n i z e da sf o l l o w ： ( 1 ) w i t ht h er e s e a r c ho nm u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m ，u s j n gt w oe a a l g o r i t h m s n s g a - i ia l g o r i t h m s ，d ea l g o r i t h m st os o l v et h ep r o b l e m ( 2 ) w i t ht h er e s e a r c ho nt h ek i n e m a t i c sa n dd y n a m i c so fr o b o t ，f o r m u l a t et h er o b o t m o d e l a tl a s tt a k i n gs t a n d f o r dr o b o ta se x a m p l e ，s t r u c t u r ei t sm o d e l ( 3 ) t h ec o s tf u n c t i o ni saw e i g h t e db a l a n c eo ft r a n s f e rt i m e ，m e a na v e r a g eo f a c t u a t o r sp o w e r ，j o i n tj e r k sa n d j o i n ta c c e l e r a t i o n s ，s i n g u l a r i t y ( 4 ) i nt h i sp a p e rw eu s eac l a m p e dc u b i cs p l i n ec u r v e st oc o n s t r u c tt h ej o i n t t r a j e c t o r yo ft h er o b o t t h ed e r i v a t i o no ft h es p l i n ef u n c t i o ni sp r e s e n t e da n da l s oi t s c o n s t r a i n te q u a t i o n ( 5 ) t h i sp a p e ra p p l i e sn s g a - i i a l g o r i t h m s ，d ea l g o r i t h m si nt h em i n i m u mc o s t t r a j e c t o r yp l a n n i n gp r o b l e m ，w h i c ht a k e ss t a n d f o r dr o b o ta se x a m p l e c o m p a r i n g t h er e s u l t so ft h e t w oo p t i m i z a t i o n s k e yw o r d s ：m i n i m u m c u r v e s ，d e c i s i o nc r i t e r i a c o s tt r a j e c t o r y , i n d u s t r i a lr o b o t ，ac l a m p e dc u b i c s p l i n e ，o p t i m a lp l a n n i n g 玎 硕十付论文 插图索引 图1 1 斯坦福机器人结构简图3 图2 1 局部拥挤距离示意图1 0 图2 2n s g a - l i 算法流程图1 2 图2 3d e 算法流程图1 4 图3 1 坐标系在另一坐标系中表示。1 8 图3 2 坐标平移1 9 图3 3 坐标旋转1 9 图3 4 复合变换2 0 图3 5 机器人坐标变换图2 l 图3 6 连杆坐标系的设定。2 2 图3 7 斯坦福机器人各构件坐标系2 5 图4 1 轨迹规划框图3 8 图5 1 两种进化算法的结果对比5 1 图5 2 an s g a i i 算法所得关节的位置图5 1 图5 2 bn s g a i i 算法所得关节的速度图5 l 图5 2 cn s g a i i 算法所得关节的加速度图5 2 图5 2 an s g a i i 算法所得关节的跃度图5 2 图5 3 ad e 算法所得关节的位置图5 2 图5 3 bd e 算法所得关节的速度图5 2 图5 3 cd e 算法所得关节的加速度图5 3 图5 3 dd e 算法所得关节的跃度图5 3 l l l r t 、i p 机器人屁优轨迹规划f 丌究 附表索引 表2 1 差分策略1 5 表3 1 斯坦福机器人各构件坐标系参数2 5 表5 1 斯坦福机器人动态参数4 8 表5 2 斯坦福机器人关节空间的7 个点4 9 表5 3 两额外点的初始值4 9 表5 4 两种算法最优解的对比5 0 i v 硕i 。何沦文 第1 章绪 论 1 1 课题的研究背景 机器人是一种自动的、位置可控的、具有编程能力的多功能机械手，这种机 械手具有几个轴，能够借助于可编程操作来处理各种材料、零件、工具盒专用装 置，以执行多种任务。本论文所指的机器人，工业机器人，或称机器人操作臂、 机器人手臂、机械手等。 机械人系统一般由四个相互作用的部分组成：执行机构、控制器、环境和任 务，执行机构( 也称为机械手、操作器或者操作手) 一般是多关节式机械结构， 由连杆、关节、末端执行器等组成，其末端执行器根据操作需要也可以换装焊枪、 吸盘、扳手、喷嘴等工具。 环境即机器人所处的周围环境。是指机器人在执行任务时，所能达到的几何 空问，而且包含此空问及其中的每个事物的全部自然特性所决定的。在机器人工 作环境中，机器人会得到完成此任务所需要的支持，如自动传输线将为机器人传 送生产所需的工件、材料等。同时，在机器人的工作环境中也会遇到一些障碍物 和其他物体，它必须避免与这些障碍物发生碰撞及对这些物体发生作用，妥善处 理好环境中各种突发事件，以保证机器人完成特定的任务。环境信息一般是确定 的和己知的，这种环境称为结构化环境。但在大多数情况下，环境具有未知和不 确定性，这种环境称为非结构化环境。 任务的定义为环境的两种状态( 初始状态和目标状态) f b 的区别。这些任务 必须用适当的程序设计语言来描述，并将其存入机器人系统的控制计算器中，而 且这种描述必须是能被计算机所理解。随着系统的不同，语言所用的系统不同语 言描述方式可以为图形、语音或者文字。 控制器是机器人系统的指挥中枢，负责信息处理和与人交互，它接受来自传 感器的信号，对其进行数据处理，并按照预存信息、机器人的状态及其环境情况 等，产生出控制信号去驱动机器人的各个关节。为此，控制器内必须保证机器人 实现其功能所必须的程序。对于技术要求简单的机器人，计算机只含有固定程序： 对于技术比较先进的机器人，可以采用可编程计算机或者微处理器作为控制器。 机器人主要应用在工业制造中，当然还有各类机器人在资源丌发、排险救灾、 社会服务和军事、航天等方面。 ( 1 ) 工业机器人 从上个世纪七十年代开始，工业机器人在汽车制造业中得到了广泛的应用， 。1 、i k 机器人最优轨迹规划研究 当然今后也仍将足工业机器人的主要用户。从发展趋势来看，工业机器人在其他 制造业中的应用也将会得到增加。 工业机器人大都应用在简单、重复、繁蕈的工作，如上下料，搬运等，以及 在工作环境恶劣的场所，如焊接、喷漆和处理核废料等，据分析预测，今后精密 装配和检验机器人的需求量将会逐渐的增加，其中有机器装配和电气装配。总的 来说，装配的过程可以概括为约束运动的规划问题，可以看成是在操作空间中机 器人的术端执行器与被操作对象之间的一系列相互接触的结果。为了解决环境、 传感器和控制的不确定性，此类机器人带有外部传感器，实现细微操作，补偿和 顺应控制。 ( 2 ) 极限环境作业的机器人 机器人代替人类工作，最能发挥其作业的场所就是对人有危险的环境，如被 污染严重的地方，有放射性的地方。深海和太空等极限( 恶劣) 环境将成为机器 人活跃的场所，又如在高层建筑或者有天进行灭火救灾等的机器人都属于极限作 业的机器人。为了完成这些极限作业，机器人技术还有许多问题亟待解决，一般 认为极限作业的机器人属于第三代机器人的范围，应具有某些智能。 ( 3 ) 医疗福利机器人 对患有先天性疾病、慢性病或者因为意外事故而失去部分人体机能的病人进 行补偿的机械，和为残疾人服务的机械统称为医疗福利机器人。例如动力假肢属 于前者；而护理机器人属于后者。 此外，机器人已经开始服务于服务产业，如商业中心。家务劳动和保健等。 一个刚体在三维空间中有六个自由度，所以，机器人要完成一个空间任务，也 要六个自由度。机器人的运动是由机器人的手臂和手腕的运动组合而成的。一般 情况下机器人的手臂有三个关节，用来改变机器人手腕参考点的位置，也称定位 机构；机器人手腕部分也有三个关节，通常它们轴线相交，用以改变执行器未端 的姿态，也称为定向机构，所以机器人的手臂可以看成是定位机构连接的定向机 构。 机器人的定位机构中三个关节的种类决定了机器人操作臂的工作空间形式。 根据这三个关节种类的不同可以将机器人为四种常见的形式：直角坐标式机器人， 它的特点是三个关节都是移动关节，结构刚度高，三个关节没有耦合运动简单， 不产生奇异状态，但是占地面积大运动范围小，灵活性差；球坐标式机器人，其 腕部参考点运动所形成的最大轨迹表面半径为的球面的一部分，以口，伊和厂为 坐标，任意点尸可表示为p = f ( o ，缈，厂) ，这类机器人占地面积小，工作空间大；关 节式机器人，该机器人所有关节都是转动关节，它动作灵活，工作空间大，结构 紧凑，占地面积小只是其运动学较为复杂，进行控制时计算量比较大。 本文对斯坦福机器人( 如图1 1 ) 的捡拾操作进行仿真的，它就是一种有6 2 硕 付论文 个自由度的机器人，除了一个关节为移动关节，其他五个关节均为转动关节。因 为它不仅含有转动关节而且还有移动关节，具有典型的代表性。 二 1 2 课题的研究意义 图1 1 斯坦福机器人结构简图 机器人的广泛应用，极大地提高了劳动生产效率，提高了产品质量，降低了 产品的成本，减轻了人的劳动强度，改善了劳动条件，扩大了人类的认知活动能 过的范围。因此世界上许多发达国家都投入了大量的人力物力发展机器人技术。 机器人学( r o b o t i c s ) 是一门高度综合和交叉的新兴学科，有着极其广泛的研 究和应用领域，如机械、电气、工艺、力学、传动、控制、通信、决策、生物、 伦理等。具体地说，它的研究内容包括了传感器与感知系统；机构的设计、驱动、 建模与控制；运动控制与规划；多机器人协调与控制；应用研究。 机器人运动控制与规划包含了机器人的轨迹规划与路径跟踪。而机械人的轨 迹规划问题是机器人学研究领域中一个长期存在的问题。近年来，引起了越来越 多学者的关注，重要的研究成果层出不穷。因为轨迹规划器负责为机器人控制器 提供输入，所以机器人是否台邑有效地完成一个任务就最终取决于它对应的轨迹规 划器的性质。轨迹规划问题在各干中工业场合中均能得到广泛应用，也是是机器人 研究领域中一个长期存在的传统问题。 机器人的运动质量很大程度上取决于目标( 价值) 方程，目标方程代表着机 器人从初始位置到终止位置的移动代价心1 。现在有许多研究将与机器人运动相关 的优化指标放在目标方程中，以减少机器人的运行代价，从而在工业生产中的提 高生产效率，但是在现在的文献中，大部分的要么以时间最优作为机器人的优化 指标，要么以能量作为其优化指标，而综合考虑两者的多目标优化算法却很少， 因此，将机器人运行中所要考虑的优化指标放在一个目标方程中，对机器人的轨 迹进行优化在实际的工业应用中是有重要现实意义的。 3 _ 1 、i k 机器人最优轨迹规划研究 1 3 国内外机器人轨迹规划技术的研究现状 最优轨迹规划是机器人的最优控制问题之。规划的任务是根据给定的路径 点，规划出通过这些点并满足各种约束条件矛u 。陛能指标的光滑的最优运动轨迹【3 1 。 由于机器人的动力学模型的非线性和强耦合性，所以对机器人控制是一个非常复 杂的问题。通常，对其研究分为两个阶段束进彳亍。第一个阶段称为机器人的的最 优轨迹规划( o p t i m a lt r a j e c t o r yp l a n n i n g ，o t p ) ，第二个阶段称为轨迹跟踪和控制 ( t r a j e c t o r yt r a c k i n ga n dc o n t r o l ，t t c ) 。前者为后者提供了机器人在运动路径上 期望的位置、速度、加速度和力( 或者力矩) 等控制命令；而后者则负责让机器 人尽可能精确地按照上面对应的控制命令移动。研究机器人轨迹控制的方法比较 多，而且比较成熟，在实际的应用中也获得了较好的效果，例如滑模控制器( s l i d i n g m o d ec o n t r o l l e r ，s m c ) 。而在机器人的轨迹规戈l j 方面，则由于涉及到机器人动力 学、运动学等诸多方面的性能的约束而显得j e 常复杂，此外在机器人轨迹规划前， 还需要有路径规划的过程，因为在机器人的q - 作空问中往往分布着一些障碍物， 要使机器人能够安全的从起始点运行到终点，就需要规划一条路径避开这些障碍 物，这就需要进行路径规划，得到一条距离障碍物尽量远的安全路径。 本文主要是针对机器人的最优轨迹规戈i j 问题进行讨论求解和仿真，下面我们 将着重介绍有关机器人o t p 问题的研究。 o t p 是工业机器人最优控制问题之一，其目标是指按照某个性能指标产生机 器人沿着该光滑路径运动至各点出的速度和力口速度时间序列。轨迹规划的性能指 标有多种形式，有时间最优，能量最优，以及时间能量综合最优轨迹规划1 4 】等。 在早期的研究中，由于工业机器人动力学模型的复杂性，其非线性部分常常不被 考虑，通常，研究者假定机器人在路径上各点的速度为常量或者只在一个很小的 范围内变化，但这样做的后果使得轨迹规戈i j 的效率很低。因为在实际的应用中， 机器人的速度和加速度的范围随着其位置、负载质量甚至是负载的形状变化而变 化，所以为了确定范围，研究者必须考虑最坏的情况。 机器人时间最优轨迹规划，是最早被提出的，它是指以时间最短作为机器人 的性能指标来优化机器人的运动轨迹的。k i m 和m c k a y 提出了一种在制定力矩约 束下沿着已知集合路径运动的最小时间轨迹规划方法，采用参数化方法表示机器 人的动力学模型，使用基于相图技术的算法计算最小时间。p f e i f f e r 和j o h a n n i 利 用工业机器人在路径上个点速度的边界条件求得最小时间，提高了计算效率，此 外，在另外一些文献中也使用了类似的方法，以速度作为约束条件，进行了时间 最优轨迹规划。 在实际的应用中，能量最优作也是一个j e 常重要的性能指标，因为，利用能 量最优进行的轨迹规划能够产生出光滑的轨迹，这样更易于轨迹的跟踪，从而提 4 硕卜何沦文 高跟踪的精度，而且还能够减少机器人执彳亍器和操作臂上的应力，同时在能源紧 张或者有限的情况下，还可以节省能量( 例如太空机器人) 。相关的研究工作有， 陈忠泽1 5 】在已知机器人末端轨迹的始末位胃的情况下，根据其各自的自由度的加 速度积分和能量最小准则寻求满足约束条件的最优平滑轨迹，得到的轨迹不仅平 滑而且安全；董宇欣等 6j q e 于祸合刚体运动规划方法应用与自由漂浮空间机器人的 轨迹规划中，得到一种针对能量优化的规戈i j 算法，得到的轨迹不仅消耗能量小， 而且关节轨迹光滑；鄢波等【_ 7 】则利用遗传算法建立了相贯线扫查机器人能量最小 优化的综合规划模型，给出了其随机搜索策略，该模型的目标函数总了考虑了机 器人避障、末端轨迹精度、动力学约束与荣誉度能量最小优化指标；罗进生等j 结合动态规划法和速度限制曲线法，在末立嵩轨迹制定的情况下，进行了机器人时 | 日j 能量加权最优二次轨迹规划，同时优化了时l 日j 和能量两个性能指标。 对于这些优化目标，一些研究工作放在了求解这些优化目标的方法中去，其 中以对算法的研究最多。l i n t9 】及其同事在l9 8 3 年提出了柔性多面体搜索( f l s x i b l e p o l y h e d r o ns e a r c h ，f p s ) 算法来进行具体求解，但是该算法只是一种局部的搜索 算法。c h o i 等人使用了进化策略( e v o l u t i o ns t r a t e g y ，e s ) 来求解优化模型，但其 设计的算法过于简单。s a h a r 和h o l l e r b a c h 在19 8 6 年设计了一种求解机器人点到 点运动下的同用算法，该算法在充分考虑了机器人末端执行器在力矩约束的条件 下运行的问题。另外还有同时考虑了机器人运动学和动力学的约束条件下而设计 的算法。例如在2 0 0 1 年杨国军和崔平远提出了基于模糊原理的遗传算法，并对遗 传算法中的变异概率和交叉概率进行了模糊控制，克服了传统的非线性规划方法 易于陷入局部极小的缺点。 对于如何构造机器人轨迹也有许多研究，t o n d u 等人【lo 】在1 9 9 4 年在最优时间 下轨迹规划的方法中，使用了带有光滑转折的直线段来连接机器人关节空间中的 关键点，但这样所产生的轨迹其缺点是不肯邑对给点的中间点进行插值操作。19 9 7 年，b a z a z 等人【i l 】则指出用三次样条曲线来连接关节空间中的各个节点是最简单 的多项式形式，但是他们在没有考虑关键点连接处加速度的连续性，从而会引起 机器手在运动的过程中出现振动的现象，这会减少机器人的跟踪精度。两年后， b a z a z 等人对前面的方法进行了一定的改进，提出了带有光滑转折的三次样条曲 线来连接关节空l 日j 中关键点的新方法。z h a 在笛卡尔空间内利用b e z i e r 曲线将机 器人的位姿向量所构成的直纹而作为机器人的轨迹，并对其进行了插值。现在应 用最广的是分段多项式，常用的分段三次样条插值是由5 段三次样条函数联系起 来的。它是使位置、速度、加速度连续的多项式插值方法中最低的插值方法。但 是其缺点是计算量大，并且由于阶次低，三次样条插值不能使机器人的跃度连续。 于是人们开始研究高次多项式插值函数的轨迹规划，在高次多项式插值函数中，5 次多项式的样条对机器人轨迹规划的较多，但是样条函数的各项系数的计算较为 5 + 州p 机器人最优轨迹规划形f 究 复杂。徐向荣等人提出了使用3 5 3 样条函数对机器人的轨迹进行规划l l2 1 。后来 的研究者们对前者进行了改进，并用仿真工具对新样条轨迹函数进行了验证。常 用的高次分段多项式插值还有3 5 4 多项式插值和4 5 6 7 多项式插值。但是由于 其阶次高、没有凸包性等原因，使其很难用传统方法优化。 除了以上的轨迹规划，文献【13 提出了基于摆线运动规律的轨迹规划，还有 研究者采用了3 阶贝塞尔曲线进行二路径规划，并提出了加速度约束条件下的时间 最优轨迹规划的方法。基于螺旋理论和空间样条曲线生成原理提出的一种笛卡尔 空间的机械手轨迹规划的方法也被提出【i4 1 。文献【15 】提出了在关节空间中使用双 曲线函数对机械手进行轨迹规戈i j ，该方法虽然算法简单，但是双曲线函数中的参 数却不容易确定。 1 4 本文的研究目标及内容 1 4 1 本文的研究目标 本文通过使用两种进化算法一基于精英策略非支配排序遗传算法和差分进化 算法，并综合考虑机器人各项性能指标一时问、能量、跃度，同时在机器人运动 学和动力学的约束条件下，对机器人的轨迹进行优化，从而得到一条综合性能最 优的轨迹。 1 4 2 本文的研究内容 本文在机器人运动学和动力学的基础上，根据机器人最小代价轨迹规划的约 束和要求，在机器人的关节空间中，采用了三次样条曲线函数来拟合其关节轨迹， 同时充分考虑了机器人在关节空问的位移、速度、加速度和二次加速度的约束条 件，选用两种进化算法一一基于精英策略的非支配排序遗传算法和差分算法来求 解最小代价轨迹规划的最优解。本文的具体工作如下： ( 1 ) 多目标优化问题的研究 本文首先介绍了多目标优化问题的数学模型，及其求解方式。然后针对本文 中的多目标优化问题，提出了用两种进化算法来求解这个问题，最后对这两种算 法( 差分进化算法和基于精英策略的非：支配排序遗传算法) 进行了介绍。 ( 2 ) 机器人模型的建立 机器人的轨迹规划时建立在其运动学和动力学的基础之上的，所以有必要的 先对它们进行介绍，并以斯坦福机器人为例，建立了该机器人的仿真模型，并对 其进行了适当的简化，用于轨迹规划的研究。 ( 3 ) 轨迹优化的具体分析 本文是在机器人的关节空问进行轨迹优化的，以最小代价作为机器人的优化 性能指标，采用三次样条曲线来拟合关节轨迹，并推导了该样条函数的求解过程 6 硕t “7 ：何论文 以及约束方程，最后通过两种进化算法一遗传算法和差分算法来求得最优解的。 ( 4 ) 实例仿真 结合斯坦福机器人的抢拾操作为例，文中将分别采用基于精英策略的非支配 排序遗传算法和差分进化算法以代价最小为最优目标，求解其运动轨迹，最后通 过调用m a t l a b 软件的计算和绘图功能对其轨迹进行了模拟，并对由这两种进化算 法产生的结果进行了对比分析。 7 川p 机器人最优轨迹规划研究 第2 章多目标优化方法及相关算法简介 2 1 多目标优化问题简介 在工程实践和科学研究中，最优化问题是个主要的l 、u j 题形式之一。若只有一 个目标函数的优化问题称为单目标优化问题，若目标函数超过一个并且需要同时 处理的最优化问题称为多目标优化问题( m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m s ， 简称m o p s ) ，它可以描述为：一个由满足一定的约束条件的决策变量组成的向量， 使得一个由多个目标函数组成的向量函数最优化。目标函数是性能标准的数学描 述。对于多目标优化问题，可能出现一个解对其中一个目标函数来说是较好的， 但对于其他的目标函数来讲，可能是较差的，因此，在多目标优化问题中，我们 不可能求出一个使得所有的目标方程都是最优的解，而是求得多目标函数的整体 性能最优的解的集合，称之为p a r e t o 最优解集( p a r e t o o p t i m a ls e t ) 或者非支配解 集( n o n d o m i n a t e ds e t ) 。 随着社会和经济的发展，人们研究设计了各种多目标问题的优化方法，并成 功的解决了社会生活中的问题。目前，多目标优化解决的问题规模朝着大型化发 展，并且在经济规划、金融决策、军事等领域发挥着巨大的作用。 2 2 多目标优化问题描述 一般的多目标优化问题的都可以用以下的数学模型定义： 寻找一个决策向量x = i x ，x ：，x 。】7 ，它满足下列条件： f ( x ) = ( 石( x ) ， ( x + ) ，l ( x ) ) ( 2 1 ) ： 孝 妻；三爱二二l i ：二土； c 2 2 ， 在式( 2 一1 ) 中，m 是待优化目标的个数，各目标之间的关系常常是相互制约 冲突的。多目标优化的目的就是寻找x = ( 玉，j r 2 ，毛) ，使目标函数f ( x ) 在满 足约束( 2 - 2 ) 的同时达到最优。 在多目标优化中，有的目标函数需要寻找其最大的目标值，而有的则与此相 反。甚至在同一个多目标优化问题中，还会出现目标函数的优化方向不一致的情 况。对于这样的问题，一般首先要将各个子目标函数的统一转化为寻找其最小目 标值。可以用下式的形式表示： m i n 厶( x ) = m i n ( 一厶( x ) ) ( 2 3 ) 同理，不等式约束 8 硕p f 节论文 g ，( x ) 0( i = 1 , 2 ，k ) 可以转化为下式： 一g ，( x ) 0 ( i = 1 , 2 ，k ) ( 2 4 ) ( 2 5 ) 通过这样的方法，任何多目标优化问题的统一转化为寻找最小目标值。 另外，上式中g ，( x ) 为不等式约束条件，h ，( x ) 为等式约束条件。 不带约束条件的优化问题较无约束优化问题，带有约束条件的优化问题称之 为约束优化问题。若优化目标函数并口约束条件均为设计变量x 的线性函数，那么 这样的优化问题称为线性规划问题；如果优化目标函数和约束条件中有一个或者 一个以上是设计变量x 的非线性函数，那么称之为非线性优化问题。若目标函数 为设计变量的二次函数，而约束条件为设计变量的一次函数时，那么该优化问题 称为二次规划问题。 多目标优化问题的最优解的标准分为非p a r e t o 机制和p a r e t o 最优。 前者的基本原则是通过加入决策者判断，缩小多目标问题有效解集的范围。 而后者的基本原则是用多目标问题优化解的自身特性来搜索多目标问题的有效解 集的范围。目前的多目标优化问题的研究中，大多数集中在非劣解集的搜索，很 少考虑决策者的偏好，而在实际的多目标优化问题中，决策者必须要在众多的解 集中做出一个选择。据此引出了两个概念：优先因子和权系数。下面我们举例对 这两个概念进行解释。 一个规划问题中，对于多个目标，决策者根据主次或者轻重缓急，认为a 要 求为第一位要达到的目标，赋予了优先因子只；次位的目标赋予了优先因子b ， 且只 - 只 ，即首先保证只级目标的实现，这时可以不考虑次级目标，而只级 目标是在只级目标的基础上考虑的。权系数与优先因子是相关的，例只最优先那 么，对应的权系数w l 最大。 优化问题求解的方法大致分为三类：直接法、解析法和智能优化方法。 随着以解决问题的同益复杂，越来越多的研究集中在智能优化方法中，目前 使用较多的智能优化方法有粒子群优化( p s o ) 、蚁群优化( a c o ) 、人工神经网 络( n n ) 人工免疫系统( a i s ) 和进化算法( e c ) 等等。 由于进化算法能够同时处理一组可能的解( 群体) 并在一次算法过程中就可 以找到p a r e t o 最优集中的多个解，而且进化算法还能够处理多非线性问题，不局 限于p a r e t o 前沿的形状和连续性，易于处理不连续图形的p a r e t o 前沿。到目前为 此，还没找到其他比进化算法更能有效地解决多目标优化问题i i 6 1 。 2 3 进化算法 进化计算( e c ) 的目标是模拟自然进化的过程，其主要概念是适者生存： 弱者必须死亡。在自然进化中，生存是通过繁重实现的。由两个( 有时多于两个) 9 t 、j p 机器人最优轨迹规划动f 宄 父代繁殖的子代继承了父代两个( 或所有) 的基因一希望是父代每一个个体的最 好的特征。那些继承了差特征的个体贝i j 较弱，会在生存竞争中失败。 进化算法利用一个群体，这罩个个体被称为染色体。一个染色体定了种群 中个体的特性。每一个特性称为一个基因。一个基因的值称为一个等位基因。对 每一个l 址代，个体相互竞争以繁飧后，f 弋。具有最强尘存能力的那些个体才有最大 的机会繁殖。子代是由父代的各部分结合产生的，这个过程称为交叉。群体中每 个个体还会经历变异，它将改变染色体的某些等位基冈，一个个体的生存强度是 用一个适应度函数来度量的，它反映了所求解问题的目标函数和约束条件。每一 世代之后，个体经过被选择，一些个体会生存到下一代( 称为精英) 。另外，行为 特征( 包装为表现型) 能够以两种方式影响其进化过程：表现型可以影响基因变 化，或和行为特征分别进化i l7 1 。 进化算法已经成功地用于大量现实应用，例如数据挖掘、组合优化、故障诊 断、分类聚类、行程安排和时问序列逼近。 人们已经提出了不同类型的进化算法( e a ) 。 ( 1 ) 遗传算法：对遗传进化的建模。 ( 2 ) 遗传编程：基于遗传算法但个体都是程序( 用树表示) 。 ( 3 ) 进化策略：侧重于策略参数的建模，这些参数控制了进化的变异，即进化的 进化。 ( 4 ) 进化规划：来源于对进化中自适应行为的模拟( 表现型进化) ( 5 ) 差分进化：与遗传算法类似，只是所用的繁殖方法不同。 ( 6 ) 文化进化：是对一个群体的文化进化和文化如何影响个体的隐性型和表现型 的进化的模型。 ( 7 ) 协调进化：这罩的初始“哑”个体是通过协作或相互竞争来进化以获得生存 的必要特性。 进化算法是一种对给定问题求最优解的随机搜索方法。该进化搜索主要受到 以下几个部分的影响。 ( 1 ) 对问题的解编码 在进化算法计算中，每个个体都代表一个优化问题的备选解：个体的性状由 染色体表示。而性状是指最优化问题所搜索的变量，每个需要优化的变量称为基 因。这些变量在可行域中的一组值叫等位基因。个体的性状可以分为两类进化信 息：基因型和表现型。前者描述了个体的基因组成，它继承于父代。后者是一个 个体在特定环境里所表现出的行为特征，它定义可个体的样貌。在设计进化算法 中，一个重要的步骤是找到备选解的合适的表示方案。搜索算法的效率与复杂性 很大程度上依赖于这个表示方案，不同的典型方法中的不同进化算法使用不同的 表示方案。 1 0 硕y 7 ：1 节论文 ( 2 ) 适应度函数：用来求适应度的函数，测试个体的生存能力。 在达尔文的进化模型罩，j 爿j 有好的性状的个体获得生存和繁殖的机会更大。 在进化算法中，为了确定一个个体的生存能力，我, f f - j 用一个数学函数来表示染色 体所表示的解有多好。适应度函数在进化算法中非常重要。进化算子如选择、交 叉、变异和精英策略，都会用适应度函数来评估染色体。 ( 3 ) 初始化 应用进化算法解决问题的第一步就是产生一d - 初始解。产生的初始种群的标 准方法是在可行域中产生随机值，并分配给每个染色体的每个基因随机选择的目 标是为了确保初始科一群在整个搜索空l n j 中均匀的表示。如果初始种群没有覆盖搜 索空问，那有可能使得为覆盖区不被搜索。 初始化种群的大小会影响算法的计算复杂性和空间探索能力。大量的个体白邑 够增加多样性，进而提高种群的空间搜索能力。但是，个体越多，每代的计算量 越大。当每代的计算时间增加时，可能只需要较少的代数便能找到可以接受的解； 另一方面，一个种群的个体数量小，那么只能搜索空间中较小的部分。虽然每代 的计算时间减少了，但是进化算法需要更多的代数才能收敛得到一个与大种群夺目 当的结果。当然，如果使用小个体数量的种群时，增加变异的频率，那么可以迫 使进化算法探索更多的搜索空间。 ( 4 ) 选择算子 选择是进化算法中的一个主要算子之一， - e 的主要目标是获得更好的解，通 过进化算法中的两个步骤完成： 第一个是新种群的选择：在每代结束时，一个由备选解构成的新种群会被选 择作为下一代的种群。新种群可以仅从后代中选择，或者同时从后代与父代中选 择。选择算子的目标是确保优良个体能活到下一代。 第二个是繁殖：后代通过交叉或者变异算子生成。在交叉中，优良个体有更 多的机会去繁殖，从而确保后代包含最好个体的基因。在变异中，选择机制关注 的是劣势个体。目的是引入更好的性状，以增加劣势个体的生存能力。 选择算子有很多种，常用的选择算子有随机选择、比例选择锦标赛选择、- j i i e 序选择、精英选择等等。 ( 5 ) 繁殖算子 繁殖是从选择的父代中应用交叉和变异算子生成子代的过程。交叉是通过组 合随机选择的两个或多个父代个体的基因物质生成新个体的过程。如果选择关注 的是最具适应能力的个体，则选择压力压力可能会降低新种群的多样性而引起过 早收敛。变异是随机改变染色体基因值的过程。其主要目标是是种群中引入新的 基因物质，提高基因的多样性，应用变异的过程要注意不要破坏高适应度个体的 优良基因。为此，变异一般以较低的概率进行。另一方面，变异的概率也可与个 i ：、f k 机器人最优轨迹枷划b 月冗 体的适应度成反比：适应度较低的个体，变异越高。为了提高前期的迭代的能力， 变异概率可以初始为较大值，并随着时问逐渐减少直到最后一代。 ( 6 ) 终止条件 在进化算法中，进化算子不断迭代执行，直到，满足终止条件。最简单的终 止条什是限制进化算法执行的代数或是调用适应度函数的次数。这个限制不能太 小，否则进化算法不会有充足的时问去搜索末知的空间。 除了限制执行时i 、只j ，另一个标准是确定种群是甭收敛。收敛可以形象的定义 为种群变得稳定的时候，也就是说，在种群中没有基因或表现特征改变的时候。 常用的收敛准则有，当连续几代内都没有提高时则终止，当种群没有改变时终止， 当得到一个可接受的解时终止，当目标函数斜率接近零时终止。 前面我们已经介绍了不同类型的进化算法，以及影响进化算法的几个部分。 在这些算法中，以带精英策略的非支配排序遗传算法和差分进化算法性能是比较 好的，下面我们就介绍下这两种算法。 2 4 带精英策略的非支配排序遗传算法 2 4 1 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 是一种全新的高度并行的、随机的和自 适应的优化算法。它主要借鉴了生物进化的一些特征，模拟生物的自然选择和遗 传机制而形成的一种自适应全局优化概率的搜索算法。它主要的概念是适者生存， 在不断变化的环境中，只有刃b 些适应性好的个体才能生存下来，并通过遗传机制 将好的特性传递给其后代。与此同时，在遗传过程或者适应环境的过程中，一些 个体还会发生变异，其中的一些变异有的还使个体具有了适应新的环境的能力。 如此在进化的过程中，生物群体将逐渐的产生出优良的群体，适应环境的变化。 其实以上过程在形式上是一种迭代方法，从选定的初始解出发，通过不断的迭代 计算过程，逐步改善当前解，知道最后搜索到最优解或者满意解。 2 4 2 带精英策略的非支配排序遗传算法简介 非支配排序遗传算法( n o n d o m i n a t e ds o r t i n gg e n e t i ca l g o r i t h m ，简称n s g a ) 是基于g u l d b e r g 的非支配扫f 序的思想，首先被确定设计的非支配解，然后被分配 一个很大的虚拟适应度值为了保持种群的多样性，这些非支配解用它们的虚拟适 应度值进行共享这些非支配个体暂时不予考虑。从余下的种群中确定第2 批非支配 个体，然后它们被分配一个比先前非支配个体共享后最小适应度值还要小的应拟 适应度值这些非支配个体也暂时不予考虑，从余下的种群中确定第3 批非支配个体 该过程一直持续到整个种群都被划分为若干等级为止。n s g a 采用比例选择来复 锘l j 出新一代n s g a 的计算复杂度为o ( m n 3 ) ，其中m 是目标个数，是种群大小， 1 2 硕卜7 ：何论文 其计算复杂度较高，而且需要预先确定共享参数町。 n s g a i i ( af a s ta n de l i t i s tm u l t i o b j e c t i v eg e n e t i ca l g o r i t h m ) 心引是d e b 年i ! 他的 学生针对n s g a 的以下三个缺点于2 0 0 0 年提出的一种改进的带有精英策略