A Fast Block-based Evolutional Algorithm for Combinatorial Problems
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:64930", author = "Huang and Wei-Hsiu Chang and Pei-Chann and Wang and Lien-Chun", title = "A Fast Block-based Evolutional Algorithm for Combinatorial Problems", 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", volume = "6", number = "7", pages = "914-7", }
