Multidomain Evolutionary Optimization on Combinatorial Problems in Complex Networks

Abstract

Knowledge transfer-based evolutionary optimization has garnered significant attention, such as in multi-task evolutionary optimization (MTEO), which aims to solve complex problems by simultaneously optimizing multiple tasks. While this emerging paradigm has been primarily focusing on task similarity, there remains a hugely untapped potential in harnessing the shared characteristics between different domains. For example, real-world complex systems usually share the same characteristics, such as the power-law rule, small-world property and community structure, thus making it possible to transfer solutions optimized in one system to another to facilitate the optimization. Drawing inspiration from this observation of shared characteristics within complex systems, we present a novel framework, multi-domain evolutionary optimization (MDEO). First, we propose a community-level measurement of graph similarity to manage the knowledge transfer among domains. Furthermore, we develop a graph learning-based network alignment model that serves as the conduit for effectively transferring solutions between different domains. Moreover, we devise a self-adaptive mechanism to determine the number of transferred solutions from different domains, and introduce a knowledge-guided mutation mechanism that adaptively redefines mutation candidates to facilitate the utilization of knowledge from other domains. To evaluate its performance, we use a challenging combinatorial problem known as adversarial link perturbation as the primary illustrative optimization task. Experiments on multiple real-world networks of different domains demonstrate the superiority of the proposed framework in efficacy compared to classical evolutionary optimization.

References in corpus (12)

• Emergence of scaling in random networks
• Power-law distributions in empirical data
• Finding community structure in very large networks
• Error and attack tolerance of complex networks
• Cascade-based attacks on complex networks
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Hiding Individuals and Communities in a Social Network
• Identification of influencers in complex networks by local information dimensionality
• Adversarial Attack on Community Detection by Hiding Individuals
• Tracking bitcoin users activity using community detection on a network of weak signals
• Scalable Transfer Evolutionary Optimization: Coping with Big Task Instances
• Visual Evolutionary Optimization on Graph-Structured Combinatorial Problems with MLLMs: A Case Study of Influence Maximization

Cited by in corpus (1)

• Can Large Language Models Be Trusted as Evolutionary Optimizers for Network-Structured Combinatorial Problems?