基于演化计算的最短避障路径算法设计  

Plan on Minimal Way Avoiding Obstruction Based on Evolutionary Algorithm

作　　者：弓晨[1] 戴光明[1] 

机构地区：[1]中国地质大学计算机系,武汉430074

出　　处：《计算机工程与应用》2005年第16期61-64,共4页Computer Engineering and Applications

摘　　要：在工程应用、自动化、人工智能等诸多领域中有很多数学模型可以归结为寻求最短避障路径的问题。在环境模型的表达上,该文利用最小多边形包络法处理过的障碍物,即把障碍物描述成为多边形。在搜索策略上,利用演化算法求解TSP的算法——改进的郭涛算法的思想。针对TSP问题和最短避障路径问题的不同,在染色体的有效范围和基因的选取范围等处对算法进行修改,并且引入了基因库,成功地用演化算法解决了最短避障路径问题。In a great deal of fields,a lot of mathematical model can be summed up as finding a plan on minimal way avoiding obstruction.The traditional expression methods of the environmental model are the raster algorithm and minimal surrounding polygon,etc.And the traditional searching strategies include artificial potential field,dynamic planning,etc.The general method,for example,exhaustive searching method,greedy method,dynamic planning,are all facing such a common problem,that when the scale of the question reached the certain degree,would produce so-called″Combinatorial Explosion″.So more and more people begin to use Neural Network,Ant Colony algorithm and Evolutionary Algorithm to solve this kind of complicated problem.On the expression method of the environmental model,it expresses the barriers with minimal surrounding polygon.This can make solving simplify.It uses the algorithm called Guotao Algorithm(GT)owned to Evolutionary Algorithm to find the minimal way avoiding obstruction.It is from TSP and plan on the minimal way avoiding obstruction the differences of issues route in issueses,effective range in chromosomes(from the starting point to terminal point in the genes) and the range of choosings of genes,wait for place revise to the algorithm,introduce gene pool come and optimize some algorithms,succeed in.

关 键 词：演化算法 郭涛算法 非法路径 基因库 最短避障路径 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]