A comparative performance analysis of computational intelligence techniques to solve the asymmetric travelling salesman problem
This paper presents a comparative performance analysis of some metaheuristics such as the African Buffalo Optimization algorithm (ABO), Improved Extremal Optimization (IEO), Model-Induced Max-Min Ant Colony Optimization (MIMM-ACO), Max-Min Ant System (MMAS), Cooperative Genetic Ant System (CGAS), an...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Hindawi Publishing Corporation
2021
|
| Subjects: | |
| Online Access: | http://umpir.ump.edu.my/id/eprint/31726/1/A%20comparative%20performance%20analysis%20of%20computational%20intelligence%20techniques.pdf |
| _version_ | 1796994665284632576 |
|---|---|
| author | Odili, Julius Beneoluchi Noraziah, Ahmad Zarina, M. |
| author_facet | Odili, Julius Beneoluchi Noraziah, Ahmad Zarina, M. |
| author_sort | Odili, Julius Beneoluchi |
| collection | UMP |
| description | This paper presents a comparative performance analysis of some metaheuristics such as the African Buffalo Optimization algorithm (ABO), Improved Extremal Optimization (IEO), Model-Induced Max-Min Ant Colony Optimization (MIMM-ACO), Max-Min Ant System (MMAS), Cooperative Genetic Ant System (CGAS), and the heuristic, Randomized Insertion Algorithm (RAI) to solve the asymmetric Travelling Salesman Problem (ATSP). Quite unlike the symmetric Travelling Salesman Problem, there is a paucity of research studies on the asymmetric counterpart. This is quite disturbing because most real-life applications are actually asymmetric in nature. These six algorithms were chosen for their performance comparison because they have posted some of the best results in literature and they employ different search schemes in attempting solutions to the ATSP. The comparative algorithms in this study employ different techniques in their search for solutions to ATSP: the African Buffalo Optimization employs the modified Karp–Steele mechanism, Model-Induced Max-Min Ant Colony Optimization (MIMM-ACO) employs the path construction with patching technique, Cooperative Genetic Ant System uses natural selection and ordering; Randomized Insertion Algorithm uses the random insertion approach, and the Improved Extremal Optimization uses the grid search strategy. After a number of experiments on the popular but difficult 15 out of the 19 ATSP instances in TSPLIB, the results show that the African Buffalo Optimization algorithm slightly outperformed the other algorithms in obtaining the optimal results and at a much faster speed. |
| first_indexed | 2024-03-06T12:51:03Z |
| format | Article |
| id | UMPir31726 |
| institution | Universiti Malaysia Pahang |
| language | English |
| last_indexed | 2024-03-06T12:51:03Z |
| publishDate | 2021 |
| publisher | Hindawi Publishing Corporation |
| record_format | dspace |
| spelling | UMPir317262021-07-28T08:51:53Z http://umpir.ump.edu.my/id/eprint/31726/ A comparative performance analysis of computational intelligence techniques to solve the asymmetric travelling salesman problem Odili, Julius Beneoluchi Noraziah, Ahmad Zarina, M. QA76 Computer software This paper presents a comparative performance analysis of some metaheuristics such as the African Buffalo Optimization algorithm (ABO), Improved Extremal Optimization (IEO), Model-Induced Max-Min Ant Colony Optimization (MIMM-ACO), Max-Min Ant System (MMAS), Cooperative Genetic Ant System (CGAS), and the heuristic, Randomized Insertion Algorithm (RAI) to solve the asymmetric Travelling Salesman Problem (ATSP). Quite unlike the symmetric Travelling Salesman Problem, there is a paucity of research studies on the asymmetric counterpart. This is quite disturbing because most real-life applications are actually asymmetric in nature. These six algorithms were chosen for their performance comparison because they have posted some of the best results in literature and they employ different search schemes in attempting solutions to the ATSP. The comparative algorithms in this study employ different techniques in their search for solutions to ATSP: the African Buffalo Optimization employs the modified Karp–Steele mechanism, Model-Induced Max-Min Ant Colony Optimization (MIMM-ACO) employs the path construction with patching technique, Cooperative Genetic Ant System uses natural selection and ordering; Randomized Insertion Algorithm uses the random insertion approach, and the Improved Extremal Optimization uses the grid search strategy. After a number of experiments on the popular but difficult 15 out of the 19 ATSP instances in TSPLIB, the results show that the African Buffalo Optimization algorithm slightly outperformed the other algorithms in obtaining the optimal results and at a much faster speed. Hindawi Publishing Corporation 2021-04-20 Article PeerReviewed pdf en cc_by_4 http://umpir.ump.edu.my/id/eprint/31726/1/A%20comparative%20performance%20analysis%20of%20computational%20intelligence%20techniques.pdf Odili, Julius Beneoluchi and Noraziah, Ahmad and Zarina, M. (2021) A comparative performance analysis of computational intelligence techniques to solve the asymmetric travelling salesman problem. Computational Intelligence and Neuroscience, 2021 (6625438). pp. 1-13. ISSN 1687-5265 (print); 1687-5273 (online). (Published) https://doi.org/10.1155/2021/6625438 https://doi.org/10.1155/2021/6625438 |
| spellingShingle | QA76 Computer software Odili, Julius Beneoluchi Noraziah, Ahmad Zarina, M. A comparative performance analysis of computational intelligence techniques to solve the asymmetric travelling salesman problem |
| title | A comparative performance analysis of computational intelligence techniques to solve the asymmetric travelling salesman problem |
| title_full | A comparative performance analysis of computational intelligence techniques to solve the asymmetric travelling salesman problem |
| title_fullStr | A comparative performance analysis of computational intelligence techniques to solve the asymmetric travelling salesman problem |
| title_full_unstemmed | A comparative performance analysis of computational intelligence techniques to solve the asymmetric travelling salesman problem |
| title_short | A comparative performance analysis of computational intelligence techniques to solve the asymmetric travelling salesman problem |
| title_sort | comparative performance analysis of computational intelligence techniques to solve the asymmetric travelling salesman problem |
| topic | QA76 Computer software |
| url | http://umpir.ump.edu.my/id/eprint/31726/1/A%20comparative%20performance%20analysis%20of%20computational%20intelligence%20techniques.pdf |
| work_keys_str_mv | AT odilijuliusbeneoluchi acomparativeperformanceanalysisofcomputationalintelligencetechniquestosolvetheasymmetrictravellingsalesmanproblem AT noraziahahmad acomparativeperformanceanalysisofcomputationalintelligencetechniquestosolvetheasymmetrictravellingsalesmanproblem AT zarinam acomparativeperformanceanalysisofcomputationalintelligencetechniquestosolvetheasymmetrictravellingsalesmanproblem AT odilijuliusbeneoluchi comparativeperformanceanalysisofcomputationalintelligencetechniquestosolvetheasymmetrictravellingsalesmanproblem AT noraziahahmad comparativeperformanceanalysisofcomputationalintelligencetechniquestosolvetheasymmetrictravellingsalesmanproblem AT zarinam comparativeperformanceanalysisofcomputationalintelligencetechniquestosolvetheasymmetrictravellingsalesmanproblem |