The Design of (Almost) Disjunct Matrices by Evolutionary Algorithms (CROSBI ID 670926)
Prilog sa skupa u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Knezevic, Karlo ; Picek, Stjepan ; Mariot, Luca ; Jakobovic, Domagoj ; Leporati, Alberto
engleski
The Design of (Almost) Disjunct Matrices by Evolutionary Algorithms
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.
Evolutionary computing Disjunct matrices Resolvable matrices Almost disjunct matrices Group testing Estimation of distribution algorithms Genetic algorithms Genetic programming
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
152-163.
2018.
nije evidentirano
objavljeno
10.1007/978-3-030-04070-3_12
Podaci o matičnoj publikaciji
Lecture notes in computer science
Fagan, David ; Martín-Vide, Carlos ; O'Neill, Michael ; Vega-Rodríguez, Miguel A.
Dublin: Springer
978-3-030-04069-7
0302-9743
Podaci o skupu
7th International Conference on the Theory and Practice of Natural Computing
predavanje
12.12.2018-14.12.2018
Dublin, Irska