Physics-inspired dynamical systems for optimization (Dinamički sustavi za optimizaciju inspirirani fizikom)

diplomski rad

• Naslov (hrvatski): Dinamički sustavi za optimizaciju inspirirani fizikom
• Autor: Luka Jovanović
• Mentor: Ilja Gogić (mentor)
• Član povjerenstva: Ilja Gogić (predsjednik povjerenstva)
• Član povjerenstva: Nikola Sandrić (član povjerenstva)
• Član povjerenstva: Maja Resman (član povjerenstva)
• Član povjerenstva: Zvonko Iljazović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2023-12-29, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Fizika

Sažetak

Ovaj diplomski rad izlaže, analizira te naposljetku predlaže unaprjeđenja dinamičkih sustava inspiriranih fizikom – novu vrstu heurističkih algoritama koji aproksimativno rješavaju NP-teške kombinatorne probleme. Diplomski rad započinje sažetim uvodom u NP-teške kombinatorne probleme, s posebnim naglaskom na problem neograničene binarne optimizacije kvadratnog funkcionala (eng. Quadratic Unconstrained Binary Optimization – QUBO) te MAX-CUT problema. Zatim se izlažu temeljni rezultati teorije dinamičkih sustava i ostalih matematičkih koncepata koji će se koristiti u ostatku rada kako bi se analizirali sustavi koji slijede. Glavni dio ovog rada su dinamički sustavi inspirirani fizikom koji rješavaju kombinatorne probleme. Numeričke simulacije ovih dinamičkih sustava predstavljaju heurističke algoritme za aproksimativno rješavanje NP-teških problema, uključujući QUBO i MAXCUT. Algoritmi koji su obradeni u ovom radu su Coherent Ising Machine (CIM), Simulated Bifurcation (SB), Simulated Coherent Ising Machine (SimCIM) i Ballistic Simulated Bifurcation (bSB). Analiziran je mehanizam ovih algoritama te je provedeno testirananje njihovih performansi na skupu podataka GSet. Na kraju rada predloženo je nekoliko tehnika koje unaprjeduju performanse navedenih algoritama.

Sažetak (engleski)

This thesis presents, analyzes, and finally proposes some improvements to physics-inspired dynamical systems – a novel paradigm of heuristic algorithms used for approximately solving NP-hard combinatorial optimization problems. The thesis begins with a brief introduction to NP-hard combinatorial problems, with a particular emphasis on the quadratic unconstrained binary optimization problem (QUBO) and the MAX-CUT problem. Then, a brief overview is provided for the theory of dynamical systems and other mathematical concepts which are important for analyzing the following systems. At the core of this master’s thesis are physics-inspired dynamical systems for solving combinatorial optimization problems. Numerical simulations of these dynamical systems provide heuristic algorithms for approximately solving some NP-hard problems, including the QUBO and the MAX-CUT problem. The algorithms that are covered in this thesis are namely the Coherent Ising Machine (CIM), Simulated Bifurcation (SB), Simulated Coherent Ising Machine (SimCIM), and Ballistic Simulated Bifurcation (bSB). The mechanism of these heuristic algorithms is analyzed, and they are further benchmarked on the GSet dataset. Finally, a few new techniques are proposed for improving the performance of these algorithms.

• Ključne riječi: heuristički algoritami; NP-teški kombinatorni problemi; kvadratni funkcional; MAX-CUT problem; QUBO
• Ključne riječi (engleski): heuristic algorithms; NP-hard combinatorial optimization problems; QUBO; MAX-CUT problem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:074762
• Studijski program: Naziv: Teorijska matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar matematike (univ. mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-02-13 10:02:02