Return to search

On the Study of Efficient Metaheuristics via Pattern Reduction

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.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0605109-175930
Date05 June 2009
CreatorsTsai, Chun-Wei
ContributorsChang-Shing Lee, Shyi-Ming Chen, Chun-Hung Lin, Tzung-Pei Hong, Yueh-Min Huang, Ming-Chao Chiang, Yau-Hwang Kuo, Chu-Sing Yang, Chung-Nan Lee
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0605109-175930
Rightsunrestricted, Copyright information available at source archive

Page generated in 0.0015 seconds