Hybridization of the optimization process as an alternative way to find approximate solutions for NP-hard problems

• Autorzy: Rozenberg L. , Rychcicki R.

Warianty tytułu

PL

Wykorzystanie hybrydowej procedury optymalizacji jako alternatywy do określenia przybliżonych rozwiązań problemów NP - trudnych

• Języki publikacji: EN

Abstrakty

EN

This paper presents the results of calculations that demonstrate the possibility of using hybrid optimization method (with variable structure) for determining the approximate solutions to NP-hard problems. The Travelling Salesman Problem (TSP) is a classic combinatorial optimization subject, which has found widespread use in practice. Simple in definition, have remained hard to solve for many years. Not only an efficient solution would yield benefits in a substantial amount of routing problems, but it would also affect planning and logistics in a positive way.

PL

W prezentowanym artykule pokazano możliwość wykorzystania hybrydy optymalizacyjnej do uzyskania przybliżonego rozwiązania zadania NP-trudnego, czyli problemu obliczeniowego o ponad wykładniczym zapotrzebowaniu na moc obliczeniową. Do badań wybrano znany od wielu lat problem komiwojażera, którego od lat nie udało się ostatecznie rozwiązać. Wybór ten jednak umożliwił uzyskanie pokaźnego materiału porównawczego.

Słowa kluczowe

EN

Monte Carlo method; hybrid algorithm; hybrid optimization; NP-hard problem

PL

metoda Monte Carlo; algorytm hybrydowy; optymalizacja hybrydowa; problem NP-trudny

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2015
• Tom: R. 91, nr 2
• Strony: 59--62
• Opis fizyczny: Bibliogr. 6 poz., rys., tab., wykr.

Twórcy

autor

Rozenberg L.

• Zachodniopomorski Uniwersytet Technologiczny w Szczecinie, Wydział Informatyki, ul. Żołnierska 49, 71-210 Szczecin

autor

Rychcicki R.

• Instytut Elektrotechniki, Zakład maszyn Elektrycznych, ul. Pożaryskiego 28, 04-703 Szczecin

Bibliografia

• [1] Buslenko N.P., Golenko D.I., Metoda Monte Carlo, PWN Warszawa 1967
• [2] Białynicki-Birula I. Modelowanie rzeczywistości, Prószyński i Ska, Warszawa, 2002
• [3] De Jong, K.A., Genetic algorithms are NOT function optimizers. Foundations of genetic algorithms, 1993. Book 2, pp. 5-17
• [4] Rychcicki, R., Szybka dyskretna transformata sinusowa. Studia i Materiały Informatyki Stosowanej, Szczecin, 2010 nr 2
• [5] Rychcicki, R., Optymalizacja trasy w euklidesowym problemie komiwojażera. Praca inżynierska; Szczecin: 2012. Zachodniopomorski Uniwersytet Technologiczny,
• [6] Rychcicki, R., Algorytmy heurystyczne i aproksymacyjne do optymalizacji trasy w problemie komiwojażera. Praca magisterska; Szczecin 2014; Zachodniopomorski Uniwersytet Technologiczny