Abstract
Evolutionary Algorithms (EAs) often struggle with high-dimensional continuous optimization problems. This paper investigates whether the difficulty arises from the inherent complexity of the problem or the size of the search space itself. By introducing domain-agnostic genotype-phenotype mapping strategies, we decouple these factors through artificial genotype compression and expansion. Our findings demonstrate that while compression severely hinders optimization, summation-based expansion can improve performance by providing additional degrees of freedom and smoothing the fitness landscape.
Introduction
In the field of continuous optimization, the "curse of dimensionality" is a well-known hurdle for Evolutionary Algorithms. However, it remains unclear if performance degradation is a result of the increased search space volume or the increased complexity of the underlying problem. To address this, we propose a methodology to manipulate the genotype size while keeping the phenotype (the actual problem variables) constant. This allows for a controlled study of how search space dimensionality independently affects EA performance.
Methodology
We evaluate two primary mapping strategies using standard floating-point EAs, specifically Genetic Algorithms (GA) and Differential Evolution (DE).
Genotype Compression (Genotype < Phenotype)
In this scenario, multiple phenotypic variables are encoded into a single genotypic floating-point variable. Given the 16-digit precision of double-precision floats, we employ two techniques:
- Sequential Mapping: The first half of the digits represents one variable, and the second half represents another.
- Alternating Mapping: Digits are interleaved between variables.
Genotype Expansion (Genotype > Phenotype)
Conversely, expansion represents a single phenotypic variable using multiple genes. We explore two arithmetic reconstruction methods:
- Summation ($x_i = \sum x_{ij}$): The phenotypic value is the sum of its corresponding genes.
- Multiplication ($x_i = \prod x_{ij}$): The phenotypic value is the product of its corresponding genes.
Experimental Results
COCO Benchmark Performance
The strategies were first tested on the COCO (Comparing Continuous Optimizers) benchmark suite. The results, summarized in the table below, highlight a clear trend: compression strategies (com-seq, com-alt) almost universally underperform compared to the default encoding. In contrast, summation-based expansion (exp-s-2, exp-s-3) frequently outperforms the default, particularly on multi-modal functions.
The table shows mean error values and the number of successful runs (in parentheses). The '+' and '-' symbols indicate statistically significant improvements or regressions relative to the default (def) encoding. While summation expansion provides a clear advantage in lower dimensions, this benefit tends to diminish as the base problem dimensionality increases.
PUF Modeling and Neural Network Optimization
Beyond synthetic benchmarks, we applied these mappings to Physical Unclonable Functions (PUFs) and Neural Network (NN) weight optimization.
- PUF Modeling: Summation expansion showed slight improvements in modeling accuracy for 32-stage and 64-stage Arbiter PUFs.
- Neural Networks: The most significant gains were observed in NN training. Summation expansion consistently achieved lower Mean Squared Error (MSE) across various regression tasks compared to standard encoding. This suggests that the redundant representation helps the EA navigate the complex weight space of even small networks more effectively.
Discussion and Key Insights
The experimental data leads to several critical insights:
- The Failure of Compression: Compression fails due to a combination of reduced numerical precision and "conflicting updates." When a mutation occurs on a compressed gene, it forces simultaneous changes across multiple phenotypic variables, preventing the algorithm from performing the fine-grained, independent adjustments necessary for convergence.
- The Benefit of Redundancy: Genotype expansion via summation introduces redundancy, allowing multiple genetic configurations to map to the same phenotypic value. This redundancy appears to "smooth" the fitness landscape, creating more viable paths for the EA to reach global optima.
- Limits of Multiplication: Unlike summation, multiplication-based expansion scales poorly. In bounded domains (0 to 1), multiplying multiple genes quickly drives the phenotype toward zero, creating a biased search space that hinders optimization in higher dimensions.
Conclusion
This research demonstrates that genotype-phenotype mapping is a powerful lever in evolutionary optimization. While artificial compression is detrimental, artificial expansion—specifically through summation—can serve as a beneficial landscape transformation. Future work will investigate "partial expansion" to balance the benefits of redundancy with the computational costs of larger genotypes, and explore the scalability of these techniques to larger neural architectures.
Summary updated