This paper introduces MADEB, a Memetic Algebraic Differential Evolution algorithm for the Binary search space. MADEB has been applied to the multidimensional two-way number partitioning problem (MDTWNPP) and its main ...
详细信息
ISBN:
(数字)9783030167110
ISBN:
(纸本)9783030167103;9783030167110
This paper introduces MADEB, a Memetic Algebraic Differential Evolution algorithm for the Binary search space. MADEB has been applied to the multidimensional two-way number partitioning problem (MDTWNPP) and its main components are the binary differential mutation operator and a variable neighborhood descent procedure. The binary differential mutation is a concrete application of the abstract algebraic framework for the binary search space. The variable neighborhood descent is a local search procedure specifically designed for MDTWNPP. Experiments have been held on a widely accepted benchmark suite and MADEB is experimentally compared with respect to the current state-of-the-art algorithms for MDTWNPP. The experimental results clearly show that MADEB is the new state-of-the-art algorithm in the problem here investigated.
In this study, a novel usage of four metaheuristic approaches Genetic algorithm (GA), Simulated annealing (SA), migrating bird optimization algorithm (MBO) and clonal selection algorithm (CSA) are applied to multidime...
详细信息
In this study, a novel usage of four metaheuristic approaches Genetic algorithm (GA), Simulated annealing (SA), migrating bird optimization algorithm (MBO) and clonal selection algorithm (CSA) are applied to multidimensional two-way number partitioning problem (MDTWNPP). MDTWNPP is a classical combinatorial NP-hard optimization problem where a set of vectors have more than one coordinate is partitioned into two subsets. The main objective function of MDTWNPP is to minimize the maximum absolute difference between the sums per coordinate of elements. In order to solve this problem, GA is applied with greedy crossover and mutation operators. SA is improved with dual local search mechanism. MBO is specialized as multiple flock migrating birds optimization algorithms. CSA is applied with problem specific hyper mutation process. Furthermore, all instances are solved using an integer linear programming model which was previously presented in the literature. In the experiments, four metaheuristic approaches and integer linear programming model are used to solve 126 datasets with different sizes and coordinates. As a brief result, the GA and SA approaches designed for this problem outperformed all other heuristics and the integer programming model. Both the performance of GA and SA approaches are in a competitive manner where GA and SA yielded the best solution for 56 and 65 out of 125 datasets, respectively.
In this work, we tackle multidimensionaltwo-waynumberpartitioning (MDTWNP) problem by combining GRASP with Exterior Path Relinking. In the last few years, the combination of GRASP with path relinking (PR) has emerg...
详细信息
In this work, we tackle multidimensionaltwo-waynumberpartitioning (MDTWNP) problem by combining GRASP with Exterior Path Relinking. In the last few years, the combination of GRASP with path relinking (PR) has emerged as a highly effective tool for finding high-quality solutions for several difficult problems in reasonable computational time. However, in most of the cases, this hybridisation is limited to the variant known as interior PR. Here, we couple GRASP with the "exterior form" of path relinking and perform extensive experimentation to evaluate this variant. In addition, we enhance our GRASP with PR method with a novel local search method specially designed for the MDTWNP problem. Our computational experiments show the superiority of this approach compared with the previous best method for MDTWNP and with alternative methods for this problem that use other forms of PR.
暂无评论