Applicability of elite samples in solving the traveling salesman problem by Goldberg model

The work objective is to study a critical traveling salesman problem which is NP complicated task of the discrete optimization. It is shown that only heuristics is appropriate in achieving this goal. The result of the ant colony algorithm (ACA) and genetic algorithm (GA) sharing is presented for the problem solution. The point is that the problem is solved using only mutations of various types (without crossover). The investigated GA is improved by the elitist strategy. The testing is done on graphs of the middle and large dimension. An “elite” sample obtained by the ACA is improved by a mean of 11%. It is shown that the efficiency of the genetic algorithm depends directly on the number of ants in the generation, and on the number of algorithm iterations. Target function values are improved more than twofold after the introduction of the elitist strategy. Increasing the number of ACA runs raises the efficiency of the algorithm by approximately 2%.

задача коммивояжера, генетический алгоритм, граф, модель Гольдберга, мутация, кроссовер, муравьиный алгоритм, элитная особь, феромон, природные вычисления, traveling salesman problem, genetic algorithm, graph, Goldberg model, mutation, crossover, ant colony algorithm, elite sample, pheromone, natural computing

1. Gladkov, L.А., Kureychik, V.V., Kureychik, V.M. Geneticheskie algoritmy. [Genetic algorithms.] Moscow: Fizmatlit, 2007, 272 p. (in Russian).

2. Gambardella, L.-M., Dorigo, M. Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.4846 (accessed: 16.09.15).

3. Dorigo, M., Maniezzo, V., Colorni, A. The Ant System: Optimization by a colony of cooperating agents. Available at: ftp://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.10-SMC96.pdf (accessed: 20.09.15).

4. Gambardella, L.-M., Dorigo, M. Solving symmetric and asymmetric TSPs by ant colonies. Available at: http://ceit.aut.ac.ir/~meybodi/Learning%20Automata%20papers/LA-Papers-Ebdali/00542672.PDF (accessed: 27.09.15).

5. Churakov, М., Yakushev, A. Murav'inye algoritmy. [Ant colony algorithms.] Available at: http://rain.ifmo.ru/cat/(accessed: 25.09.2015) (in Russian).

6. Shtovba, S.D. Murav'inye algoritmy. [Ant colony algorithms.] Available at: http://www.serhiyshtovba.narod.ru/doc/Shtovba_Ant_Algorithms_ExponentaPro_2003_3.pdf (accessed: 25.09.15) (in Russian).

7. Yemelyanov, V.V., Kureychik, V.M., Kureychik, V.V. Teoriya i praktika evolyutsionnogo modelirovaniya. [Theory and practice of evolutionary modeling.] Moscow: Fizmatlit, 2003, 432 p. (in Russian).

8. Kobak, V.G., Rudova, I.S., Zhukovskiy, A.G. Sravnitel'nyy analiz modifitsirovannoy modeli Gol'dberga i murav'inogo algoritma pri reshenii zadachi kommivoyazhera. [Comparative analysis of Goldberg modified model and ant colony algorithm for solving the traveling salesman problem.] Proc. of Moscow Technical University of Communications and Informatics, North Caucasian Branch. Rostov-on-Don, 2015, vol. 1, pp. 362–365 p. (in Russian).

9. Kobak, V.G., Rudova, I.S. Reshenie zadachi kommivoyazhera modifitsirovannoy model'yu Gol'dberga s ispol'zovaniem razlichnykh sil'nykh mutatsiy. [Traveling salesman problem solution by Goldberg modified model using different strong mutations.] Proc. Conf. of students and young researchers dedicated to the 85th Anniversary of DSTU. Rostov-on- Don, 2015, pp. 146–156 (in Russian).

10. Kobak, V.G., et al. Reshenie zadachi kommivoyazhera modifitsirovannoy model'yu Gol'dberga s pomoshch'yu razlichnogo vida mutatsiy. [Traveling salesman problem solution by Goldberg modified model by different strong mutations.] Proc. of Moscow Technical University of Communications and Informatics, North Caucasian Branch. Rostov-on-Don, 2014, vol. 1, pp. 258–261 (in Russian).