Details

Optimizacija preiskovanja grafov z vložitvami grafov
ID CIGLARIČ, TIMOTEJ (Author), ID Robnik Šikonja, Marko (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (433,35 KB)
MD5: 4CD52369EA54C4E2CB91AA8A005066CE

Abstract
Problem usmerjanja vozil s kapaciteto je NP-poln kombinatorični problem. Poleg njegove uporabnosti za dostavne službe se lahko nanj učinkovito preslika tudi veliko drugih problemov. Za reševanje problema uporabim rekurenčno nevronsko mrežo GRU z mehanizmom pozornosti. Po fazi učenja, ki traja toliko časa kot uporaba stohastičnih optimizacijskih algoritmov na več tisoč primerih, dobimo na majhnih grafih primerljivo dobre rezultate, na večjih grafih pa se zaradi povečevanja kompleksnosti problema nevronski model ne uči več dovolj hitro in je slabši. Med vložitvami grafov, ki sem jih preizkusil, dajeta najboljše rezultate node2vec in GraRep.

Language:Slovenian
Keywords:nevronska mreža, graf, kombinatorična optimizacija, problem usmerjanja vozil, vložitve grafov
Work type:Bachelor thesis/paper
Typology:2.11 - Undergraduate Thesis
Organization:FRI - Faculty of Computer and Information Science
Year:2021
PID:20.500.12556/RUL-130322 This link opens in a new window
COBISS.SI-ID:77579779 This link opens in a new window
Publication date in RUL:13.09.2021
Views:1615
Downloads:114
Metadata:XML DC-XML DC-RDF
:
CIGLARIČ, TIMOTEJ, 2021, Optimizacija preiskovanja grafov z vložitvami grafov [online]. Bachelor’s thesis. [Accessed 18 March 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=130322
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:Graph search optimization using graph embeddings
Abstract:
The capacitated vehicle routing problem is an NP-complete combinatorial problem. In addition to its usefulness for delivery services, many other problems can be efficiently mapped to it. To solve the problem, I use the GRU recurrent neural network with the attention mechanism. After a learning phase that lasts as long as using stochastic optimization algorithms on thousands of cases, we get comparatively good results on small graphs. On larger graphs the neural models do not learn fast enough and produce worse results due to an increasing problem complexity. Among the tested graph embedding methods, node2vec and GraRep give the best results.

Keywords:neural net, graph, combinatorial optimization, vehicle routing problem, graph embeddings

Similar documents

Similar works from RUL:
  1. Health care of patient with Buruli ulcer
  2. Nurse's psychological support to a child with chronic disease
  3. Primary immunodeficiency diseases in child
  4. ǂThe ǂholistic approach of a nurse to a woman with chronic pelvic pain
  5. Relieve chronic fatigue in cancer patients
Similar works from other Slovenian collections:
  1. Zr/Cu-TiO[sub]2 catalysts for photocatalytic water treatment
  2. Doped rutile TiO2 mechanism for changing photocatalytic activity
  3. Pristine and ruthenium-doped TiO [sub] 2 nanoclusters for nitrogen reduction reaction
  4. Brookite vs. rutile vs. anatase
  5. Highly active photocatalytic coatings prepared by a low-temperature method

Back