Reducing the computational cost of local search in the hybrid evolutionary algorithm with application to electronic imaging

Abstract

This article focuses on the efficiency problems associated with the use of local search in the hybrid evolutionary algorithm. A two-phase cyclic local search is proposed that alternates the random search and the downhill simplex method (DSM), and helps prevent the algorithm from converging to a sub-optimal solution in multidimensional optimization. The algorithm utilizes a novel micro-model of image local response, in order to reduce the number of fitness evaluations during the local DSM search, with the application to the global optimization problem arising in electronic imaging. The problem is stated as the search for the feasible transformation parameters that minimize the difference between two images. Image local response is defined as the variation of the fitness function that occurs because of a small variation of the parameters, and is computed over a small pixel area. The computed response coefficients specify a contraction transformation applied to the vector of the regular DSM coefficients that control the movement and the shape of the simplex. The transformation adjusts the length of the vector, making the step size of the simplex adaptive to the local properties of the fitness landscape. The computational experiments with two-dimensional grayscale images provide the experimental support and justification of the analytical model of image local response and its utilization for the reduction of the computational cost of local search, without the loss of the quality of the final solution.

Keywords:

• Hybrid evolutionary algorithm
• Local search
• Global optimization
• Electronic imaging