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 and 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-202. 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-1273. 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, American Mathematical Society, (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-977. 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, Department of Applied Mathematics and Physics, Kyoto University, (January 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, ICCES 2009, (14-16 Dec. 2009), 151-156.

[8]

A. Hedar and A. F. Ali, Tabu Search with variable partitioning for high dimensional problems, The 7th International Conference on Informatics and Systems, INFOS 2010, (28-30 March 2010), 1-8.

[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-319. 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, P.D. Tao (Eds), Modelling. Computation and Optimization in Information Systems and Management Sciences, Hermes Science Publishing Ltd, (2004), 215-222.

[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-300. 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-399. 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-133. 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, Boca Raton, 2003. doi: 10.1201/9781420036268.

[16]

D. J. Wales, H. A. Scheraga, Global optimization of clusters, crystals and biomolecules, Science, 285 (1999), 1368-1372. doi: 10.1126/science.285.5432.1368.

[17]

J. H. Zar, "Biostatistical Analysis," Prentice Hall, Englewood Cliffs, 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-202. 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-1273. 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, American Mathematical Society, (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-977. 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, Department of Applied Mathematics and Physics, Kyoto University, (January 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, ICCES 2009, (14-16 Dec. 2009), 151-156.

[8]

A. Hedar and A. F. Ali, Tabu Search with variable partitioning for high dimensional problems, The 7th International Conference on Informatics and Systems, INFOS 2010, (28-30 March 2010), 1-8.

[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-319. 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, P.D. Tao (Eds), Modelling. Computation and Optimization in Information Systems and Management Sciences, Hermes Science Publishing Ltd, (2004), 215-222.

[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-300. 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-399. 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-133. 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, Boca Raton, 2003. doi: 10.1201/9781420036268.

[16]

D. J. Wales, H. A. Scheraga, Global optimization of clusters, crystals and biomolecules, Science, 285 (1999), 1368-1372. doi: 10.1126/science.285.5432.1368.

[17]

J. H. Zar, "Biostatistical Analysis," Prentice Hall, Englewood Cliffs, 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 and 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 and 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 and Management Optimization, 2020, 16 (1) : 103-115. 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2020, 16 (3) : 1203-1220. doi: 10.3934/jimo.2018200

[11]

Dieudonné Nijimbere, Songzheng Zhao, Xunhao Gu, Moses Olabhele Esangbedo, Nyiribakwe Dominique. Tabu search guided by reinforcement learning for the max-mean dispersion problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3223-3246. doi: 10.3934/jimo.2020115

[12]

Sen Zhang, Guo Zhou, Yongquan Zhou, Qifang Luo. Quantum-inspired satin bowerbird algorithm with Bloch spherical search for constrained structural optimization. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3509-3523. doi: 10.3934/jimo.2020130

[13]

Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070

[14]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and 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 and Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19

[16]

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 and Management Optimization, 2016, 12 (1) : 141-167. doi: 10.3934/jimo.2016.12.141

[17]

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 and Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

[18]

Yukang He, Zhengwen He, Nengmin Wang. Tabu search and simulated annealing for resource-constrained multi-project scheduling to minimize maximal cash flow gap. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2451-2474. doi: 10.3934/jimo.2020077

[19]

Yang Chen, Xiaoguang Xu, Yong Wang. Wireless sensor network energy efficient coverage method based on intelligent optimization algorithm. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 887-900. doi: 10.3934/dcdss.2019059

[20]

Adrian Korban, Serap Şahinkaya, Deniz Ustun. A novel genetic search scheme based on nature-inspired evolutionary algorithms for binary self-dual codes. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022033

 Impact Factor: 

Metrics

  • PDF downloads (118)
  • HTML views (0)
  • Cited by (12)

[Back to Top]