[1]马超.遗传算法和Dijkstra算法在动态权值系统中的比较[J].计算机技术与发展,2012,(09):21-24.
　MA Chao.Comparison of Genetic Algorithm and Dijkstra Algorithm in Dynamic Weight System[J].,2012,(09):21-24.
点击复制

遗传算法和Dijkstra算法在动态权值系统中的比较()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2012年09期
页码:
21-24
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
Comparison of Genetic Algorithm and Dijkstra Algorithm in Dynamic Weight System
文章编号:
1673-629X（2012）09-0021-04
作者:
马超
西北大学软件学院
Author(s):
MA Chao
College of Software, Northwest University
关键词:
遗传算法; Dijkstra算法; 最短路径; 动态权值
Keywords:
genetic algorithm;  Dijkstra algorithm;  shortest path ;  dynamic weight
分类号:
TP301.6
文献标志码:
A
摘要:
针对遗传算法和Dijkstra算法在求解动态权值系统中最短路径时的性能问题，采用比较法，将两种算法应用在同一个实际游戏模型中，对其算法的稳定性、智能性、时间复杂度进行对比测试。游戏模型模拟了各种条件下的动态权值系统。为了使遗传算法更加可靠，通过优化其变异过程使得收敛速度更快，可靠性更高。实验数据表明，遗传算法在每张地图上的得分数以及算法所用时间普遍高于Dijkstra算法，从而得出遗传算法在求解动态权值系统中最短路径问题时稳定性和预期效果明显好于Dijkstra算法，但其时间复杂度较高的结论
Abstract:
Used a comparative approach to compare the performance of the genetic algorithm with the Dijkstra algorithm when solve the shortest path problem in the dynamic weight system. Did an experiment in the actual model with these two algorithms in order to test their stability, intelligence and time complexity. The game model makes many kinds of dynamic weight system. In order to make the genetic algorithm more reliable, the new algorithm gets a way to optimize the process of mutation to make the speed of the genetic algorithm faster and the reliability better. The experiment data shows that most data of the genetic algorithm is higher than the Dijkstra algorithm. The experiment makes a conclusion that the stability and expected result of the genetic algorithm is better than the Dijkstra algorithm in the dynamic weight system, but the time complexity of algorithm is higher than the Dijkstra algorithm

相似文献/References:

[1]冯智明,苏一丹,覃华,等.基于遗传算法的聚类与协同过滤组合推荐算法[J].计算机技术与发展,2014,24(01):35.
　FENG Zhi-ming,SU Yi-dan,QIN Hua,et al.Recommendation Algorithm of Combining Clustering with Collaborative Filtering Based on Genetic Algorithm[J].,2014,24(09):35.
[2]余晓光 严洪森 殷乾坤.基于Flexsim的车间调度优化[J].计算机技术与发展,2010,(03):44.
　YU Xiao-guang,YAN Hong-sen,YIN Qian-kun.Workshops Scheduling Optimization Based on Flexsim Simulation[J].,2010,(09):44.
[3]贺计文 宋承祥 刘弘.基于遗传算法的八数码问题的设计及实现[J].计算机技术与发展,2010,(03):105.
　HE Ji-wen,SONG Cheng-xiang,LIU Hong.Design and Implementation of Eight Puzzle Problem Based on Genetic Algorithms[J].,2010,(09):105.
[4]沈珏萍 庄亚明.基于Agent的二级供应链企业自动谈判研究[J].计算机技术与发展,2010,(03):121.
　SHEN Jue-ping,ZHUANG Ya-ming.A Research for Company Automatic Negotiation in Secondary Supply Chain Based on Agent[J].,2010,(09):121.
[5]张磊 王晓军.基于遗传算法的业务流程测试[J].计算机技术与发展,2010,(03):155.
　ZHANG Lei,WANG Xiao-jun.Test of Business Process Based on Genetic Algorithm[J].,2010,(09):155.
[6]曹道友 程家兴.基于改进的选择算子和交叉算子的遗传算法[J].计算机技术与发展,2010,(02):44.
　CAO Dao-you,CHENG Jia-xing.A Genetic Algorithm Based on Modified Selection Operator and Crossover Operator[J].,2010,(09):44.
[7]范维博 周俊 许正良.应用遗传算法求解第一类装配线平衡问题[J].计算机技术与发展,2010,(02):194.
　FAN Wei-bo,ZHOU Jun,XU Zheng-liang.Appication of Genetic Algorithm to Assembly Line Balancing[J].,2010,(09):194.
[8]熊伟平 曾碧卿.几种仿生优化算法的比较研究[J].计算机技术与发展,2010,(03):9.
　XIONG Wei-ping,ZENG Bi-qing.Studies on Some Bionic Optimization Algorithms[J].,2010,(09):9.
[9]余晓光 严洪森.基于禁忌搜索遗传混合算法的装配线平衡[J].计算机技术与发展,2010,(05):5.
　YU Xiao-guang,YAN Hong-sen.Assembly Line Balancing Based on Tabu Search and Genetic Hybrid Algorithm[J].,2010,(09):5.
[10]黄永聪 张旭[] 吴义纯 吴琦 程家兴.改进的径向基函数网络的研究及应用[J].计算机技术与发展,2010,(05):158.
　HUANG Yong-cong,ZHANG Xu,WU Yi-chun,et al.Research and Application of Improved Genetic Algorithm-Based RBFANN[J].,2010,(09):158.

备注/Memo

备注/Memo:
陕西省科技攻关项目（2009k01-53）马超（1990-），男，陕西安康人，软件工程师，研究方向为网络与信息安全
更新日期/Last Update: 1900-01-01