摘要
提出了一种带有启发信息的邻接表结点存储结构模型,给出了结点间权值计算的具体评判函数,依据评判函数值优化邻接表中节点的相对位置。基于最短路径问题提出了带有启发信息的遗传算法思想,将启发信息加入到了初始种群生成过程中,提出了新的交叉方法。通过模拟仿真得到了算法的性能参数,并将本文算法和Dijkstra算法进行比较,结果表明,在求解数据规模比较大的最短路径问题时,本文算法具有更高的执行效率。
An adjacency list storage model with heuristic information is proposed. An evaluation function to calculate the weight among nodes was derived. The relative position of the node in the adjacency list was optimized using the evaluation function. The process of initial population with heuristic information and chromosome coding, and the strategy of dynamic adjustment of the fitness function were presented. The main performance parameters were obtained by simulation, and the proposed algorithm was compared with the Dijkstra algorithm. Experiment results show that the proposed algorithm possesses higher efficiency when solving the optimization problem of shortest path with high spatial complexity.
出处
《吉林大学学报（工学版）》
EI
CAS
CSCD
北大核心
2011年第1期182-187,共6页
Journal of Jilin University:Engineering and Technology Edition
基金
'十一五'国家科技支撑计划重大项目(2006BAK01A33)
