This paper proposes a new method for the design and analysis of multi-objective unconstrained binary quadratic programming (mUBQP) instances, commonly used for testing discrete multi-objective evolutionary algorithms (MOEAs). These instances are usually generated considering the sparsity of the matrices and the correlation between objectives but randomly selecting the values for the matrix cells. Our hypothesis is that going beyond the use of objective correlations by considering different types of variables interactions in the generation of the instances can help to obtain more diverse problem benchmarks, comprising harder instances. We propose a parametric approach in which small building blocks of deceptive functions are planted into the matrices that define the mUBQP. The algorithm for creating the new instances is presented, and the difficulty of the functions is tested using variants of a decomposition-based MOEA. Our experimental results confirm that the instances generated by planting deceptive blocks require more function evaluations to be solved than instances generated using other methods.
['Murilo Zangari', 'Roberto Santana', 'Alexander Mendiburu', 'Aurora Pozo']
On the Design of Hard mUBQP Instances