Zastosowanie algorytmu genetycznego z operatorem inwersji genów w celu poszukiwania rozwiązania problemu komiwojażera

• Authors: Handzel Zbigniew , Gajer Mirosław

Title variants

EN

Using Genetic Algorithm with Gene Inversion Operator for the Purpose of Searching the Solutions of the Traveling Salesman Problem

• Languages of publication: PL

Abstracts

PL

W artykule przedstawiono propozycję zastosowania algorytmu genetycznego z operatorem inwersji genów na potrzeby rozwiązania zagadnienia komiwojażera. Jak już uprzednio wspomniano, algorytm genetyczny nie jest w stanie odnaleźć rozwiązania optymalnego, czyli takiego, które charakteryzuje się najmniejszą z możliwych długością trasy, jaką musi pokonać komiwojażer, aby odwiedzić każde z miast dokładnie jeden raz. W związku z tym odnajdywane przez algorytm genetyczny rozwiązania są jedynie [rozwiązaniami suboptymalnymi, czyli związane z nimi długości tras komiwojażera są na pewno dłuższe od długości pożądanej trasy optymalnej. Jednak wykonywanie algorytmu genetycznego przez odpowiednio dużą liczbę pokoleń daje gwarancję, że uzyskane rezultaty nie będą zbytnio odbiegały od pożądanego rozwiązania optymalnego i zwykle z punktu widzenia praktycznych zastosowań odnajdywane przez algorytm genetyczny rozwiązania są już odpowiednio wysokiej jakości i mogą być wstępnie wykorzystywane w wielu różnorodnych praktycznych zastosowaniach w wybranych obszarach techniki i ekonomii. (fragment tekstu)

EN

In the paper we propose to use a genetic algorithm for the purpose offinding solutions of the traveling salesman problem. We use a unique gene inversion operator, which allowed us to implement the genetic algorithm in the form of evolutionary strategy with many evolving individuals. The traveling salesman problem belongs to the broader class of NP-hard problems, which causes that the optimal solution cannot be found in a reasonable time period, even for the relatively low number of cities. The implemented by the authors evolutionary strategy makes it possible to find suboptimal solutions of traveling salesman problem, which are of relatively good quality.(original abstract)

Keywords

PL

Algorytmy genetyczne; Rozwiązywanie problemów; Podróże służbowe

EN

Genetic algorithms; Solving problems; Business trips

• Publisher: Wydawnictwo WSEI Kraków
• Journal: Zeszyty Naukowe Wyższej Szkoły Ekonomii i Informatyki w Krakowie
• Year: 2013
• Volume: 9
• Pages: 127-134

Contributors

author

Handzel Zbigniew

• Wyższa Szkoła Ekonomii i Informatyki w Krakowie

author

Gajer Mirosław

• Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

References

• Goldberg D. E., Algorytmy genetyczne i ich zastosowania. Wydawnictwa Naukowo-Techniczne, Warszawa, 1996.
• Rutkowska D., Piliński M., Rutkowski L., Sieci neuronowe, algorytmy genetyczne i systemy rozmyte, Wydawnictwo Naukowe PWN, Warszawa-Łódź, 1997.
• Michalewicz Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, Wydawnictwa Naukowo-Techniczne, Warszawa, 2003.
• Arabas J., Wykłady z algorytmów ewolucyjnych. Wydawnictwa Naukowo-Techniczne, Warszawa, 2004.
• Rutkowski L., Metody i techniki sztucznej inteligencji, Wydawnictwo Naukowe PWN, Warszawa, 2012.
• Filipowicz В., Badania operacyjne, Wydawnictwo ABART, Kraków, 2007.
• Gajer M., Accelerating the rate of evolutionary processes with the use of constant learning, Przegląd Elektrotechniczny, vol. 87, n. 1, 2011, pp. 204-209.
• Gajer M., Implementation of evolutionary algorithms in the discipline of Artificial Chemistry, Przegląd Elektrotechniczny, vol. 87, n. 4, 2011, pp. 198-202.
• Gajer M, The implementation of the evolutionary computations in the domain of electrical circuits theory, Przegląd Elektrotechniczny, vol. 87, n. 6, 2011, pp. 150-153.
• Gajer M., Visualization of particle swarm dynamics with the use of Virtual Reality Modeling Language, Przegląd Elektrotechniczny, vol. 87, n. 11, 2011, pp. 20-24.
• Gajer M., The analysis of impact of learning on the rate of evolution in the case of a multimodal fitness function, Przegląd Elektrotechniczny, vol. 86, n. 2, 2010, pp. 24-29.
• Gajer M., The implementation of the evolutionary algorithm for the analysis of nonlinear electrical circuits, Przegląd Elektrotechniczny, vol. 86, n. 7, 2010, pp. 342-345.