Abstract
Traditional evolutionary algorithms often rely on random crossover point selection, leading to computational waste through "repetitive failure reproduction." This paper introduces C-MOEA-MCD, a novel multi-objective evolutionary algorithm that incorporates reinforcement learning-inspired feedback to adaptively learn optimal crossover distributions. By penalizing ineffective crossover points and maintaining mathematical stability through a "virtual point" mechanism, the proposed method reduces the expected runtime of standard benchmark problems from $O(n \log n)$ to linear $\Theta(n)$ time. Empirical results on COCZ and LOTZ problems validate the theoretical speedup, demonstrating significant performance gains over conventional crossover-enabled algorithms.
Introduction
In the field of Evolutionary Computation, the crossover operator is a fundamental mechanism for combining genetic traits from parent solutions to produce superior offspring. However, a significant limitation of most existing algorithms is their reliance on uniform random selection for crossover points. Unlike deep learning, which utilizes gradients to navigate the search space, evolutionary algorithms often operate "blindly," repeatedly attempting crossover operations at locations that have previously failed to yield improvements. This paper addresses the challenge of providing evolutionary algorithms with a form of "sight"—the ability to learn from past failures without the prohibitive computational cost of gradient calculations.
Methodology: C-MOEA-MCD
The researchers propose a feedback-based adaptive crossover rate mechanism termed C-MOEA-MCD. The architecture consists of three core innovations:
- Modifiable Cross Distribution (MCD): Instead of uniform selection, the algorithm maintains a preference score list ($L$) for all possible crossover points. These scores are converted into a probability distribution using a Softmax function.
- Q-Learning Inspired Feedback: The algorithm treats crossover point selection as an action in a reinforcement learning context. When a crossover produces inferior or "unacceptable" offspring, the preference score for that specific point is decreased ($l_i \leftarrow l_i - \alpha$). This negative feedback loop teaches the algorithm to avoid unproductive regions of the search space.
- The Virtual Point Mechanism: A critical technical challenge in adaptive distributions is "probability backflow," where reducing the score of one point causes unstable fluctuations in others. The authors introduced a "virtual point" to act as a mathematical sink. It absorbs the probability lost from penalized points, keeping the Softmax denominator constant and ensuring a smooth, stable learning process.
Experimental Setup and Datasets
The performance of C-MOEA-MCD was evaluated using three classic Pseudo-Boolean benchmark problems:
- COCZ (Count Ones, Count Zeros): A bi-objective problem maximizing 1s and 0s in distinct segments.
- LOTZ (Leading Ones, Trailing Zeros): A bi-objective problem focusing on the prefix and suffix of bitstrings.
- Hierarchical-COCZ: A tri-objective problem designed to test scalability on higher-dimensional Pareto fronts.
Key Results and Discussion
The primary breakthrough of this work is the theoretical and empirical reduction in runtime complexity. Traditional crossover-enabled MOEAs typically require $O(n \log n)$ steps to find the Pareto front for problems like COCZ. By learning to avoid useless crossover points, C-MOEA-MCD achieves the same result in linear $\Theta(n)$ time.
For the more complex Hierarchical-COCZ, the method guarantees an expected runtime of $\Theta(n^2 \log n)$, outperforming the standard $O(n^2 \log^2 n)$ baseline. Empirical validation across 500 runs per problem size confirmed these theoretical bounds, with the performance gap between C-MOEA-MCD and traditional methods widening significantly as the problem size ($n$) increases.
Conclusion and Future Work
C-MOEA-MCD demonstrates that negative feedback alone is sufficient to accelerate evolutionary search significantly. The introduction of the "Virtual Point" provides the necessary stability to integrate reinforcement learning principles into evolutionary operators. While currently focused on discrete pseudo-Boolean functions, future research will explore resetting mechanisms to prevent local optima entrapment and extend the framework to continuous optimization and dynamic environments where optimal crossover points may shift over time.
Summary updated