A HYBRIDIZED MEMETIC ALGORITHM FOR SOLVING THE MULTI-OBJECTIVE STOCHASTIC MULTIPLE KNAPSACK PROBLEM

ABSTRACT In this paper, we focus on the multi-objective stochastic multiple knapsack problem, in which the object weights are random. We propose a new approach called the multi-objective memetic algorithm with either Martello and Toth’s heuristic method (MTHM) or the method denoted MTHMn, recently developed and inspired by MTHM. In each iteration of this approach, crossover, mutation, and local search techniques are applied to the current feasible population (parents), initially generated by the greedy algorithm. These operations generate new solutions that form a population of descendants. Next, a selection operator is employed to choose the best elements from the combined population comprising parents and offspring, using the non-domination sorting and the crowding distance calculation algorithms. A comparative analysis of the memetic algorithm using the MTHM and MTHMn heuristics with an exact method is performed, and the experimental results demonstrate the significant efficiency achieved by the memetic algorithm with the MTHMn heuristic.