Information flow and Laplacian dynamics on local optima networks

Richter, Hendrik; Thomson, Sarah L.

Abstract

We propose a new way of looking at local optima networks (LONs). LONs represent fitness landscapes; the nodes are local optima, and the edges are search transitions between them. Many metrics computed on LONs have been proposed and shown to be linked to metaheuristic search difficulty. These have typically considered LONs as describing static structures. In contrast to this, Laplacian dynamics (LD) is an approach to consider the information flow across a network as a dynamical process. We adapt and apply LD to the context of LONs. As a testbed, we consider instances from the quadratic assignment problem (QAP) library. Metrics related to LD are proposed and these are compared with existing LON metrics. The results show that certain LD metrics are strong predictors of metaheuristic performance for iterated local search and tabu search.

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: IEEE Congress on Evolutionary Computation (IEEE CEC)
• Start Date: Jun 30, 2024
• End Date: Jul 5, 2024
• Acceptance Date: Mar 15, 2024
• Deposit Date: Apr 17, 2024
• Publisher: Institute of Electrical and Electronics Engineers
• Public URL: http://researchrepository.napier.ac.uk/Output/3594926
• Related Public URLs: https://2024.ieeewcci.org/