American Institute of Mathematical Sciences

2011, 1(1): 191-209. doi: 10.3934/naco.2011.1.191

Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction

 1 Dept. of Computer Science, Faculty of Computers and Information, Assiut University, Assiut 71526 2 Department of Mathematics, Faculty of Science, Assiut University, Assiut, 71516, Egypt 3 Department of Information Systems, Faculty of Computers and Information, Assiut University, Assiut, 71526, Egypt

Received  October 2010 Revised  November 2010 Published  February 2011

The search for the global minimum of a potential energy function is very difficult since the number of local minima grows exponentially with the molecule size. The present work proposes the application of genetic algorithm and tabu search methods, which are called GAMCP (Genetic Algorithm with Matrix Coding Partitioning) [7], and TSVP (Tabu Search with Variable Partitioning) [8], respectively, for minimizing the molecular potential energy function. Computational results for problems with up to 200 degrees of freedom are presented and are favorable compared with other four existing methods from the literature. Numerical results show that the proposed two methods are promising and produce high quality solutions with low computational costs.
Citation: Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191
References:
 [1] H. J. C. Barbosa, C. Lavor and F. M. Raupp, A GA-simplex hybrid algorithm for global minimization of molecular potential energy function,, Annals of Operations Research, 138 (2005), 189. doi: 10.1007/s10479-005-2453-2. [2] M. Dražić, C. Lavor, N. Maculan and N. Mladenović, A continuous variable neighborhood search heuristic for finding the three-dimensional structure of a molecule,, European Journal of Operational Research, 185 (2008), 1265. doi: 10.1016/j.ejor.2006.06.052. [3] C. A. Floudas, J. L. Klepeis and P. M. Pardalos, Global optimization approaches in protein folding and peptide docking, , DIMACS Series in Discrete Metjematics and Theoretical Computer Science, (1999). [4] S. Garcia, A. Fernandez, J. Luengo and F. Herrera, A study of statistical techniques and performance measures for genetics-based machine learning, accuracy and interpretability,, Soft Computing, 13 (2009), 959. doi: 10.1007/s00500-008-0392-y. [5] A. Hedar, B. T. Ong and M. Fukushima, "Genetic algorithms with automatic accelerated termination,", Technical Report 2007-002, (2007), 2007. [6] A. Hedar, B. T. Ong and M. Fukushima, Genetic algorithms combined with accelerated mutation and automatic termination,, Submitted to Soft Computing., (). [7] A. Hedar and A. F. Ali, Genetic algorithm with population partitioning and space reduction for high dimensional problems,, International Conference on Computer Engineering $&$ Systems, (2009), 14. [8] A. Hedar and A. F. Ali, Tabu Search with variable partitioning for high dimensional problems,, The 7th International Conference on Informatics and Systems, (2010), 28. [9] F. Herrera, M. Lozano and J. L. Verdegay, Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis,, Artificial Intelligence Review, 12 (1998), 265. doi: 10.1023/A:1006504901164. [10] V. Kovačević-Vujčić, M. čangalović, M. Dražić and N. Mladenović, VNS-based heuristics for continuous global optimization,, In:L.T. Hoai An, (2004), 215. [11] C. Lavor and N. Maculan, A function to test methods applied to global minimization of potential energy of molecules,, Numerical Algorithms, 35 (2004), 287. doi: 10.1023/B:NUMA.0000021763.84725.b9. [12] N. Mladenović, J. Petrović, V. Kovačević and M. čangalović, Solving spread spectrum radar ployphase code design problem by tabu search and variable nieghbourhood search,, European Journal of Operational Research, 151 (2003), 389. doi: 10.1016/S0377-2217(02)00833-0. [13] P. M. Pardalos, D. Shalloway and G. L. Xue, Optimization methods for computing global minima of nonconvex potential energy function,, Journal of Global Optimization, 4 (1994), 117. doi: 10.1007/BF01096719. [14] A. Pogorelov, "Geometry, Mir Publishers,", Moscow, (1987). [15] D. J. Sheskin, "Handbook of Parametric and Nonparametric Statistical Procedures,", CRC Press, (2003). doi: 10.1201/9781420036268. [16] D. J. Wales, H. A. Scheraga, Global optimization of clusters, crystals and biomolecules,, Science, 285 (1999), 1368. doi: 10.1126/science.285.5432.1368. [17] J. H. Zar, "Biostatistical Analysis,", Prentice Hall, (1999).

show all references

