论文部分内容阅读
本论文针对避障TSP问题的特点,对算法的各个环节进行了细致的分析和设计。
为了降低避障TSP问题的算法的复杂度,首先对障碍物环境进行适当的抽象和简化,把环境中的障碍物简化为互不相交的不规则的多边形集合,并用快速排斥试验和跨立试验识别障碍物。
其次,在分析了目前各种路径规划方法拓扑法、单元分解法、人工势场法、演化算法、神经网络法的优缺点以及最短路径算法Diikstra、A<*>、D<*>、Flody算法基础上,发现演化算法的智能性、本质并行性和自适应性,以及在寻求全局最优解方面具有很强的全局搜索能力和搜索表示能力,演化算法被广泛的应用在避障路径规划中。但是,目前已有的这些算法由于设计本身的不足,不能很好的解决障碍环境下的路径规划问题,更不能解决真正意义上的避障TSP问题。
针对以上不足,进行了如下的研究:
1)首先引入代价矩阵来存放和记录每个城市和其它城市之间的距离,把表示环境信息的点状图转换成邻接矩阵;同时,以链表形式存储城市间的距离信息,并且按从小到大的顺序排列,这样很容易看到距离某个城市最近的几个城市;
2)结合具体的障碍环境信息,通过先验知识构造初始种群,避免产生很多的非法个体;
3)使用启发式交叉和边重组交叉相结合的交叉算子保证了算法的速度和质量,起到比较好的全局搜索的作用;
4)考虑到在好的路径中,城市一般都和其邻近的城市连接,很少出现抛开邻近城市而直接同其它较远的城市连接的情况,因此,在设计变异算子时加入了这一启发知识,引入基因库;同时,利用了一种最优模式的变异算子;利用这两个变异算子保证了群体在变异时的多样性和全局搜索能力,避免产生无效解而丢失有用的信息。通过这一系列措施避免了演化过程中非法个体的产生,同时也避免了无效和盲目的选择,提高了演化的效率,从而有效的解决了避障TSP问题。
最后,对全文进行了总结并对避障TSP问题的研究进行了展望。
本论文的创新之处在于运用求解一般无约束条件TSP问题的演化算法来求解有约束条件的避障TSP问题。