Covariance Local Search for Memetic Frameworks: A Fitness Landscape Analysis Approach

Neri, Ferrante; Zhou, Yuyang

Abstract

© 2020 IEEE. The design of each agent composing a Memetic Algorithm (MA) is a delicate task which often requires prior knowledge of the problem to be effective. This paper proposes a method to analyse one feature of the fitness landscape, that is the epistasis, with the aim of designing efficient local search algorithms for Memetic Frameworks. The proposed Analysis of Epistasis performs a sampling of points within the basin of attraction and builds a data set containing those candidate solutions whose objective function value falls below a threshold.The covariance matrix associated with this data set is then calculated. The eigenvectors of this covariance matrix are then computed and used as the reference system for the local search: a change of variables is performed and then the local search is performed on the new variables. The Analysis of Epistasis has been implemented on the three local search algorithms composing a popular MA called Multiple Trajectory Search (MTS). Numerical results show that the three modified local search algorithms outperform their original counterparts.

Citation

Neri, F., & Zhou, Y. (2020, July). Covariance Local Search for Memetic Frameworks: A Fitness Landscape Analysis Approach. Presented at 2020 IEEE Congress on Evolutionary Computation (CEC), Glasgow, United Kingdom

• Presentation Conference Type: Edited Proceedings
• Conference Name: 2020 IEEE Congress on Evolutionary Computation (CEC)
• Start Date: Jul 19, 2020
• End Date: Jul 24, 2020
• Acceptance Date: Mar 20, 2020
• Online Publication Date: Sep 3, 2020
• Publication Date: 2020-07
• Deposit Date: Apr 2, 2020
• Publicly Available Date: Jul 31, 2020
• Publisher: Institute of Electrical and Electronics Engineers
• Pages: 1-8
• Book Title: 2020 IEEE Congress on Evolutionary Computation (CEC)
• ISBN: 978-1-7281-6930-9
• DOI: https://doi.org/10.1109/CEC48606.2020.9185548
• Keywords: Index Terms-Memetic Algorithms; Fitness Landscape Analy- sis; Epistasis; Covariance Matrix; Local Search
• Public URL: https://nottingham-repository.worktribe.com/output/4243345
• Publisher URL: https://ieeexplore.ieee.org/document/9185548
• Related Public URLs: https://wcci2020.org/; https://2020.wcci-virtual.org/presentation/oral/covariance-local-search-memetic-frameworks-fitness-landscape-analysis-approach
• Additional Information: © 2020 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.