1. Constructing block designs and strongly regular graphs with prescribed automorphism group using genetic algorithms
- Author
-
Zrinski, Tin and Crnković, Dean
- Subjects
genetski algoritam ,Matematika ,automorphism group ,jako regularan graf ,grupa automorfizama ,orbitna matrica ,PRIRODNE ZNANOSTI. Matematika ,block design ,strongly regular graph ,genetic algorithm ,NATURAL SCIENCES. Mathematics ,udc:51(043.3) ,blokovni dizajn ,orbit matrix ,Mathematics - Abstract
Konstrukcija blokovnih dizajna s određenim dopustivim parametrima se često pokušava izvesti za određeni skup parametara uz pretpostavljanje nekih dodatnih ograničenja na strukturu dizajna kako bi pretraživanje bilo računalno izvedivo. Prirodno ograničenje je pretpostavka da određena grupa automorfizama djeluje na dizajn. Jedna od metoda konstruiranja blokovnih dizajna s pretpostavljenom grupom automorfizama je metoda koja koristi orbitne matrice, a sastoji se od dvaju koraka: konstrukcije orbitnih matrica za pretpostavljenu grupu automorfizma i konstrukcije blokovnih dizajna za orbitne matrice dobivene na ovaj način (ovaj korak se naziva indeksiranje orbitnih matrica). Indeksiranje orbitnih matrica obično se provodi metodom iscrpnog pretraživanja. Međutim, ponekad iscrpno pretraživanje nije izvedivo jer postoji previše slučajeva koje bi trebalo provjeriti. Slično, jako regularni grafovi s određenim dopustivim parametrima se mogu konstruirati korištenjem orbitnih matrica za pretpostavljenu grupu automorfizma. Genetski algoritam je metoda pretraživanja koja se koristi u računarstvu za pronalazak točnih ili približno točnih rješenja za probleme optimizacije i pretraživanja. Genetski algoritam oponaša prirodnu evoluciju, odnosno temelji se na optimizaciji populacije, podskupa cijelog prostora pretraživanja. Kao i u prirodi, populacija se sastoji od jedinki koje se mogu razmnožavati i nad kojima mogu djelovati određene mutacije te se na taj način stvaraju nove jedinke s boljim ili lošijim svojstvima od prethodnih. Cilj algoritma je usmjeriti populaciju ka stvaranju boljih jedinki što može rezultirati pronalaskom optimalnih rješenja zadanog problema. U ovoj doktorskoj disertaciji opisujemo korištenje genetskog algoritma u koraku indeksiranja orbitnih matrica za konstrukciju blokovnih dizajna i jako regularnih grafova s pretpostavljenom grupom automorfizama. Korištenjem ovog pristupa konstruirali smo nove blokovne dizajne, točnije nove Steinerove sustave s parametrima S(2,5,45) i nove simetrične dizajne s parametrima (71,15,3) te nove jako regularne grafove s parametrima (96,19,2,4) i (96,20,4,4). Construction of block designs with certain admissible parameters is often attempted for a particular set of parameters with the assumption of some additional constraints on the design structure in order to make the search computationally feasible. A natural constraint is the assumption that a given group of automorphisms acts on the design. One of the methods for constructing block designs with a prescribed automorphism group is the method that uses so called orbit matrices. It consists of two steps: construction of orbit matrices for the given automorphism group and construction of block designs for the orbit matrices obtained in this way (this step is called "indexing of orbit matrices"). Indexing is usually performed by exhaustive search. However, sometimes exhaustive search is not feasible because there are too many cases to check. Similarly, strongly regular graphs with certain admissible parameters can be constructed using orbit matrices for the prescribed automorphism group. Genetic algorithms are search methods used in computing whose objective is to find exact or approximate solutions to optimization and search problems. A genetic algorithm mimics natural evolution, that is, it is based on optimizing a population (a subset of the entire search space). As in nature, the population consists of individuals that can reproduce and that can be affected by certain mutations, thus creating new individuals with better or worse properties than the previous ones. The goal of the algorithm is to direct the population towards creating better individuals, which can result in finding optimal solutions to a given problem. In this doctoral dissertation, we describe the use of a genetic algorithm in the step of indexing of orbit matrices for the construction of block designs and strongly regular graphs with a prescribed automorphism group. Using this approach, we have constructed new block designs, namely new Steiner systems with parameters S(2,5,45), new symmetric designs with parameters (71,15,3) and new strongly regular graphs with parameters (96,19,2,4) and (96,20,4,4).
- Published
- 2022