东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2011, Vol. 32 ›› Issue (6): 769-772.DOI: -

• 论著 • 上一篇    下一篇

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

高立群;依玉峰;郑平;程伟;   

  1. 东北大学信息科学与工程学院;
  • 收稿日期:2013-06-19 修回日期:2013-06-19 发布日期:2013-04-04
  • 通讯作者: -
  • 作者简介:-
  • 基金资助:
    国家自然科学基金资助项目(60674021)

The application of harmony search algorithm for solving shortest path problems

Gao, Li-Qun (1); Yi, Yu-Feng (1); Zheng, Ping (1); Cheng, Wei (1)   

  1. (1) School of Information Science and Engineering, Northeastern University, Shenyang 110819, China
  • Received:2013-06-19 Revised:2013-06-19 Published:2013-04-04
  • Contact: Yi, Y.-F.
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

1214

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

关键词: 和声搜索算法, 最短路径, 基因突变, 优先值编码, 网络拓扑

Abstract: 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.

中图分类号: