On the Design of Diploid Memetic Algorithms for Solving the Multidimensional Multi-way Number Partitioning Problem

In this paper, we investigate the ability and the performance of a diploid memetic algorithm (DMA) to solve the multidimensional multi-way number partitioning problem (MDMWNPP). Given a multiset consisting of a number of vectors of fixed dimension, the MDMWNPP searches for a partition of the vectors into a given number of subsets with the property that the sums of the elements in each subset are equal or almost equal for all the coordinates of the vectors. We design an enhanced genetic algorithm using diploidy to maintain diversity of the population for solving the MDMWNPP. The resulted diploid genetic algorithm (DGA) is hybridized by incorporating a local search procedure to guide the search towards the most promising search regions of the solution space, obtaining a diploid memetic algorithm. We report preliminary computational results on a set of standard benchmark instances from the literature to assess the performance of our developed DMA. The achieved computational results show that our novel solution approach compares favorably against the existing state-of-the-art algorithms. These findings were confirmed by the performed statistical evaluation. Finally, we conduct ablation studies on key algorithmic components to confirm their novelty and effectiveness.