Covariance Pattern Search with Eigenvalue-determined Radii

Neri, Ferrante; Zhou, Yuyang

Abstract

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.

Citation

Neri, F., & Zhou, Y. (2021, June). Covariance Pattern Search with Eigenvalue-determined Radii. Presented at 2021 IEEE Congress on Evolutionary Computation (CEC 2021), Krakow, Poland (Virtual)

• Presentation Conference Type: Edited Proceedings
• Conference Name: 2021 IEEE Congress on Evolutionary Computation (CEC 2021)
• Start Date: Jun 28, 2021
• End Date: Jul 1, 2021
• Acceptance Date: Apr 6, 2021
• Online Publication Date: Aug 9, 2021
• Publication Date: Aug 9, 2021
• Deposit Date: Apr 10, 2021
• Publicly Available Date: Aug 9, 2021
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Pages: 335-342
• Book Title: 2021 IEEE Congress on Evolutionary Computation (CEC 2021)
• ISBN: 978-1-7281-8394-7
• DOI: https://doi.org/10.1109/CEC45853.2021.9505002
• Keywords: Index Terms-Memetic Algorithms; Fitness Landscape Analy- sis; Pattern Search; Covariance Matrix; Local Search
• Public URL: https://nottingham-repository.worktribe.com/output/5439895
• Publisher URL: https://ieeexplore.ieee.org/document/9505002
• Additional Information: © 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.