Advanced Backtracking Genetic Algorithm for TSP
Genetic algorithm is used widely for the optimization, and some problems bother with users long time, such as prematurity, how to select proper operators, etc. Illuminated from the atavism in organic evolution, backtracking is banded together with genetic
- PDF / 223,121 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 77 Downloads / 196 Views
Abstract Genetic algorithm is used widely for the optimization, and some problems bother with users long time, such as prematurity, how to select proper operators, etc. Illuminated from the atavism in organic evolution, backtracking is banded together with genetic algorithm to solve the problem of prematurity. This method makes genetic algorithm out of local optimum, and prematurely, converging problem is solved with the selection of proper backtracking strategy, which includes partial backtracking, and variable distance sampling, etc. Then, the traveling seller problem is solved with an elaborate design of genetic operators, and pruning method is used to insure higher convergence velocity. The simulation experiment indicates that this algorithm can get preferable result than others. Keywords Optimal combination
Evolution algorithm Partial backtracking
1 Introduction Traveling salesman problem (TSP) is a classical combination optimization problem. Many real problems can be solved by translated into a TSP [1]. The number of paths for a TSP is rising at an exponential rate with the number of cities, so it is an NP-complete problem [2], and will maintain the standard for new algorithm. As an evolution algorithm drawing lessons from organism genetic process, genetic algorithm is applied to many subjects or area, such as combinational optimization, functional optimization, automatic control, machine learning, data mining, etc. As an NP-complete problem, a TSP is hardly solved in polynomial time by deterministic algorithm, and so often solved with approximate algorithm, such as genetic algorithm. As genetic algorithm is used, prematurely convergence is an extrusive problem. L. Tan (&) X. Liu Key Laboratory of Machine Vision and Intelligent Information System, Chongqing University of Arts and Sciences, Chongqing, China e-mail: [email protected]
Z. Wen and T. Li (eds.), Foundations of Intelligent Systems, Advances in Intelligent Systems and Computing 277, DOI: 10.1007/978-3-642-54924-3_96, Springer-Verlag Berlin Heidelberg 2014
1025
1026
L. Tan and X. Liu
Many scholars severally advanced their improved solutions. Chen brought forward a genetic operator improving method based on neighbor-select strategy in [3]. Xu accelerated the convergence of local searching by interchanging developmental crossing operator in [4]. Wang combined greedy algorithm and simulated annealing algorithm to improve operator in [5]. Xu constructed initial population in a special method and get a better result in [6]. Cao restrained the prematurity by inducting adaptive operator and local regressive operator in [7]. Yang advanced algorithm with re-evolving to disused chromosomes in [8]. Li classified the population based on fuzzy clustering in [9]. In above-mentioned methods, some were too complex, and they all did not radically solve premature problem. In this paper, backtracking strategy is imported into genetic algorithm, so as to get the better performance and global convergency. The emulation indicated that the method could achieve th
Data Loading...
