Abstract
Metaheuristic optimization algorithms often suffer from sensitivity to coordinate transformations, leading to inconsistent performance across translated, scaled, or rotated search spaces. This paper presents a principled mathematical framework for deriving variation operators that are inherently invariant to these transformations. By identifying the necessary linear structure for invariance, the authors introduce AutoV, an automated design system that evolves high-performance variation operators. Results demonstrate that AutoV-generated operators significantly outperform state-of-the-art human-designed metaheuristics on both small-scale and high-dimensional benchmark problems.
Introduction
In black-box optimization, metaheuristics like Genetic Algorithms (GA) and Differential Evolution (DE) utilize variation operators to explore the search space. Traditionally, these operators are designed through empirical trial-and-error. However, such manually crafted rules often lack search space independence. When a problem is shifted, stretched, or rotated, the performance of these algorithms can degrade significantly. This study addresses this brittleness by mathematically defining the conditions for invariance and automating the discovery of robust operators.
Theoretical Framework for Invariance
The authors utilize Taylor series expansions and partial differential equations to determine the generic mathematical form required for translation, scale, and rotation invariance. The derivation proves that a fully invariant operator must be a linear combination of parent solutions where the weights sum to unity:
$$h(x) = \sum r_i x_i \text{ where } \sum r_i = 1$$
This constraint drastically narrows the search space for effective variation operators, moving away from arbitrary heuristic designs toward a mathematically grounded structure.
AutoV: Automated Variation Design
Building on this theoretical foundation, the authors propose AutoV, a framework that treats variation operator design as an optimization problem. AutoV optimizes the parameters ($\mu, \sigma$) of normal distributions from which the weights ($r_i$) are sampled. Crucially, AutoV is self-evolving; it employs its own discovered operators to further refine and evolve subsequent generations of candidate variation rules.
Key Insights: The Challenge of Rotation
While many common operators exhibit translation and scale invariance, rotation invariance remains a significant hurdle. True rotation invariance requires an operator to treat all dimensions of the search space equivalently, regardless of the coordinate system's orientation.
As shown in the figure above, rotation-invariant algorithms like DE maintain consistent search trajectories even when the landscape is rotated, whereas non-invariant methods like standard SBX-based GAs struggle to adapt to the new coordinate alignment.
Experimental Results
The framework was evaluated against standard benchmarks and the CEC’2013 Large-Scale Global Optimization (LSGO) suite.
Performance and Robustness
AutoV demonstrated superior robustness across transformed landscapes. In rotated benchmark tests, AutoV's performance remained stable, contrasting with the significant degradation observed in traditional metaheuristics.
Quantitatively, AutoV outperformed top-tier metaheuristics such as CMA-ES and IMODE. On small-scale problems (30 variables), it achieved top results on 9 out of 13 functions. More impressively, on 1,000-variable large-scale problems, AutoV maintained its lead, winning on 9 out of 15 functions.
Conclusion
By shifting from heuristic-based design to a principled mathematical approach, this work provides a robust foundation for metaheuristic development. AutoV successfully automates the creation of high-performance, invariant variation operators that excel in complex, high-dimensional environments. Future research will explore non-linear operator structures and the automated design of selection strategies to complete the automated metaheuristic pipeline.
Summary updated