PreInitialAlgo: Slashing the Cost of Expensive Optimization via Diversity-Driven Initialization

TL;DR

Bio-inspired metaheuristics like Genetic Algorithms (GA) and Differential Evolution (DE) are notorious for requiring thousands of fitness evaluations. In "Expensive Optimization" scenarios—where one evaluation costs hours—this is a dealbreaker. PreInitialAlgo solves this by adding a low-cost "Secondary Optimization" stage that ensures the initial population is as diverse as possible, allowing the main algorithm to converge to high-quality solutions in 80% less time.

Background: The Curse of the "Expensive" Evaluation

In the world of metaheuristics, we usually assume that calculating "fitness" is cheap. We throw thousands of random agents into a search space and let them evolve over 1,000+ generations. But in data mining tasks (like time-series weighting), a single evaluation might involve processing massive datasets.

If you simply cut the number of generations to save time, the algorithm often gets stuck in a local optimum near its random starting point. The author identifies a critical insight: Random initialization is a liability when you don't have enough generations to "drift" away from it.

Methodology: The Two-Stage Meta-Optimization

The author proposes a decoupled architecture:

1. SecOptim (The Scout): A fast, independent optimization task. Its goal is to pick a subset of individuals from a large pool that are as far apart as possible (Max-Min Distance). It uses a "cheap" fitness function—Euclidean distance between candidates—not the "expensive" real-world function.
2. MainOptim (The Worker): The actual expensive optimization task (e.g., Differential Evolution for time-series). It starts with the "diverse" population provided by SecOptim.

The "Diversity" Intuition

Why maximize distance? Drawing from the Rule of Separation in flocking behaviors, if two agents are close, they likely represent the same information. By forcing the initial population to be maximally scattered, the algorithm "seeds" the entire search space, ensuring that even a short run of 20 generations explores the most promising regions.

Figure 1: The Pre-initialization workflow showing how SecOptim prepares the "Optimal Population" for the Main task.

Experimental Proof: 5x Speedup in Data Mining

The method was tested on a time-series dimensionality reduction task (DEWPAA). The benchmark compared a standard DE (100 generations) against the PreInitialAlgo (20 generations).

Key Findings:

• Accuracy: In datasets like Lighting7 and MALLAT, PreInitialAlgo actually achieved lower classification errors than the 100-generation baseline, despite having 5x fewer chances to "evolve."
• Efficiency: The wall-clock time dropped from over 16 hours to roughly 3 hours on the MedicalImages dataset.
• Negligible Overhead: The "Secondary Optimization" took only 7-12 seconds, rendering it practically free in the context of hour-long main tasks.

Table 1: Classification error comparison across various compression ratios. PreInitialAlgo matches or beats the baseline with 1/5th the iterations.

Critical Insight & Future Outlook

The brilliance of this work lies in its problem-independence. The "SecOptim" doesn't need to know what you are optimizing; it only needs to know the boundaries of the search space.

Limitations: While Euclidean distance works well for continuous parameters, it might struggle in high-dimensional discrete spaces or manifold-constrained environments where distance doesn't correlate with "diversity."

Future Work: The author suggests exploring different combinations of algorithms (e.g., using Particle Swarm for the secondary stage) and refining the diversity metric. This approach has massive potential for Neural Architecture Search (NAS) and Automated Machine Learning (AutoML), where evaluation costs are currently the primary bottleneck.

Conclusion

PreInitialAlgo proves that where you start matters as much as how you move. By replacing random noise with deliberate spatial diversity, we can make "expensive" problems affordable again.