A Theoretical Analysis of Analogy-Based Evolutionary Transfer Optimization

Xiaoming Xue, Liang Feng, Yinglan Feng, Rui Liu, Kai Zhang, Kay Chen Tan

Evolutionary Transfer Optimization (ETO) has emerged as a powerful paradigm for solving complex optimization problems by leveraging knowledge from previously solved tasks. Despite its empirical success, the field has historically lacked a rigorous mathematical foundation, often relying on heuristic designs and "gut feeling." This paper provides a much-needed theoretical framework by formalizing the cognitive process of analogical reasoning within ETO, establishing the conditions necessary for performance gains and the prevention of "negative transfer."

The Theory-Practice Gap in ETO

The core intuition behind ETO is simple: if Problem A is similar to Problem B, the solution to A should help solve B. While this "analogical reasoning" has inspired dozens of algorithms, practitioners have lacked a unified framework to explain why these methods work or when they might fail. The most significant risk in ETO is negative transfer—a phenomenon where transferring knowledge actually hinders the optimization process, making it slower or less accurate than a standard evolutionary algorithm.

A Framework for Analogical Reasoning

The authors bridge the theory-practice gap by mapping the cognitive steps of analogy onto three core subprocesses of ETO:

  1. Retrieval (What to transfer): The process of identifying which source tasks in a library are most similar to the target task.
  2. Mapping (How to transfer): The adaptation of source knowledge to better fit the specific constraints and landscape of the target task.
  3. Evaluation (When to transfer): A critical "gatekeeping" step that decides whether the transferred knowledge is actually beneficial before it is integrated into the search.

By treating the relationship between measured similarity and knowledge usefulness as a monotonic function, the authors use mathematical proofs to establish five key theorems regarding the efficacy and safety of these processes.

Key Theoretical Insights

The Monotonicity of Similarity

Through Theorems 1 and 2, the authors establish that if similarity and usefulness are linked by bijectivity (one-to-one correspondence) and continuity, a monotonic function must connect them. This provides a formal justification for using similarity as a proxy for usefulness—a fundamental assumption in almost all ETO research.

The Similarity Threshold

Theorem 3 proves the existence of a deterministic "similarity threshold" ($s^{thre}$). This threshold acts as a boundary that can theoretically separate useful knowledge from useless noise, providing a target for future algorithm designers to aim for when building retrieval mechanisms.

The Necessity of Evaluation

Perhaps the most significant finding is Theorem 4, referred to as the "Safety Result." It formally proves that an ETO method is only "unconditionally nonnegative"—meaning it is guaranteed never to perform worse than a standard algorithm—if it includes an explicit evaluation subprocess. Without this "safety valve" to check the quality of the transfer, there is always a mathematical risk of negative transfer.

Paths to Positive Gain

Theorem 5 (the "Power Result") demonstrates that positive performance gains can be conditionally assured through two primary routes:

  • Big-Source Retrieval: As the number of available source tasks approaches infinity, the probability of finding a highly useful task approaches 1.
  • Appropriate Mapping: Sophisticated adaptation techniques can "lift" the usefulness of source knowledge, making it effective even if the initial similarity was low.

Reconciling ETO with the No Free Lunch Theorem

A common critique of ETO is how it relates to the No Free Lunch (NFL) theorem, which suggests that no optimization algorithm is better than any other when averaged over all possible problems. The authors argue that ETO does not break the NFL theorem. Instead, it is a specialized form of Evolutionary Optimization (EO) where the "analogy-based bias" happens to align more closely with the structure of real-world problems than the general search bias of standard algorithms.

Conclusion and Future Directions

This paper moves ETO from a heuristic-driven field toward a more mature, theoretically grounded discipline. While the current analysis is limited to analogy-based reasoning, it sets the stage for future theoretical explorations into other cognitive models, such as inductive generalization, causal inference, and abductive reasoning. By understanding the mathematical requirements for "safe" transfer, researchers can begin to develop more trustworthy and self-correcting ETO systems.

Summary updated

BibTeX
@inproceedings{xue2025theoretical,
  author = {Xiaoming Xue and Liang Feng and Yinglan Feng and Rui Liu and Kai Zhang and Kay Chen Tan},
  title = {{A Theoretical Analysis of Analogy-Based Evolutionary Transfer Optimization}},
  booktitle = {CEC},
  year = {2025},
  doi = {10.1109/cec65147.2025.11043001},
}
Figure