diplomsko delo
Jakob Škornik (Author), Marko Robnik Šikonja (Mentor)

Abstract

Delo predstavlja poskus kombinatorične optimizacije s pomočjo strojnega učenja. Kombinatorična optimizacija zajema množico problemov, kjer iščemo najboljšo rešitev iz končne množice možnih rešitev. Izbrali smo problem usmerjanja vozil. S strojnim učenjem iščemo dober približek iskane funkcije. Na začetku definiramo problem usmerjanja vozil in predstavimo metode za njegovo reševanje. Glavna tema dela je reševanje problema usmerjanja vozil s strojnim učenjem. Uporabimo variacijski samokodirnik, ki z uporabo vzorčenja grafa ustvari vektorsko vložitev grafa. V dekodirniku uporabimo naučeno predstavitev za iskanje rešitve problema. S samokodirnikom uspešno rešimo problem na grafih z manj kot 100 vozlišči. Posebej uspešni so samokodirniki na gostih grafih.

Keywords

kombinatorična optimizacija;strojno učenje;problem usmerjanja vozil;računalništvo in informatika;univerzitetni študij;diplomske naloge;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [J. Škornik]
UDC: 004.85:629(043.2)
COBISS: 30831363 Link will open in a new window
Views: 981
Downloads: 135
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Machine learning for combinatorial optimization for the vehicle routing problem
Secondary abstract: This paper presents an attempt of combinatorial optimization using machine learning. Combinatorial optimization encapsulates a set of problems, where the best solution is sought in a finite set of possible solutions. We work on the vehicle routing problem. Machine learning aims to find an approximation of a desired function. In the work we first define the vehicle routing problem and established methods of solving it. The aim of this paper, is a solution to the vehicle routing problem using machine learning. We used a variational autoencoder, that makes use of structured sampling and constructs a vector embedding of the input graph. This representation is used in the decoder to find the solution to the vehicle routing problem. We successfully solve the problem on instances of size up to 100 nodes. Autoencoders were especially successful on dense graphs.
Secondary keywords: combinatorial optimization;machine learning;vehicle routing problem;computer and information science;diploma thesis;
Type (COBISS): Bachelor thesis/paper
Study programme: 1000468
Embargo end date (OpenAIRE): 1970-01-01
Thesis comment: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages: 34 str.
ID: 12033207