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

Abdel-Rahman Hedar; Ahmed Fouad Ali; Taysir  Hassan Abdel-Hamid

doi:10.3934/naco.2011.1.191

Article Contents

2011, Volume 1, Issue 1: 191-209. Doi: 10.3934/naco.2011.1.191

This issue Previous Article Parametric excitation based bipedal walking: Control method and optimization Next Article

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
3.
Department of Information Systems, Faculty of Computers and Information, Assiut University, Assiut, 71526

Received: October 2010

Revised: November 2010

Published: February 2011

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 92D20, 68T20, 68W20; Secondary: 68T05, 91E40.

Citation:

Related Papers

Cited by

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.