An Improved Hybrid Genetic-Hierarchical Algorithm for the Quadratic Assignment Problem
In this paper, an improved hybrid genetic-hierarchical algorithm for the solution of the quadratic assignment problem (QAP) is presented. The algorithm is based on the genetic search combined with the hierarchical (hierarchicity-based multi-level) iterated tabu search procedure. The following are tw...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-11-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/23/3726 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850106525204348928 |
|---|---|
| author | Alfonsas Misevičius Aleksandras Andrejevas Armantas Ostreika Dovilė Verenė Gintarė Žekienė |
| author_facet | Alfonsas Misevičius Aleksandras Andrejevas Armantas Ostreika Dovilė Verenė Gintarė Žekienė |
| author_sort | Alfonsas Misevičius |
| collection | DOAJ |
| description | In this paper, an improved hybrid genetic-hierarchical algorithm for the solution of the quadratic assignment problem (QAP) is presented. The algorithm is based on the genetic search combined with the hierarchical (hierarchicity-based multi-level) iterated tabu search procedure. The following are two main scientific contributions of the paper: (i) the enhanced two-level hybrid primary (master)-secondary (slave) genetic algorithm is proposed; (ii) the augmented universalized multi-strategy perturbation (mutation process)—which is integrated within a multi-level hierarchical iterated tabu search algorithm—is implemented. The proposed scheme enables efficient balance between intensification and diversification in the search process. The computational experiments have been conducted using QAP instances of sizes up to 729. The results from the experiments with the improved algorithm demonstrate the outstanding performance of the new proposed approach. This is especially obvious for the small- and medium-sized instances. Nearly 90% of the runs resulted in (pseudo-)optimal solutions. Three new best-known solutions have been achieved for very hard, challenging QAP instances. |
| format | Article |
| id | doaj-art-d96243e1e1a6487f83c382ad49e5063a |
| institution | OA Journals |
| issn | 2227-7390 |
| language | English |
| publishDate | 2024-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-d96243e1e1a6487f83c382ad49e5063a2025-08-20T02:38:48ZengMDPI AGMathematics2227-73902024-11-011223372610.3390/math12233726An Improved Hybrid Genetic-Hierarchical Algorithm for the Quadratic Assignment ProblemAlfonsas Misevičius0Aleksandras Andrejevas1Armantas Ostreika2Dovilė Verenė3Gintarė Žekienė4Department of Multimedia Engineering, Kaunas University of Technology, Studentų st. 50, LT-51368 Kaunas, LithuaniaDepartment of Multimedia Engineering, Kaunas University of Technology, Studentų st. 50, LT-51368 Kaunas, LithuaniaDepartment of Multimedia Engineering, Kaunas University of Technology, Studentų st. 50, LT-51368 Kaunas, LithuaniaDepartment of Multimedia Engineering, Kaunas University of Technology, Studentų st. 50, LT-51368 Kaunas, LithuaniaDepartment of Multimedia Engineering, Kaunas University of Technology, Studentų st. 50, LT-51368 Kaunas, LithuaniaIn this paper, an improved hybrid genetic-hierarchical algorithm for the solution of the quadratic assignment problem (QAP) is presented. The algorithm is based on the genetic search combined with the hierarchical (hierarchicity-based multi-level) iterated tabu search procedure. The following are two main scientific contributions of the paper: (i) the enhanced two-level hybrid primary (master)-secondary (slave) genetic algorithm is proposed; (ii) the augmented universalized multi-strategy perturbation (mutation process)—which is integrated within a multi-level hierarchical iterated tabu search algorithm—is implemented. The proposed scheme enables efficient balance between intensification and diversification in the search process. The computational experiments have been conducted using QAP instances of sizes up to 729. The results from the experiments with the improved algorithm demonstrate the outstanding performance of the new proposed approach. This is especially obvious for the small- and medium-sized instances. Nearly 90% of the runs resulted in (pseudo-)optimal solutions. Three new best-known solutions have been achieved for very hard, challenging QAP instances.https://www.mdpi.com/2227-7390/12/23/3726combinatorial optimizationheuristic algorithmsgenetic algorithmstabu searchquadratic assignment problem |
| spellingShingle | Alfonsas Misevičius Aleksandras Andrejevas Armantas Ostreika Dovilė Verenė Gintarė Žekienė An Improved Hybrid Genetic-Hierarchical Algorithm for the Quadratic Assignment Problem Mathematics combinatorial optimization heuristic algorithms genetic algorithms tabu search quadratic assignment problem |
| title | An Improved Hybrid Genetic-Hierarchical Algorithm for the Quadratic Assignment Problem |
| title_full | An Improved Hybrid Genetic-Hierarchical Algorithm for the Quadratic Assignment Problem |
| title_fullStr | An Improved Hybrid Genetic-Hierarchical Algorithm for the Quadratic Assignment Problem |
| title_full_unstemmed | An Improved Hybrid Genetic-Hierarchical Algorithm for the Quadratic Assignment Problem |
| title_short | An Improved Hybrid Genetic-Hierarchical Algorithm for the Quadratic Assignment Problem |
| title_sort | improved hybrid genetic hierarchical algorithm for the quadratic assignment problem |
| topic | combinatorial optimization heuristic algorithms genetic algorithms tabu search quadratic assignment problem |
| url | https://www.mdpi.com/2227-7390/12/23/3726 |
| work_keys_str_mv | AT alfonsasmisevicius animprovedhybridgenetichierarchicalalgorithmforthequadraticassignmentproblem AT aleksandrasandrejevas animprovedhybridgenetichierarchicalalgorithmforthequadraticassignmentproblem AT armantasostreika animprovedhybridgenetichierarchicalalgorithmforthequadraticassignmentproblem AT dovileverene animprovedhybridgenetichierarchicalalgorithmforthequadraticassignmentproblem AT gintarezekiene animprovedhybridgenetichierarchicalalgorithmforthequadraticassignmentproblem AT alfonsasmisevicius improvedhybridgenetichierarchicalalgorithmforthequadraticassignmentproblem AT aleksandrasandrejevas improvedhybridgenetichierarchicalalgorithmforthequadraticassignmentproblem AT armantasostreika improvedhybridgenetichierarchicalalgorithmforthequadraticassignmentproblem AT dovileverene improvedhybridgenetichierarchicalalgorithmforthequadraticassignmentproblem AT gintarezekiene improvedhybridgenetichierarchicalalgorithmforthequadraticassignmentproblem |