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.

The pattern reduction (PR) algorithm we proposed previously, which works by eliminating patterns that are unlikely to change their membership during the convergence process, is obviously one of the most efficient methods for reducing the computation time of clustering algorithms. However, it is limited to problems with solutions that can be binary or integer encoded, such as combinatorial optimization problems. As such, this study is aimed at developing a new pattern reduction algorithm, called pattern reduction over continuous space, to get rid of this limitation. Like the PR, the proposed algorithm consists of two operators: detection and compression. Unlike the PR, the detection operator is divided into two steps. The first step is aimed at finding out subsolutions that can be considered as the candidate subsolutions for compression. The second step is performed to ensure that the candidate subsolutions have reached the final state so that any further computation is eventually a waste and thus can be compressed. To evaluate the performance of the proposed algorithm, we apply it to metaheuristics for clustering.

Recent years have witnessed increasing interest in using metaheuristics to solve the codebook generation problem (CGP) of vector quantization as well as increasing interest in reducing the computation time of metaheuristics. One of the recently proposed methods aimed at reducing the computation time of metaheuristics is based on the notion of pattern reduction (PR). The problem with PR is in that it may compress and remove patterns that are not supposed to be compressed and removed, thus decreasing the quality of the solution. In this thesis, we proposed a fuzzy version of PR called fuzzy pattern reduction (FPR) to reduce the possibility of compressing and removing patterns that are not supposed to be compressed and removed. To evaluate the performance of the proposed algorithm, we apply it to the following four metaheuristics: generalized Lloyd algorithm, code displacement, genetic k-means algorithm, and particle swarm optimization and use them to solve the CGP. Our experimental results show that the proposed algorithm can not only significantly reduce the computation time but also improve the quality of all the metaheuristics evaluated.