（控制理论与控制工程专业论文）多目标遗传优化及其在机器人路径规划中的应用.pdf

硕士论文 摘要 在胡器人相关技术研究中，导航技术g 口路径规划是核心技术，在朝器天硬件系统的精度 短期内得不至情欲的情况下，对路径规题j 算法的研究尤为重要。本文对多目标遗传算法及其 在耄兀器人路径规划中的应用进行了研究。 本文对基于p 孤幻优化的多目标算法n s g a h 进行了分析，为解决其在高维问题中表现 不佳的问题，提出了基于聚类方法和改进精英策略的多目标遗传算法，该算法在非支配个体 选择过程中采用聚类方法取代n s g a 中的拥挤度方法：在种群非劣分级后，弓j 劣解个体 参加交叉操作，克服了n ! g a 精英保留策略的缺陷，在保证算法收敛性的同时，提高了算 法的多样性。还对钆器 、路径环境进行了建模，把本文算法应用至i | 胡器人路霍溅l 怕勺求解中， 并引入了启发式生成功始种群和自适应i i 司整参数燃更好的实验效果。 仿真结果表明，所提算法与n s g + 姐算法相比，在相同环境下，能够次搜索到更多的 非劣解，可见本文算法在机器人路径颤内l 问题中表现出比n s g a 算珐更好的多样性。 关键词：多目标优化路径规地g a 机器人 a b s t r a c t 硕士论文 p a l h p m m g i sn l e k e y t e c t m o i o g y o f m o b i l e r o b o t t e s e a t c k , f l a er e s e a r c h o f 鼬p l a t m i n g i s v e r y 曲l p 嘲e s p e c i a l l y w h e n 吐l e h a r d w a r e o f r o b o l sc a l m o t r e a c h ah i 曲p f 随i ns h o r t 衄 n t i sp a p e rd o e sr e s e a r c hi nm u l t i - o b j e c t i v eg 鼬a l g 嘶a m aa n d 缸a p p l i c a t i o ni nr o b o tp a t h p l a n n i n g i n s t m i c m o b i l e r o b o t e n v i r a n m m m t h e b a s i c t h e o r y o f g a a n d t h e r e s e a r c h g a i n s o f p 日赶lp i 加痂唱粥蜘m m 捌i n t h i s p a p e a n d a n e w d 卿血m i s 蕊p a d 删b a s e d 0 1 3 a 哪蛐g m 劬0 d a n d i m p r o v e d e l i l i s t 斑嘲t os o l v e t h ed i 辎a 血五e dr e p r e s e 眦a l i o no f n s g a w h e ni ti su s e di nh i g hd i m m s i o m l i t y , t h en e wa l g o r i t h m l l 鲻o u s t e t i n gm e t h o di n s t e a d0 f 跟嘁i x o , e o u 豫w h i c hi su s e di nn s g a l ；t h e nt 曲l g st h e n o n - d i f i 吱i n d i v i d u a l s i n t o t a - c 8 s o v e r o p e r a t i o n t o0 、i 嚣。呲t h e l i m i t a l i o n o f e l i t i s t 蜘m 螂w h i c h i s a i m t o 勰s l e 曲c o m 伍n 删绷d j n 驴黼m ed i v e r s i 哆o f a l 舒时吐n t h d e 、，d o p e d t h e m o d e l o f m o b i l er o b o ta l v j l a 毗慨a n dt h ei 删a l g o d t t m ai sa p p l i e dt ot h er o b o tp a t hp l a n n i n g , 嗣黜k e y t e d m o l o g i e s 辩u s e di na 嘶n g 证砌g e l l e l a l i o l la n dl x u a m e a x ss e t t i n gi no r d e r 的g e tb e t t o r e x l x x i m e n t r e s u l t t h es i m u l a t i o nr e s u l t sh a d i c a t ef l a a t , c 0 删肛e dt on s g a i nt h es 黜即埔栅m 日也t h e 脚 a l g 瑾i o m a c a ns e a r c h o u t m o r e n o n - d o m i n a t e d i n d i v i d u a l s w h i c h a r e 妇f e a s i b l e p a t h s , a n d i m p l d v 苍 讥ed i v c 嫡哆o f t i l ea l 蓼t 曲帆 h i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名：年 月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：年月 日 南京理工大学硕士孥垃论文多目标遗传优化及其在机器人路径规划中的应用 1 绪论 i j 机焉| 人路径由咧问题f 目l 述 机器 、技术是综合了计算机、控制论、机构学、信息和传感技术、 、工智能、仿生学等 多学科而形成的高新技术，是当代研究十分活跃，应用日益广泛的领域。机器人应用情况， 是个国家工业自动化水平的重要标志。柳器 、并不是在简单意义e 代替人工的劳动，而是 综合了人的特长和机器特长的种拟人的电予川镕贮装i 置，既有 、对环境状态的快速反应和分 析判断能力，又有桐器可长时间持续工作、精确度高、抗恶劣环境的能力，从某件意义上说 它也是机器进化过程的产物，它是工j k 以及非产业界的重要生产和服务性设备，也是先进制 造技术领域不可缺! p 的自动化设备”。 移动机器 、是种在复杂的环境下工作的具有自规划、自组织、自适应能力的机器 、。 在移动机器 的相关陵= 柯院中，导航技术可以说是其楔c 姝，也是其实现真正的智胄化 和完全的自主移动晦繇越胡趔。 图1 1 胡器 、技术窿用( a ) 机城臂救暖棚器八( c ) s 公司秽1 器狗回火星探隈车 路径规划是移动机器人导航技术中不可缺少的重要组成部分，它要求机器 、根据给予的 指令及环境信息自主地决定路径，避开障碍物，实现任务目标。路径规划是移动机器 完成 任务的安全保障，同时也是移动柳器人智能似陂的重要标卷l 】1 2 1o 尤其是在机器 硬件系 统的精度在短期内不能得至懈决的情况下，对路径规划算法的研究更显得尤为重要，这将从 根本e 改变移动机器人的导航性能，将提商眵动机器人的智力水平，减少移动机器人在移动 绪论硕士论文 过程中存在的不确定状态，高移动机器人移动的速度及灵活性，为开发高智能的远距离搬运 机器人、探测机器k 服务机器 、汽车自动驾驶系统打下基础。 机器人路径规划研究一般涉及到环境表达、规划方法、路径执行3 个方面，产生了以下 四个相关问题： ( 1 ) 杌器人如何从环境中有效地获取周围的障碍信息和其它相关信息。 ( 2 ) 机器 、如何根摒内部及外利糍麴睐回答当前处于j 也图中什么位置。 ( 3 ) 棚器 、如何根据其处于当前地图的位置和当前地图中信息确定行动策略。 ( 4 ) 如何产生合适的驱动信号使机器 、运动在预定的轨迹匕。 路径规划问题具有如下特点p ： 复杂性：在复杂环境尤其是动态喊妻研磺中，机器人路径规划非常复杂，且需要很 大的计算量。 随柳性：复杂环境的变化往往存在很多随机性和不确定因素。动态障碍物的出现也 带有随机性 多约束：机器 鲍运动存在几何约束和物理约束。月何约束是指机器 、的f 眵状制约， 而物理约束是指机器人的速度和加速度。 多目标：机器人运动过程中路径性能要求存在多种目标，如路径最短，时间最优， 安全陛能最好，能源消耗最小。但它们之间往往存在冲突。 典型的路径规划问题的提法是给定个移动机器 、所处的环境( 环境可以通过移动机器 人视觉系统或者别的途径获葡，个起始点和个期望的终点，移动机器 路径规划就是根 据一定的任务要习之( 路径最短、消耗能量最少或使用时间最短韵寻求条连 斑点到终点且 能避开环境中障碍物的移动机器人的运动轨迹，即最优或次优有效路倒”。因此，机器人路 径规划是个有约束的优化问题。求解这个问题要进行大量的运算，并且其复杂性随自由度 的增加成指数增长。研究者为寻求高效的解决方案提出了许多方法，但依然存在不少的困难。 近年来有很多学者运用人工智能韵些方法来解决路径规划的问题，取得了不错的效果。 比如神经网络法，遗传算法等等。但大多是在些复杂的静态环境下，而对于环境售袁嗡为 复杂的动态环境，国内外的学者探讨的还不是很多。机器 、路径的规划是机器人控制策略当 中的个重要分支。如果机器人能够像 、样根据变化的环境自由的选取合适的路径，那么 这样的机器 控制策略已经非常成功了。但是从目前国内外有关这方面的研究现状身e 看，距 离这一目标的实现还有较大的差距。 近年来，随着人工智能应用领域的不断扩大，传统的基于符号处理机制的人工智能方法 在知识表示、信息处理和解决组合鼠蚱嘞面所遇到的困难越来越明显，从而使 导寻求种 适合大规模问题并具有自组织、自适应、自学习能力的算法成为研究目标。受生物进化论的 2 南京理工大学硕士学位论文多目标遗传优化及其在机器人路径规划中的应用 启发，j 月0 丑觚d 教授于1 9 r 7 5 年提出了遗传算法( g c 氆l i c 啦娜吐皿s ，简称g a ) 闻。g a 是基于“适 者生存”的种高度并行、随机和自适应的优化算法，他将问题的求解表示成“染色体”的 适者生存勰，通过“染色l 体”群的州弋进化，最终1 5 潋到“最适应环境”的个体，从而 求得问题的最优解或满意解。g a 是种通用的优化算法，其编码技术和遗传操作比较简单， 优化不受限制性条件的约束。其两个最显著特点则是隐含并行性和全局解空间搜索。目前随 着计算秽廿支术的发展，g 鲥逮来越得至研究 、员的重视，并在机器学习，模式识别，图像处理、 神经网络、优化控制、组合优化等领域得到成功应用吼吼陬阎。 由于传统伊讹方法在机器 、路径规射i 这类复杂非线性优化问题中缺乏自适应性，计算太 复杂，不能对些不确定性正确响应，优化过程缺乏鲁棒性并缺乏替代路径，因此遗传算法 在朔器人路径规翅i 中的应用研究得到科研人员的高度重视，也取得了一定的成果。但是从目 前国内外有关这方面的研究昵状来看，路径规划的策略仍然难以适囱觅实的复杂环境，采用 多目标遗传算法应用于其中正是研究热点之一，还有很多难题有待解决。因此在前 、研究丽 基础e ，尝试将多目标遗传算法应用到复杂环境下机器人路径规划中，具有定的乖阿f 意义。 及应用前景。本文就致力于这方面的研究。 1 3 机器入路径规划的研究现状 机器人的研究发展迅速，应用的范围十分广泛，就目前来看，机器人的发展仍然处于初 级的阶段，需要去完成的工作仍然很多，特别是在许多具体的环境中仍要具体问题具体分析。 ( 1 ) 静态确定环境路径规划 棚器 、在确定已知的环境下的路径期踟j 研究己经茫于较为威：熟的阶段，现有以下错典型 的方法，分别是位姿空间法、图搜索法、 、工势场法和导航法。 1 ) 位姿空间法 位姿空间法是由tl 0 珊n 阳嗽和m 丸w 鼬掣等人在1 9 7 9 年提出的神无磁崮酌至规划 算i ；掣。基于位姿空间法提出了可视图法g 唧崎旧。该方法将所有障碍物的顶点和机器人 起始点及目标点用直线组合相连，要求柳器人和障碍物各项点之间、目标点和障碍物各项点 之间以及各障碍物顼点与顶点之间的连线均不能穿越障碍物，即直线是“可视的”，砂而产生 条路径。 位姿空间法假设机器人的尺寸大小忽略不计，会使期器人通过障碍物顶点时离障碍物太 近甚至接触，并且搜索时间长。另外该方法缺乏灵活性，即一要机器人的起点和目标点发生 改变，就要重新构造可视囹1 1 1 。 2 ) 图搜索法 图搜索法根据棚格法或栅格解耦法将整个环境翅| 分单元，并将单元视为节点，其间相关 关系用弧线柜连，得到个连通图，h 而将路径规划问题就演变为点间搜索路径的问题。r 九 3 绪论硕士论文 b 1 0 0 咖10 z m 明h 眩提出的切分法，将位姿空间切分为块块的单元，然后搜索相邻单元 组成的连接图。但是切分单元的数目随着精度的提高而迅速膨胀为了提高表示的效率，人们 采用层次结构表示。a e f c s 捌提出的网络模型，将确定性的网络用于离线的全局规划。s u b b e 瑚 & 叨b b 粗瑚丘采用不完全四叉树表示工作空间，将叶节点连接成张拓扑图，规划出满足性能 的指标路径。从严格意义e 看，位姿空间也属于图方法的种。 3 ) 人工赞场法 人工势场法是由l a i b 提出的种虚拟力澎1 3 o 它的基本思想是将机器人在周围环境中的 运动，设计成种抽象的人造引力场中的运动，目标点对移动机器 、产生“引力”，障碍物对 移动机器人产生“斥力”，最后通过求合力来控制移动机器人的运动。势场法结构简单，但存 在局部最优解的问题，因此如何设计“引力场”问题就成为该方法的关键。 势场法实际上是试图使障碍物的分布情况及其形状等信息反映在环境的每一点的势场值 中。机器 、的运动是由机器人当前的位置听承受的势场，即其梯度方向所决定。所以它与全 局规划相比具有计算量小，实时性好的特点。 4 ) 导航法 导航法将针对己知障碍所作的全局规划以及实时避碰的局部规划相结合。其中种方法 是沿着墙壁走的方法。机器人沿着墙壁运动，如果遇到障碍物，机器人将障碍物看成是堵 墙处理，沿着障碍物走直到回到预定的全局路径匕。这种导航方法在技术上并不复杂，但是 在实际中很难执行。 ( 2 ) 动态嚏娇境路径规划 过去对路径规划的研究大都集中在静态环境中，而机器人的实际工作环境中往往是动态 的。r d f 和s i 证分析了动态环境中运动规划的复杂性问题，研究表明，处理动态a 不境中的 运动规划比静态环境下复杂的多，因此，已有的静态规划方法很难推广到动态不确定环境中 去，而动态规划方法还未形成套系统的方法和理论，下面就介绍n 州影手来提出的n 个具 体的解决方法。 k 龇和五l c 蚶l 田提出了两极期9 a 肱，谚沩程建躺列环境中的静态耩嚼物规划出 蒜最 短路径，然后腔粒朗器人沿着规划好的路径运动，并通过调整机器人的运动速度来避开动态 障碍物。这种方法虽然大大减少了问题的搜索空间，但存在很大的缺陷，如预定路径不能依 照环境的最新变化而变化，一旦有障碍物停留在预定的路径上，机器人就无法到达目标。 e r d n m n 和io 捌静删坍研究了多个运动物体在静态环境中的规划问题，当运动物体每次 改变它的速度就萤社 一次位姿空间，这种方法需要大量的计算。母d 肼d e v i 甜1 句等将运动时间 划分成卜化j 、区间，并且设定在每个时间片中，障碍物的位置和速瑟均能预知。通过构 造潜在的碰撞区，利用启发式知识引导速度向量朝向优化的路径。q i m 嘴2 h u 【l7 1 针对动态障 碍物的避碰提出了运动机器人的视觉引导模型和控制策略。用随机过程描述障碍物的运动， 即采用隐式马尔科夫模型描述和预测动态环境下障碍物的运动。未知速度、加速度等参数均 4 南京理工大学硕士学位论文 多目标遗传优化及其在机嚣人路径规划中的应用 用概率分布函数预测。规划过程中循环选择个蒯加速度向量。 路径规划的问题尚处在不断的发展和完善之中。该问题盼本晚唇葩【 乍环境中为机器人 规划繁优化的运动路径，关键芷。于如何黼环g 雅隐。全局规划甑融蠕鞘中的全部 先验信息，而机器人的工作环境大部分是动态时变的，很难准确预隗而局部规划的方法强调 避融所亍为，虽实时性6 子，但是由于缺乏规划而丧失t f 己化自筘点。最佳的旃菇姨注全局翘划 的基础e ，进 偏部微调，提高规划速度及精度，同时具有定的灵活性，可以互相结合， 取长补短。此外还有优化问题，现有的静态环境中的路径规划法都追求全局最优，对于较大 规滇自搠域，计算量走，目难于适应喇鹤啊觏揍轼伏的魂柳把羽磺，更刁：硬于实时实 现。如何优化才能使问题求解规模大大减小，便于解决 匕较复杂的问题和便于实时实现也是 值得探讨的闯题。 论文的主要内容如下： 第章：简要介绍了棚器人路径规划及其 哩论意义和工程背景，重点介绍国内夕瞬陋规 划的研究现状。 第二章：介绍了遗传算法的基本慨念和基本理论以及用遗传算法解决组合优化问题的常 用策略。对遗传操作的关键算子，如选择、交叉和变舜敢了详细的介绍。 第三章：介绍了两种用于同时找到多个p 锄奶最优解且采用最优保存策略的多目标遗传 鲻嗟：s p f _ - a 2 和n s g ai i ，在n s g ai i 的基础上，重点介绍本文提出懈聚钫祛和改进 精英策略的多目标遗传算 基给出了拿鼓去框图，详细叙述了改进的方面燃的问题，并在 四个；! 受i 腻函数上与n s g a i i 做了分析与比较。 第四章：主要介绍针对已知静态障碍物的环境下基于本文算法的优化路径规划的实现。 给出了本文实现路径规妣疗法的总体构架，重点讨论了适应度函数的设计与实现。详细介绍 了遗僦的3 个基本算子：选甄交叉，变异的具黼i 翊至。着重 i ：寸论了优化算子的主 要思想和在协喻晰雕扫朔姐参数设置中引入的一些关键方法。 第五章：根据e _ 溯舫法实现了路径贼帕m 籼仿真，详细分析了仿真结 果并得出结论。 最后对论文的工作做总结并对今后的工作做出展望。 5 南京理工大学硕士学位论文 多目标遗传优化及其在机器人路径规划中的应用 遗传算法( g e n 锄血a l ：酌劬n b ，g a ) 由美国j 盥0 丑锄d 教授于1 9 7 5 年在其著作自然系 统和人工系统的适配( a d a p 碰缸a l 删锄d a l 匝d a l s y s t e m s ) 中提出，是模拟自然界生 物进化过程与机制求解极值问题的类自组织、自适应人工智能技术。它模拟达尔文的自然 进化论和孟德尔的遗怒啪论，具有坚实的生物学基础：它提供从智能生成过匿昵点对生 物智能的模拟，目适合于无表达或有表达的任何类实际问题，具有广泛的应用价值。因此遗 传算法在i 雪内外备受重觋目前已经西俐：、机器学习和并行处理等筑晦b 得到了越来越广泛 的应用坷。 在介纽遗传算法之前，有必要了解有关生物进化理论和遗传学的基本知识。下面给出一 些生砑掸的基本概念与术语嘲，这列霹嘟谳算 南影艮彀的。 晏 色体( c t n o m a m m e ) 是遗传物质的主要载体，由多个遗传因子基因组成。 遗传因子( g e n e ) 基本遗传i 位，也称作基因。 基因型( 蛳) 遗传因子组合的模型，是性状染色钵的内部表现。 表现型( p i l 0 t y p e ) 由染色体决定性状的外部表现，即根据基因型形成的个体。 个体( i n d i v i d u a l ) 指染色体带有特征的实体。 种群( p o p i l l 砸) 个体的集合。该集合内个体数称为种群大小。 进化( e v o l u t i o n ) 生物在生存过程中逐渐适应生存环境，使表现型不断改良，称为进化。 适应度( f i t n e s s ) 度量某个物种对生存环境的适应程度。 选择( s e l e c t i o n ) 以一定的概率从种群中选择若干个体的操作，是种基于适应度的优 胜劣汰的过程。 交叉( a i 嘀眦) 在繁殖下代时两个同源染色体之间通过交叉而重组，这个过程称为 基因重组。 变异( m u 碰o n ) 在个体复制时可能以很小的概率产生某些复制差错，使d n a 发生某 种变异，产生新的染色体从而表现出新的性状。 编码( c o d 缸培) 从表现型到基因型的映射。 解码( 出c o d i n g ) 从基因型到表现型的映射。 引用以e 术语可以很好地描述遗传算法的基本思想：遗传算法是从代表问题可能潜在解 集的个种群( p o p i | 雠m ) 开始的，而个种群则由经过基因( 蓼) 编码( c o d h l g ) 的一 定数目的个体( h 】d i v i d e a l ) 组成。每个个体实际上是染色体( c l l 唧啪8 咖) 带有特征的实体。 染色体作为遗传物质的主要载体，其内部表现( 基因型) 是某种基因组合，它决定了个体性 状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。初代种群产 遗传算法原理 硕士论文 生之后，按照适者生存和伊曲甥汰的原理，逐代( g 骶f 撕) 演化产生出越* 蝴的谢以解。 每代根据问题域中个体的适应度( f i a 】簋s ) 大，j 谢哒( s e l c c f i ) 个体，借叻于自然遗传学 的遗传算子( 渺o p e 胁嘶) 进行组合交叉( 味觥) 和变异( m u m i i o n ) ，产生出新的种 群。这个过程将使种群像自然进化样越来越适应环境，末代种群中的最优个体经过解码 ( d e c o d i n g ) ，可以作为问题近似最优解。 遗传算法在激励方面具有搜索过程和优化杌制等属性，数学方面的性质可以通过模式定 理和构造块假设等分析加以讨论，m s o r 链也是分析遗传算法的个有效工具。遗传算法具 有丰富的动忽睁眭，从数学机理e 加以讨论，有助于遗传算法的理论研究和应用。 r 1 田 2 2 1 模式赢蚕瞪1 种群中个体的相似样板称为“模式”，模式表示基因串中某些特征位相同的结构。而所有的 模式并不是以同等机会产生的。为了定量地描述漠式，引入两个重要参数：模式阶( s d 埘m o r d e r ) 和定义距( d e 丘r l 矗培1 则啦) 。 模式定理：在遗传算亏链择、交叉轻变异的作用下，具有低阶、短定义长度并目平均适 应度高于群体平均适应度的模式在子代中将得以指数级增长。 模式定理是遗传算法的基本理论，保证了较优模式( 遗传算法的密优解) 的数目呈指数 增长，为解释遗传算法提供了种数学工具。 z 垃积木块侵甜删 在模式定理中所指的具有低阶、短定义距以及平均适应度高删平均适应度的模式定 义为积木块( b u i l d i n g b l o c k ) 。它们在遗传算法中很重要，在子代中呈指数增长，在遗传操作 下相互结合，产生适应度更高的个体，从而找到更优的可行解。 积木块假设( b u i l d i n gb l o c kh y p o 吐l e s i s ) ：遗传算法通过短定义距、低阶以及高平均适应 度的模式( 积木块) ，在遗传操作作用下相互结合，最终接近全局最优解。 满足这个假设的条件比较简单，包括两方面： 表现型相近自勺，个体，其基因型劐以； 遗传因子间相关陛 氐 n 埘 圮3 收敛性分析1 我们给出g a 收敛的精确定义：设z 。= m a ) 【 ，( 及( i ) ) ：t = 1 ，2 ，” 是个随机a 眨量 序列。该变量代表在时间步t 状态中最佳的适应度。g a 收敛至l 拴局最优值，当且仅当： l i m p z , = f 1 = 1 。则保留当前最佳个体的g a 可以收敛至全民最优值。 虽然g a 能够以概率1l 渐问题最优解，但如果收敛速度太匣也无法解决实际问题， 所以旮鹋捌收濒蠕谶行| 分析，懒崩导至嵘解效率，又 雠女潞的质量。 从解空间的某一点x 出发，作向其临界点的随机漫游 而) ；并确定各漫游点的适应瘦函 数 ，( 五) 】。以i 舌应度f 为随机变量，则该随机漫游过程中所得到的适应度函数的自相关函 数可定义为： 加魄专砉匦铲 ， 式3 - x 中，f 表示随初0 爱量的适应度的平均值；盯( f ) 焘! 示隧r 秽强跫量的适应度的枥潍编 差。随机漫游的结果表明：对于许多组合优化问题，适应度函数的自相关函数是以某相关 长度之为参数翱或的： p ( 咖唧( 兹 相关长度意味着当前搜索点的适应度函数和相关长度以前的点无关，它对相关长度以 前的点来说，是呈随机摆动的趋势。因此，函数优化时，应按相关长度之把可行鹪区域分割 为些小的区域，并目相关长度越短，需分割的份数越多。 遗传算法主要由六个部分组成编码方式。初始群体产生的方法、评价函数、遗传操作、 算法终止条件、算法参数的设置。要利用遗传算法成功地解决非线性规划问题，每个部分的 设计都非常关键。 2 3 1 编码方式 g a 的编码就是解的遗传表示，是应用g a 求解问题的第步。h o l l a n d 提出的编码符号 集由二进制符号o 和1 组成，因此实际的编码串是个= 进韵腑号串，其优点在于编码、解 码操作简单，奴、变异等遗矧剿乍便于实现；其缺点在于不便于反匣所求问题的特殊知识， 对于些连续函数的优化问题，由于遗传算法的随机特性而使得其局部搜索能力较差，对于 些高维高精度要求的连续函数口讹，二进制编码存在着连续函数离散时的映射误差。后来 有学者提出了改进的编翟捌基例如，为提高遗传算法的局部搜索能力，提出了格雷码( c , - m y c o d e ) 编码：为改善遗传算法复杂性，提高运算效率，提出了浮点数编码、符号编码 j 珐；此外礴多参数级联编码和交叉编码方法，近年来随着生物计算理论研究的兴起，有 人提出d n a 编码法并在模糊控制器口讹的应用中取得很好的效梨闭。 2 3 2 适圄嘲翻配财姐嗽 遗传算法自斟燃中基本1 硎用外音刚言息，仅以j 吞应度函数( f m e s sf u m 砸o n ) 为依据， 利用种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要，直接影响到 9 遗传算法原理硕士论文 遗传算 去的收敛速度以及能否找到最优解。一般来说，适应度函数是由目标函数变换而成的。 对目标函数值域的某种映射变熬称为适应度的尺废翌抉o i m e 鹤s c a l i n g ) 。 适应度函数基本匕有以下三科1 田： 直接以待求解的目标函数转化为适应度函数。这种适应度函数简单直观，但存磕两 个问题：其是可能不 薪足常用的轮盘赌选择中概率非负的要求；其二是某些待求解的函数 在函数值分布匕相差很大，由此得到的平均适应度可能不利于表现种群的平均性能，影响算 法的性能。 若目标函数为最小问题，则： 只f ( m ) ) = i o , - - f ( x ) , 。妇f 工 ( 2 4 ) 式中c 。为f ( x ) 的最小值估计。 若目标函数为最小闯题 f i t ( f ( 工) ) 2 南 若目标函数为最大问题 e - 0 ，c + f ( x ) - 0 ( 2 5 ) 砌( m ) ) 5 雨南c 0 c m ) 0 ( 2 6 ) 适应度函数的设计主要满足以- f g t ：拉l 】： 单直、连续、非负、最大比； 合理、致性要求适应值反应对应解的优劣性； - 洲, g m d 、适应度函数设计应该尽可能简单，i 割e 4 _ = - - j 以减少计算时间和空间上的复杂 性，刚氏计算成本； 通用性强适应度对某类具体问题，应该尽可能通用，最好勿需使用者改变适应度函 数中的参数。 2 3 3 遗传操作 ( 1 ) 选择 选择策略对黉鞋性能会起到举足轻重的影响。不同的选择策略将导致不同的选择压力， 即下代中父代个体复制数目的不同分配关系。较大的选择压力使最优个体具有较高的复制 数目，从而使得算法 叟= 岗翦蔓较快，但也较容易出现过早收垒卿象。对于非线性规划问题来 1 0 南京理工大学硕士学位论文 多目标遗传优化及其在机器人路径规划中的应用 说，就是容易陷 蔚爵隅忧。 下面是遗传算法中较常用到的n 剥嘲幽功法： 1 ) 轮盘赔选择法( m u l e n e w h e e l s e l e c a o n ) 这是最简单的剥q 龟障方法。为了选择瘦氟研唯降渐多轮选择。先计黉聊懒相列适应 度n = 正正，然后根据选择概率 a ，i = 1 ，2 ，n 】把个圆盘分成n 份，其中第i 个扇形 的中心角另2 # 聃。进行选择时，每轮产生个【o l 】均匀随机数r ，将该随机数作为选择 指针来确定被选择个体，若 n + p 2 + + a l r a + p 2 + + p f ( 2 刀 则选择个体i 。如表2 - 1 所示，第轮随机数为0 8 7 ，则个体5 被选中；第二轮随即数为 0 4 5 ，则个体2 被选中；以此类推。显然，个体的适应度越大，它被选择到的机会也越大。 从而其基因结构被保留到下代的可能性| 眭瘟g 大。 表2 - 1 轮盘贼刳争个劂 个体l2 345 6 适应度 1 21 4 -o ，81 60 60 4 选择概率 o 20 2 30 1 30 1 2 60 1唧 累计概率舵 m 4 3o 5 6 0 8 2o - 9 2 l 2 ) 锦枥谨瞬僦( t o m - a a m e m s e l e c t i o n ) 在锦标赛选择法中，随机地从种群中拶瞄基一定数目的个体，然后将最好的个体选作父本。 这个过程重复进行完成个体的选择。锦标赛选择的参数为竞赛规模t o u r ，其取值范围为 2 n i n d 。表2 - 2 表示了竞赛规模与选择强度之间的关系。 表2 - 2 竞赛规漠与选择强度问的关系 选择；踱：&砌(to“r)=2(109(tour)-log,44114log(tour) lm 多桦 匕损失：工挪妒嘞h ( 扬比r ) = z 饥r - 丽鬲一勋r 丽 ( 2 9 ) ( 2 ) 交叉 交叉即是把两个父本的部分结构加以替换重组产生新个体的遗传操作。交叉式遗传算法 获得新优良个体的最重要的手段。本文采用的是双点交叉，在以二进制交叉为例做简单介绍： 二- 进带! 】交叉中有单点交叉、多点奴和均匀交叉阻圆。 l l 遗传算法原理 硕士论文 ( d 单点交叉交叉点k 的范围为【1 ，n v a x - 1 ，n v 孤为个体变量数目，在该点为分界相互 交换变量，如图2 1 所示。 父个体 i 子个体 i 图2 1 单点交叉 ( 萤多点交叉对于多点交叉，m 个交叉位置墨可以无重复地随机选择，在交叉点之间的 变量间续地才耳互交换，产生两个新的个体，如图2 2 所示。 父个体 图2 2 多点交叉 子个体 均匀交叉单点和多点交叉的定义使得个体在交叉点处分成片断，均匀交叉则更加广 义化，使每个点都成为潜在的交叉点。随机地产生予个体 争长的0 - i 掩码，掩码中的片断表 明哪个父本向子个阚是供变量值。 除了上述交叉= 号法之外，还有部分四氢饺叉、顺序交叉、循环交叉秘院牌交叉等。 ( 3 ) 变异 变异即个体变量以很小的概渤长产生转变，变量转变的概率目涉长与耋匡! 嫩比， 与种群大小无关。x 于于多峰函数解的自适应j 墩i 生台昱彳贿益处。变异本身是_ 种局部 随阢搜索，与选择、交叉结合在趣，保证了遗僦脯效陛，使得：遗 传算法具有局部的 随秽蠓能力，同时 吏j 韩女持了种群的多十矧幽，下面是常用的变异策略： 均匀至瞬设j = ( v 1 ，v 2 “) 是父解，z = ( z 。，z ：z 。) 是娣产生的后代。均匀变 异是：先在父解向量中随机地选择个分量唯，然后再其定义区间( q ，玩) 中均匀随机地取 1 2 南京理工大学硕士学位论文多目标遗传优化及其在机器人路径规划中的应用 个量v ，替代v 。以得出z 。如果只选择个分量进行交异，称为单点变异；着有多个分量 进彳j ：变异，则称为多点变异。 自适应变异结合模拟退火算法中的温度概念来说明自适应变异的原理。设 j - - - ( v l ，v 2 ，) 是角孚空间的个向量，( s ) 是它的适应值，厶。是所解问题的最大适应值， 则陵渭激定义为： r ：1 一坤形 ( 2 1 0 ) 自适应变异是现在父解向量中随机选个分量唯7 替代吒以得出z 。 唯= k + ( 7 ，钆一k ) 如罘伽d ( 2 ) = o ； 。，。 心= 唯- a ( t ，巩一心) 如果瑚d ( 2 ) = l ； 这里啪d ( 2 ) 表鹬觥生的正塞篁；| ! i 蟆2 所得的结果。t 为变异温度，而函数( t ，y ) 的值域为【o ，y 】，并使得当t 减小时，a ( t ，y ) 接近于。的概率增加，从而使得算法在演化初 期能搜索至蝇扶的范围，而在后期主要是进行局部搜索。 2 3 4 遗传算法参数选择 在运行算法时，需要对些参数做事先选择，它们包括种群的大小、染色体长度、交叉 率、变异率、最大进化代数等，这些参数对遗传算法的性能者隋很重要的影响。如果能在演 化过程中，程序自己不断的调节这堂参数，就能使算法适用于更多类型的问题。 参数的调节方式大致可以划分为三类：确定性调节，适应性调节，自适应性调制”。 确定性调节方式是指参数的调节方式是靠事先确定好的策略调节的，这种调节没有用到 解的反馈信息，只用到了时河信息。例如在变异策略中，可以在前面_ 丌代中使用大的步长变 异，而当收敛到一定代数后使用步长较小变异。i 塞里只用到了代数这个参数，并没有其他 关于群体的反馈信息。 自适应调节哆黾指将参数作为个体的一个梁造。体和其他需要优化的参数起用遗传算 法进行i 优化。参嬲骨符本身就是假杂的抛化j 立程，而遗传算法本身也是种优化算法， 既然遗传算法可以用来蚀蚓隧眺捌问题，也应i 亥可以用来优化自身的参数。这种方法己 经成功地用于交异算子，杂交算子和群体大小的优化。但是这种方法并不适用于罚函数的参 数调节。与杂交和变异算子的参数不同，罚函数的参数自接影响到个体的适应值，而杂交和 变异算子的参数并不参与适应值的计算。 弘多目标剐训眦的帕瞄沭 在多目标优化和单目标优化问题中分别使用遗传算法，最大的区别是对个体适应度的评 。 1 3 遗传算法原理硕士论文 价。单目标仿比问题中，个体的性能由目标函数隹涞度量，因l 幽吲嗵应压瞄往就等于目标 函数值或者对目标函数值进行适当的数学变换。而在多目标优化问题中，由于同时存在着多 个相互矛盾的目标，使得洽当的选择机制，特别是如何对个舒适应值进彳亍j 置当的评价，成为 遗传搜索算法最终能否收敛到p a r e t o 最优解集的关键因素。 遗传算弦求解多目标优化问题有两个性能要求：是保证算法的收敛性，即在目标空间 中，所求得的p a r e t o 最优解集与实际的p a r e t o 最优解集应尽可能的接近；二是多样性的维 护，即希望找到的p a r e t o 最优解集具有较好的分布特性( 如均匀分布) ，且分布范围尽可能 的宽广调。为了满足以匕要球，通常在m o g a 中设用如下几种技术方法： ( 1 ) 群体多样性的维护 求解多目标优化问题时，为了防止早熟收敛，般希望所得到的解能够尽可能均匀地分 布在整个p a t e t o 最优解集内，而不是集中在某个较小的区域上( _ i t r i w 的遗传漂移现象) 。为 了达至i 趑个要求，目前已发展了两类疗法：小生境技书朗刨、生境技术。 小生境技术的特点是形成并维持多个稳定的予群体，即小生境，让个体商蝴定的生 存环境中翅化。算鞋姗同令喇啊测骱体的数量加以限带9 ，以便能够产生出种类较多的不 同的最优解。小生境法主要有三种：基于预选择的小生境法、基于排脐的小生境法和基于适 应值共享的小生境法闭。其中基于适应直共享的小生境法最为常用。适应筐共享的思想是在 同个小生境中的所有个体必须共享资源。它通过反映个体之间相似程度的共享函数来调整 群体中各个个体的适应度。 非小生境技术中最常见的是参晤哟芽乎口，这是种非随机；晤a 策略。两个差异很大的个 体进行交配可能会产生刁- j 舌当的子孙，甚至是“致命”的因子，因l 比需要对配对重组的两个 个体进行约束。当两个个体在个给定的距离。以内时，才可交配，以形成祀父辈相似的 子孙，减少搜索的风脸性，提高在线性能，保持p a r e t o 前沿e 个体的物种连续性。 ( 2 ) 僦 近几年来发展的几种m o g a ( 如s p e a 2 圆、n s g a - i i l 2 9 1 等) 中都弓l 入了精英的概念， 这是为了防l e 在优化过程中，由于随机因素和群体规模的限制，而丢失了优良解。在单目标 优化中，每代的最优解总是直接保留到下代的群体中，这就是种精英思想的体现。在 多目标优化中使用精英法相对要复杂的多，因为通常在个群体中，存在多个精英。 目前m o g a 中主要有两种使用精英的方式。第种最常见，它使用个外部的群体保 存当前群体中的优良解，即非劣解。这个外部的群体可能仅仅只是作为个外部的存储器， 也有可能参与到m o g a 的选擗s 掘中。外词群供初始化为骜毛拯下的每代中，葡嗄对 外部群体进行更新：把当前群体中所有的非劣解复制到外部群体中，再把外部群体中不再是 非劣解或是重复的解去除。然而，在某些问题中，由于内存资源的约束，不可能菜冉澌有的 非劣解。因此，外部群体的大小应设置为个适当的常数，当出现过量的解时，采耽潜施( 如 依据密度信息、个体进入外部群体的时间或聚类法阁等) 去除掉部分解。当然，在精简外部 1 4 南京理工大学硕士学位论文多目标遗传优化及其在机器人路径规划中的应用 群体时，应保留它的原有特性( 如均匀分布等) 。 另种精英法为( + 名) 瑚；择法。父代和子代个徽间相互竞争，选择其中的非劣解( 或 也遵循些其它准则，如分布密度) 作为下卅：的新群体。而不像常规算法那样直接使用生 成的子孙来替代原来的群体。些著名的算法如n s g a - i i 、n i ：b a 2 等均采用此精英法。 精英法是提高m o g a 搜索效率的重要因素。不过，如果在适应值分配过程中加入偏好 信息，并目这些瞎息实时发生变化，则精娃的使用将会出现问题。 ( 3 ) 偏好处理 。 在实际簖j 中，用户往往最终只需要个哼茼足问题需求的p 锨幻最优解，而不是整个 p a r e t o 最优解集，因l i ? 经em o g a 中加入用户的偏好信亩以缩小搜索范围是有必要的。 在m o g a 中，偏好可以事先表达 事后表达或以种交互的方式表达。如果偏好在事 先表达，则决策者必须在开始搜索之前定：；c 好偏好信息。例如组合函数法要事先为每个目标 确定好权重值，以把它们组合成个目标函数。事后表达为目前大多数m o g a 所采用( 如 n s g a - i i 、n t g a 2 等) 。在算法的优化过程中，认为所有目标具有相同的重要性，当算法运 行结束搜索至i 卜组p a r e m 最优解后，再由决策者分析并从中挑选出满意解。以交互的方式表 达偏好是指使用决策者的偏好信息来指导算法的搜索过程，并目危许啸好信息实时改变。这 种方式在目前的m o g a 中使用较少，但是当决策者事先没有掌握足够多的目标信息，或者 随着对问题i 击步的了解和经验的增加而需要改变期望值时，这种渐翊碰坡决策者的偏好信 息明朗化的交互方法将会非常有效地提高算法的搜索效率。 2 5 本章小结 本章主要介鳐i 遗传算珐的i 基本原理，阐述了遗供算法的基本糟晚湘基席：理! _ 论，列- 逼 传操 作的关键算子，如选择、交叉和变异做了详细的介绍。并简介了用遗传算法解决组合优化问 题的常用策略，以及近年来用于多目标遗传优化的_ 兀顶相关技术。 南京理工大学硕士学位论文多目标遗传优化及其在机嚣人路径规趣中的应用 工程中经常需要解决含多目标和多约束的优化问题，即多目标优化印( m u l d q 3 b j e c t i v e o p d m i z a f i o n , m o ) 。理想的多目标优化过程的目榜边是找到尽可能多的p 缸幻最优解。由 于多目标优化遗传算法( m o g a ) 可以对多个目标同时优化、协调，所以理论匕它应该自毪够 在次仿真运行中得蛰卜_ 钼p 缸幻最优解。决策者可以依据问题的当前需要或偏好信息，从 中挑选出个或多个非劣解作为多目标优化问题的最终解刚。另方面，可以利用m o g a ( m u l f i q ：) b j e c d v eg e n e r a 6 ca 蛳d x n ) 的科嘤谬排同错洲鼎酬椭中的所有非劣解并且同 h 司使用小生境策略保留组互异的j 劣解。用这科叻斌阿以在种群中发期咦二保持多个好的解。 在许多代之后，算法可能导致种群收敛到近似l ：x - a v e t o 最优解并且有个好的分布。因此， m o g a 更适合于多目标优化问题的求解。 本章首先将介绍两种用于同时找到多个p a 戚o 最优解且采用最优保存策略的多目标演 化算法，随后重点介绍本文提出的改进多目标优化算法，该拿魏匕芷n s g a i i 基础匕进行改进， 为解决n s g a i i 在2 维问题e 有很好的表现但在高维问题中表现不佳的问题，本文算法i 毛用 聚类方法( c l o g ) 取代原算法中的拥挤度方法，并改进了精英策略，引入劣解参加遗传 操作，旨在保证算法收敛性的同时，提高算法的多样性。 1 基本定义 多目标优化问题中的多个目标之间往往是相互矛