Original title: Kvantově inspirované optimalizační algoritmy
Translated title: Quantum-Inspired Optimisation Algorithms
Authors: Kosík, Dominik ; Sekanina, Lukáš (referee) ; Bidlo, Michal (advisor)
Document type: Master’s theses
Year: 2022
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato práce se zabývá implementací zvoleného kvantově inspirovaného optimalizačního algoritmu a jeho rozšířeními, které budou porovnávány v závěru práce. Jako optimalizační algoritmus byl zvolen algoritmus pro simulované kvantové žíhání. V první části se nachází základní popis běžných optimalizačních metod použitých v této práci, teoretické základy fyziky, ze které vychází inspirace pro kvantově  inspirované optimalizační algoritmy, a popis simulovaného kvantového žíhání. V druhé části práce je implementace algoritmů pro námi zvolené úlohy, kterými jsou problém obchodního cestujícího, hledání pravidel pro celulární automaty a problém MAX-SAT. Poslední část obsahuje modifikace simulovaného kvantového žíhání, srovnání se základní variantou a s běžnými optimalizačními algoritmy následované vyhodnocením tohoto srovnání. The focus of this work is an implementation of the chosen quantum-inspired optimisation algorithm and its modifications, which will be compared at the end of the work. As the optimisation algorithm was chosen simulated quantum annealing algorithm. The first part of the work will lay the theoretical groundwork of standard optimisation algorithms used in this work, physics from which the inspiration for the simulated quantum annealing originates, and a description of the chosen algorithm. The second part will focus on the implementation of the algorithms on the selected problems. The selected problems are travelling salesman problem, searching rules for cellular automaton and MAX-SAT problem. The last part will contain the proposed modifications of the simulated quantum annealing, a comparison of the basic variant and standard optimisations algorithms, and an evaluation of the results.
Keywords: Cellular Automaton; Clonal Selection; Evolution Strategy; Hill Climbing; Ising Spin Glass Model; MAX-SAT; Path Integral Monte Carlo; Simulated Annealing; Simulated Quantum Annealing; Traveling Salesman Problem; celulární automat; evoluční strategie; horolezecký algoritmus; Isingův model spinových skel; klonální selekce; MAX-SAT; Monte Carlo založené na křivkovém integrálu; problém obchodního cestujícího; simulované kvantové žíhání; simulované žíhání

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/207459

Permalink: http://www.nusl.cz/ntk/nusl-505000


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses