prikaz prve stranice dokumenta Physics-inspired dynamical systems for optimization (Dinamički sustavi za optimizaciju inspirirani fizikom)
  Download
PDF 1015.72 KB
master's thesis
Physics-inspired dynamical systems for optimization (Dinamički sustavi za optimizaciju inspirirani fizikom)
Zagreb: University of Zagreb, Faculty of Science, 2023. urn:nbn:hr:217:074762
Jovanović, Luka
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Jovanović, L. (2023). Physics-inspired dynamical systems for optimization (Dinamički sustavi za optimizaciju inspirirani fizikom) (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:074762

Jovanović, Luka. "Physics-inspired dynamical systems for optimization (Dinamički sustavi za optimizaciju inspirirani fizikom)." Master's thesis, University of Zagreb, Faculty of Science, 2023. https://urn.nsk.hr/urn:nbn:hr:217:074762

Jovanović, Luka. "Physics-inspired dynamical systems for optimization (Dinamički sustavi za optimizaciju inspirirani fizikom)." Master's thesis, University of Zagreb, Faculty of Science, 2023. https://urn.nsk.hr/urn:nbn:hr:217:074762

Jovanović, L. (2023). 'Physics-inspired dynamical systems for optimization (Dinamički sustavi za optimizaciju inspirirani fizikom)', Master's thesis, University of Zagreb, Faculty of Science, accessed 22 November 2024, https://urn.nsk.hr/urn:nbn:hr:217:074762

Jovanović L. Physics-inspired dynamical systems for optimization (Dinamički sustavi za optimizaciju inspirirani fizikom) [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2023 [cited 2024 November 22] Available at: https://urn.nsk.hr/urn:nbn:hr:217:074762

L. Jovanović, "Physics-inspired dynamical systems for optimization (Dinamički sustavi za optimizaciju inspirirani fizikom)", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2023. Available at: https://urn.nsk.hr/urn:nbn:hr:217:074762

Metadata
TitlePhysics-inspired dynamical systems for optimization (Dinamički sustavi za optimizaciju inspirirani fizikom)
Title (croatian)Dinamički sustavi za optimizaciju inspirirani fizikom
AuthorLuka Jovanović
MentorIlja Gogić (mentor)
Committee memberIlja Gogić (predsjednik povjerenstva)
Committee memberNikola Sandrić (član povjerenstva)
Committee memberMaja Resman (član povjerenstva)
Committee memberZvonko Iljazović (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2023-12-29, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Physics
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:074762
Study programmeTitle: Theoretical Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2024-02-13 10:02:02