What is it about?
The multidimensional multi-way number partitioning problem (MDMWNPP) is an extension of the number partitioning problem. In this paper, our genetic algorithm approach use diploidy to maintain diversity of the population, resulting an enhancement of the performance of genetic algorithm (GA) in solving the MDMWNPP. The resulted diploid genetic algorithm (DGA) is combined with an efficient local search procedure to guide the search towards promising regions of the solution space.
Featured Image
Photo by Sangharsh Lohakare on Unsplash
Why is it important?
The number partitioning problem (NPP) is a classical combinatorial optimization problem which aims to partition a set S of positive integers into subsets such that the difference between the sum of elements in subsets is minimized. The use of NPP include problems of elections, cryptography, machine learning etc.
Perspectives
The aim of this paper was to solve the multidimensional multiway number partitioning problem (MDMWNPP) using a diploid genetic algorithm. We use diploidy to enhance the performance of the classical GAs by maintaining diversity of the population, and we combine the diploid genetic algorithm with a local search procedure, in order to obtain a powerful and effective novel solution approach for solving the MDMWNPP.
Cosmin Sabo
Universitatea Tehnica din Cluj-Napoca
Our experimental results show that the proposed DGA is effective in solving the MDMWNPP. We also discuss the limitations of our approach and identify some promising directions for future research. These include investigating other dominance schemes and local search strategies, as well as evaluating the generality and scalability of the DGA on larger instances.
Adrian Petrovan
Universitatea Tehnica din Cluj-Napoca
Read the Original
This page is a summary of: A Diploid Genetic Algorithm for Solving the Multidimensional Multi-way Number Partitioning Problem, July 2023, ACM (Association for Computing Machinery),
DOI: 10.1145/3583133.3590672.
You can read the full text:
Contributors
The following have contributed to this page
