Spelling suggestions: "subject:"euristiche"" "subject:"euristique""
1 |
Euristiniai algoritmai NP-pilniems uždaviniams spręsti ir jų realizacija GRIDui / Heuristic algorithms for np-complete problems and their realization for gridVenckus, Irmantas 01 July 2014 (has links)
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.
|
2 |
Iteratyvioji tabu paieška ir jos modifikacijos komivojažieriaus uždaviniui / Iterated tabu search and its modifications for the travelling salesman problemEimontienė, Ieva 16 August 2007 (has links)
Šiame darbe nagrinėjamas patobulintas tabu paieškos metodas, žinomas kaip iteratyvioji tabu paieška (ITP). Pasiūlytos kai kurios ITP metodo modifikacijos, besiremiančios tam tikromis sprendinių mutavimo (pertvarkymo) procedūromis (inversijos, įterpimai ir kt.), kurios įgalina pagerinti gaunamų sprendinių kokybę. Atlikti išsamūs sudaryto ITP algoritmo ir kitų pasiūlytų modifikacijų eksperimentiniai tyrimai, panaudojant testinius KU pavyzdžius iš KU testinių pavyzdžių bibliotekos TSPLIB. Gauti rezultatai patvirtina pasiūlytų modifikacijų pranašumą kitų ITP variantų atžvilgiu. / In this work, one of the heuristic algorithm – the iterated tabu search and its modifications are discussed. The work is organized as follows. Firstly, some basic definitions and preliminaries are given. Then, the iterated tabu search algoritm and its variants based on special type mutations are considered in more details. The ITS algorithms modifications were tested on the TSP instances from the TSP library TSPLIB. The results of this tests (experiments) are presented as well. The work is completed with the conclusions.
|
3 |
Heuristic Algorithms for Nurse Rostering Problem / Darbų grafikų sveikatos priežiūros įstaigose optimizavimasLiogys, Mindaugas 30 September 2013 (has links)
In the dissertation the nurse rostering problem is investigated. The formulation of the problem is based on real-world data of one of the largest healthcare centers in Lithuania. Most recent publications that tackle the nurse rostering problem and the methods for solving the nurse rostering problem are reviewed, the mathematical formulation of the single objective and the multi-objective nurse rostering problem is presented, the requirements for the roster are described and a new method for solving the single objective and the multi-objective nurse rostering problem is proposed in this dissertation. / Disertacijoje nagrinėjamas sveikatos priežiūros įstaigos darbuotojų darbų grafikų optimizavimo uždavinys, kuris formuluojamas ir sprendžiamas, remiantis vienos didžiausių Lietuvos sveikatos priežiūros įstaigų, realiais duomenimis. Disertacijoje apžvelgiami darbų grafikų optimizavimo uždaviniai bei jų sprendimo metodai. Pateikiama nagrinėjamo darbų grafikų vienakriterio ir daugiakriterio optimizavimo uždavinių matematinės formuluotės. Aprašomos sąlygos, kurias turi tenkinti sudaromasis darbų grafikas. Nagrinėjami metodai, tiek vienakriteriams, tiek daugiakriteriams darbų grafikų optimizavimo uždaviniams spręsti. Pasiūlytas naujas metodas, kuris yra efektyvesnis nei kiti nagrinėti metodai sprendžiant disertacijoje suformuluotą uždavinį.
|
Page generated in 0.0624 seconds