A hybrid genetic algorithm, list-based simulated annealing algorithm, and different heuristic algorithms for travelling salesman problem
| Autor: | Vladimir Ilin, Dragan Simić, Svetislav D Simić, Svetlana Simić, Nenad Saulić, José Luis Calvo-Rolle |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | Logic Journal of the IGPL. |
| ISSN: | 1368-9894 1367-0751 |
| Popis: | The travelling salesman problem (TSP) belongs to the class of NP-hard problems, in which an optimal solution to the problem cannot be obtained within a reasonable computational time for large-sized problems. To address TSP, we propose a hybrid algorithm, called GA-TCTIA-LBSA, in which a genetic algorithm (GA), tour construction and tour improvement algorithms (TCTIAs) and a list-based simulated annealing (LBSA) algorithm are used. The TCTIAs are introduced to generate a first population, and after that, a search is continued with the GA. The problem of premature convergence of the GA to local optimum is tackled by a method called social disaster technique. Afterwards, the LBSA is applied to generate a new population based on one of two proposed operators called packing and judgement day. The proposed algorithm is implemented in the MATLAB environment, and its two variants, called GA-TCTIA-LBSA packing and GA-TCTIA-LBSA judgement day, are tested on symmetric and asymmetric instances from TSPLIB. The overall results demonstrate that the proposed GA-TCTIA-LBSAs offer promising results, particularly for small-sized instances. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|