The Design of (Almost) Disjunct Matrices by Evolutionary Algorithms

Conference Paper (2018)
Author(s)

Karlo Knezevic (University of Zagreb)

Stjepan Picek (TU Delft - Cyber Security)

Luca Mariot (University of Milano-Bicocca)

Domagoj Jakobovic (University of Zagreb)

Alberto Leporati (University of Milano-Bicocca)

Research Group
Cyber Security
DOI related publication
https://doi.org/10.1007/978-3-030-04070-3_12
More Info
expand_more
Publication Year
2018
Language
English
Research Group
Cyber Security
Pages (from-to)
152-163
ISBN (print)
978-3-030-04069-7
ISBN (electronic)
978-3-030-04070-3

Abstract

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.

No files available

Metadata only record. There are no files for this record.