crta
Hrvatska znanstvena Sekcija img
bibliografija
3 gif
 Home
 About the project
 FAQ
 Contact
4 gif
Browsing
Basic search
Advanced search
Statistical data
Other bibliographies
Similar projects
 Catalogues and databases

Bibliographic record number: 975246

Journal

Authors: Knezevic, Karlo; Picek, Stjepan; Mariot, Luca; Jakobovic, Domagoj; Leporati, Alberto
Title: The Design of (Almost) Disjunct Matrices by Evolutionary Algorithms
( The Design of (Almost) Disjunct Matrices by Evolutionary Algorithms )
Source: / Fagan, David ; Martín-Vide, Carlos ; O'Neill, Michael ; Vega-Rodríguez, Miguel A. (ed). - Dublin, Ireland : Springer International Publishing , 2018. 152-163 (ISBN: 978-3-030-04069-7).
ISSN: 0302-9743
Meeting: 7th International Conference on the Theory and Practice of Natural Computing
Location and date: Dublin, Irska, 12.-14.12.2018.
Keywords: Evolutionary computing Disjunct matrices Resolvable matrices Almost disjunct matrices Group testing Estimation of distribution algorithms Genetic algorithms Genetic programming
( Evolutionary computing Disjunct matrices Resolvable matrices Almost disjunct matrices Group testing Estimation of distribution algorithms Genetic algorithms Genetic programming )
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.
Type of meeting: Predavanje
Type of presentation in a journal: Full-text (1500 words and more)
Type of peer-review: International peer-review
Original language: eng
Category: Znanstveni
Research fields:
Computer science
Full paper text: 975246.submission.pdf (tekst priložen 12. Ožu. 2019. u 09:46 sati)
Contrib. to CROSBI by: Karlo Knežević (Karlo.Knezevic@fer.hr), 20. Pro. 2018. u 16:03 sati



Print version   za tiskati


upomoc
foot_4