|
|
|
| Solving TSP Problems with Estimation of Distribution Algorithm Based on Superiority Pattern Junction |
| HE Xiao-Juan1,2, ZENG Jian-Chao2 |
1.College of Electrical and Information Engineering, Lanzhou University of Technology, Lanzhou 730050
2.Complex System and Computational Intelligence Laboratory, Taiyuan University of
Science and Technology, Taiyuan 030024 |
|
|
|
|
Abstract An estimation of distribution algorithm for TSP problems based on superiority pattern junction is proposed. The pairwise adjacent pattern matrix is constructed, then the junction blocks are built combining with superiority individual information. Each block is adjusted as a whole to avoid repeating search. Therefore, the disruption of superiority building blocks is solved and the search speed is improved. Meanwhile, the patterns within each block is made local adjustment under special conditions to enhance the local search ability. The simulation results show that the proposed algorithm has better efficiency in solving the TSP problems.
|
|
Received: 17 August 2009
|
|
|
|
|
|
[1] Pelikan M, Goldberg D E, Lobo F G. A Survey of Optimization by Building and Using Probabilistic Models. Computational Optimization and Applications, 2002, 21(1): 5-20
[2] Harik G R, Lobo F G, Goldberg D E. The Compact Genetic Algorithm. IEEE Trans on Evolutionary Computation, 1999, 3(4): 287-297
[3] Baluja S. Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning. Technical Report, CMU-CS-94-163, Pittsburgh, USA: Carnegie Mellon University. Department of Computer Science, 1994
[4] de Bonnet J S, Isbell C L, Viola P. MIMIC: Finding Optima by Estimating Probability Densities // Jordan M I, Kearns M J, Solla S A, eds. Advances in Neural Information Processing Systems, Cambridge, USA, MIT Press, 1997, IX: 424-430
[5] Zhou Shude, Sun Zengqi. A Survey on Estimation of Distribution Agorithm. Acta Automatica Sinica, 2007, 33(2): 113-124 (in Chinese)
(周树德,孙增圻.分布估计算法综述,自动化学报, 2007, 33(2): 113-124)
[6] Paul T K, Iba H. Linear and Combinatorial Optimizations by Estimation of Distribution Algorithms // Proc of the 9th MPS Symposium on Evolutionary Computation. Nagoya Japan, 2002: 1-8
[7] Leung K S, Jin Huidong, Xu Zongben. A Expanding Self-Organizing Neural Network for the Travel Salesman Problem. Neuron Computing, 2004, 62: 267-292
[8] DePuy G W, Whitehouse G E. Meta-RaPS: A Simple and Effective Approach for Solving the Traveling Salesman Problem. Transportation Research Part E: Logistics and Transportation Review, 2005, 41(2): 115-130
[9] Tsai C F, Tsai C W, Tseng C. A New Hybrid Heuristic Approach for Solving Large Traveling Salesman Problem. Information Sciences, 2004, 166(1): 67-81
[10] Mühlenbein H, Paass G. From Recombination of Genes to the Estimation of Distributions I. Binary Parameters // Proc of the 4th International Conference on Parallel Problem Solving from Nature. Berlin, Germany, 1996: 178-187
[11] Tsutsui S. Probabilistic Model-Building Genetic Algorithms in Permutation Representation Domain Using Edge Histogram // Proc of the 7th Parallel Problem Solving from Nature. Granada, Spain, 2002: 224-233
[12] Larranaga P, Lozano J A. Estimation of Distribution Algorithms. Dordrecht, Netherlands: Kluwer Academic Publishers, 2002
[13] Ventresca M, Tizhoosh H R. A Diversity Maintaining Population-Based Incremental Learning Algorithm. Information Sciences, 2008, 178(21): 4038-4056
[14] Oliver I M, Smith D J, Holland J R C. A Study of Permutation Crossover Operators on the Travel Salesman Problem // Proc of the 2nd International Conference on Genetic Algorithms. Cambridge, USA, 1987: 224-230
[15] Starkweather T, McDaniel S, Mathias K, Whitley D, Whitley C. A Comparison of Genetic Sequence Operators // Proc of the 4th International Conference on Genetic Algorithms. San Diego, USA, 1991: 69-76
[16] Tsutsui S, Pelikan M, Ghosh A. Effect of Local Search on Edge Histogram Based Sampling Algorithms for Permutation Problems. // Proc of the 6th Meta-Heuristics International Conference. Vienna, Austria, 2005: 865-872
[17] Lin S, Kernighan B W. An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research, 1973, 21: 498-516
[18] Helsgaun K. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. European Journal of Operational Research, 2000, 126(1):106-130 |
|
|
|
2011, Vol. 24 
