순서화 문제에서 이산적 Particle Swarm Optimization들의 성능 비교
Performance Comparison of Discrete Particle Swarm Optimizations in Sequencing Problems
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
Particle Swarm Optimization (PSO) which has been well known to solve continuous problems can be applied to discrete combinatorial problems. Several DPSO (Discrete Particle Swarm Optimization) algorithms have been proposed to solve discrete problems such as traveling salesman, vehicle routing, and flow shop scheduling problems. They are different in representation of position and velocity vectors, operation mechanisms for updating vectors. In this paper, the performance of 5 DPSOs is analyzed by applying to traditional Traveling Salesman Problems. The experiment shows that DPSOs are comparable or superior to a genetic algorithm (GA). Also, hybrid PSO combined with local optimization (i.e., 2-OPT) provides much improved solutions. Since DPSO requires more computation time compared with GA, however, the performance of hybrid DPSO is not better than hybrid GA.
Abstract
Particle Swarm Optimization (PSO) which has been well known to solve continuous problems can be applied to discrete combinatorial problems. Several DPSO (Discrete Particle Swarm Optimization) algorithms have been proposed to solve discrete problems such as traveling salesman, vehicle routing, and flow shop scheduling problems. They are different in representation of position and velocity vectors, operation mechanisms for updating vectors. In this paper, the performance of 5 DPSOs is analyzed by applying to traditional Traveling Salesman Problems. The experiment shows that DPSOs are comparable or superior to a genetic algorithm (GA). Also, hybrid PSO combined with local optimization (i.e., 2-OPT) provides much improved solutions. Since DPSO requires more computation time compared with GA, however, the performance of hybrid DPSO is not better than hybrid GA.
참고문헌 (17)
- Anghinolfi,D, "A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times", European Journal of Operations Research, 193, pp.73~85 (2009)
- Chandrasekaran,S, "An Application of particle swarm optimization algorithm to permutation flow shop scheduling problems to minimize makespan,total flowtime and completion time variance", 2006 IEEE International Conference on Automation Science and Engineering, pp.513~518 (2006)
- Cunkas,M, "A Comparative Study on Particle Swarm Optimization and Genetic Algorithms for Traveling Salesman Problems", Cybernetics and Systems:An International Journal, 40, pp.490~507 (2009)
- Davis,L, "Applying Adaptive Algorithms to Epistatic Domains", Proceedings of the International Joint Conference on Artificial Intelligence, pp.162~164 (1985)
- Goldberg,D.E, "Alleles, Loci, and the TSP", Proceedings of the First International Conference on Genetic Algorithms, pp.154~159 (1985), Lawrence Erlbaum Associates
- Hu,X, "Swarm Intelligence for Permutation Optimization:A Case Study of n-Queens Problem", 2003 IEEE Swarm Intelligence Symposium, pp.243~246 (2003)
- Johnson,D.S, "The Traveling Salesman Problem : A Case Study in Local Optimization,” Local Search in Combinatorial Optimization", pp.215~310 (1997), John Whiley and Sons
- Kennedy,J, "Particle Swarm Optimization", Proceeding of the 1995 IEEE International Conference on Neural Networks, pp.1942~1948 (1995)
- Liao,Ching-Jong, "A discrete version of particle swarm optimization for flowshop scheduling problems", Computers and OR, 34, pp.3099~3111 (2007)
- Marinakis,Y, "A Hybrid genetic-Particle Swarm Optimization Algorithms for the Vehicle Routing Problem", Expert Systems with Applications, 37, pp.1446~1455 (2010)
- Oliver,I.M, "A Study of Permutation Crossover Operators on the traveling Salesman Problem", Proceedings of the Second International Conference on Genetic Algorithms, pp.224~230 (1987), Lawrence Erlbaum Associates
- Pang W, "Fuzzy discrete particle swarm optimization for traveling salesman problem", Proceedings of the fourth international conference on computing and information technology(CIT’04), pp.796~800 (2004)
- Potvin,J.Y, "Genetic Algorithms for the Traveling Salesman Problem", Annals of Operations Research, 63, pp.339~370 (1996)
- Shi,X.H, "Particle Swarm Optimization-based algorithms for TSP and generalized TSP", Information Processing Letters, 103, pp.169~176 (2007)
- Tasgetiren,F, "Particle Swarm Optimization algorithm for single machine weighted tardiness problem", Proceedings IEEE congress on evolutionary computation, pp.1412~1419 (2004)
- Zhong,Wei-Liang, "A novel discrete particle swarm optimization to solve traveling salesman problem", Proceedings IEEE Congress on Evolutionary Computation, pp.3283~3287 (2007)
- "TSPLIB"[URL]