RT Journal Article
T1 Memetic collaborative approaches for finding balanced incomplete block designs
A1 Rodríguez Rueda, David
A1 Cotta-Porras, Carlos
A1 Fernández-Leiva, Antonio José
K1 Algoritmos evolutivos
AB The balanced incomplete block design (BIBD) problem is a difficult combinatorial problem with a large number of symmetries, which add complexity to its resolution. In this paper, we propose a dual (integer) problem representation that serves as an alternative to the classical binary formulation of the problem. We attack this problem incrementally: firstly, we propose basic algorithms (i.e. local search techniques and genetic algorithms) intended to work separately on the two different search spaces (i.e. binary and integer); secondly, we propose two hybrid schemes: an integrative approach (i.e. a memetic algorithm) and a collaborative model in which the previous methods work in parallel, occasionally exchanging information. Three distinct two-dimensional structures are proposed as communication topology among the algorithms involved in the collaborative model, as well as a number of migration and acceptance criteria for sending and receiving data. An empirical analysis comparing a large number of instances of our schemes (with algorithms possibly working on different search spaces and with/without symmetry breaking methods) shows that some of these algorithms can be considered the state of the art of the metaheuristic methods applied to finding BIBDs. Moreover, our cooperative proposal is a general scheme from which distinct algorithmic variants can be instantiated to handle symmetrical optimisation problems. For this reason, we have also analysed its key parameters, thereby providing general guidelines for the design of efficient/robust cooperative algorithms devised from our proposal.
PB Elsevier
YR 2020
FD 2020
LK https://hdl.handle.net/10630/35046
UL https://hdl.handle.net/10630/35046
LA eng
NO D. Rodríguez Rueda, C. Cotta, A.J. Fernández Leiva, Memetic collaborative approaches for finding balanced incomplete block designs, Computers & Operations Research 144:104804, 2020
NO Junta de Andalucía (project P10-TIC-6083, DNEMESIS – http://dnemesis.lcc.uma.es/wordpress/), Ministerio Español de Economía y Competitividad (projects TIN2014-56494-C4-1-P, UMA::EPHEMECH – https://ephemech.wordpress.com/ and TIN2017-85727-C4-1-P, UMA::DeepBio – http://deepbio.wordpress.com),
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 22 ene 2026