Nalazite se na CroRIS probnoj okolini. Ovdje evidentirani podaci neće biti pohranjeni u Informacijskom sustavu znanosti RH. Ako je ovo greška, CroRIS produkcijskoj okolini moguće je pristupi putem poveznice www.croris.hr
izvor podataka: crosbi !

The Design of (Almost) Disjunct Matrices by Evolutionary Algorithms (CROSBI ID 670926)

Prilog sa skupa u časopisu | izvorni znanstveni rad | međunarodna recenzija

Knezevic, Karlo ; Picek, Stjepan ; Mariot, Luca ; Jakobovic, Domagoj ; Leporati, Alberto The Design of (Almost) Disjunct Matrices by Evolutionary Algorithms // Lecture notes in computer science / Fagan, David ; Martín-Vide, Carlos ; O'Neill, Michael et al. (ur.). 2018. str. 152-163 doi: 10.1007/978-3-030-04070-3_12

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

Povezanost rada

Računarstvo

Poveznice