Approximate Bayesian Inference Team Seminar: Talk by Dr. Hugo Monzon.

Speaker: Dr. Hugo Monzon

Title: Dynamic and Performance Models for Analysis and Configuration of Multi-Objective Evolutionary Algorithms

Abstract:
Evolutionary algorithms (EAs) show great results on complex multi-objective optimization problems. To keep this trend in the presence of problems with a large number of variables and objectives, a deeper understanding of their inner workings is needed. It is also desirable to automatically select and configure them for new problems.
A promising way forward on these goals is to characterize the algorithms' dynamics through models. Dynamic compartmental models (DCMs), inspired by epidemiology models, track the algorithm's population changes modeling them as exchanges between compartments. Each compartment is defined using features on the population: Pareto dominance status, solution's recentness, and their membership to reference sets. A trained model's parameter set packs information of the algorithm's behavior on an instance, serving as an analysis tool. Estimations of the population change can be computed using the compartments' composition at a given time.
Using MNK-landscapes, several problem instances were created to test the model with two sets of features.
Results on the first set, using the Pareto Optimal set, showed that the fitted model followed the population's change during the search process. An analysis of how representative algorithms keep discovering optimal solutions even after convergence was possible by looking at the model's parameters. Correlating compartment's change to a performance metric allowed algorithm comparison. Training one model per configuration and extracting new possible ones from their parameters promising results were obtained on algorithm configuration under a budget.
The second set used the non-dominated solution set as a reference, making it appropriate for any problem where the optimum is unknown.
To correlate compartments to performance a complementary model was introduced. Results showed that the new features make the model retain more of the variability found in the data, with better estimations on unseen instances.
Overall results indicate that DCMs are one possible step to understanding and improving EAs.