Finding Minimal Hitting Sets Using Tabu Search

No Thumbnail Available

Files

URL

Journal Title

Journal ISSN

Volume Title

Sähkötekniikan korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2024-09-19

Department

Major/Subject

Informaatioteknologia

Mcode

ELEC3015

Degree programme

Sähkötekniikan kandidaattiohjelma

Language

en

Pages

31

Series

Abstract

This thesis researches the applying a Tabu Search algorithm to the problem of identifying minimal hitting sets in the projective plane PG(2, 11). This PG(2, 11) can be presented by 133x133 matrix. This matrix, in 2-dimensions, is a configuration of points and lines. Hitting sets, defined as a subsets of points that intersects every line in the projective plane matrix at least once, are important in various mathematical and theoretical applications. When writing this thesis, there is no research done yet that would research all the minimal hitting sets in the projective plane PG(2, 11). Also, no previous research has focused on applying heuristic algorithms like Tabu Search to this problem within finite projective planes. The primary goal is to investigate the characteristics of minimal hitting sets found in PG(2, 11). They are bounded in the theoretical framework provided by Bruen’s theorem ranging from 16 to 37 points. In the computational perspective it is very important to limit the search into the certain range, as this makes the search of the minimal hitting sets more efficient. The research demonstrates the effectiveness of the Tabu Search algorithm in efficiently navigating the complex search space, leveraging techniques such as cost function construction and neighborhood exploration to ensure the minimality of the hitting sets. The results of this thesis have significant implications for error-correction algo- rithms, such as LDPC (Low-Density Parity-Check), where minimal hitting sets can be applied to vital role in the optimization of these algorithms. This thesis provides not only a novel methodological framework and algorithm for the identification of the minimal hitting sets but also highlights its practical applications in improving error-correction strategies. By addressing a previously unexplored area of research, this work extends the understanding of hitting sets in finite projective planes and underscores their broader relevance in fields requiring robust error-correction solutions. The algorithm created in this thesis is also possible to apply into a different size projective planes than PG(2,11). It will work in other 2-dimentional planes as well, thus making future research easier.

Tässä työssä tutkitaan Tabuhaku-algoritmin soveltamista minimaalisten peittävien joukkojen tunnistamiseen(eng. minimal hitting set) projektiivisen geometrian (eng. projective geometry) projektiivisessa tasossa (eng. projective plane), jota merkitään PG(2, 11). Tämä PG(2, 11) voidaan esittää 133𝑥133 matriisina, joka 2-ulotteisessa tasossa on pisteiden ja janojen erilaisia konfiguraatioita. Peittävät joukot määritellään pistejoukkona, jotka leikkaavat projektiivisen tason jokaista janaa vähintään kerran, ja ne ovat keskeisiä useissa sovelluksissa, esimerkiksi virheenkorjauskoodeissa. Tämän tutkielman kirjoitushetkellä ei ole vielä tehty tutkimusta, joka käsittelisi ilman rajoituksia, kaikkia peittäviä joukkoja PG(2, 11) tasossa. Aikaisemmat tutkimukset ovat joko keskittyneet pienempiin tasoihin, tai sisältäneet suuria rajoituksia minimaalisille peittäville joukoille. Lisäksi aiemmat tutkimukset eivät ole käyttäneet tabuhakua lähestymistapana, joten tämä lähestymistapa on myös uusi ja antaa merkittävän panoksen kyseiselle tutkimusalueelle. Tutkielman ensisijainen tavoite on tutkia PG(2,11) tason minimaalisten peittävien joukkojen ominaisuuksia ja tunnistaa ne mahdollisimman tehokkaasti. Tätä varten tutkielmassa on kehitetty algoritmi python ohjelmointikielellä, jolla laskenta suoritetaan. Apuna käytetään Bruenin teoreemasta saatua määritelmää, joka rajaa tämän kokoisessa projektiivisessa geometriassa minimaaliset peittävät joukot välille [16,36], mikä tarjoaa perustan laskentaprosessille. Laskentatehon näkökulmasta on erityisen tärkeää rajoittaa haku tietylle pistevälille, mikä tekee minimaalisten peittävien joukkojen laskemisesta tehokkaampaa. Tutkielma osoittaa tabuhaun tehokkuuden navigoida monimutkaisessa hakuavaruudessa, tämä saavutettiin käyttämällä erilaisia tekniikoita, kuten kustannusfunktiota ja naapuruston hyödyntämistä. Algoritmin kyky paeta paikallisista epäkelvollisista ratkaisuista korostaa sen tehokkuutta verrattuna heuristisiin lähestymistapoihin. Saadut tulokset ovat erittäin merkittäviä virheenkorjauskoodien optimoinnissa, jossa minimaalisia peittäviä joukkoja voidaan hyödyntää parantamalla näiden algoritmien suorituskykyä. Tämä työ tarjoaa paitsi uuden kehyksen ja algoritmin minimaalisten peittävien joukkojen tunnistamiseen, sekä niiden potentiaalia käytännönsovelluksissa. Lisäksi, tässä tutkielmassa kehitettyä algoritmia voidaan soveltaa muihin erikokoisiin projektiivisiin tasoihin. Algoritmi toimii myös muilla 2-ulotteisilla tasoilla, mikä mahdollistaa tulevien tutkimusten helpomman toteuttamisen, etenkin jos niissä halutaan hyödyntää tabuhaku algoritmia. Tämä laajentaa suuresti algortimin käyttökelpoisuutta ja tekee siitä tärkeän työkalun sekä nykyisissä, että tulevissa tutkimuksissa. Tässä tutkielmassa keskityttiin PG(2, 11) tasoon, ja muita tasoja ei tutkittu, mutta kehitetty algoritmi kuitenkin mahdollistaa olemassa olevalla logiikalla muiden 2-ulotteisten tasojen tutkimisen.

Description

Supervisor

Aalto, Samuli

Thesis advisor

Östergård, Patric

Keywords

hitting sets, blocking sets, projective geometry, projective plane, tabu search

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202409246474

Collections

[kand] Sähkötekniikan korkeakoulu / ELEC