基于改进遗传算法的餐厅服务机器人路径规划

针对遗传算法（GA）易产生早熟现象和收敛速度慢的问题，提出了一种基于传统遗传算法（TGA）的改进遗传算法——HLGA，用于实际餐厅服务机器人的路径规划。首先，通过基于编辑距离的相似度方法对拟随机序列产生的初始种群进行优化；其次，采用自适应算法的改进交叉概率和变异概率调整公式，对选择操作后的个体进行交叉、变异操作；最后，计算具有安全性评价因子函数的个体适应度值，进一步对比、迭代得到全局最优解。理论分析和Matlab仿真表明，与TGA和基于个体相似度改进的自适应遗传算法（ISAGA）相比，HLGA的运行时间分别缩短了6.92 s和1.79 s，且规划的实际路径更具有安全性和平滑性。实验结果表明HLGA在实际应用中能有效提高路径规划质量，同时缩小搜索空间、减少规划时间。

Path planning for restaurant service robot based on improved genetic algorithm

Since the Genetic Algorithm (GA) is easy to produce premature phenomenon and has slow convergence rate, an improved GA based on Traditional GA (TGA), called HLGA (Halton-Levenshtein Genetic Algorithm), was proposed for path planning of real restaurant service robots. Firstly, the similarity method based on edit distance optimized the initial population of quasi-random sequence; secondly, the improved crossover probability and mutation probability adjustment formula based on the adaptive algorithm were adopted to cross and mutate the individuals after they had been selected. Finally, the individual fitness values of the safety evaluation factor functions were calculated, and the global optimal solution was obtained by comparison and iteration. Through theoretical analysis and Matlab simulation, the running time of HLGA was decreased by 6.92 seconds and 1.79 seconds compared with TGA and Adaptive Genetic Algorithm based on Improved independent Similarity (ISAGA), and the actual path of planning was more secure and smooth. The simulation results show that HLGA can effectively improve the quality of path planning in practical applications, meanwhile reduces the searching space and the planning time.