References:
 [1] H. J. C. Barbosa, C. Lavor and F. M. Raupp, A GA-simplex hybrid algorithm for global minimization of molecular potential energy function,, Annals of Operations Research, 138 (2005), 189. doi: 10.1007/s10479-005-2453-2. [2] M. Dražić, C. Lavor, N. Maculan and N. Mladenović, A continuous variable neighborhood search heuristic for finding the three-dimensional structure of a molecule,, European Journal of Operational Research, 185 (2008), 1265. doi: 10.1016/j.ejor.2006.06.052. [3] C. A. Floudas, J. L. Klepeis and P. M. Pardalos, Global optimization approaches in protein folding and peptide docking, , DIMACS Series in Discrete Metjematics and Theoretical Computer Science, (1999). [4] S. Garcia, A. Fernandez, J. Luengo and F. Herrera, A study of statistical techniques and performance measures for genetics-based machine learning, accuracy and interpretability,, Soft Computing, 13 (2009), 959. doi: 10.1007/s00500-008-0392-y. [5] A. Hedar, B. T. Ong and M. Fukushima, "Genetic algorithms with automatic accelerated termination,", Technical Report 2007-002, (2007), 2007. [6] A. Hedar, B. T. Ong and M. Fukushima, Genetic algorithms combined with accelerated mutation and automatic termination,, Submitted to Soft Computing., (). [7] A. Hedar and A. F. Ali, Genetic algorithm with population partitioning and space reduction for high dimensional problems,, International Conference on Computer Engineering $&$ Systems, (2009), 14. [8] A. Hedar and A. F. Ali, Tabu Search with variable partitioning for high dimensional problems,, The 7th International Conference on Informatics and Systems, (2010), 28. [9] F. Herrera, M. Lozano and J. L. Verdegay, Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis,, Artificial Intelligence Review, 12 (1998), 265. doi: 10.1023/A:1006504901164. [10] V. Kovačević-Vujčić, M. čangalović, M. Dražić and N. Mladenović, VNS-based heuristics for continuous global optimization,, In:L.T. Hoai An, (2004), 215. [11] C. Lavor and N. Maculan, A function to test methods applied to global minimization of potential energy of molecules,, Numerical Algorithms, 35 (2004), 287. doi: 10.1023/B:NUMA.0000021763.84725.b9. [12] N. Mladenović, J. Petrović, V. Kovačević and M. čangalović, Solving spread spectrum radar ployphase code design problem by tabu search and variable nieghbourhood search,, European Journal of Operational Research, 151 (2003), 389. doi: 10.1016/S0377-2217(02)00833-0. [13] P. M. Pardalos, D. Shalloway and G. L. Xue, Optimization methods for computing global minima of nonconvex potential energy function,, Journal of Global Optimization, 4 (1994), 117. doi: 10.1007/BF01096719. [14] A. Pogorelov, "Geometry, Mir Publishers,", Moscow, (1987). [15] D. J. Sheskin, "Handbook of Parametric and Nonparametric Statistical Procedures,", CRC Press, (2003). doi: 10.1201/9781420036268. [16] D. J. Wales, H. A. Scheraga, Global optimization of clusters, crystals and biomolecules,, Science, 285 (1999), 1368. doi: 10.1126/science.285.5432.1368. [17] J. H. Zar, "Biostatistical Analysis,", Prentice Hall, (1999).
 [1] Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial & Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31 [2] Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279 [3] Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018142 [4] Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703 [5] Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial & Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469 [6] Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015 [7] Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017 [8] M. Montaz Ali. A recursive topographical differential evolution algorithm for potential energy minimization. Journal of Industrial & Management Optimization, 2010, 6 (1) : 29-46. doi: 10.3934/jimo.2010.6.29 [9] Ping-Chen Lin. Portfolio optimization and risk measurement based on non-dominated sorting genetic algorithm. Journal of Industrial & Management Optimization, 2012, 8 (3) : 549-564. doi: 10.3934/jimo.2012.8.549 [10] Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2018200 [11] Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070 [12] Cheng-Ta Yeh, Yi-Kuei Lin. Component allocation cost minimization for a multistate computer network subject to a reliability threshold using tabu search. Journal of Industrial & Management Optimization, 2016, 12 (1) : 141-167. doi: 10.3934/jimo.2016.12.141 [13] Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029 [14] Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 [15] Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19 [16] Yang Chen, Xiaoguang Xu, Yong Wang. Wireless sensor network energy efficient coverage method based on intelligent optimization algorithm. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 887-900. doi: 10.3934/dcdss.2019059 [17] Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240 [18] Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391 [19] Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99 [20] Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193

Impact Factor: