Adapting the Chemical Reaction Optimization Algorithm to the Printed Circuit Board Drilling Problem
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:68934", author = "Taisir Eldos and Aws Kanan and Waleed Nazih and Ahmad Khatatbih", title = "Adapting the Chemical Reaction Optimization Algorithm to the Printed Circuit Board Drilling Problem", 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.", volume = "9", number = "1", pages = "247-6", }
