Two-step optimization algorithm operated by heuristic and machine learning methods

Heuristics aim to provide approximate solutions for NP-hard combinatorial optimization (CO) problems in a reasonable time. They are faster than deterministic methods, where the solving process may take days. This paper presents an attempt to combine a heuristic algorithm and some machine learning (ML) methods for solving the Multidimensional Knapsack Problem (MKP), which is a well-known CO case. The approach named Genetic Algorithm and Machine Learning (GAML) is a two-step algorithm that first uses four machine methods to produce four solutions and then integrates the best one within the GA. For this purpose, (1) This approach builds models by training four machine learning (ML) methods using the decision variables obtained from the optimal solutions of simple MKP instances. The decision variable of an item is equal to one if it is selected in the knapsack and zero otherwise. (2) The four models are applied to predict the decision variables for complex MKP instances. (3) A dummy algorithm constructs feasible solutions from the predictions by adding the selected items randomly while the constraints are not violated. (4) For each MKP instance, the best feasible solution among the four built is integrated with the initialization and the crossing operators of a genetic algorithm. An experiment has been conducted on well-known complex MKP benchmarks. The results proved that the models were able to provide high-quality solutions. Also, the proposed algorithm was faster than other approaches in the literature.