Covariance Pattern Search with Eigenvalue-determined Radii

Effective implementations of Memetic Algorithms often integrate, within their design, problem-based pieces of information. When no information is known, an efficient MA can still be designed after a preliminary analysis of the problem. This approach is usually referred to as Fitness Landscape Analysis (FLA). This paper proposes a FLA technique to analyse the epistasis of continuous optimisation problems and estimate those directions, within a multi-dimensional space, associated with maximum and minimum directional derivatives. This estimation is achieved by making use of the covariance matrix associated with a distribution of points whose objective function value is below (in case of minimisation) a threshold. The eigenvectors and eigenvalues of the covariance matrix provide important pieces of information about the geometry of the problem and are then used to design a memetic operator that is a local search belonging to the family of generalised Pattern Search. A restarting mechanism enables a progressive characterisation of the fitness landscape. Numerical results show that the proposed approach successfully explore ill-conditioned basins of attractions and outperforms the standard pattern search as well as a pattern search recently proposed in the literature and partially based on a similar design logic. The proposed local search based on FLA also displays a performance competitive with that of other types of local search.