首頁 > 網路資源 > 大同大學數位論文系統

Title page for etd-0714104-153843


URN etd-0714104-153843 Statistics This thesis had been viewed 2468 times. Download 1131 times.
Author Yueh-tsun Chang
Author's Email Address tennno@fuzzy.cse.ttu.edu.tw
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 indicate access worldwide
    Date of Defense 2004-07-09 Date of Submission 2004-07-14


    Browse | Search All Available ETDs