A Comparative Analysis of Metaheuristic Approaches for Multidimensional Two-Way Number Partitioning Problem
| Autor: | Kemal Alaykiran, Erkan Ülker, Vahit Tongur, Ayse Merve Acilar, Mehmet Hacibeyoglu |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
021103 operations research Multidisciplinary Optimization problem Computer science business.industry Crossover 0211 other engineering and technologies 02 engineering and technology Clonal selection algorithm Genetic algorithm Mutation (genetic algorithm) Simulated annealing 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Local search (optimization) business Metaheuristic |
| Zdroj: | Arabian Journal for Science and Engineering. 43:7499-7520 |
| ISSN: | 2191-4281 2193-567X |
| DOI: | 10.1007/s13369-018-3155-9 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|