یک الگوریتم ژنتیک ترکیبی جدید با جستجوی ممنوع برای بهینه سازی توابع چند بعدی و به رسمیت شناختن الگوی نقطه

Hybrid evolutionary algorithms are drawing significant attention in recent time for solving numerous real world problems. This paper presents a new hybrid evolutionary approach for optimizing mathematical functions and Point Pattern Recognition (PPR) problems. The proposed method combines a global search genetic algorithm in a course-to-fine resolution space with a local (Tabu) search algorithm. Such hybridization enhances the power of the search technique by virtue of inducing hill climbing and fast searching capabilities of Tabu search process. The approach can reach the global or near-global optimum for the functions in high dimensional space. Tests have been successfully made on several benchmark functions in up-to 100 dimensions. The performance of the proposed algorithm has been compared with other relevant algorithms using non-parametric statistical approaches like Friedman test, multiple sign-test and contrast estimation. Also, the hybrid method with grid based PPR technique has been applied for solving dot pattern shape matching and object matching represented as edge maps. The performance of proposed method compares favorably with relevant approaches reported in the article.

Evolutionary Algorithms (EAs) are a class of search and optimization techniques that work on the principle inspired by Darwinian Evolution. EAs are used in solving a wide variety of combinatorial optimization problems in diverse fields as machine vision, astronautics, document processing, biometrics, computational biology and computational chemistry [1], [2], [19] and [26]. In recent years the hybrid genetic algorithms have gained significant interest and are being increasingly used in solving various real world problems. It is now well known that pure evolutionary algorithms are not suited for a fine tuned search in complex combinatorial spaces. Instead hybridization with other techniques can improve the efficiency of the search process [11]. The combination of Evolutionary Algorithm with Local Search approach is known as “Memetic” or “Hybrid” algorithm. Memetic or hybrid algorithms are extensions of evolutionary algorithms which apply separate processes of hill climbing to refine individual chromosome. In recent past, we proposed a CAscaded Genetic Algorithm (CAGA) for optimization problems [7] which is a coarse-to-fine search method. The process starts in low resolution over the entire space and in subsequent stages the space is reduced and the resolution is increased. Recently we have upgraded this algorithm by introducing varying degree of search space reduction so that the global solution can be better attained. This approach is described in Section 2.3. However, there have been occasions where the global optimum has been missed by CAGA. In this paper CAGA with Tabu search has been explored as a remedy to this problem. The hybridization overcomes the limitation of the coarse-to-fine search based genetic algorithm by reducing the possibility of the search process getting trapped in local optima. Since the search (coarse-to-fine) process jumps from one hypercube to another in a multi-dimensional space, there is a possibility of missing the global solution in this movement. The inclusion of a local search process with the Genetic Algorithm (GA) helps to search in the neighborhood of the solution (when the solution is converged in a hypercube in an intermediate stage) when the GA jumps to the new hypercube (see Fig. 1 and Fig. 2 and description in Section 2.3). Thus, the hybridization process largely (but not entirely) reduces the possibility of missing the global solution. As a result, the proposed method can work on high dimensional spaces. The user also has the option to control the rate of reduction of search space. The reduction in slower pace may be necessary to reach the global optimum solution. Tests have been made on the benchmark functions in up-to 100 dimensions as described in Section 4.2.The effective use of genetic algorithm in point pattern recognition is reported in various literatures [10], [11] and [26]. Given two sets of points in d-dimensional space, one has to determine whether there is a transformation that maps the first set onto or close to the second set of points. In general, pattern matching can be of two categories namely, complete matching and approximate matching. Complete matching usually occurs in an idealistic situation while in practice there exist spurious or lost points due to image degradation and binarization error, so that exact match is not possible. Depending on additional information of an image (such as color, intensity etc.) other than pixel coordinates, the point pattern recognition can be done on labeled points or unlabeled points [26]. The unlabeled point matching is more difficult than its labeled counterpart but such a situation is encountered more often. Among other hybrid approaches, in [20] the GA is combined with two neural networks namely, a feature extraction network and a neural classifier. The hybrid GA is used to select the receptive field parameters to improve the classification performance and is applied for handwritten digit classification and face recognition. Another genetic approach hybridized with fuzzy logic has been proposed by Ishibuchi et al. [14] for designing fuzzy rule based systems for pattern classification. Also, the memetic evolutionary method with Tabu search has been used for cell image segmentation [16]. Among the different approaches proposed for point pattern matching, a heuristic algorithm has been used by Denton and Beveridge [4] to minimize the effect of spurious points for matching two point patterns. A meta-heuristic particle swarm optimization algorithm [25] has also been proposed in the recent past. Zhang et al. [26] employed genetic algorithm for point pattern recognition. They used the reference triplet points as the chromosome representation in order to reduce the search space significantly. In a noise-free environment Caetano et al. [1] proposed point pattern matching as a weighted graph matching problem where the weights correspond to Euclidean distance between nodes. Carcassoni and Hancock [2] have applied the spectral graph theory to compute the point pattern correspondence. Li et al. [19] used the point pattern matching method in palm pattern recognition. The matching is performed in two-phases based on the local structure of the minutiaes and the global feature. Usually, GAs require a large number of iterations in order to converge to a solution. In pattern recognition or similar problems, generally one starts with chromosome length dependent on the accuracy of the required solution. The length then remains constant throughout the execution of the algorithm. Thus, the chromosome length will be increased with the increase in accuracy of the required solution, which eventually will increase the execution time of the GA. The benefit of the proposed approach is the improvement in the efficiency of the system by hybridization of a local search technique with coarse-to-fine search strategy based GA. Such combination can work with smaller chromosome length and fast convergence to the solution. In this paper our contribution has two parts. The first one is a cascaded hybrid genetic approach with Tabu search and the second is a grid based point pattern matching method where the match is optimized by the proposed hybrid genetic algorithm. The performance of the Hybrid CAscaded Genetic Algorithm (H-CAGA) is tested on twenty benchmark functions. They are used to compare the optimization capability of the hybrid method with several relevant genetic algorithms in 30 dimensional space. The performance of H-CAGA is also evaluated for the functions in higher (1 0 0) dimensional space with fast and slow reduction of search space. We also performed the set of non-parametric procedures (like Friedman test, multiple sign-test, contrast estimation) for doing statistical comparison between H-CAGA and the relevant algorithms considered in the experiment. In solving pattern recognition problems, we have partitioned the pattern space with a grid structure. The proposed grid based Point pattern Recognition (PPR) method with H-CAGA is named as Grid based Optimized Pattern Matching (GOPM) technique. The performance of GOPM is also evaluated on different pattern sets and compared with related pattern matching algorithms. The rest of the paper is organized as follows. The next section describes different optimization techniques presented in this paper. Section 3 depicts the hybridization schemes of the sequential optimization methods discussed in Section 2. Analysis of empirical results of H-CAGA on several standard unimodal and multimodal functions [23] and [24] which are compared with the results of other relevant algorithms is included in Section 4. The performance of various hybrid genetic algorithms based pattern recognition is also elaborated in this section. The paper is concluded in Section 5.

The performance of H-CAGA on twenty high and low dimensional benchmark functions shows its improvement over other relevant methods. It has the capability to reach the global optimum for most of the problems having dimension 100 by slowing down the partitioning process. On the other hand, the non-parametric test for statistical analysis also shows that H-CAGA performs better than the other optimizing methods. The point pattern matching approach depends on the matching score of two point patterns by finding an optimal transformation. The efficiency of the proposed pattern matching technique (GOPM) is enhanced with the dual applications of hybrid cascaded GA and grid based approach. The grid based approach helps to match much lesser number of points for entire pattern matching. In the experiment it was noticed that the success rate of the genetic techniques for pattern matching improves with the increase of the degree of overlapping objects in the pattern. The best result is usually achieved by any of these techniques for the centrally located P1 pattern. We have performed our pattern matching experiment on some synthetic point patterns except the image of Lena. We can extend our test for some real point patterns in future. There is also a scope for future work to increase the dimension of the mathematical functions beyond 100 to examine the limits of the slow partitioning process.