A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem |
| |
Authors: | Petrică C Pop Oliviu Matei |
| |
Institution: | 1. Technical University of Cluj-Napoca, North University Center Baia Mare, Department of Mathematics and Computer Science, Baia Mare, Romania;2. Technical University of Cluj-Napoca, North University Center Baia Mare, Department of Electrical Engineering, Baia Mare, Romania |
| |
Abstract: | In this paper, we describe a generalization of the multidimensional two-way number partitioning problem (MDTWNPP) where a set of vectors has to be partitioned into p sets (parts) such that the sums per every coordinate should be exactly or approximately equal. We will call this generalization the multidimensional multi-way number partitioning problem (MDMWNPP). Also, an efficient memetic algorithm (MA) heuristic is developed to solve the multidimensional multi-way number partitioning problem obtained by combining a genetic algorithm (GA) with a powerful local search (LS) procedure. The performances of our memetic algorithm have been compared with the existing numerical results obtained by CPLEX based on an integer linear programming formulation of the problem. The solution reveals that our proposed methodology performs very well in terms of both quality of the solutions obtained and the computational time compared with the previous method of solving the multidimensional two-way number partitioning problem. |
| |
Keywords: | Number partitioning Genetic algorithms Local search Memetic algorithm Combinatorial optimization |
本文献已被 ScienceDirect 等数据库收录! |