Principled Design of Translation, Scale, and Rotation Invariant Variation Operators for Metaheuristics

Ye Tian, Xingyi Zhang, Cheng He, Kay Chen Tan, Yaochu Jin

Abstract

A large number of metaheuristics have been proposed and shown high performance in solving complex optimization problems. While most variation operators in existing metaheuristics are empirically designed, new operators are automatically designed in this work, which are expected to be search space independent and thus exhibit robust performance on different problems. This work first investigates the influence of translation invariance, scale invariance, and rotation invariance on the search behavior and performance of some representative operators. This work then deduces the generic form of translation, scale, and rotation invariant operators, and proposes a principled approach for the automated design of operators, which searches for high-performance operators based on the deduced generic form. The experimental results demonstrate that the operators generated by the proposed approach outperform state-of-the-art ones on a variety of problems with complex landscapes and up to 1000 decision variables.

Introduction

In the field of "black-box" optimization, metaheuristics such as Genetic Algorithms (GA) and Differential Evolution (DE) are indispensable tools for finding solutions to problems where the underlying mathematical structure is unknown. The performance of these algorithms is largely dictated by their variation operators—the mechanisms like crossover and mutation that generate new candidate solutions.

Historically, these operators have been designed through human intuition and trial-and-error. However, this empirical approach often leads to "brittle" algorithms that perform well on specific benchmarks but fail when the problem is slightly modified—for instance, by shifting its location in space (translation), changing its size (scaling), or rotating its coordinate system. This paper addresses this limitation by mathematically deriving the conditions for transformation invariance and introducing an automated framework to design robust operators.

Theoretical Framework: The Necessity of Invariance

The authors argue that for an optimization algorithm to be truly robust, its variation operators must be search space independent. They focus on three key properties:

  1. Translation Invariance: The search behavior should not change if the entire function is shifted.
  2. Scale Invariance: The operator should adapt to the magnitude of the decision variables.
  3. Rotation Invariance: The operator should be effective regardless of the orientation of the coordinate system.

Through rigorous derivation using partial differential equations and Taylor series expansions, the authors prove that for an operator to be invariant to translation, scale, and rotation, it must follow a specific linear structure: $$h(x_{1d}, x_{2d}, \dots) = r_1x_{1d} + r_2x_{2d} + r_3x_{3d} + \dots$$ where the weights ($r_i$) are constants that must sum to exactly 1. This "principled" constraint narrows the infinite search space of possible operators down to a manageable, robust subset.

AutoV: Automated Variation Design

Since the optimal weights ($r_i$) for this linear form are unknown, the authors propose AutoV (Automated Variation). This is a meta-evolutionary approach where the system evolves its own operators. Instead of picking fixed numbers for the weights, AutoV optimizes the mean and variance of normal distributions from which these weights are sampled. This allows for a balance between exploration and exploitation, creating a virtuous cycle of improvement without needing a pre-existing "master" optimizer.

Experimental Evaluation and Results

The researchers evaluated AutoV-generated operators against several benchmark suites, including classic functions (Schwefel, Ackley, Rastrigin) and the high-dimensional CEC’2013 suite (up to 1,000 variables).

Robustness to Transformations

A key finding was the stark difference in performance between invariant and non-invariant operators when problems were translated.

Comparison of search behavior between translation invariant (SBX) and non-invariant (SBX') operators under various coordinate shifts.

As shown in the figure above, standard operators that are translation invariant (like SBX) maintain their search trajectory regardless of the shift. In contrast, non-invariant variants (SBX') see their search behavior drastically altered, often failing to reach the global minimum as the translation increases.

Performance Against State-of-the-Art

In head-to-head comparisons with eight leading algorithms (including CMA-ES, SHADE, and IMODE), AutoV demonstrated superior performance:

  • Small-Scale Robustness: AutoV achieved the best results on 9 out of 13 problems when random rotations were applied.
  • Large-Scale Scalability: On 1,000-dimensional problems from the CEC’2013 suite, AutoV again outperformed competitors on 9 out of 15 benchmarks.

Conclusion

This work shifts the paradigm of metaheuristic design from empirical guesswork to a principled mathematical foundation. By proving that invariant operators must be linear combinations of parents with coefficients summing to one, the authors provide a clear blueprint for future algorithm development. The success of the AutoV framework demonstrates that automated design, when guided by these mathematical principles, can produce operators that are both computationally simple and significantly more robust than human-designed alternatives.

Summary updated

Abstract

A large number of metaheuristics have been proposed and shown high performance in solving complex optimization problems. While most variation operators in existing metaheuristics are empirically designed, new operators are automatically designed in this work, which are expected to be search space independent and thus exhibit robust performance on different problems. This work first investigates the influence of translation invariance, scale invariance, and rotation invariance on the search behavior and performance of some representative operators. This work then deduces the generic form of translation, scale, and rotation invariant operators, and proposes a principled approach for the automated design of operators, which searches for high-performance operators based on the deduced generic form. The experimental results demonstrate that the operators generated by the proposed approach outperform state-of-the-art ones on a variety of problems with complex landscapes and up to 1000 decision variables.
BibTeX
@inproceedings{tian2023principled,
  author = {Ye Tian and Xingyi Zhang and Cheng He and Kay Chen Tan and Yaochu Jin},
  title = {{Principled Design of Translation, Scale, and Rotation Invariant Variation Operators for Metaheuristics}},
  booktitle = {Chinese},
  year = {2023},
  doi = {10.23919/cje.2022.00.100},
}
Figure