A New Hybrid Genetic Algorithm for Traveling Salesman Problem

doi:10.3969/j.issn.1006-2475.2010.11.004

Computer and Modernization ›› 2010, Vol. 1 ›› Issue (11): 12-15.doi: 10.3969/j.issn.1006-2475.2010.11.004

• 算法设计与分析 • Previous Articles Next Articles

A New Hybrid Genetic Algorithm for Traveling Salesman Problem

HU Zhi-wei¹, QIE Pei², ZHAO Xin-chao³, LI Xian-xu¹

1.School of Information and Telecommunication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China; 2.School of Computer, Beijing University of Posts and Telecommunications, Beijing 100876, China; 3.Department of Mathematics, School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received:2010-08-10 Revised:1900-01-01 Online:2010-11-25 Published:2010-11-25

Abstract

Abstract: The paper presents an improved hybrid genetic algorithm to solve the Traveling Salesman Problem (TSP). Based on the traditional genetic algorithm, Guo Tao algorithm is introduced to the crossover operation, which keeps good diversity and global search capability to overcome the shortcomings of premature convergence. PSO algorithm is introduced to the mutation operation, which accelerates the convergence rate, improves the solution quality, and finds the optimal solution more quickly. Verified by many examples from TSPLIB, the obtained results are better than the available optimal solutions, which demonstrate the efficiency and efficacy of the algorithm.

Key words: traveling salesman problem, genetic algorithm, Guo Tao algorithm, Particle Swarm Optimization

CLC Number:

TP301.6

HU Zhi-wei;QIE Pei;ZHAO Xin-chao;LI Xian-xu. A New Hybrid Genetic Algorithm for Traveling Salesman Problem[J]. Computer and Modernization, 2010, 1(11): 12-15.

[1]	WANG Jia1, GU Wenjun1, JU Weigang2, LI Yuwei1, ZHANG Yunlong2, MI Chuanmin3, ZHOU Zhipeng3. Environmental Topology Task Scheduling Based on Diverse Hierarchical Difference Optimization Genetic Algorithm [J]. Computer and Modernization, 2024, 0(10): 65-73.
[2]	WANG Zhiqiang, ZHENG Shuang. Semi-supervised Image Generation Model Based on StyleGAN [J]. Computer and Modernization, 2024, 0(06): 14-18.
[3]	WANG Dongyue, LIU Hao. Multi-agent Genetic Algorithm Based Cloud Platform Anti-fake Data Injection Attack Method [J]. Computer and Modernization, 2024, 0(04): 21-26.
[4]	LIU Xian-zhuo, DENG Wei-si, XIE En-yan. Adaptive Protection System for Distribution Network Considering Grid Connection of Distributed Generation [J]. Computer and Modernization, 2023, 0(09): 120-126.
[5]	ZHANG Zhi-xia, XIE Bao-qiang. Natural Gas Load Forecasting Based on FCGA-LSTM and Transfer Learning [J]. Computer and Modernization, 2023, 0(07): 7-12.
[6]	WANG Min, XU Ying-hao, ZHU Xi-jun. Prediction Model of Diabetic Complications Based on BP Neural Network Optimized by Improved Genetic Algorithm#br# [J]. Computer and Modernization, 2022, 0(11): 69-74.
[7]	WANG Yang, CHEN Mei, LI Hui. FOCoR: A Course Recommendation Approach Based on Feature Selection Optimization [J]. Computer and Modernization, 2022, 0(10): 1-7.
[8]	RAN Hao-jie, WANG Hong-zhi. Distribution Center Site Selection of Fresh Agricultural Products Based on Improved Simulated Annealing Algorithm [J]. Computer and Modernization, 2022, 0(10): 36-40.
[9]	ZHAN Jun-wei, ZHUANG Yi. Mobile Edge Computing Task Offloading Model and Algorithm Based on Energy Consumption and Delay Optimization [J]. Computer and Modernization, 2022, 0(08): 86-93.
[10]	WU Dai-yang, ZHAO Jie, LIANG Jia-ming, DONG Zhen-ning, LIANG Zhou-yang. Host Matching for C2C Online Short-term Rentals [J]. Computer and Modernization, 2022, 0(06): 43-48.
[11]	XU Sheng-chao, XIONG Mao-hua. Optimization of Container Cloud Resource Allocation Based on Genetic Algorithm [J]. Computer and Modernization, 2022, 0(01): 108-112.
[12]	XU Ming, ZHANG Jian-ming, CHEN Song-hang, CHEN Hao. Multi-objective Optimization Algorithm for Flexible Job Shop Scheduling Problem [J]. Computer and Modernization, 2021, 0(12): 1-6.
[13]	ZHANG Lin-peng, WANG Xi-yuan, LI Qiang. Image Classification Based on Double-pooling Feature Weighted Convolutional Neural Network [J]. Computer and Modernization, 2021, 0(11): 67-71.
[14]	YANG Xiao-dong. Risk Assessment Model of Accounting Resource Sharing Management Based on Genetic Algorithm [J]. Computer and Modernization, 2021, 0(06): 24-28.
[15]	LIU Jun, PENG Hui-xian, HUANG Bin, Tony SHAY. Breast Cancer Diagnosis Model Based on BP-GamysBoost [J]. Computer and Modernization, 2021, 0(04): 8-14.

A New Hybrid Genetic Algorithm for Traveling Salesman Problem

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments