模拟退火算法在路径优化问题中的应用

Application of optimizing the path by simulated annealing

模拟退火算法是解NP完全组合优化问题的有效近似算法,将该算法应用于路径优化问题,利用该算法对类似货郎担问题的路径问题进行求解;针对城市道路行走不同的目标条件(路径最短、时间最短)进行优化,选择最佳行走路径;并将用该算法优化得到的计算结果与树形算法进行比较,显示该算法能够克服传统优化算法易陷入局部极值的缺点,同时表明该算法在解类似货郎担交通路径方面的问题时有较高的精确性。因而该算法在解决城市道路交通问题方面具有一定的实用价值。

Simulated annealing is an effective approximate arithmetic for NP completely combinatorial optimization problem. It is applied to optimizing the path in this thesis which is used in solving the kind of problem similar to the stall-keep. The problems whose target conditions are different between the shortest path and the least time are optimized in this thesis and the best traveling path is chosen. Contrary to the tree arithmetical is indicated that simulated annealing overcomes the disadvantage of traditional optimizing arithmetic which is easy to get into part extremism. And the results are more accurate than those which come from other arithmetics. Therefore,simulated annealing takes on determinate practical value in solving the problem of transportation of city.