多目标优化算法及其在移动机器人路径规划中的应用

作     者：王慧莹 

作者单位：兰州理工大学 

学位级别：硕士

导师姓名：李二超

授予年度：2018年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 080202[工学-机械电子工程] 08[工学] 0804[工学-仪器科学与技术] 0835[工学-软件工程] 0802[工学-机械工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：多目标优化 NSGA-Ⅱ算法 基于参考点的进化算法RPEA 交叉变异概率 移动机器人路径规划 

摘      要：多目标优化问题在实际应用中普遍存在,常应用于工程设计、工艺设计、投资组合、车间调度、电网配置、轨道交通、物流路径等领域。多目标优化需要同时考虑两个以上目标的最优,而实际应用中多目标之间往往存在着复杂的关系,一个目标上的提升,可能导致其他目标上的损失,往往很难在多个目标之间进行取舍,所以研究多目标优化算法有着极其重要的价值。本文选取智能优化算法中的NSGA-II(Nondominated Sorting Genetic Algorithms II)算法和基于参考点的优化算法中的RPEA(Reference Points-based Evolutionary Algorithm)算法做了详细介绍,并在NSGA-II算法的基础上对其做了部分改进:1)提出精英替换策略来加速种群的优胜劣汰,种群每进化一代,选取上一代种群中若干个最优解替换当前种群中表现最差的若干个解;2)分析并指出自适应遗传算法在调整遗传参数上存在的不足,针对其不足对遗传参数的调整策略进行改进:分阶段调整交叉概率和自适应调整变异概率。采用标准测试函数集ZDT和DTLZ对改进NSGA-II算法进行了实验测试,与原NSGA-II算法进行对比,实验结果验证该改进NSGA-II算法在分布性和收敛性上明显优于原NSGA-II算法。基于参考点的进化算法RPEA采用一种新的参考点生成策略:求出种群中的非支配最优解,通过在非支配最优解的每个子目标上减去一个较小值得到参考点。选取种群中距离参考点距离近的个体到下一代。通过种群不断进化,参考点逐渐接近问题的真实帕累托前沿,并可以求出多目标优化问题的帕累托最优解。最后采用标准测试函数集ZDT和DTLZ进行实验测试,比较RPEA算法与改进NSGA-II算法求解多目标优化问题的性能,测试结果验证RPEA算法在求解性能上优于改进NSGA-II算法。将以上研究的两种多目标优化算法应用到移动机器人路径规划问题中,首先介绍了遗传操作采用的编码方法、交叉算子和变异算子,并对路径选取方法进行改进。接着,搭建移动机器人的运动环境模型,利用Matlab软件仿真实现移动机器人的路径规划。最后,通过实验对比与分析,验证了改进NSGA-II算法求出的路径在路径长度和危险程度上都优于传统NSGA-II算法求出的路径,并且改进NSGA-II算法运行时间更短;采用RPEA算法求解移动机器人路径规划问题的仿真结果验证RPEA算法在求解移动机器人路径规划问题上具有可行性。