Announcement for Downloading full text filePlease respect the Copyright Act.
All digital full text dissertation and theses from this website are authorized the copyright owners. These copyrighted full-text dissertation and theses can be only used for academic, research and non-commercial purposes. Users of this website can search, read, and print for personal usage. In respect of the Copyright Act of the Republic of China, please do not reproduce, distribute, change, or edit the content of these dissertations and theses without any permission. Please do not create any work based upon a pre-existing work by reproduction, Adaptation, Distribution or other means.
URN etd-0714104-153843 Statistics This thesis had been viewed 2706 times. Download 1131 times. Author Yueh-tsun Chang Author's Email Address firstname.lastname@example.org Department Computer Science and Enginerring Year 2004 Semester 2 Degree Master Type of Document Master's Thesis Language English Page Count 75 Title A QUICK CONVERGENT GENETIC ALGORITHM FOR PATTERN ALIGNMENT Keyword pattern alignment genetic algorithm elite competition chromosome chromosome elite competition genetic algorithm pattern alignment Abstract As we know, conventional genetic algorithms considered the fixed crossover and mutation rates during the evolution processes. Higher crossover or mutation rates may cause abrupt changes during converging processes. On the contrary, smaller rates may not be enough for population to diversify the solution space. There is no guarantee that the traditional mutation and crossover operations will result in better offspring. As a result, the conventional method has the drawback of slow convergent problem.
In order to solve those problems, we present a modified genetic algorithm to overcome the slow convergent problem existed in traditional genetic algorithms. We introduce the new methods to adapt the crossover and mutation rates which in turn help expedite the evolution. In order to prevent the chromosomes from being deteriorated by the crossover and mutation operations, we take the elite preservation policy into account. As a result, we can guarantee the offspring will perform as least as good as their parent. We also get an adaptable mutation rate by the comparison between the better and the worse chromosomes. The crossover rates are also calculated by the sum of the fitness values of elitists. The modified operations are able to find the suitable rates. In case the after-crossover chromosomes are exactly the same, we just allow one of them surviving into the next generation. Therefore, we can avoid the results stuck at local optimum.
Our proposed algorithm not only accelerates the convergent speed, but also improves the pattern matching degree. On the benefits of the rapid convergence, our proposed algorithm is very suitable to solve the optimization problems in many application domains. Moreover, to verify the effectiveness of the proposed model, we use the algorithm to solve the problems of the polynomial fitting and the gene sequence alignment. The experimental results demonstrate that our proposed algorithm is more efficient than traditional algorithms.
Advisor Committee Yo-ping Huang - advisor
none - co-chair
none - co-chair
Files Date of Defense 2004-07-09 Date of Submission 2004-07-14