Napredna pretraga

Pregled bibliografske jedinice broj: 975246

The Design of (Almost) Disjunct Matrices by Evolutionary Algorithms


Knezevic, Karlo; Picek, Stjepan; Mariot, Luca; Jakobovic, Domagoj; Leporati, Alberto
The Design of (Almost) Disjunct Matrices by Evolutionary Algorithms // 7th International Conference on the Theory and Practice of Natural Computing / Fagan, David ; Martín-Vide, Carlos ; O'Neill, Michael ; Vega-Rodríguez, Miguel A. (ur.).
Dublin, Ireland: Springer International Publishing, 2018. str. 152-163 doi:10.1007/978-3-030-04070-3_12 (predavanje, međunarodna recenzija, cjeloviti rad (in extenso), znanstveni)


Naslov
The Design of (Almost) Disjunct Matrices by Evolutionary Algorithms

Autori
Knezevic, Karlo ; Picek, Stjepan ; Mariot, Luca ; Jakobovic, Domagoj ; Leporati, Alberto

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

ISBN
978-3-030-04069-7

Skup
7th International Conference on the Theory and Practice of Natural Computing

Mjesto i datum
Dublin, Irska, 12.-14.12.2018

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
Evolutionary computing Disjunct matrices Resolvable matrices Almost disjunct matrices Group testing Estimation of distribution algorithms Genetic algorithms Genetic programming

Sažetak
Disjunct Matrices (DM) are a particular kind of binary matrices which have been especially applied to solve the Non-Adaptive Group Testing (NAGT) problem, where the task is to detect any configuration of t defectives out of a population of N items. Traditionally, the methods used to construct DM leverage on error- correcting codes and other related algebraic techniques. Here, we investigate the use of Evolutionary Algorithms to design DM and two of their generalizations, namely Resolvable Matrices (RM) and Almost Disjunct Matrices (ADM). After discussing the basic encoding used to represent the candidate solutions of our optimization problems, we define three fitness functions, each measuring the deviation of a generic binary matrix from being respectively a DM, an RM or an ADM. Next, we employ Estimation of Distribution Algorithms (EDA), Genetic Algorithms (GA), and Genetic Programming (GP) to optimize these fitness functions. The results show that GP achieves the best performances among the three heuristics, converging to an optimal solution on a wider range of problem instances. Although these results do not match those obtained by other state-of-the-art methods in the literature, we argue that our heuristic approach can generate solutions that are not expressible by currently known algebraic techniques, and sketch some possible ideas to further improve its performance.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo



POVEZANOST RADA


Ustanove
Fakultet elektrotehnike i računarstva, Zagreb

Citati