Current Proceedings on Technology

Yazarlar: Bahriye Akay, Emre Aydogan, Levent Karacan

Konular:-

Anahtar Kelimeler:2-Opt,Artificial Bee Colony,Greedy Algorithm,Traveling Salesman Problem

Özet: Combinatorial optimization finds the best subset in a discrete problem space. In engineering or management fields, many problems are formulated as a combinatorial optimization problem. A well-known hard combinatorial optimization problem, the Traveling Salesman Problem (TSP), tries to find a minimum cost tour of n cities starting from a city, visiting all cities only once and finally returning the start city. An improvement algorithm, 2-Opt algorithm, is a basic local search heuristic for solving TSP. However, major disadvantages of 2-opt algorithm are that its performance is highly dependent upon the initial solution provided to it and it lacks a global search mechanism to escape local minima by uphill moves. Therefore, hybrid algorithms are needed to combine a global search heuristic with 2-opt local search algorithm. In this study, a hybrid method, called 2-Opt-ABC, is proposed which combines a successful global optimization algorithm, Artificial Bee Colony (ABC) algorithm, and 2-opt local search algorithm. In the method, ABC algorithm provides global search ability to avoid local minima and 2-opt algorithm improves local searches. Since 2-opt algorithm uses the improved solutions by ABC algorithm which uses neighborhood based 2-opt moves, the disadvantage of 2-opt algorithm, that is dependency of performance upon the quality of initial solutions, is removed. In the benchmarks, in order to investigate the combination of global search and local search, we have compared the performance of the 2-opt-ABC algorithm with that of 2-opt algorithm on some problem instances from TSPLIB. 

---