In this work, we aim to push further the integration of machine learning and combinatorial optimization, by proposing a new framework which combines deep neural networks with the best tools of "classical" metaheuristics for graph coloring, so as to solve very difficult graph coloring problems which still resist the best current methods. In order to achieve this integration, we propose to revisit an idea proposed in [1]} twenty years ago. In [1]}, Boyan and Moore remarked that the performance of a local search procedure depends on the state from which the search starts and therefore proposed to use a regression algorithm to predict the results of a local search algorithm. Once learned, this predictive model can help to select new good starting points for the local search and to accelerate the search process. We propose to exploit this idea with the use of modern deep learning techniques to better select promising crossovers among those possible ones in each generation of a memetic algorithm. We design a specific neural network architecture for graph coloring problems inspired by deep set networks [3]}, [4]}, in order to make it invariant by permutation of the color classes. Furthermore, as training a deep neural network requires a large amount of data, we follow the recent work [5]} to adopt a very large population \(P\)  (\(|P|>20^4\) ) for the underlying memetic algorithm, whose individuals evolve in parallel in the search space. In order to learn the neural network and to compute all the local searches in parallel for all the individuals of the population, we leverage GPU (Graphic Processing Units) computation.
