|
|
Experiments with the Swarm Intelligence
Hula, Tomáš ; Zbořil, František (referee) ; Grulich, Lukáš (advisor)
This work deals with the issue of swarm intelligence as a subdiscipline of artificial intelligence. It describes biological background of the dilemma briefly and presents the principles of searching paths in ant colonies as well. There is also adduced combinatorial optimization and two selected tasks are defined in detail: Travelling Salesman Problem and Quadratic Assignment Problem. The main part of this work consists of description of swarm intelligence methods for solving mentioned problems and evaluation of experiments that were made on these methods. There were tested Ant System, Ant Colony System, Hybrid Ant System and Max-Min Ant System algorithm. Within the work there were also designed and tested my own method Genetic Ant System which enriches the basic Ant System i.a. with development of unit parameters based on genetical principles. The results of described methods were compared together with the ones of classical artificial intelligence within the frame of both solved problems.
|
|
|
Ant Colony Optimization for Solving Big Instances of TSP
Ramosová, Patrícia ; Jaroš, Jiří (referee) ; Bidlo, Michal (advisor)
Currently, many applications place emphasis on finding the optimal solution to a particular problem. However, it is typical for some tasks that their complexity increases exponentially depending on the size of the instance. A typical example of such a problem is the Traveling Salesman Problem (TSP). One class of methods that have proven to be very helpful in solving TSPs are ant algorithms. Nonetheless, they reached their limit - a high number of cities in the instance and became almost unusable due to time and memory requirements. This bachelor thesis aims to modify the ant algorithm and create a system capable of quickly and efficiently solve large-scale TSPs without significant loss in the quality of the solution found. Optimization will focus on reducing memory complexity and total execution time.
|
|
| |
|
|
Evolutionary algorithms for global optimization problem solving
Dragon, Ondřej ; Kozumplík, Jiří (referee) ; Mézl, Martin (advisor)
This work is devoded to evolutionary algorithms and solution of global optimization problems, mainly the traveling salesman problem. The traveling salesman problem is analyzed in detail as well as its methods of solution, such as: graph theory, heuristics and evolutionary algorithms. The main optimization method of this work is a Inver - over operator. In conclusion are implemented selected methods and performed testing and evaluation of the individual data sets.
|
|
| |
|
|
Ant colony optimization of antennas on EBG substrates
Wilder, Roman ; Lukeš, Zbyněk (referee) ; Horák, Jiří (advisor)
This diploma thesis deals with optimization of planar antennas on the Electromagnetic Bandgap (EBG) substrates by the help of Ant Colony Optimization (ACO). This method is based on the communications mechanisms of a real ant colony. Firstly, the working principle of the planar antennas and the theory of the Ant Colony Optimization are analyzed. Next, the description of the working principle of the Electromagnetic Bandgap and generally physical phenomena accompanying electromagnetic waves propagation in a periodic medium are given. In the second part of this thesis, the ACO was implemented into the VBA language, and was applied to two models of planar antennas. These models were created in the CST Microwave Studio. After an optimization of the antennas the results were evaluated, and the optimization of one of the antennas was compared to the optimization methods in CST Microwave Studio. Then, the standard substrate of the second model was replaced by the EBG substrate, and the results were confronted. Two types of EBG lattice were used. The design procedure of the square lattice was described, and the dispersion diagram was created in the CST Microwave Studio. In the final part of thesis, the verification of the results was carried out in Ansoft HFSS, and the results from both simulation programs were compared to each other.
|
|
|
Analysis of Various Approaches to Solving Optimization Tasks
Knoflíček, Jakub ; Samek, Jan (referee) ; Zbořil, František (advisor)
This paper deals with various approaches to solving optimization tasks. In prolog some examples from real life that show the application of optimization methods are given. Then term optimization task is defined and introducing of term fitness function which is common to all optimization methods follows. After that approaches by particle swarm optimization, ant colony optimization, simulated annealing, genetic algorithms and reinforcement learning are theoretically discussed. For testing we are using two discrete (multiple knapsack problem and set cover problem) and two continuous tasks (searching for global minimum of Ackley's and Rastrigin's function) which are presented in next chapter. Description of implementation details follows. For example description of solution representation or how current solutions are changed. Finally, results of measurements are presented. They show optimal settings for parameters of given optimization methods considering test tasks. In the end are given test tasks, which will be used for finding optimal settings of given approaches.
|
|
|
Travelling Salesman Problem
Řezníček, Jan ; Zbořil, František (referee) ; Zbořil, František (advisor)
The work focuses on implementing algorithms that solve the Traveling Salesman Problem. It also includes a user interface with a map for importing locations. The main algorithms that are part of the work are ACO and an algorithm that I have devised and implemented. ACO optimization improves results, such as setting initial pheromone levels using the nearest neighbor algorithm. My algorithm works on the principle of gradually improving the path.
|
|
|
Ant Colony Optimization: Implementace a testování biologicky inspirované optimalizační metody
Havlík, Michal
Havlík, M. Ant Colony Optimization: Implementation and testing of bio-inspired optimization method. Diploma thesis. Brno, 2015. This thesis deals with the implementation and testing of algorithm Ant Colony Optimization as a representative of the family of bio-inspired opti-mization methods. A given algorithm is described, analyzed and subsequently put into context with the problems which can be solved. Based on the collec-ted information is designed implementation that solves the Traveling sale-sman problem. Implementation contains graphical user interface to track the algorithm. Implementation is further optimized using parallel programming and other methods. Finally the implementation compared and summarized results.
|
|
|
Application of ACO to simple subsitution ciphers
Turek, Luboš ; Tůma, Jiří (advisor) ; Surynek, Pavel (referee)
Název práce: Použití ACO algoritmu na řešení jednoduché substituční šifry Autor: Luboš Turek Katedra (ústav): Katedra algebry Vedoucí bakalářské práce: doc. RNDr. Jiří Tůma, DrSc. e-mail vedoucího: jiri.tuma@mff.cuni.cz Abstrakt: V předložené práci studujeme kombinatorickou metaheuristiku Ant Colony Optimization a zkoumáme možné způsoby jejího použití k pro- lomení jednoduché substituční šifry. Součástí práce je návrh a implementace programu. Tento program je srovnán s genetickým algoritmem. Klíčová slova: jednoduchá substituční šifra, ant colony optimization, ACO, kryptologie, kryptografie Title: Application of ACO to simple subsitution ciphers Author: Luboš Turek Department: Department of Algebra Supervisor: doc. RNDr. Jiří Tůma, DrSc. Supervisor's e-mail address: jiri.tuma@mff.cuni.cz Abstract: In the present work we study combinatorial metaheuristic Ant Colony Optimization and we search for its application to the problem of cracking simple subtitution cipher. Functional implementation is a part of the thesis. The program is compared to genetic algorithm. Keywords: simple substitution cipher, ant colony optimization, ACO, cryp- tology, cryptography 6
|
guest ::
