Nowa wersja platformy jest już dostępna.
Przejdź na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | z. 9 | 127-134
Tytuł artykułu

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

Warianty tytułu
Using Genetic Algorithm with Gene Inversion Operator for the Purpose of Searching the Solutions of the Traveling Salesman Problem
Języki publikacji
PL
Abstrakty
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)
Rocznik
Numer
Strony
127-134
Opis fizyczny
Twórcy
  • Wyższa Szkoła Ekonomii i Informatyki w Krakowie
  • AGH Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
Bibliografia
  • [1] Goldberg D. E., Algorytmy genetyczne i ich zastosowania. Wydawnictwa Naukowo-Techniczne, Warszawa, 1996.
  • [2] Rutkowska D., Piliński M., Rutkowski L., Sieci neuronowe, algorytmy genetyczne i systemy rozmyte, Wydawnictwo Naukowe PWN, Warszawa-Łódź, 1997.
  • [3] Michalewicz Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, Wydawnictwa Naukowo-Techniczne, Warszawa, 2003.
  • [4] Arabas J., Wykłady z algorytmów ewolucyjnych. Wydawnictwa Naukowo-Techniczne, Warszawa, 2004.
  • [5] Rutkowski L., Metody i techniki sztucznej inteligencji, Wydawnictwo Naukowe PWN, Warszawa, 2012.
  • [6] Filipowicz В., Badania operacyjne, Wydawnictwo ABART, Kraków, 2007.
  • [7] 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.
  • [8] Gajer M., Implementation of evolutionary algorithms in the discipline of Artificial Chemistry, Przegląd Elektrotechniczny, vol. 87, n. 4, 2011, pp. 198-202.
  • [9] 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.
  • [10] 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.
  • [11] 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.
  • [12] 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171314387
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.