Marco Sacchet
Design and development of a general purpose evolutionary algorithm fuzzer and optimizer.
Rel. Giovanni Squillero, Alberto Paolo Tonda. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2024
|
PDF (Tesi_di_laurea)
- Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives. Download (1MB) | Preview |
Abstract: |
The aim of this thesis is to develop a comprehensive set of components for an evolutionary tool intended to serve as a foundation for a fuzzer or optimizer, providing all the necessary tools to generate and evolve solutions to a problem presented by the user, by studying self-adaptation and developing a self-adaptive evolutionary algorithm. This algorithm differs from a non-self-adapting vanilla evolutionary algorithm for the ability to allow individuals to die of old age, the existence of an elitist subset of individuals with high fitness, the option to tweak the reward given to operators, and the ability to behave differently according to the current state of the evolution. The study also covered the auto-adaptation of the operator's selection based on previous results and sigma adaptation, following the works of Davis (1991) and De Jong (1975). The study on operator selection shows a clear advantage in using such a technique with multi-armed bandits algorithm such as Successive Elimination [Slivkins (2019)]. This algorithm, using the reward history of each operator, performs an adaptive exploration of the space of the possible operators. It greatly reduces the number of calls to inefficient operators that fail to generate valid offspring. The study on sigma adaptation focuses on how the algorithm is able to balance the different phases of exploration and exploitation by managing mutation's strength, introducing a user-defined temperature, and the notion of proximity related to a fitness function. The results show that implementing directly in the genetic operators the concept of mutation's strength, making them capable of acting differently based on the current state of evolution, leads to more efficient executions and more balance between exploration and exploitation phases. Overall, this thesis showcases the process of designing, implementing, and enhancing a self-adaptive evolutionary algorithm and the benefits of this algorithm compared to a non-self-adaptive one. |
---|---|
Relators: | Giovanni Squillero, Alberto Paolo Tonda |
Academic year: | 2023/24 |
Publication type: | Electronic |
Number of Pages: | 51 |
Subjects: | |
Corso di laurea: | Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering) |
Classe di laurea: | New organization > Master science > LM-32 - COMPUTER SYSTEMS ENGINEERING |
Aziende collaboratrici: | UNSPECIFIED |
URI: | http://webthesis.biblio.polito.it/id/eprint/31463 |
Modify record (reserved for operators) |