Classifier-based evolutionary multiobjective optimization for the graph protection problem

Krzysztof Michalak

doi:10.1016/j.asoc.2022.109721

2022-12-01

PRE

Krzysztof Michalak *

DOI：10.1016/j.asoc.2022.109721

原文链接

原文求助

摘要

En 中文

In this paper, a graph-based optimization problem related to epidemics control is studied. This multiobjective optimization problem requires determining which graph nodes to protect in order to limit the number of nodes affected by a threat spreading in the graph. In the paper, a classifier-based evolutionary algorithm is proposed in which population initialization, crossover, mutation and local search can use a previously trained classifier to decide which graph nodes to protect. The classifier is trained on a dataset collected by running an optimization algorithm on small problem instances and it is subsequently reused for solving multiple, larger instances of the same optimization problem. Selecting graph nodes to protect using a previously trained classifier allows the algorithm to find better solutions to the optimization problem compared to an algorithm not using a classifier. In the experiments, several machine learning models were evaluated and a multilayer perceptron (MLP) neural network was selected as the best performing classifier. The proposed optimization method was tested and found to work effectively when the MLP classifier was trained on data collected when solving problem instances with 1000 graph nodes. In tests on problem instances with up to 20000 nodes the proposed method outperformed an evolutionary optimizer not using any classifier-based components thereby showing that knowledge can be transferred from smaller problem instances to larger ones.(c) 2022 Elsevier B.V. All rights reserved.

Keyword:

Combinatorial optimization

Machine learning

Epidemics control

Vaccination optimization