Fitness-based Linkage Learning in the Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm

The recently introduced Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (RV-GOMEA) has been shown to be among the state-of-the-art for solving grey-box optimization problems where partial evaluations can be leveraged. A core strength is its ability to effectively exploit the linkage structure of a problem. For many real-world optimization problems, the linkage structure is unknown a priori and has to be learned online. Previously published work on RV-GOMEA however demonstrated excellent scalability only when the linkage structure is pre-specified appropriately. The commonly used mutual-information-based metric that is used to a learn linkage structure online in the discrete version of GOMEA did not show as effective in the real-valued domain and did not result in similarly excellent results, especially in a black-box setting. In this thesis, the strengths of RV-GOMEA are combined with a new fitness-based linkage learning approach that is inspired by differential grouping but reduces its computational overhead by an order of magnitude for problems with fewer interactions. The resulting new version of RV-GOMEA achieves scalability similar to when a predefined linkage model is used. Additionally, for the first time, the EDA AMaLGaM, that served as a foundation for RV-GOMEA is outperformed in a black-box setting, where partial evaluations cannot be leveraged.Computer Science | Data Science and Technolog