Cross Entropy Method for Solving Generalized Orienteering Problem
- 1
- 2
Abstract
Optimization technique has been growing rapidly throughout the years. It is caused by the growing complexity of problems that require a relatively long time to solve using exact optimization approach. One of complex problems that is hard to solve using the exact method is Generalized Orienteering Problem (GOP), a combinatorial problem including NP-hard problem. Recently, there has been plenty of heuristic method development to solve this problem. This research is an implementation of cross entropy (CE) method in real case of GOP. CE is an optimization technique that relatively new, using two main procedures; generating sample solution and parameter updating to produce better sample for next iteration. At this research, GOP problem that occurs at finding optimal route consist of 27 cities in eastern China is investigated. Results indicate that CE method give better performance than those of Artificial Neural Network (ANN) and Harmony Search (HS).
- Z. Sevkli, and F. dan E. Sevilgen, “Variable Neigh- borhood Search for the Orienteering Problem,” A. Levi et al., Eds., ISCIS, Springer-Verlag, Berlin, Heidelberg, 2006, pp. 134-143.
- Q. Wang, X. Sun, B. L. Golden and J. Jia, “Using Artificial Neural Networks to Solve the Orienteering Problem,” Annals of Operations Research, Vol. 61, No. 1, 1995, pp. 111-120.
- Tasgetiren and M. Fatih, “A Genetic Algorithm with an Adaptive Penalty Function for Orienteering Problem,” Journal of Economic and Social Research, Vol. 4, No. 2, 2000, pp. 1-26.
- G. Z. Woo, T. C. Li, D. Park and J. Yong, “Harmony Search for Generalized Orienteering Problem: Best Touring in China,” L. Wang, K. Chen and Y. S. Ong, Eds., Springer-Verlag, Berlin Heidelberg, 2005, pp. 741- 750.
- Z. Sevkli and F. dan E. Sevilgen, “Particle Swarm Optimization for the Orienteering Problem,” Proceedings of International Symposium on Innovation in Intelligent Systems and Applications, Istanbul, 2007, pp. 185-190.
- R. Rubinstein and D. Kroese, “The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization,” Monte-Carlo Simulation, and Machine-Learning, Springer-Verlag, Berlin, Heidelberg, 2004.
- H. Zhou, J. Wang and Y. Qiu, “Application of the Cross Entropy Method to the Credit Risk Assessment in an Early Warning System,” International Symposiums on Information Processing, 2008.
- R. Y. Rubinstein, “Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-Event Estimation,” Methodology and Computing in Applied Probability, Vol. 7, No. 1, 2005, pp. 5-50.
- D. Magee, “A Sequential Scheduling Approach to Combining Multiple Object Classifiers Using Cross-Entropy,” T. Windeatt and F. Roli, Eds., Springer-Verlag, Berlin, Heidelberg, 2003, pp. 135-145.
- D. P. Kroese and K.-P. Hui, “Applications of the Cross- Entropy Method in Reliability,” Computational Intelligence in Reliability Engineering, Vol. 40, 2007, pp. 37- 82.