Title page for etd-0605109-175930


[Back to Results | New Search]

URN etd-0605109-175930
Author Chun-Wei Tsai
Author's Email Address cwtsai87@gmail.com
Statistics This thesis had been viewed 5368 times. Download 1000 times.
Department Computer Science and Engineering
Year 2008
Semester 2
Degree Ph.D.
Type of Document
Language English
Title On the Study of Efficient Metaheuristics via Pattern Reduction
Date of Defense 2009-05-23
Page Count 123
Keyword
  • convergence process
  • metaheuristics
  • pattern reduction
  • Abstract Over the past three decades or so, metaheuristics has been one of the most important and successful techniques for finding the true or near optimal solution of complex problems. Instead of systematically enumerating and checking all the candidate solutions that would take
    forever to accomplish, it works by guessing the right directions for finding the true or near optimal solution so that the space searched, and thus the time required, can be significantly reduced. However, our observation shows that most of the metaheuristic algorithms face a common problem. That is, because of the requirements of convergence, they all involve a lot of redundant computations during the convergence process. In this thesis, we present a simple but efficient algorithm for solving the problem, called the Pattern Reduction algorithm
    (or PR for short). The proposed algorithm is motivated by the observation that some of the sub-solutions that are repeatedly computed during the convergence process can be considered as part of the final solutions and thus can be first compressed and then removed to eliminate
    the redundant computations at the later iterations during the convergence process. Since PR is basically a concept that is not limited to any particular metaheuristic algorithm, we present several methods derived from the concept for eliminating the duplicate computations of metaheuristics in the thesis. Although our simulation results show that they all perform well in terms of the computation time reduced, they are not perfect in terms of the quality of the end results because in some cases they will cause a small loss of the quality. For this reason, rather than how much computation time the proposed algorithm can reduce, our ultimate
    goal is to eliminate all the redundant computations while at the same time preserving or even enhancing the quality of the end result of metaheuristics alone.
    Advisory Committee
  • Yau-Hwang Kuo - chair
  • Chang-Shing Lee - co-chair
  • Chung-Nan Lee - co-chair
  • Chun-Hung Lin - co-chair
  • Tzung-Pei Hong - co-chair
  • Shyi-Ming Chen - co-chair
  • Yueh-Min Huang - co-chair
  • Chu-Sing Yang - advisor
  • Ming-Chao Chiang - advisor
  • Files
  • etd-0605109-175930.pdf
  • indicate access worldwide
    Date of Submission 2009-06-05

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys