An effective Discrete Bacterial Memetic Evolutionary Algorithm for the Traveling Salesman Problem

作者：Koczy Laszlo T^*; Foldesi Peter; Tuu Szabo Boldizsar

来源：International Journal of Intelligent Systems, 2017, 32(8): 862-876.

DOI：10.1002/int.21893

In recent years, a large number of evolutionary and other population-based heuristics were proposed in the literature. In 2009, we suggested to combine the very efficient bacterial evolutionary algorithm with local search as a new Discrete Bacterial Memetic Evolutionary Algorithm (DBMEA) (Farkas etal., In: Towards intelligent engineering & information technology, Studies in Computational Intelligence, Vol 243. Berlin, Germany: Springer-Verlag; 2009. pp 607-625). The method was tested on one of Traveling Salesman Problem (TSP) benchmark problems, and a difference was found between the real optimum calculated by the new and the published result because the Concorde and the Lin-Kernighan algorithm use an approximation substituting distances of points by the closest integer values. We modified the Concorde algorithm using real cost values to compare with our results. In this paper, we systematically investigate TSPLIB benchmark problems and other VLSI benchmark problems () and compare the following values: optima found by the DBMEA heuristic and by the modified Concorde algorithm with real cost values, run times of DBMEA, modified Concorde, and Lin-Kernighan heuristic. In this paper, for the evaluation of metaheuristic techniques, we suggest the usage of predictability of the successful run in addition to the accuracy of the result and the computational cost as third property. We will show that in the case of DBMEA, the run time is more predictable than in the case of Concorde algorithm, so we suggest the use of DBMEA heuristic as very efficient for the solution of TSP and other nondeterministic polynomial-time hard optimization problems.

• 出版日期2017-8