多目标遗传算法在机器人路径规划中的应用
第３０卷第６期南京理工大学学报ｖ０１．３０Ｎｏ．６』竺丝垦丝旦———塑些塑丝些塑堑型堕！竺堕鲤２￡墅ｉ竺些！璺鲤！呈堕塾坐Ｑ敛望丝：呈堂多目标遗传算法在机器人路径规划中的应用
申晓宁，郭毓，陈庆伟，胡维礼
（南京理工大学自动化学院，江苏南京２１００９４）
摘要：针对具有多个优化目标的机器人全局路径规划问题，提出一种改进的多目标优化遗传
算法。在初始群体的生成中，采用把随机法和基于问题先验知识的启发式方法相结合的策略。
以加快收敛速度；在遗传算子的设计中，引入删除、修复和平滑算子，以提高算法的搜索效率；在选择算子中，加入避免外部存储器中出现相同个体的机制，以防止早熟收敛。仿真结果表明：该文算法运行一次能够有效地产生一组近似Ｐａｒｅｔｏ最优路径解。
关键词：多目标优化；遗传算法；机器人；路径规划
中图分类号：ＴＰ１８文献标识码：Ａ文章编号：１００５—９８３０（２００６）０６—０６５９—０５
ＡｐｐＨｃａｔｉｏｎｏｆＭｕｌｔｉ－ｏｂｊｅｃｔｉＶｅｏｐｔｉｍｉｚａｔｉｏｎＧｅｎｅｔｉｃＡｌｇｏｒｉｔｌＩｍ
ｔｏＲｏｂｏｔＰａｔｈＰｌａｎＩｌｉｎｇ
ＳＨＥＮＸｉａｏ—ｎｉｎｇ，ＧＵＯＹｕ，ＣＨＥＮＱｉｎｇ—ｗｅｉ，ＨＵＷｅｉ—ｌｉ
（ＳｃｈｏｏｌｏｆＡｕｔｏｍａｔｉｏｎ，ＮＵＳＴ，Ｎａｎｊｉｎｇ２１００９４，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｎｉｍｐｒ０Ｖｅｄｍｕｌｔｉ－ｏｂｊｅｃｔｉＶｅｏｐｔｉｍｉｚａｔｉｏｎｇｅｎｅｔｉｃａ１９０ｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｔｏｏｐｔｉｍｉｚｅｔｈｅｐｍｂｌｅｍｏｆｍｂｏｔ９１０ｂａｌｐａｔｈｐｌａｎｎｉｎｇｗｉｔｈｍｕｌｔｉｐｌｅｏｂｊｅｃｔｉｖｅｓ．Ｔｈｅｒａｎｄｏｍａｐｐｒｏａｃｈｃｏｍｂｉｎｅｄｗｉｔｈｔｈｅｈｅｕｒｉｓｔｉｃｍｅｔｈｏｄｂａｓｅｄｏｎｄｏｍａｉｎｋｎｏｗｌｅｄｇｅａｒｅｅｍｐｌｏｙｅｄｉｎｔｈｅｉｎｉｔｉａ“ｚａｔｉｏｎｔｏｍｏｔｉｖａｔｅｔｈｅｃｏｎＶｅ唱ｅｎｃｅｓｐｅｅｄａｎｄｔｈｒｅｅｇｅｎｅｔｉｃｏｐｅｒａｔｏｒｓｎａｍｅｄｄｅｌｅｔｉｏｎ，ｒｅｐａｉｒａｎｄｓｍｏｏｔｈａｒｅａｄｏｐｔｅｄｔｏｉｍ—ｐｒｏＶｅｔｈｅｓｅａＩ℃ｈｉｎｇｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ．ＩｎｔｈｅｓｅｌｅｃｔｉｏｎｏｐｅＬａｔｏｒ，ａｓｔｒａｔｅｇｙｔｈａｔａｖｏｉｄｓｔｈｅａｐｐｅ９ｒａｎｃｅｏｆｔｈｅｓａｍｅｉｎｄｉＶｉｄｕａｌｓｉｎｔｈｅａｒｃｈｉｖｅｉｓｉｎｃｏｒｐｏｍｔｅｄｔｏｐｒｅｖｅｎｔｐｒｅｍａｔｕｒｅ．Ｓｉｍｕｌａｔｉｏｎ
ｒｅｓｕｈｓｉｎｄｉｃａｔｅｔｈａｔｔｈｅ
ｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｃａｎｆｉｎｄａｓｅｔｏｆ印ｐｒｏｘｉｍａｔｅＰａｒｅｔｏ叩ｔｉｍａｌｓｏｌｕｔｉｏｎｓｅｆ＿６ｃｉｅｎｔｌｙｉｎｏｎｅｒｕｎ．
Ｋｅｙｗｏｒｄｓ：ｍｕｌｔｉ—ｏｂｊｅｃｔｉＶｅｏｐｔｉｍｉｚａｔｉｏｎ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ；ｒｏｂｏｔｓ；ｐａｔｈｐｌａｎｎｉｎｇ
机器人路径规划本质上是一个具有多个性能指标的ＮＰ完全问题，难以求得精确解。传统的图搜索法‘１｜、栅格法Ⅲ等搜索效率较低，路径优化结果也不尽理想。遗传算法是模拟生物在自然
收稿日期：２００５—０９—２６修回日期：２００６—０９—３０
基金项目：国家自然科学基金（６０４７４０３４；６０１７４０１９）
作者简介：申晓宁（１９８１一），女，江苏南京人，博士生，主要研究方向：进化算法、多目标优化，Ｅ．ｍａｉｌ：ｓｘｎｙｓｔｓ”＠ｓｉｎａ．ｃｏｍ．ｃｎ；通讯作者：胡维礼（１９４ｌ一），男，江苏东台人，教授，博士生导师，主要研究方向：智能控
制、网路控制系统、机器人控制、数字交流伺服系统，Ｅ．ｍａｉｌ：ｈｗｌｌ００２＠ｈｏｔｍａｉｌ．ｃｏｍ。
万方数据
南京理工大学学报第３０卷第６期
环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，它对复杂的非线性问题具有良好的适用性。近年来，国内外一些学者开始研究使用遗传算法求解路径规划问题旧。Ｊ，并取得了一定的成果。然而，多数文献为了简化问题，仅对机器人路径规划问题的单个目标进行优化【３Ｊ，或采用加权求和法把问题的多个性能指标组合成一个标量函数，使之转化为单目标优化问题进行求解Ｈ’５Ｊ。加权求和法简单直观，但它运行１次只能得到１个解，且解的值依赖于权重的选取。多目标遗传算法∞ｏ能够对多个目标同时优化，在它们之间进行协调，算法运行一次可以并行得到问题的一组Ｐａｒｅｔｏ最优解。决策者可以依据问题的当前需要，从中挑选出满意的解作为问题的最终解。因此，多目标遗传算法更适合于求解多目标优化问题。
ＳＰＥＡ２【６１是一种高效的多目标优化遗传算法，它基于Ｐａｒｅｔｏ支配的概念进行适应值分配和选择操作，并采用了小生境法和精英保留的机制。本文针对机器人全局路径规划问题的特点，采用启发式方法对ｓＰＥＡ２算法的群体初始化过程和遗传算子进行了改进，并加入了防止算法早熟收敛的策略，使其能够对问题的３个性能指标（路径总长度、平滑性和安全性）同时优化。仿真实例表明了本文算法的有效性。
１问题描述
１．１数学模型
为了便于描述，视机器人工作环境为二维空间，其中存在若干个障碍物。设机器人运动的起始点为ｓ，目标点为ｇ。机器人全局多目标路径规划问题的数学模型可表述为
寻找可行路径Ｐ４＝［ｐ？ｐ；…ｐ：］，使得
ＪＦＴ（Ｐ＋）＝ｍｉｎ［＾（Ｐ），厶（Ｐ），厶（Ｐ）］（１）且满足
ｐ？＝ｓ，ｐ：＝ｇ（２）式中：ｐ？（Ｊ＝１，２，…，ｎ）为路径Ｐ＋的经过点，Ｚ（Ｐ）表示路径的总长度，五（Ｐ）表示路径的光滑性，六（Ｐ）表示机器人与障碍物发生碰撞的可能性（安全性能）。
１．２Ｐａｍｔｏ最优解
优化问题的多个目标之间往往是相互矛盾
的，因而不存在一个解能够使得所有的目标同时达到最优。求解多目标优化问题一般使用Ｐａｒｅｔｏ最优解的概念。
定义１（Ｐ盯ｅｔｏ最优解）：假设求解最小化问题，Ｆ＝［＾五…厶］为目标向量，ｘ为问题的决策空间。如果不存在任何ｚ∈ｘ，使得工（工）≤，（ｚ＋），Ｖｉ∈｛１，２，…，ｍ｝，并且Ｚ（工）＜．ｆ（ｚ＋），了，∈｛１，２，…，ｍ｝，则工＋是多目标优化问题的一个Ｐａｒｅｔｏ最优解。
一个多目标优化问题通常存在多个Ｐａｒｅｔｏ最优解，这些解共同构成了问题的Ｐａｒｅｔｏ最优解集。机器人多目标路径规划问题即要求产生ｌ组有效的Ｐａｒｅｔｏ最优路径解。
２用于机器人全局路径规划的多目标遗传算法
２．１编码和初始群体的生成
２．１．１编码
每个染色体表示一条由一系列点连接而成的路径。其结构为
（石１，ｙ１）＿（省２，ｙ２）＿…叶（石。，），。）
染色体采用浮点数编码，长度ｎ可变。其中，（戈．，，，。）和（石。，ｙ。）分别表示起始点和终止点的坐标，（戈ｉ，ｙ从，＝２，…，ｎ一１）表示路径上除两端点以外某一中间点的坐标。这样的编码方式直观简洁，有助于算法遍历整个解空间，从而提高了搜索的精度和灵活性。
２．１．２群体的初始化
初始群体由两部分组成。一部分个体包含的中间点个数及其相应坐标均随机产生。由于路径的起始点和终止点已知，且当环境中不存在障碍物时，这两点的连线是长度最短、最平滑的一条路径，为了提高算法的搜索效率，借助这一信息启发式地产生另一部分初始个体。具体做法如图１所示。
图１启发式地产生部分初始群体示意图把起点ｓ到终点ｇ的连线随机平分成若干段（如图１中为３段），在第Ｊ（图１中，，＝１，２，３）段上随机取两点玛一，，勘，假设戈。＜茁，且儿＜％（戈，），
万方数据
总第１５ｌ期申晓宁郭毓陈庆伟胡维礼多目标遗传算法在机器人路径规划中的应用６６１
分别指相应点的坐标），在点ｐ：Ｈ与ｐ：ｉ之间随机产生一点矽（满足戈，：Ｈ＜埽＜石，：，，），。＜聊＜％），顺次连接ｐ：『＿１，ｐ，，％，添加到产生的路径中。图１中所示产生的初始路径为：Ｐ＝［ｓｐ。ｐ，ｐ：ｐ３ｐ≥ｐ４ｐ５ｐ孑ｐ６ｇ］。
２．２适应值评价与选择算子
２．２．１目标函数
设任意一条可行路径为Ｐ＝［ｐ。ｐ：…ｐ。］，凡≥２，则问题的３个性能指标定义如下：（１）路径总长度一（Ｐ）
ｎ—ｌ
■（Ｐ）＝∑Ｉ册＋。Ｉ（３）式中：Ｉｐ『ｐ…Ｉ表示路径段ｐ沪…的长度。
（２）路径光滑性五（Ｐ）
由于机器人的几何外形对其运动特性有一定的影响，因此整条行驶路径应平缓而光滑，即每一转折点处的拐角值应尽可能小。
当凡＞２时，
ｎ一１
∑哟＋后×们
以（Ｐ）＝丝—－－一（４）五（Ｐ）为路径Ｐ的平均拐角值。式（４）中：仅，（Ｊ＝２，３，…，ｎ一１）表示两向量ｐ卜。ｐｆ和ｐ矽…间的夹角（０≤ａｉ＜订）；Ｉ｜｝为ａｉ中大于或等于订／２的个数，即当某一夹角大于或等于订／２时，对目标值进行惩罚。
当ｎ＝２时，路径为起始点与终止点的连线。若其可行，则正（Ｐ）值为０。
（３）路径安全性能六（Ｐ）
为了防止机器人的某一部位与障碍物发生碰撞，应尽量使其与障碍物保持一定的安全距离。
六（Ｐ）＝１／ｄ（５）式中：ｄ表示路径Ｐ距离所有障碍物的最短距离。
当路径Ｐ与障碍物有交点，即Ｐ不可行时，应对它的目标函数值进行惩罚。记形（江１，２，３）为当前群体中的所有可行解在目标函数，上的最差值，则对不可行解Ｐ，令
Ｚ（Ｐ）＝形＋ｎ１×Ｃｉ，ｉ＝１，２，３（６）式中，ｎ，为Ｐ中不可行段的个数；ｃｊ为惩罚因子。式（６）保证了不可行解的目标函数值差于可行解。
２．２．２适应值分配与选择
本文使用ｓＰＥＡ２的适应值分配策略，在为每个个体分配适应值时，综合考虑支配该个体和受该个体支配的其余个体的数目。对ｓＰＥＡ２的环境选择算子作了改进：在判断某个解是否应加入到外部存储器中时，需考察当前外部存储器中是否已存在与之相同的解，若存在，则阻止该解进入外部存储器。这样做的目的是防止某个适应值较好的个体在后代群体中迅速繁殖和扩张，以避免早熟收敛。２．３遗传算子
２．３．１遗传算子的描述
本文设计一类基于路径优化问题专门知识的启发式遗传算子，以提高算法的搜索效率。
（１）交叉
采用双点交叉。考虑到个体长度可变，在两个母体上分别随机选取两个交叉点（首点和尾点除外），交换两个体在各自交叉点之间的部分染色体。
（２）变异
ａ．当路径可行时，对路径上中间点的坐标依概率进行小范围调整，并保证变异后的路径仍为可行路径；
ｂ．当路径不可行时，对路径上不可行段的端点坐标依概率进行较大范围调整。若有端点位于障碍物中，则使其变异到障碍物之外，否则，在两端点中随机选择一点进行变异，并保证变异后的端点不在障碍物中。
（３）删除
ａ．若某一路径中存在如图２（ａ）中的点ｐｉ，删除ｐｆ后，ｐｆ的前一个路径点ｐ卜。与后一个路径点ｐ…相连为可行的路径段，则删除点ｐｉ；
ｂ．如果某一路径不可行，如图２（ｂ）所示，ｐｉ点所在的两条线段ｐ『－ｌｐｆ和ｐ沪…均不可行，则删除点ｐｉ，从而使不可行段个数减小。从图２（ａ）和图２（ｂ）中可以看出，删除算子使路径的长度减短。
（４）修复
修复算子是利用已知的机器人工作环境中的障碍物形状和位置信息而设计的智能遗传算子。如图２（ｃ）所示，路径段ｐ沪…与障碍物相交，则在障碍物周围产生点ｐ。，ｐ：，ｐ，，顺次连接点ｐｆ，ｐ。，ｐ：，ｐ，，ｐ…，则不可行段ｐ∥…被修补为环绕障碍物的可行路径段序列：ｐＪｐｌ—巾ｌｐ２—巾２ｐ３—垆３ｐｆ＋ｌ。
（５）平滑
平滑算子只对可行路径中最大的拐角进行操作。如图２（ｄ）所示，删除拐角仅。。的顶点ｐｉ，依次连接点ｐＨ，ｐ。，ｐ：，ｐ…，构成可行路径段序列：ｐ，一ｌｐｌ—巾ｌｐ２—巾２ｐ，＋ｌ。
万方数据
６６２南京理工大学学报第３０卷第６期
（ａ）删除算子１（ｂ）删除算子２
（ｃ）修复算子（ｄ）平滑算子
图２部分遗传算子示意图
２．３．２遗传算子概率的选择
在进化过程的前期，群体中存在大量的不可行解，交叉、变异和修复算子的概率应较大，而平滑算子的概率较小；随着进化过程的推进，可行解增多，应适当提高平滑算子的概率以提高解的平滑性能，同时，为了防止交叉算子对解可行性的破坏，需降低交叉概率，并取较小的变异概率对可行解的形状进行微调，修复算子概率也应相应减小。由于删除算子可以减小染色体的长度，所以对其始终取较大的概率。
２．４算法的步骤
Ｓｔｅｐ１：生成初始群体脚（０），设置一个初始为空的外部存储器Ａ（０），设进化过程中外部存储器的大小固定为肜，最大进化代数为丁，计数器￡＝０：
ｓｔｅｐ２：对Ｐｏｐ（ｔ）和Ａ（ｔ）中的所有个体进行适应值评价；
Ｓｔｅｐ
３：环境选择。把Ｐｏｐ（￡）和Ａ（￡）中所有的非支配解加入到Ａ（￡＋１）中。如果Ａ（￡＋１）的规模超过Ｍ，则采用基于密度信息的“裁减”法∞１移除多余的非支配解；反之，则再选取若干个适应值较优的受支配解加入Ａ（￡＋１），直到Ａ（￡＋１）中解的个数达到肘为止；
ｓｔｅｐ４：交配选择。采用联赛法从Ａ（ｆ＋１）中选择出较优解组成交配池；
ｓｔｅｐ５：在交配池中进行多种遗传算子的操作，把生成的子代群体作为下一代的新群体Ｐｏｐ（ｔ＋１）；
Ｓｔｅｐ６：终止准则。如果￡≥ｒ，则把Ａ（ｆ）中所有的非支配解组成的集合作为问题最终的Ｐａｒｅｔｏ最优解集输出，算法终止；否则，￡＝￡＋１，转到ｓｔｅｐ２。３仿真
使用本文算法在一个复杂的机器人工作环境下进行了仿真试验，并把它与未作改进的ＳＰＥＡ２算法进行了比较。设工作环境为１０ｍ×１０ｍ的正方形。本文算法的运行参数为：群体规模与外部存储器的大小均为３０，交配选择中的联赛规模取为２，最大进化代数丁＝８０。前∥２代中，交叉概率Ｐ。＝ｏ．５，变异概率Ｐ。＝ｏ．５，删除概率Ｐｄ＝ｏ．４，修复概率Ｐ，＝０．３，平滑概率Ｐ。＝０．１；后∥２代中，Ｐ，＝Ｏ．２，Ｐ。＝Ｏ．１，Ｐｄ＝０．４，Ｐ，＝０．１，Ｐ。＝０．６。
在给定的工作环境下，本文算法每运行１次，便可以有效地得到１组非支配路径解，从这组解中选择３个具有代表性的解，如图３所示。其中，图３（ａ）相应的路径解在长度和平滑性上的性能非常好，而安全性能很差；网３（ｂ）相应的路径解安全性能很好，而长度和平滑性较差；图３（ｃ）对应的解在３个目标上的值都比较平均。表１分别给出了图３中各子图所对应的路径解在３个优化目标上的值。可见，本文算法搜索到的解具有较好的多样性，它们在各目标函数上的性能各有侧重，决策者可以根据当前的需求，从这组非支配解中挑选出满意的解作为机器人运动的路径。一旦工作需求发生变化，决策者可以直接从这组解中挑选出另一个符合要求的满意解，而无需重新运行算法，方便而实用。
（ａ）长度／。和平滑性＾很好，
安全性，，很差
（ｂ）长度／。和平滑性／：较差
安全性，彳艮好
（ｃ）长度．厂，和平滑性厂：，
安全性厂，比较平均
图３３种不同的非支配路径示意图
万方数据
总第１５１期申晓宁郭毓陈庆伟胡维礼多目标遗传算法在机器人路径规划中的应用６６３表ｌ图３中各路径解的目标函数值
把本文算法与未改进的ｓＰＥＡ２算法进行比较。未改进的ＳＰＥＡ２算法进化到一定的代数之后，在群体中产生了大量相同的不可行个体。这是由于机器人的工作环境比较复杂，而未改进的ｓＰＥＡ２算法没有采用任何基于路径优化问题专门知识的启发式方法（群体初始化时采用随机生成法，遗传算子仅使用交叉和变异算子），因而它难以有效地搜索到可行解；又因为未改进的ＳＰＥＡ２算法在环境选择算子中没有采用避免相同个体出现的策略，所以当算法搜索到某个适应值相对较好的不可行解时，该解将通过选择操作在后代群体及外部存储器中迅速繁殖和扩张，造成算法早熟收敛。此后，由于群体中存在许多相同的个体，因此交叉算子的作用使得个体的染色体长度迅速增加，占用了大量的内存资源，而变异算子仅作局部搜索，效率低下。该算法在运行了相当长的时间之后（大于Ｏ．５ｈ），仍然无法搜索到任何可行路径。这表明未作改进的ｓＰＥＡ２算法不能够求解机器人多目标路径优化问题。而在给定的工作环境下，运行本文算法１０次，平均每次运行时间为１３４．４ｓ．且每次运行均产生了１组可行而有效的非支配路径解。由此说明，本文所采用的基于问题已知信息的启发式方法和改进的选择策略是非常有效而实用的，尤其对于机器人路径规划这类复杂问题，更是如此。４结束语
本文对多目标优化遗传算法ＳＰＥＡ２进行了改进，并把它应用到机器人多目标路径规划问题中。在复杂工作环境下的仿真实例表明，本文提出的基于问题先验知识的启发式群体初始化方法和智能遗传算子能够显著地提高算法的搜索效率，加快算法的收敛速度；在选择算子中引入的避免外部存储器中出现相同个体的策略，有效地防止了算法早熟收敛。本文算法只需运行１次，就可产生１组多样性较好的路径非支配解，供决策者在不同的工作目标下进行选择。今后的工作将研究在线决策方法，使得本文算法能够解决机器人动态路局规划问题。
参考文献：
［１］Ａｌｅｘｏｐｏｕｌｏｓｃ，ＧｒｉｍｎＰＭ．Ｐａｔｈｐｌａｎｎｉｎｇｆｂｒａｍｏ－ｂｉｌｅｍｂｏｔ［Ｊ］．ＩＥＥＥ。１１ｒａｎｓａｃｔｉｏｎｏｎｓｙｓｔｅｍ，Ｍａｎａｎｄ
Ｃｙｂｅｍｅｔｉｃｓ，１９９２，２２（２）：３１８—３２２．
［２］马兆青，袁曾任．基于栅格的移动机器人实时导航和避障机器人［Ｊ］．机器人，１９９６，１８（６）：３４４
—３４８．
［３］罗熊，樊晓平，易晟，等．具有大量不规则障碍物的环境下机器人路径规划的一种新型遗传算法［Ｊ］．
机器人，２００４，２６（１）：１１—１５．
［４］ｘｉａｏＪ，Ｍｉｃｈａｌｅｗｉｃｚｚ，ｚｈａｎｇＬ，ｅｔａ１．Ａｄａｐｔｉｖｅｅｖｏ—ｌｕｔｉｏｎａｒｙｐｌａｎｎｅｒ／ｎａｖｉｇａｔｏｒｆｏｒｍｏｂｉｌｅ
ｒｏｂｏｔｓ［Ｊ］．ＩＥＥＥ７ＩｈｎｓａｃｔｉｏｎｏｎＥｖｏｌｕｔｉｏｎａｒｙＣｏｍｐｕｔａｔｉｏｎ，１９９７，
ｌ（１）：８—２８．
［５］陈刚，沈林成．复杂环境下路径规划问题的遗传路径规划方法［Ｊ］．机器人，２００１，２３（１）：４２—４４．［６］ｚｉｔｚｌｅｒＥ，ＬａｕＩ啪ｎｓＭ，Ｂｌｅｕｌｅｒｓ．Ａｔｕｔ耐ａｌｏｎｅｖｏｌｕ－ｔｉｏｎａｒｙ咖ｌｔｉｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．Ｍｅ蛔ｈｅｕｒｉｓｔｉｃｓ
ｆｏｒＭｌｌｌｔｉｏｂｊｅｃｔｉｖｅ０ｐｔｉｍｉｓａｔｉｏｎ，２００４，２（１）：３—３７．
万方数据
多目标遗传算法在机器人路径规划中的应用
作者：申晓宁， 郭毓， 陈庆伟， 胡维礼， SHEN Xiao-ning， GUO Yu， CHEN Qing-wei， HU Wei-li
作者单位：南京理工大学,自动化学院,江苏,南京,210094
刊名：
南京理工大学学报（自然科学版）
英文刊名：JOURNAL OF NANJING UNIVERSITY OF SCIENCE AND TECHNOLOGY(NATURAL SCIENCE)
年，卷(期)：2006，30(6)
被引用次数：3次
参考文献(6条)
1.Alexopoulos C.Griffin P M Path planning for a mobile robot 1992(02)
2.马兆青.袁曾任基于栅格的移动机器人实时导航和避障机器人 1996(06)
3.罗熊.樊晓平.易晟具有大量不规则障碍物的环境下机器人路径规划的一种新型遗传算法[期刊论文]-机器人2004(01)
4.Xiao J.Michalewicz Z.Zhang L Adaptive evolutionary planner/navigator for mobile robots 1997(01)
5.陈刚.沈林成复杂环境下路径规划问题的遗传路径规划方法[期刊论文]-机器人 2001(01)
6.Zitzler https://www.wendangku.net/doc/f37022048.html,umanns M.Bleuler S A tutorial on evolutionary multiobjective optimization 2004(01)
相似文献(10条)
1.期刊论文常江.Kwang Y.Lee基于遗传算法的火电单元机组多目标优化协调控制-深圳职业技术学院学报
2004,3(2)
作者提出了一种基于遗传算法的火电单元机组多目标优化协调控制策略.该策略通过改进的遗传算法进行多目标优化求解机组最优稳态控制量以得到最优设定值,从而完成多目标优化协调控制任务.改进的遗传算法采用十进制编码,规范化几何秩选择,混合交叉及均匀变异.仿真结果表明,在不同的运行目标下控制量的最优适应度函数都能快速收敛,遗传算法为多目标优化协调控制提供了有效的途径.
2.学位论文张萍多目标优化遗传算法在建筑协同设计冲突消解中的应用2009
计算机支持协同工作(Computer Supported Cooperative Work，CSCW)是一种将人类合作行为模式与计算机支持技术融合为一体的新兴技术，即在计算机技术支持的环境下，一个群体协同完成一项共同的任务。计算机支持的协同设计(CSCD)是计算机支持的协同工作中的一个重要领域，将协同工作的理论应用于设计系统就是计算机支持的协同设计。CSCD主要研究如何利用计算机网络对多人参与的协同设计工作、所涉及的数据和设计过程进行组织、管理和协调。
在协同设计过程中，各小组或领域设计人员的知识背景互不相同，设计目标互不相同，不同设计对象与其之间的属性也是相互依赖的，因而难免发生冲突。为使协同设计能够顺利进行，提高协同设计小组的工作效率和效果，必须有一种有效的冲突消解策略，来解决协同设计中的设计冲突，协调产品开发过程。
多目标优化遗传算法是近年来针对多目标优化问题发展起来的一种新的优化算法。由于其具有高效、实用的特点，因此越来越受到学术界的重视。本文在充分分析研究协同设计的冲突和多目标优化问题的基础上，将协同设计的冲突理解为一个多目标优化问题，因此多目标优化遗传算法是冲突消解的有效途径。本文提出了基于多目标优化遗传算法的冲突消解策略，通过对协同设计过程进行检测，及时发现冲突，然后在定性分析的基础上，采用多目标优化遗传算法协调各领域设计人员设计目标达到整体最优，从而达到冲突消解的目的。
建筑协同设计是网络环境下一种新兴的建筑设计方式。在该方式下，分布在不同地理位置上的设计人员通过网络在各种计算机辅助工具的支持下协同地进行建筑的设计工作。传统的建筑设计中解决冲突的方式是采用人工方式协调而非计算机智能解决。本文设计并开发了建筑协同设计系统，并且将基于多目标优化遗传算法的冲突消解策略应用于建筑协同设计系统中，自动发现建筑协同设计中的冲突并且进行消解，使传统的人工协调由计算机协调取代，取得了较为满意的效果，保证了建筑协同设计能够顺利进行。本文利用多目标优化遗传算法解决冲突，所得的多个非支配解为决策者提供了多样性的选择，更有利于决策者做出正确的决策，为研究协同设计冲突消解提供了一种新的途径与方法。
本文所做的主要工作如下：1.对多目标优化遗传算法NSGA—II的优良性能进行了验证。总结了建筑协同设计特点和过程、建筑协同设计的冲突并且对建筑协同设计的冲突进行了数学描述。2.构建了协同设计冲突的多目标优化模型。在对协同设计的冲突和多目标优化问题深入研究的基础上，本论文将协同设计中的冲突描述为多目标优化问题，构建了协同设计冲突的多目标优化模型，在此模型的基础上，可以根据实际出现的协同设计系统的冲突
，建立具体冲突的多目标优化模型。3.提出了基于多目标优化遗传算法的冲突消解策略。提出了基于多目标优化遗传算法的冲突消解策略，利用国际上先进的多目标优化遗传算法NSGA—II进行冲突求解。并给出了冲突检测的有效方法，给出了整个策略的流程和具体的实现方法。4.将基于多目标优化遗传算法的冲突消解策略应用于建筑协同设计中。设计并实现了一个建筑协同设计系统。系统以Hoops/Net作为整体架构、三维引擎ACIS为造型内核，采用SQL Server2000数据库系统，利用VC++．NET2003在WindowsXP平台上开发完成。重点介绍了如何进行冲突消解，并且给出了采用多目标优化遗传算法对建筑协同设计进行冲突消解的实例，对冲突消解的结果进行了实例展示，证明了该策略的有效性。同时所得的多个非支配解也可以使决策者对整个问题非劣解集的分布具有更加全面的了解，这有利于决策者作出更好的决策。
3.期刊论文胡静.李金龙.曹先彬模拟退火算法与遗传算法结合及多目标优化求解研究-计算机应用与软件
2000,17(11)
多目标优化问题是目前遗传算法应用研究的一个重点.本文针对经典遗传算法在多目标优化计算中,难以获得足够的比较均匀的Pareto优集的不足,提出一种热力学遗传算法,研究热力学中熵和温度的概念,并综合利用约束交叉、适应度共享技术来进行多目标函数的优化计算.实验结果显示,这种改进型遗传算法能得到一个较好的Pareto优集.
4.学位论文耿玉磊改进的多目标优化遗传算法及多目标优化软件的研制2005
优化设计作为现代设计方法之一，已被广泛应用于各个领域。而大部分优化问题为多目标优化。由于多目标优化问题常由若干个相互冲突的目标构成，所以通常不能求得绝对的最优解，而只能求得一组非劣解。近些年，遗传算法已广泛应用于多目标优化非劣解的求解，但如何评价非劣解质量的好
坏，还没有满意的理论。另外，目前还没有一个通用且实用的多目标优化软件，这也限制了多目标优化的应用。
本文介绍了多目标优化和遗传算法的原理和方法，并对遗传算法进行了改进。把多准则模糊优选理论应用于并列选择遗传算法，从而得到即满足整体的最优性，又尽可能的逼近各子目标最优值的非劣解。另外，针对权系数往往难以确定的问题，用变权系数法求出非劣解组，然后进行模糊决策，从而让决策者选择客观、合理的满意解。
本文编制了多目标优化软件，该软件包括常用的传统多目标优化方法和基于遗传算法的现代多目标优化方法。使用方便，通用性好。对于推动多目标优化的应用有积极意义。
5.期刊论文杨铭.汪文娟.YANG Ming.WANG Wen-juan BP神经网络结合遗传算法用于丹参提取工艺的多目标优化-
药学服务与研究2007,7(6)
目的:使用BP神经网络结合遗传算法用于丹参提取工艺的多目标优化. 方法:通过已知文献的丹参提取工艺优化实例,采用均匀设计法优化BP神经网络模型参数,并建立网络模型,再利用遗传算法对网络进行多目标寻优,获得丹参最佳提取工艺. 结果:BP神经网络结合遗传算法用于丹参提取工艺的多目标优化,模型拟合度和预测性均高于文献采用的多元回归法. 结论:BP神经网络结合遗传算法可用于丹参提取工艺的多目标优化.
6.学位论文汪晗基于进化计算的多目标优化与决策方法研究2002
该文介绍了传统多目标优化与决策的研究和国内外在进化多目标优化与决策方面的研究进展.文中分别研究了进化计算和多目标优化与决策理论,在此基础上用进化计算的方法来研究多目标优化与决策问题.文中主要研究了下面几种多目标优化算法:多性别遗传算法、向量评估算法、非劣分层算法、小组决胜算法.并将小生境共享技术推广到多目标问题,研究了小生境尺度设计,通过实验对其算法性能、收敛特性、种群的分布特性、参数选择、计算效率等方面作了具体分析,并在此基础上对算法作了一些改进.
7.期刊论文胡贵强.HU Gui-qiang多目标优化的遗传算法及其实现-重庆文理学院学报（自然科学版）
2008,27(5)
遗传算法是一种通过模拟自然进化过程搜索最优解的方法,在优化方法中具有独特的优越性,有着非常重要的理论意义和广泛的应用领域.多目标优化问题求解已成为遗传算法的一个重要研究方向,而基于Pareto最优概念的多目标遗传算法则是当前遗传算法的研究热点.本文对遗传算法的理论基础进行分析,包括模式定理等,讨论用遗传算法来解决多目标优化问题的方法并给出其实现,介绍遗传算法的各种改进措施,并指出遗传算法的发展动向.
8.学位论文朱文龙基于遗传算法的BP神经网络在多目标优化中的应用研究2009
多目标优化起源于许多实际复杂系统的设计、建模和规划问题，这些系统涉及的领域包括工业制造、资本预算、网络通讯、道路规划等等。现实生活中，几乎每个重要的决策和预测都需要考虑各种制约条件，并处理若干目标的相互冲突，这就涉及多个目标的优化。因为这些目标并不是独立存在的，对其中一个目标进行优化必须以牺牲其它目标为代价，并且各目标的单位又往往不一致，这就导致很难客观地评价多目标优化求解的优劣性。传统的求解多目标优化的方法通常存在许多缺陷，如各目标加权值的分配带有较大的主观性，优化目标仅为各目标加权和，过程中各目标优化的不可操作性等。
本文着重对人工智能中两个热点问题遗传算法和人工神经网络进行分析和改进，尝试对这两种方法进行融合，并将其应用到多目标优化领域。论文主要内容包括：
首先，介绍遗传算法的原理，重点介绍现今经典的多目标遗传算法的优缺点，分析多目标遗传算法设计中所要解决的问题：适应度分配、多样性保持、收敛性。针对简单遗传算法应用过程中所存在的不易收敛，结果常常陷入局部最优等缺点，在改进型非劣分层遗传算法基础上提出改进的并行混合非劣分类遗传算法。多个算例测试表明，改进的算法在解的多样性和收敛性方面都有不俗表现，其性能明显优于改进型非劣分层遗传算法。
其次，通过对BP神经网络的关键技术及其算法的研究，针对BP神经网络的限制与不足进行分析，提出一种改进技术。
最后，将改进后的遗传算法与BP神经网络融合，提出基于遗传算法的BP神经网络融合算法。利用基于遗传算法的BP神经网络对多目标优化问题进行求解，充分发挥遗传算法的全局搜索能力和BP算法的局部搜索能力，加快收敛速度，提高收敛精度。将其应用于多目标车间作业动态调度实例中，也取得较好的效果。
9.期刊论文王达.WANG Da针对多目标优化的精英保留非劣排序遗传算法-河南化工2005,22(4)
遗传算法是模拟自然界生物进化过程的计算模型.作为一种有效的全局并行优化搜索工具,它具有简单、通用、鲁棒性强和适于并行分布处理的特点以及广泛的应用潜力.本文阐述了遗传算法的基本原理和方法,并着重介绍了一种改进的遗传算法--精英保留非劣排序遗传算法(NSGA-Ⅱ),并将其应用于化工中的多目标优化.
10.期刊论文杨铭.余敏英.史秀峰.滕艳萍.YANG Ming.YU Min-ying.SHI Xiu-feng.TENG Yan-ping BP神经网络结
合遗传算法多目标优化秦皮提取工艺的研究-中国中药杂志2008,33(22)
目的:使用BP神经网络结合遗传算法用于秦皮提取工艺的多目标优化.方法:以秦皮甲素和秦皮乙素为指标,采用均匀设计法优化BP神经网络模型参数,并建立网络模型,再利用遗传算法对网络进行多目标寻优,获得秦皮的最佳提取工艺.结果:得到的最优工艺条件为提取温度99℃、乙醇体积分数50%、液固比7、提取时间94 min,网络在此条件下的预测值为秦皮甲素提取量为9.617 mg·g-1,秦皮乙素提取量为2.195 mg·g-1,和实际测量值的相对误差仅为-1.16%和-5.14%,具有较好的网络预测性.结论:BP神经网络结合遗传算法可用于秦皮提取工艺的多目标优化.
引证文献(3条)
1.机器人路径规划的多目标二次优化方法[期刊论文]-计算机仿真 2009(10)
2.王雪松.高阳.程玉虎.马小平知识引导遗传算法实现机器人路径规划[期刊论文]-控制与决策 2009(7)
3.谭宝成.廉春原.徐艾.张海刚一种基于改进遗传算法的机器人路径规划方法[期刊论文]-西安工业大学学报
2008(5)
本文链接：https://www.wendangku.net/doc/f37022048.html,/Periodical_njlgdxxb200606001.aspx
授权使用：武汉理工大学(whlgdx)，授权号：f7e5198e-0db8-422b-be83-9e5b00b76bcd
下载时间：2010年12月29日