A Novel Meta-Heuristic Optimization Algorithm Inspired by the Spread of Viruses

Zhixi Li, Vincent W. L. TamarXiv 2020 · arXiv

Introduction

In the field of mathematical optimization, the No-Free-Lunch (NFL) theorem posits that no single algorithm can optimally solve every problem. Established meta-heuristics like Particle Swarm Optimization (PSO) and Genetic Algorithms (GA) are widely used but often encounter two significant hurdles: premature convergence to local optima and poor scalability as the number of variables increases.

To address these challenges, this paper introduces Virus Spread Optimization (VSO). VSO is a nature-inspired meta-heuristic that mimics the biological processes of viral infection and mutation. By balancing exploration and exploitation through a hierarchical population structure and a hybrid "imported infection" mechanism, VSO aims to provide a robust solution for high-dimensional, complex search spaces.

Methodology: The Viral Analogy

VSO conceptualizes a potential solution as the ribonucleic acid (RNA) of a virus, while the host serves as the container for that solution. The algorithm maps natural biological phenomena to specific algorithmic functions to search the solution space effectively.

Mapping biological viral spread terminology to algorithmic optimization concepts.

The population is categorized into four distinct host types based on their fitness levels:

  1. Healthy Hosts: These perform a purely random search, facilitating global exploration.
  2. Mildly Infected Hosts: These carry viruses with low infection rates but high mutation intensity, providing a balanced search strategy.
  3. Severely Infected Hosts: These conduct neighborhood searches around known optima with medium infection rates, focusing on exploitation.
  4. Critical Hosts: This category contains the single best solution found. It does not mutate but possesses the highest infection rate to propagate its "good genes" throughout the population.

Key Novel Operations

The core of VSO's effectiveness lies in its unique operational mechanisms:

Infection Mechanism

Information sharing occurs when infectious hosts (Critical, Severe, or Mild) contact Healthy hosts. Depending on the infector's type, the Healthy host may inherit the RNA directly or through a probabilistic swap.

The infection mechanism where genetic information (RNA) is transferred from a source host to a destination host.

Recovery and Imported Infection

To prevent premature convergence, VSO employs a gradual recovery mechanism. Instead of a hard restart, worst-performing infected hosts are "downgraded" (e.g., from Severe to Mild), preserving the general search area while relaxing constraints to escape local traps. Additionally, an Imported Infection feature integrates a separate Differential Evolution (DE) colony that periodically "infects" the main VSO population with its best results, maintaining genetic diversity.

Experimental Evaluation

VSO was rigorously tested against state-of-the-art optimizers across several domains:

  • Classical Benchmarks: 16 standard functions (e.g., Ackley, Rosenbrock) at 30 dimensions.
  • IEEE CEC 2014: 30 complex, rotated, and shifted functions.
  • Scalability: Evaluation at 100, 300, 500, and 1,000 dimensions.
  • Real-World Applications: Financial portfolio optimization (S&P 500 and CSI 300) and SVM hyper-parameter tuning using UCI datasets.

Key Results

VSO demonstrated superior performance, particularly in high-dimensional spaces. In the CEC 2014 suite, it ranked first in fitness for the majority of functions, outperforming CMA-ES, Grey Wolf Optimizer (GWO), and Whale Optimization Algorithm (WOA). In portfolio optimization for the CSI 300 (250 stocks), VSO achieved a Sharpe ratio of 2.802, significantly higher than its closest competitor, Artificial Bee Colony (ABC), which scored 1.718. Furthermore, VSO showed remarkable stability across independent runs, as evidenced by low variance in box plot analyses.

Conclusion and Future Work

Virus Spread Optimization offers a powerful new framework for complex optimization tasks, excelling in scalability and robustness. While the algorithm introduces higher parameter complexity (11 unique parameters) and increased computational overhead compared to simpler heuristics like PSO, its ability to find global optima in high-dimensional spaces is a significant advancement. Future research will focus on developing self-adaptive parameter tuning and extending the VSO framework to multi-objective and discrete optimization problems.

Summary updated

BibTeX
@misc{li2020novel,
  author = {Zhixi Li and Vincent W. L. Tam},
  title = {{A Novel Meta-Heuristic Optimization Algorithm Inspired by the Spread of Viruses}},
  year = {2020},
  eprint = {2006.06282},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.06282},
}
Figure