بهینه سازی کلونی مورچه های سریع برای ایجاد کدهای کتابی

This paper presents an effective and efficient method for speeding up ant colony optimization (ACO) in solving the codebook generation problem. The proposed method is inspired by the fact that many computations during the convergence process of ant-based algorithms are essentially redundant and thus can be eliminated to boost their convergence speed, especially for large and complex problems. To evaluate the performance of the proposed method, we compare it with several state-of-the-art metaheuristic algorithms. Our simulation results indicate that the proposed method can significantly reduce the computation time of ACO-based algorithms evaluated in this paper while at the same time providing results that match or outperform those ACO by itself can provide.

Vector quantization (VQ) is an important technique for not only image compression but also pattern recognition [1] and [40], pattern compression [42] and [43], speech recognition [37], and face detection [61]. Generally, three phases—codebook generation, encoding, and decoding—and a codebook are employed by VQ to encode and decode a signal [30]. Because the codebook generation phase may strongly affect the performance of VQ, it has become an important research topic for many years. Generalized Lloyd algorithm (GLA) [44] is one of the most widely used methods in codebook generation because it is simple and easy to implement. Also known as k-means [48], the basic idea of GLA is to find a codebook that minimizes the distortion between the training patterns and the codewords. To improve the quality of VQ, many heuristic-based algorithms [39], [12], [25], [25] and [19] have been proposed for the codebook generation problem (CGP) over the past one and a half decades or so. To reduce the computation time of CGP, two kinds of approaches have been taken. The first kind of approach is to employ a structured codebook to speed up the VQ process, such as tree-structured codebook [10], [54] and [68]. The second kind of approach is to reduce the number of codewords compared so as to reduce the search complexity of the partitioning step of GLA, such as codeword reduction [11], [16] and [50] and triangle inequalities [31]. Of course, many other fast algorithms [67] have also been proposed to reduce the computational time of GLA, such as dimensional reduction [18].

This study is motivated by the following two observations, and the proposed method is designed accordingly. The first observation is that during the convergence process of ACO for CGP, patterns or subsolutions reach their final states at different times. The second observation is that most of the patterns are assigned to the same codewords after a certain number of iterations. According to these observations, we present an extended version of pattern reduction, which includes redesign of the representation and voting mechanisms as well as addition of a local search operator to speed up ACS for CGP. To enhance the performance of ACS, this study assumes that the proposed algorithm is able to effectively detect and compress patterns that are essentially redundant during the evolution process of ACS for CGP so that most, if not all, of the computations applied to these redundant patterns can be eliminated at the later generations of the evolution process, thus saving a large amount of the computation time. The simulation results of this study not only show that the proposed algorithm indeed can significantly reduce the computation time of ACS in solving the CGP while making the loss of the quality almost negligible but also illustrate that many computations are essentially redundant on the convergence process. In a nutshell, not only can the proposed algorithm significantly reduce the computation time of ACO-based algorithms, but it can also be readily adapted to different kinds of combinatorial optimization problems. Our experiences show that to apply the proposed algorithm to different optimization problems, the very first thing to do is to modify the detection operator to fit it into the structure of the solution. The second thing to do is to modify the compression operator in such a way that the probability computation method and the operators of ACO will bypass all the computations that are essentially redundant. For instance, one possible representation of ACO for bin packing problem is to encode the solution as an n-bit string, X = {x1, x2, …, xn}, where n denotes the number of items and xi ∈ {1, 0} with xi = 1 denoting that xi is packed and xi = 0 denoting that xi is not packed. For this particular problem, the detection operator has to be modified to find for which subsolution xi most of the ants assume the same value at the same time and if it satisfies the threshold Ψ. The compression operators for CGP and TSP are similar to each other in the sense that they both have to consider how to compress patterns detected by the detection operator so that later computations will bypass these patterns. In the future, our focus will be on finding a more effective prediction method to either retain the quality of the solution of PREACO or apply it to different research domains