An evolutionary method for solving the traveling salesman problem

• Дата: 2019
• Автори: Oliinyk, A. О., Fedorchenko, Iе. М., Stepanenko, О. О., Rud, M. S.
• Формат: Стаття
• Мова: Ukrainian
• Опубліковано: Інститут проблем реєстрації інформації НАН України 2019
• Теми: optimal path; traveling salesman problem; genetic algorithm; evolutionary algorithm; minimum distance; graph; C; Qt
• Онлайн доступ: http://drsp.ipri.kiev.ua/article/view/183550
• Назва журналу: Data Recording, Storage & Processing

A method is proposed for solving the traveling salesman problem on the basis of an evolutionary approach, and their approbation in the pharmacy business has been carried out by optimizing the operation of the drug delivery device. A modification of the evolutionary algorithm has been developed, namely, three methods for initializing an initial population of a simple GA: the standard method (Default), the mixed method (Random), and the mixed optimal (Random optimal). In the developed standard method, each individual, when generating the initial population, consists of the same gene sequence — indices of the visited drug packages, arranged in ascending order from first to last. When using the mixed method, each individual in the generation of the initial population consists of different sequences of genes — indices of visited packages of drugs arranged in a random order. In the mixed optimal method developed, each individual, when generating the initial population, will consist of identical sequences of genes, each of which is the best way among the number of generated mixed paths specified by the user.Unlike existing methods, a modified GA version allows one to select the initial population initialization method when solving the traveling salesman problem, which, in turn, allows generating more adapted chromosomes (chromosomes with better fitness functions) at the initialization stage and thus improving the results of the algorithm. The proposed modification allows significantly increase the speed due to the fact that when using the standard initial population initialization method, the initial value of the calculated fitness function and, accordingly, the distance will be less than when using other initialization methods, which will allow to more accurately determine the optimum of the problem.Created software that allows you to change the initial parameters of the genetic algorithm, graphically observe the process of solving the traveling salesman problem get the result in text and graphic form. Tabl.: 1. Fig.: 6. Refs: 29 titles.