Abstract
Bayesian Optimization Algorithms (BOA) are highly effective at solving complex optimization problems by modeling the dependencies between variables. However, their reliance on large populations often leads to a high number of expensive fitness evaluations. This paper explores the integration of fitness inheritance into BOA, where the probabilistic models used to generate new solutions are also utilized to estimate their fitness. By evaluating only a small fraction of the population and allowing the remainder to inherit estimated values, the proposed method achieves significant computational speedups—up to a factor of 53—without sacrificing the ability to find global optima in deceptive landscapes.
Introduction
Genetic and Evolutionary Algorithms (GEAs) are powerful tools for global optimization, yet they are notoriously computationally expensive. In practical applications such as structural engineering, fluid dynamics, or drug discovery, the "fitness" of a solution is rarely a simple mathematical function. Instead, it often requires high-fidelity simulations or physical experiments that can take hours or even days to complete.
The central challenge in evolutionary computation is maintaining the robust search capabilities provided by large populations while minimizing the number of actual fitness evaluations. This paper addresses this challenge by extending the Bayesian Optimization Algorithm (BOA) with a mechanism for fitness inheritance, leveraging the algorithm's internal probabilistic model to predict solution quality.
Methodology: Extending the Bayesian Network
The Bayesian Optimization Algorithm (BOA)
Unlike standard Genetic Algorithms that rely on random crossover and mutation, BOA builds a probabilistic model—specifically a Bayesian network—of the most promising solutions in each generation. This model captures the structural dependencies of the problem, allowing the algorithm to sample new candidate solutions that are likely to be high-performing.
Fitness Inheritance Mechanism
The authors propose a novel extension where the Bayesian network serves a dual purpose: generation and estimation.
- Extended Bayesian Networks: The Conditional Probability Tables (CPTs) or decision trees within the network are modified to store the average fitness observed for specific variable configurations.
- Estimation Formula: To estimate the fitness of a new individual, the algorithm starts with the current population's average fitness. It then adds the "contributions" (deviations from the mean) of each variable, conditioned on its parents in the Bayesian network.
- Hybrid Evaluation Strategy: In each generation, only a tiny fraction of the population is evaluated using the true, expensive fitness function. The rest of the population inherits their fitness scores from the model.
- Model Integrity: To prevent the accumulation of errors (where the model begins to "believe" its own incorrect predictions), the Bayesian network is updated exclusively using the solutions that underwent actual evaluation.
Experimental Setup
The effectiveness of the inheritance mechanism was tested on three synthetic benchmarks designed to represent varying levels of problem difficulty and variable dependency:
- Onemax (50-bit): A linear problem where fitness is simply the sum of bits.
- Concatenated 4-bit Trap (40-bit): A deceptive problem where local gradients lead away from the global optimum, requiring the algorithm to identify 4-bit dependencies.
- Concatenated 5-bit Trap (50-bit): A more complex version of the trap problem requiring the modeling of 5-bit dependencies.
Key Insights and Results
The Population Sizing Synergy
A significant finding of this research is the counter-intuitive relationship between population size and inheritance accuracy. In standard BOA, large populations are required to build an accurate model of the search space. This requirement, often seen as a computational burden, becomes an advantage for fitness inheritance. The same large population that allows for a high-quality structural model also provides the statistical density necessary for highly accurate fitness estimations.
Performance and Speed-up
The authors measured the "Speed-up" factor, representing the reduction in actual fitness evaluations compared to a standard BOA run. The results were striking:
- Onemax: 31x speedup.
- 4-bit Trap: 32x speedup.
- 5-bit Trap: 53x speedup.
As the problem complexity increased (from 4-bit to 5-bit traps), the potential for speedup actually improved. The authors found that for these complex problems, evaluating less than 1% of the population was sufficient to maintain convergence to the global optimum.
Discussion and Limitations
While the results are promising, the authors identify several areas for further study. One primary concern is the potential for accumulation of error. If the proportion of evaluated individuals is too low, the algorithm may converge prematurely on a local optimum due to over-optimistic fitness estimates. Additionally, the current model does not explicitly account for niching, or the maintenance of diversity across multiple peaks in a fitness landscape.
Conclusion
By repurposing the probabilistic models already inherent in BOA, fitness inheritance transforms a traditionally "data-hungry" algorithm into a highly efficient optimizer. The ability to skip over 99% of expensive evaluations while maintaining search integrity suggests that BOA with fitness inheritance is a viable candidate for solving high-stakes, real-world engineering problems where evaluation costs are the primary bottleneck.
Summary updated