A Fast Block-based Evolutional Algorithm for Combinatorial Problems

Authors: Huang, Wei-Hsiu Chang, Pei-Chann, Wang, Lien-Chun

Abstract:

The problems with high complexity had been the challenge in combinatorial problems. Due to the none-determined and polynomial characteristics, these problems usually face to unreasonable searching budget. Hence combinatorial optimizations attracted numerous researchers to develop better algorithms. In recent academic researches, most focus on developing to enhance the conventional evolutional algorithms and facilitate the local heuristics, such as VNS, 2-opt and 3-opt. Despite the performances of the introduction of the local strategies are significant, however, these improvement cannot improve the performance for solving the different problems. Therefore, this research proposes a meta-heuristic evolutional algorithm which can be applied to solve several types of problems. The performance validates BBEA has the ability to solve the problems even without the design of local strategies.

Keywords: Combinatorial problems, Artificial Chromosomes, Blocks Mining, Block Recombination

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1086073

References:

[1] P. C. Chang, S. H. Chen, C. Y. Fan, "Mining gene structures to inject artificial chromosomes for genetic algorithm in single machine scheduling problems," Applied Soft Computing Journal, vol. 8, no. 1, pp. 767-777, 2008.
[2] P. C. Chang, S. H. Chen, C. Y. Fan, C. L. Chan, "Genetic Algorithm with Artificial Chromosomes for Multi-Objective Flow shop Scheduling Problems," Applied Mathematics and Computation, vol. 205, no. 2, pp. 550-561, 2008.
[3] P. C. Chang, S. H. Chen, C. Y. Fan, "Generating Artificial Chromosomes with Probability Control in Genetic Algorithm for Machine Scheduling Problems," Annals of Operations Research, vol. 180, no. 1, pp. 197-211, 2010.
[4] G. Laporte, "The vehicle routing problem: An overview of exact and approximate algorithms," European Journal of Operational Research, vol. 59, no. 2, pp. 345-358, 1992.
[5] G. C. Onwubolu, M. Clerc, "Optimal path for automated drilling operations by a new heuristic approach using particle swarm optimization," International Journal of Production Research, vol. 44, no. 3, pp. 473-491, 2004.
[6] M. Affenzeller, S. Wanger, "A Self-Adaptive Model for Selective Pressure Handling within the Theory of Genetic Algorithms," Lecture Notes in Computer Science, vol. 2809, no. 1, pp. 384-393, 2003.
[7] M. Budinich, "A self-organizing neural network for the traveling salesman problem that is competitive with simulated annealing" Neural Computing, vol. 8, 416-424, 1996.
[8] G. Liu, Y. He, Y. Fang, Y. Oiu, "A novel adaptive search strategy of intensification and diversification in tabu search," Proceedings of Neural Networks and Signal Processing, Nanjing, China, 2003.
[9] L. Bianchi, J. Knowles, J. Bowler, "Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms." European Journal of Operational Research, vol. 162, no. 1, pp. 206-219, 2005.
[10] S. C. Chu, J. F. Roddick, J. S. Pan, "Ant colony system with communication strategies," Information Sciences, vol. 167, no. 1-4, pp. 63-76, 2004.
[11] K. S. Leung, H. D. Jin, Z. B. Xu, "An expanding self-organizing neural network for the traveling salesman problem," Neural computing, vol. 62, pp. 267-292, 2004.
[12] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, "Optimization by simulated annealing," Science, vol. 220, no. 4598, pp. 671-680, 1983.
[13] J. Grefenstette, R. Gopal, B. Rosimaita, D. van. Gucht, "Genetic algorithms for the traveling salesman problem," in Proc. Int. Conf. Genetics Algorithms and Their Applications, pp.160-168, 1985.
[14] H. C. Braun, "On solving traveling salesman problems by genetic algorithm," Lecture Notes in Computer Science, vol. 496, pp. 129-133, 1991.
[15] Z. Michalewicz, "Genetic Algorithms + Data Structures = Evolution Programs, 3rd ed," Berlin. Germany: Springer-Verlag, 1996.
[16] J. Fan, D. Li, "An overview of data mining and knowledge discovery," Journal of Computer Science and Technology, vol. 13, no. 4, pp. 348-368, 1998.
[17] P. Moscato, M. G. Norman, "A memetic approach for the traveling salesman problemÔÇöimplementation of a computational ecology for combinatorial optimization on message-passing systems," International conference on parallel computing and transputer application, IOS Press, Amsterdam, Holland, pp. 177-186, 1992.
[18] J. G. Skellam, "Studies in statistical ecology," I. Spatial pattern Biometrica, vol. 39, pp. 346-362, 1952.
[19] R. Pasti, L. N. de. Castro, "A Neuro-immune network for solving the traveling salesman problem," Proceedings of International Joint Conference on Neural Networks, vol. 6, pp. 3760-3766, 2006.
[20] S. Somhom, A. Modares, T. Enkawa, "A self-organizing model for the travelling salesman problem," Journal of the Operational Research Society, vol. 48, pp. 919-928, 1997.