和声搜索算法在求解最短路径问题中的应用

The Application of Harmony Search Algorithm for Solving Shortest Path Problems

提出了一种改进的全局和声搜索算法来解决最短路径问题.首先,定义了动态基因突变率,并引入到和声搜索算法中,有效地阻止了算法陷入局部最优解.其次,应用动态优先值编码方案,根据和声向量中变量对应节点的优先值来构造路径,通过迭代更新和声记忆库,并最终获得最短路径.对由20~100个节点构成的网络拓扑进行仿真实验,应用三种性能指标来比较所提算法与粒子群算法和原始和声搜索算法在解决最短路径方面的性能.实验结果表明,本文算法优于另两种最短路径搜索算法.

This paper proposed an improved global harmony search algorithm（IGHS） to solve the shortest path（SP） problem.Firstly,a dynamical genetic mutation probability was defined and introduced into the harmony search algorithm,which can effectively prevent the IGHS from trapping into the local optimum.Secondly,a dynamical priority-based encoding approach was used for harmony representation in IGHS,and a path will be built according to the value of decision variable in the harmony vector.The shortest path will be obtained through updating harmonic memory.The experiments have been carried out on different network topologies for networks consisting of 20～100 nodes,and three performance indexes were used to compare the proposed algorithm with PSO-based and traditional harmony search（HS） based shortest path searching algorithm.It is shown that the performance of the proposed algorithm surpasses PSO-based and HS-based approaches for this problem