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.
Задача коммивояжера (ЗК) является NP сложной задачей дискретной оптимизации и определяется следующим образом: для заданного полного взвешенного графа G = (V, E, D) с множеством вершин V = {vi}n, множеством ребер E и матрицей весов D = {di,j}nxn необходимо найти Гамильтонов цикл (vi1, vi2,…,vin), где (i1,…,in) — перестановка на множестве {1,2,…,n}, а vi
V, с минимальной суммой весов дуг [1]
Вершины графа G часто называются городами, а любой Гамильтонов цикл называется маршрутом коммивояжера. Очевидным решением задачи является метод полного перебора. Выйдя из первого города, коммивояжер может направиться в один из (n – 1) городов, откуда в (n – 2) оставшихся городов и т. д., пока не останется один-единственный город, откуда он вышел. Таким образом, общее число маршрутов, подлежащих просмотру, составляет (n – 1) · (n – 2) … 2 · 1 = (n – 1) всевозможных вариантов. С увеличением количества городов это значение быстро возрастает и уже при 15 городах достигает астрономических цифр. Поиск точных и приближенных способов решения задачи о коммивояжере остается актуальным и с теоретической, и с практической точки зрения, так как не найдено, а возможно, и не существует точных алгоритмов, решающих ЗК за короткое (полиномиальное) время. Поэтому для решения задачи коммивояжера эффективнее использовать не точные, а эвристические методы. Применение эвристических алгоритмов к какой-либо практической задаче обычно позволяет сформулировать рекомендации, которые намного лучше произвольного решения и которые наиболее близки к лучшему варианту.
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. Availa-ble 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_Exponenta Pro_2003_3.pdf (accessed: 25.09.15) (in Rus-sian).
7. Yemelyanov, V.V., Kureychik, V.M., Kureychik, V.V. Teoriya i praktika evolyutsionnogo modelirovani-ya. [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 mu-rav´inogo algoritma pri reshenii zadachi kommivoyazhera. [Comparative analysis of Goldberg modified model and ant col-ony 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 dif-ferent 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 muta-tions.] Proc. of Moscow Technical University of Communications and Informatics, North Caucasian Branch. Rostov-on-Don, 2014, vol. 1, pp. 258–261 (in Russian).
