Genetiniai algoritmai komivojažieriaus uždaviniui: negatyvieji ir pozityvieji aspektai*

Santrauka

Šiame straipsnyje nagrinėjami klausimai, susiję su genetinių algoritmų taikymu, sprendžiant gerai žinomą kombinatorinio optimizavimo uždavinį – komivojažieriaus uždavinį (KU) (angl. traveling salesman problem). Svarstoma, jog genetinio algoritmo efektyvumui didelę įtaką turi uždavinio specifi nės savybės, todėl labai svarbu kūrybiškai sudaryti genetinį algoritmą konkrečiam sprendžiamam uždaviniui. Pateikiami eksperimentų, atliktų su realizuotu genetiniu algoritmu, rezultatai, iliustruojantys skirtingų veiksnių įtaką rezultatų kokybei. Konstatuojama, kad tinkamas genetinių operatorių ir lokaliojo individų (sprendinių) gerinimo derinimas leidžia gerokai padidinti genetinės paieškos efektyvumą.

On the Genetic Algorithms for the Traveling Salesman Problem: Negative and Positive Aspects
Alfonsas Misevičius, Andrius Blažinskas, Jonas Blonskis, Vytautas Bukšnaitis

Summary
In this paper, we discuss some issues related to the application of genetic algorithms (GAs) to the well-known combinatorial optimization problem – the traveling salesman problem (TSP). The results obtained from the experiments with the different variants of the genetic algorithm are presented as well. Based on these results, it is concluded that the effi ciency of the genetic search is much infl uenced by both the specifi c nature of the problem and the features of the algorithm itself. In particular, it should be emphasized that the incorporation of the (postcrossover) procedures for the local improvement of offspring has one of the crucial roles in obtaining high-quality solutions.