Elitist Ant System with 2-opt Local Search for the Traveling Salesman Problem
The Traveling Salesman Problem is one of the most famous problems in combinatorial optimization. The paper presents an algorithm based upon the elitist ant system for solving the traveling salesman problem. 2-opt local search is incorporated in the elitist ant system, and it is used for improvemen...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Stefan cel Mare University of Suceava
2012-02-01
|
| Series: | Advances in Electrical and Computer Engineering |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.4316/AECE.2012.01005 |
| _version_ | 1818215713537523712 |
|---|---|
| author | MARTINOVIC, G. BAJER, D. |
| author_facet | MARTINOVIC, G. BAJER, D. |
| author_sort | MARTINOVIC, G. |
| collection | DOAJ |
| description | The Traveling Salesman Problem is one of the most famous problems in combinatorial optimization. The paper presents an algorithm based upon the elitist ant system for solving the traveling salesman problem. 2-opt local search is incorporated in the elitist ant system, and it is used for improvement of a given number of solutions previously constructed by artificial ants. A simple mechanism for avoiding a too early stagnation of the search is also proposed. The aforementioned is based on depositing strong pheromones on solution edges of randomly selected ants called random elitist ants. The aim is to encourage exploration in a greater area of the solution space. Experimental analysis shows how high-quality solutions can be achieved by using the considered algorithm instead of the usual elitist ant system with incorporated 2-opt local search. |
| first_indexed | 2024-12-12T06:40:27Z |
| format | Article |
| id | doaj.art-eee42fab9cf34de48276f699807d72f9 |
| institution | Directory Open Access Journal |
| issn | 1582-7445 1844-7600 |
| language | English |
| last_indexed | 2024-12-12T06:40:27Z |
| publishDate | 2012-02-01 |
| publisher | Stefan cel Mare University of Suceava |
| record_format | Article |
| series | Advances in Electrical and Computer Engineering |
| spelling | doaj.art-eee42fab9cf34de48276f699807d72f92022-12-22T00:34:21ZengStefan cel Mare University of SuceavaAdvances in Electrical and Computer Engineering1582-74451844-76002012-02-01121253210.4316/AECE.2012.01005Elitist Ant System with 2-opt Local Search for the Traveling Salesman ProblemMARTINOVIC, G.BAJER, D.The Traveling Salesman Problem is one of the most famous problems in combinatorial optimization. The paper presents an algorithm based upon the elitist ant system for solving the traveling salesman problem. 2-opt local search is incorporated in the elitist ant system, and it is used for improvement of a given number of solutions previously constructed by artificial ants. A simple mechanism for avoiding a too early stagnation of the search is also proposed. The aforementioned is based on depositing strong pheromones on solution edges of randomly selected ants called random elitist ants. The aim is to encourage exploration in a greater area of the solution space. Experimental analysis shows how high-quality solutions can be achieved by using the considered algorithm instead of the usual elitist ant system with incorporated 2-opt local search.http://dx.doi.org/10.4316/AECE.2012.010052-opt algorithmelitist ant systemlocal searchTraveling Salesman Problemsearch stagnation |
| spellingShingle | MARTINOVIC, G. BAJER, D. Elitist Ant System with 2-opt Local Search for the Traveling Salesman Problem Advances in Electrical and Computer Engineering 2-opt algorithm elitist ant system local search Traveling Salesman Problem search stagnation |
| title | Elitist Ant System with 2-opt Local Search for the Traveling Salesman Problem |
| title_full | Elitist Ant System with 2-opt Local Search for the Traveling Salesman Problem |
| title_fullStr | Elitist Ant System with 2-opt Local Search for the Traveling Salesman Problem |
| title_full_unstemmed | Elitist Ant System with 2-opt Local Search for the Traveling Salesman Problem |
| title_short | Elitist Ant System with 2-opt Local Search for the Traveling Salesman Problem |
| title_sort | elitist ant system with 2 opt local search for the traveling salesman problem |
| topic | 2-opt algorithm elitist ant system local search Traveling Salesman Problem search stagnation |
| url | http://dx.doi.org/10.4316/AECE.2012.01005 |
| work_keys_str_mv | AT martinovicg elitistantsystemwith2optlocalsearchforthetravelingsalesmanproblem AT bajerd elitistantsystemwith2optlocalsearchforthetravelingsalesmanproblem |