Genetic algorithm for beacon placement design
Saavalainen, Mikko (2020)
2020
Tietotekniikan DI-ohjelma - Master's Programme in Information Technology
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2020-12-18
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202012108703
https://urn.fi/URN:NBN:fi:tuni-202012108703
Tiivistelmä
The placement of navigational beacons to provide localisation is an active area of research with a long history. It presents problems for automated design due to the combinatorial expansion of the problem with increased complexity, as well as the requirement to factor in multiple aspects of design, such as localisation accuracy and hardware cost.
The main goal of this thesis is to present and evaluate the usage of genetic algorithms to automatically design beacon placements. Additionally, the well-seen metric, its usage in optimi-sation, and how well it compares to HDOP is presented.
Results showed the efficacy of genetic algorithms for solving this problem, with improvements over a hill-climbing algorithm, as well as a random generation algorithm. The well-seen metric that was used during optimisation provided a computationally lighter alternative to HDOP, while also providing a minimisation of HDOP during optimisation. Lähettimien sijoittaminen sijainnin määrittämistä varten on aktiivinen tutkimusalue jolla on pitkä historia. Näiden lähettimien automaattinen suunnittellu on ongelmallista kombinatorisesta kompleksisuudesta johtuen, joka etenkin tulee esille suunittelu ongelman laajentuessa. Lisäksi muiden asioidien huomiointi suunnittelussa, kuten lokalisaation tarkkuus ja laitteiston kustannukset, laajentavat ongelmaa.
Tämän diplomityön pääasiallinen tavoite on tutkia ja esittää geneettisten algoritmien käyttö lähettimien automaattiseen suunnitteluun. Lisäksi hyvin-nähty metriikka, sen hyödyntäminen optimoinnissa ja kuinka se vertaa HDOP metriikkaan, ovat tarkastelussa.
Tulokset esittivät geneettisten algoritmien sopivuuden ongelman ratkaisuun. Geneettisillä algoritmeilla saadut tulokset vertasivat hyvin muihin algoritmeihin, kuten mäen-nousuun ja satunnaiseen generointiin. Hyvin-nähty metriikka, jota käytettiin optimoinnissa, oli laskelmallisesti kevyempi ja aiheutti HDOP metriikan madaltumisen optimoinnin aikana.
The main goal of this thesis is to present and evaluate the usage of genetic algorithms to automatically design beacon placements. Additionally, the well-seen metric, its usage in optimi-sation, and how well it compares to HDOP is presented.
Results showed the efficacy of genetic algorithms for solving this problem, with improvements over a hill-climbing algorithm, as well as a random generation algorithm. The well-seen metric that was used during optimisation provided a computationally lighter alternative to HDOP, while also providing a minimisation of HDOP during optimisation.
Tämän diplomityön pääasiallinen tavoite on tutkia ja esittää geneettisten algoritmien käyttö lähettimien automaattiseen suunnitteluun. Lisäksi hyvin-nähty metriikka, sen hyödyntäminen optimoinnissa ja kuinka se vertaa HDOP metriikkaan, ovat tarkastelussa.
Tulokset esittivät geneettisten algoritmien sopivuuden ongelman ratkaisuun. Geneettisillä algoritmeilla saadut tulokset vertasivat hyvin muihin algoritmeihin, kuten mäen-nousuun ja satunnaiseen generointiin. Hyvin-nähty metriikka, jota käytettiin optimoinnissa, oli laskelmallisesti kevyempi ja aiheutti HDOP metriikan madaltumisen optimoinnin aikana.