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

Povzetek

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.

Ključne besede

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

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [J. Škornik]
UDK: 004.85:629(043.2)
COBISS: 30831363 Povezava se bo odprla v novem oknu
Št. ogledov: 981
Št. prenosov: 135
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Machine learning for combinatorial optimization for the vehicle routing problem
Sekundarni povzetek: 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.
Sekundarne ključne besede: combinatorial optimization;machine learning;vehicle routing problem;computer and information science;diploma thesis;
Vrsta dela (COBISS): Diplomsko delo/naloga
Študijski program: 1000468
Konec prepovedi (OpenAIRE): 1970-01-01
Komentar na gradivo: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani: 34 str.
ID: 12033207