Određivanje topološkog svojstva grafa primjenom strojnog učenja i konsenzusa

diplomski rad

• Naslov (engleski): Determining the topological property of a graph using machine learning and consensus
• Autor: Matea Španić
• Mentor: Stjepan Bogdan (mentor)
• Član povjerenstva: Zdenko Kovačić (član povjerenstva)
• Član povjerenstva: Stjepan Bogdan (predsjednik povjerenstva)
• Član povjerenstva: Goran Vasiljević (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2021-07-09, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Elektrotehnika

Sažetak

U ovome se radu obrađuje problem decentralizirnog određivanja minimalnog nezavisnog
dominantnog seta grafa. Nakon uvoda o višeagentnim sustavima i matematičke
podloge, minimalni nezavisni dominantni set definiran je kao topološko svojstvo grafa
povezanosti višeagentnog sustava. Nadalje, konsenzus algoritam je predstavljen kao
alat koji omogućuje da se svi agenti dogovore oko određene odluke. Da bi se ta odluka
donijela, korišteno je potporno učenje. Prvo je upotrijebljen centralizirani algoritam
Q-učenja. Nakon što su dobiveni pozitivni rezultati, decentralizirano Q-učenje je istraženo
i implementirano. Različita poboljšanja decentraliziranog algoritma
testirana su na nekoliko tipičnih klasa grafova. Naposljetku, rezultati različitih metoda
su uspoređeni i analizirani.

Sažetak (engleski)

This thesis is concerned with the problem of decentralized determining the minimal independent dominating set of a graph. After giving the introduction about the multi-agent systems and mathematical preliminaries, the minimum independent dominating set was defined as a topological property of a connectivity graph in a multi-agent system. Next, consensus algorithm was presented as a tool which enables that all of the agents agree on a certain decision. To make that decision, reinforcement learning is used. First, a centralized version of the Q-learning was applied. After receiving positive results, decentralized Q-learning algorithm was investigated and implemented. Furthermore, different improvements to decentralized algorithm were tested on several typical graph classes. Finally, the results of the different methods are compared and analyzed.

• Ključne riječi: minimalni nezavisni dominantni set; višeagentni sustav; Q-učenje; potporno učenje; konsenzus; decentralizacija
• Ključne riječi (engleski): minimal independent dominating set; multi-agent system; Q-learning; reinforcement learning; consensus; decentralization
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:606214
• Studijski program: Naziv: Elektrotehnika i informacijska tehnologija; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka elektrotehnike i informacijske tehnologije (mag. ing. el. techn. inf.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 13:58:31