Gray Code Optimization (GCO) algorithm is a deterministic algorithm based on the Gray code, binary numbers representation. It sometimes suffers from slow convergence and sub-optimal solutions. Expectation Maximization (EM) algorithm is used to analyze how the GCO explores the search space. The investigation of how the GCO generates a population indicates that it is similar to generating samples with a mixture Gaussian distribution. The EM algorithm extracts a three components mixture Gaussian model. Based on these findings, a novel stochastic optimization algorithm based on the mixture Gaussian model is proposed. The new Mixture Gaussian Optimization (MGO) algorithm is not only a continuous stochastic algorithm, but also provides a rigorous mathematic model for answering some theoretical questions. A proof of the convergence of MGO based on the Markov Model is given. The MGO algorithm is applied to the global optimization problems in bioinformatics. For example, the conformations available to a molecule can have a dramatic effect on its activity. Obtaining global minimum energy conformations of molecule is a very hard optimization problem. The difficulty arises from the following two factors: the conformational space of a reasonable size molecular is very large, and there are many local minima that are hard to sample efficiently. The energy landscape in the conformational space is very rugged, and there are many large barriers between local minima. In this report, the MGO algorithm is used to search the conformation space and locate the global minimal energy structure.

Date of this Version

August 2005