Adapting the Chemical Reaction Optimization Algorithm to the Printed Circuit Board Drilling Problem

Authors: Taisir Eldos, Aws Kanan, Waleed Nazih, Ahmad Khatatbih

Abstract:

Chemical Reaction Optimization (CRO) is an optimization metaheuristic inspired by the nature of chemical reactions as a natural process of transforming the substances from unstable to stable states. Starting with some unstable molecules with excessive energy, a sequence of interactions takes the set to a state of minimum energy. Researchers reported successful application of the algorithm in solving some engineering problems, like the quadratic assignment problem, with superior performance when compared with other optimization algorithms. We adapted this optimization algorithm to the Printed Circuit Board Drilling Problem (PCBDP) towards reducing the drilling time and hence improving the PCB manufacturing throughput. Although the PCBDP can be viewed as instance of the popular Traveling Salesman Problem (TSP), it has some characteristics that would require special attention to the transactions that explore the solution landscape. Experimental test results using the standard CROToolBox are not promising for practically sized problems, while it could find optimal solutions for artificial problems and small benchmarks as a proof of concept.

Keywords: Evolutionary Algorithms, Chemical Reaction Optimization, Traveling Salesman, Board Drilling.

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

References:

[1] Goldberg DE (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA, USA.
[2] Kennedy J, Eberhart RC (2001) Swarm Intelligence. MorganKaufmann, San Francisco.
[3] Ong YS, Lim MH, Chen XS (2010) Research Frontier: Memetic Computation Past, Present and Future. IEEE Computational Intelligence Magazine 5(2):24–36.
[4] ChenXS, OngYS, LimMH, TanKC (2011) A Multifacet Survey on Memetic Computation. IEEE Trans Evolutionary Computation 15(5):591–607.
[5] Price K, Storn R, Lampinen J (2005) Differential Evolution: APractical Approach to Global Optimization. Springer, Berlin.
[6] Dorigo M, Stutzle T (2004) Ant Colony Optimization. The MITPress, Cambridge, MA, USA.
[7] Geem ZW, Kim JH, Loganathan GV (2001) A New Heuristic Optimization Algorithm: Harmony Search. Simulation 76(2):60–68.
[8] Lam AYS, Li VOK (2010) Chemical-Reaction-Inspired Metaheuristic for Optimization. IEEE Trans Evolutionary Computation 14(3):381– 399.
[9] E. Rashedi, H. Nezamabadipour, and S. Saryazdi, "GSA: A Gravitational Search Algorithm." Journal of Information of Science 179, 2232-2243, 2009.
[10] Rose Alqasem, Taisir Eldos, “An Efficient cell Placement Algorithm Using Gravitational Search Algorithms”, Journal of Computer Science 9 (8): 943-948, 2013.
[11] Scott Kirkpatrick, ”Optimization by simulated annealing: Quantitative studies”, Journal of Statistical Physics, Vol 34, Issue 5-6, 975-986, 1984.
[12] Jin Xu, Albert Y.S. Lam, Victor O.K. Li, "Chemical Reaction Optimization for the Grid Scheduling Problem," IEEE Communications Society, publication in the IEEE ICC, 2010.
[13] Albert Y.S. Lam and Victor O.K. Li, "Chemical Reaction Optimization for Cognitive Radio Spectrum Allocation, "IEEE Communications Society, Proceedings of Globecom, 2010.
[14] A. Y. S. Lam, V. O. K. Li, and J. J. Q. Yu, “Real-Coded Chemical Reaction Optimization,” IEEE Trans Evolutionary Computation, Vol. 16, No. 3, 339–353, Jun. 2012.
[15] K. Helsgaun, An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic, European Journal Operations Research 126, 106-130, 2000.
[16] Y. Chen, P. Zhang, Optimized Annealing of Traveling Salesman Problem from the nth-Nearest-Neighbor Distribution, Physica A: Statistical Mechanics and its Applications, Vol. 371, Issue 3, 627- 632,2006.
[17] C.-N. Fiechter, A Parallel Tabu Search Algorithm for Large Traveling Salesman Problems, Discrete Applied Mathematics 51, 243-26, 1994.
[18] M. Albayrak, N. Allahverdi, N.: Development a New Mutation Operator to Solve the Traveling Salesman Problem by Aid of Genetic Algorithms, Expert System Applications 38 , 1313-1320, 2011.
[19] N. Mladenović, P. Hansen, Variable neighborhood search, Computational Operations Research 24, 1097-1100, 1997.
[20] J.C. Créput, A. Koukam, A Memetic Neural Network for the Euclidean Traveling Salesman Problem. Neurocomputing 72,1250-1264, 2009.
[21] C.F. Tsai, C.W. Tsai, C.C. Tseng, A New Hybrid Heuristic Approach for Solving Large Traveling Salesman Problem, Information Science. 166,67-81, 2004.
[22] X.H. Shi, Y.C. Liang, H.P.Lee, C. Lu, Q.X. Wang, Particle Swarm Optimization-Based Algorithms for TSP and Generalized TSP, Information Proceeding Letter. 103,169-176, 2007.
[23] Helmi Md Rais, Zulaiha Ali Othman, Abdul Razak Hamdan, “Improved Dynamic Ant Colony System (DACS) on symmetric Traveling Salesman Problem,” International Conference on Intelligent and Advanced Systems,43-48, 2007.
[24] Ahmed Rabie Ginidi Ginidi, Ahmed M. A. M. Kamel, Hassen Taher Dorrah, “Development of New Fuzzy Logic-based Ant Colony Optimization Algorithm for Combinatorial Problems, “Proceedings of the 14th International Middle East Power Systems Conference, Cairo University, Egypt, 2010.
[25] Wolpert DH, Macready WG (1997) No Free Lunch Theorems for Optimization. IEEE Trans Evolutionary Computation 1(1):67–82.