[1]丁华福 刘晓路 唐远新 石福斌.面向旅行商问题的一种改进遗传算法[J].计算机技术与发展,2011,(06):51-54.
　DING Hua-fu,LIU Xiao-lu,TANG Yuan-xin,et al.An Improved Genetic Algorithm for Traveling Salesman Problem[J].,2011,(06):51-54.
点击复制

面向旅行商问题的一种改进遗传算法()
分享到：

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

卷:
期数:
2011年06期
页码:
51-54
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
An Improved Genetic Algorithm for Traveling Salesman Problem
文章编号:
1673-629X（2011）06-0051-04
作者:
丁华福 刘晓路 唐远新 石福斌
哈尔滨理工大学计算机科学与技术学院
Author(s):
DING Hua-fu; LIU Xiao-lu; TANG Yuan-xin; SHI Fu-bin
Sch.of Computer Sci.and Tech.,Harbin Univ.of Sci.and Tech
关键词:
遗传算法; 种群多样性; 启发式交叉算子; 二分局部搜索; 自适应遗传参数
Keywords:
genetic algorithm;  population variation;  heuristic crossover operation;  second detach local search;  self-adapt genetic parameter
分类号:
TP301.6
文献标志码:
A
摘要:
针对传统遗传算法解决组合优化领域的典型难题——旅行商问题时存在的缺陷与不足,对传统遗传算法加以改进。引入了种群熵和基因座多样性来测度种群的多样性,并利用求得的测度值修改了个体的适应度,达到了预期目的。还提出启发式交叉算子、二分局部搜索、自适应遗传参数,使该算法在提高搜索效率与解质量方面取得了综合平衡。在算法的仿真和测试中,改进后的算法明显优于传统的遗传算法。这表明,该算法具有良好的可行性和实用性
Abstract:
By analyzing the deficiency of traditional genetic algorithm in solving the traveling salesman problem,one representative problem of the combination optimization,the algorithm structure of traditional genetic algorithm was improved.Entropy and the locus of population diversity are introduced to measure the population diversity in this paper,and the measure values obtained are used to modify the fitness of the individual to achieve the desired purpose.Also introduces self-adjust adapt value and proposing heuristic crossover operation,second detach local searching and self-adapt genetic parameter,the algorithm achieved a balance between quality and efficiency.According to the analysis and test,the improved genetic algorithm can get the better result than the traditional genetic algorithm.This shows that the method has better feasibility and practicability

相似文献/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(06):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,(06):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,(06):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,(06):121.
[5]张磊 王晓军.基于遗传算法的业务流程测试[J].计算机技术与发展,2010,(03):155.
　ZHANG Lei,WANG Xiao-jun.Test of Business Process Based on Genetic Algorithm[J].,2010,(06):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,(06):44.
[7]范维博 周俊 许正良.应用遗传算法求解第一类装配线平衡问题[J].计算机技术与发展,2010,(02):194.
　FAN Wei-bo,ZHOU Jun,XU Zheng-liang.Appication of Genetic Algorithm to Assembly Line Balancing[J].,2010,(06):194.
[8]熊伟平 曾碧卿.几种仿生优化算法的比较研究[J].计算机技术与发展,2010,(03):9.
　XIONG Wei-ping,ZENG Bi-qing.Studies on Some Bionic Optimization Algorithms[J].,2010,(06):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,(06):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,(06):158.
[11]鲁群 周爱武.双变异算子遗传算法的应用[J].计算机技术与发展,2008,(07):42.
　LU Qun,ZHOU Ai-wu.Application of Genetic Algorithm Based on Dual Mutation[J].,2008,(06):42.

备注/Memo

备注/Memo:
黑龙江省教育科研项目（11531049）丁华福（1962-），男，哈尔滨人，硕士研究生导师，研究员，研究方向为数据挖掘、数据库
更新日期/Last Update: 1900-01-01