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%.
Целью данной работы является исследование актуальной задачи коммивояжера, которая является NP сложной задачей дискретной оптимизации. Показано, что для достижения поставленной цели пригодны лишь эвристические методы. Для решения задачи представлен результат совместного использования муравьиного (МА) и генетического (ГА) алгоритмов. Особенностью предложенного генетического алгоритма является то, что задача решается только с помощью различных мутаций (без кроссовера). Исследуемый ГА был улучшен введением элитарной стратегии. Испытания проводились на графах средней и большой размерности. Элитная особь, получаемая с помощью муравьиного алгоритма, в среднем улучшалась на 11 %. Показано, что эффективность генетического алгоритма напрямую зависит от количества особей в поколении и количества итераций алгоритма. Ввод элитарной стратегии улучшил получаемые значения целевой функции более чем в 2 раза. Увеличение числа запусков МА при выборе элиты позволило повысить эффективность алгоритма приблизительно на 2 %.
The authors declare that there are no conflicts of interest present.