Darbe nagrinėjami euristiniai algoritmai NPC aibės uždaviniams spręsti ir jų taikymas lygiagrečiųjų ir paskirstytųjų skaičiavimų (angl. GRID) tinkle. NPC aibės uždaviniai, taikant įprastus algoritmus, nėra išsprendžiami per polinominį laiką, todėl jiems taikomi euristiniai algoritmai, kurie pasižymi gebėjimu, per priimtiną laiko tarpą, rasti geros kokybės sprendinius, bet didėjant uždavinių apimtims, euristinių algoritmų vykdymo laikas taip pat sparčiai ilgėja. Norint gauti geresnės kokybės sprendinius, reikia daugiau kompiuterinių išteklių. Darbe detaliau nagrinėjami trys populiarūs euristiniai algoritmai: genetinis, modeliuoto atkaitinimo ir skruzdžių kolonijų. Visi šie algoritmai buvo pritaikyti keliaujančio prekeivio uždaviniui (angl. Traveling salesman problem) spręsti GRID skaičiavimo tinkle. Atlikti bandymai su 20 didelės apimties TSPLIB bibliotekos testinių pavyzdžių leidžia teigti, kad kompiuterinių išteklių problemą, sėkmingai galima išspręsti euristinius algoritmus vykdant GRID skaičiavimo tinkle. Gauti rezultatai rodo, kad euristinių algoritmų efektyvumas, juos vykdant GRID skaičiavimo tinkle yra labai aukštas. Daugelyje bandymų pavyko rasti optimalius sprendinius, o kitais atvejais rasti sprendiniai nedaug skyrėsi nuo optimalių. Darbo autorius euristinių algoritmų bandymams siūlo naudoti „DAG“ tipo GRID užduotis. Tokio tipo užduotys leidžia ta patį bandymą atlikti skirtinguose skaičiavimo klasteriuose tuo pačiu metu, tokiu būdu galima įvykdyti daug pakartotinų... [toliau žr. visą tekstą] / The main goal of this work is to implement and test heuristic algorithms for GRID computing network to solve NP-complete problems. The problems of NP-complete set are not solved in polynomial time. To solve such problems, researchers have to use heuristic algorithms. Heuristic algorithms always give result in polynomial time, but it doesn’t mean that result is optimal, also computing time grows together with problem scope, and in this case bigger computing recourses are needed. Three popular heuristic algorithms are included in this works: genetic, simulated annealing and ant colony. All of them were implemented to solve traveling salesman problem in GRID computing network. With mentioned heuristic algorithms 20 TSP instances of TSPLIB library were solved. Experiential results shows that efficiently of heuristic algorithms are high and with 12 tested instances optimal solution was found. Author of this work recommends to use “DAG” type GRID tasks. Such type tasks allows to execute algorithms in different clusters at same time, so in same time researcher can execute a lot of tests and final test will give best results.
| Identifer | oai:union.ndltd.org:LABT_ETD/oai:elaba.lt:LT-eLABa-0001:E.02~2009~D_20140701_175546-91600 |
| Date | 01 July 2014 |
| Creators | Venckus, Irmantas |
| Contributors | Žilinskas, Antanas, Vilnius University |
| Publisher | Lithuanian Academic Libraries Network (LABT), Vilnius University |
| Source Sets | Lithuanian ETD submission system |
| Language | Lithuanian |
| Detected Language | Unknown |
| Type | Master thesis |
| Format | application/pdf |
| Source | http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2009~D_20140701_175546-91600 |
| Rights | Unrestricted |
Page generated in 0.002 seconds