Generalised Pattern Search with Restarting Fitness Landscape Analysis

Neri, Ferrante

Abstract

Fitness landscape analysis for optimisation is a technique that involves analysing black-box optimisation problems to extract pieces of information about the problem, which can beneficially inform the design of the optimiser. Thus, the design of the algorithm aims to address the specific features detected during the analysis of the problem. Similarly, the designer aims to understand the behaviour of the algorithm, even though the problem is unknown and the optimisation is performed via a metaheuristic method. Thus, the algorithmic design made using fitness landscape analysis can be seen as an example of explainable AI in the optimisation domain. The present paper proposes a framework that performs fitness landscape analysis and designs a Pattern Search (PS) algorithm on the basis of the results of the analysis. The algorithm is implemented in a restarting fashion: at each restart, the fitness landscape analysis refines the analysis of the problem and updates the pattern matrix used by PS. A computationally efficient implementation is also presented in this study. Numerical results show that the proposed framework clearly outperforms standard PS and another PS implementation based on fitness landscape analysis. Furthermore, the two instances of the proposed framework considered in this study are competitive with popular algorithms present in the literature.

Citation

Neri, F. (2022). Generalised Pattern Search with Restarting Fitness Landscape Analysis. SN Computer Science, 3(2), Article 110. https://doi.org/10.1007/s42979-021-00989-8

• Journal Article Type: Article
• Acceptance Date: Dec 5, 2021
• Online Publication Date: Dec 23, 2021
• Publication Date: 2022-03
• Deposit Date: Dec 5, 2021
• Publicly Available Date: Dec 24, 2022
• Journal: SN Computer Science
• Print ISSN: 2661-8907
• Electronic ISSN: 2661-8907
• Publisher: Springer Science and Business Media LLC
• Peer Reviewed: Peer Reviewed
• Volume: 3
• Issue: 2
• Article Number: 110
• DOI: https://doi.org/10.1007/s42979-021-00989-8
• Public URL: https://nottingham-repository.worktribe.com/output/6900847
• Publisher URL: https://link.springer.com/article/10.1007/s42979-021-00989-8