An Evolutionary Algorithm with Probabilistic Annealing for Large-scale Sparse Multi-objective Optimization

2026-03-13 · Source: cs.NE updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, extended

Summary

Researchers from Anhui University and Sapient Intelligence propose PAMEA, an evolutionary algorithm with probabilistic annealing for large-scale sparse multi-objective optimization problems (LSMOPs). These problems, common in areas like adversarial attacks and sparse signal reconstruction, involve high-dimensional search spaces where optimal solutions have few nonzero variables. PAMEA addresses the exploration-exploitation conflict by employing a dual-entropy probability vector scheme: a low-entropy, convergence-oriented vector for stable exploitation and a high-entropy, annealing-driven vector for adaptive global exploration that transitions to local refinement. The algorithm also features an annealing-based variable clustering method. Experimental results on eight benchmark LSMOPs (SMOP1-SMOP8) and ten real-world applications (SR1-SR5, PM1-PM5) demonstrate PAMEA's superior performance in convergence and diversity compared to five state-of-the-art evolutionary algorithms, including TS-SparseEA and DKCA, achieving faster convergence and higher-quality solutions.

Key takeaway

For research scientists developing optimization algorithms for high-dimensional, sparse problems, PAMEA offers a robust approach to overcome the exploration-exploitation trade-off. You should consider implementing a dual-entropy probability vector scheme and annealing-based variable clustering to achieve superior convergence and solution diversity, especially in scenarios with expensive function evaluations. This method can significantly improve the efficiency of identifying critical nonzero variables in complex landscapes.

Key insights

PAMEA uses dual-entropy probability vectors and annealing-based clustering to balance exploration and exploitation in large-scale sparse multi-objective optimization.

Principles

• Balance exploration and exploitation dynamically.
• Prioritize critical variables for faster convergence.
• Decouple sparse structure identification from value optimization.

Method

PAMEA utilizes two subpopulations guided by convergence-driven (low-entropy) and annealing-driven (high-entropy) probability vectors. It employs an exploitation search strategy for local refinement and an annealing search strategy with variable clustering for global exploration, dynamically adjusting probabilities.

In practice

• Apply dual-level encoding for sparse solutions.
• Use Latin hypercube sampling for initial variable importance.
• Integrate multi-population cooperation for enhanced search.

Topics

• Large-scale Multi-objective Optimization
• Sparse Optimization
• Evolutionary Algorithms
• Probabilistic Annealing
• Dual-entropy Probability Vectors

Best for: Research Scientist, AI Researcher, AI Scientist, Machine Learning Engineer

Related on AIssential

• FOSC-X: An Extended Framework for Optimal Local Cuts and Non-Horizontal Cluster Selection from Clustering Hierarchies — FOSC-X extends hierarchical clustering to extract top-M optimal flat solutions with flexible cluster-count constraints via dynamic programming.
• p-PSO: A Penalized Particle Swarm Optimization Technique for Finding D-Optimal Designs with Mixed Factors in Generalized Linear Models — p-PSO introduces an algorithm-agnostic penalty formulation for constrained optimization, enhancing D-optimal design search in GLMs with mixed factors.
• Stein Variational Black-Box Combinatorial Optimization — SVGD-EDA uses kernel-induced repulsion to prevent premature convergence in black-box combinatorial optimization.
• Typed Component Algebras for Simulated Annealing and Markov-Chain Monte Carlo — Decomposing SA/MCMC into a typed component algebra enables modular improvements and verifiable correctness.
• Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits — TTPFTS is the first anytime Bayesian MOMAB algorithm for Pareto Set Identification, offering robust, monitorable multi-objective optimization.
• P1-KAN: an effective Kolmogorov-Arnold network with application to hydraulic valley optimization — P1-KAN offers superior accuracy and stability for high-dimensional function approximation compared to MLPs and ReLU-KANs.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.NE updates on arXiv.org.