Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/6238

Multi-population genetic algorithm for the mapping of landscape of complex function

Authors Guo, Yunbo
Issue Date 2009
Summary A set of multi-population genetic algorithm (MPGA) operators, including mutation, crossover, and migration, are employed to perform a mapping of the landscape of complex functions. The introduction of forbidden laws into migration operator and using exact differentials as fitness values are two innovations. The smaller the exact differential’s absolute value, the higher the fitness is. Specifically, we first generate a multi-population matrix randomly, and search for local maxima on the landscape of 2-D Rastrigin’s function using MPGA. After evolution, most of the local maxima can be found. We introduce two measures: cover degree (CD) and precision (Pr) as measurements of the performance of our algorithm, and the effect of migration on the final results and the evolution processes are also investigated. It is found that as “migration strength” increases, CD decreases while Pr increases, which can be regarded as a kind of “uncertainty relation”. We also perform test on other benchmark functions with this algorithm, and the method of expecting the radius of the maxima using this MPGA is introduced. We further investigated the novel MPGA’s performance in the noisy environment. The absolute value of the exact differential is employed as the chromosomes’ fitness, and Pr and CD are used as measurements of the algorithm For noisy environment, the derivatives used in calculating exact differentials are obtained through second order polynomial fitting. It is found that the variance of the noise will change both CD and Pr. Pr has a negative correlation with variance, while CD’s dependence on variance is complex. The migration strength’s influence on the algorithm’s performance is also discussed, but not as obvious as variance. Finally, we apply this MPGA to map out the free energy landscape of a protein, modeled by a chain with 27 units that tries to fold to a cube in the cubic lattice. The chromosomes represent the bond directions, through which we can obtain the chain’s configuration, the energy can be computed from the configuration. The Hamiltonian of the protein chain is composed of two terms: the nearest neighbor interactions and the pseudo entropic term. We define fitness f = -E, where E is the energy. Several lowest energy configurations are listed, and the convergence of the searching process is investigated. It is found that this algorithm converges fast in the early stage, and then fully folded after a long time scale. This agrees with the kinetic process of protein folding, which is characterized by a fast folding process to a molten globule state and a slow folding process from the globule state to the compact folded state.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2009
Subjects
Language English
Format Thesis
Access
Files in this item:
File Description Size Format
th_redirect.html 339 B HTML