Publications | Alejandro Marrero

2024

GECCO
Learning Descriptors for Novelty-Search Based Instance Generation via Meta-evolution

Alejandro Marrero, Eduardo Segredo, Coromoto León, and 1 more author

In Proceedings of the Genetic and Evolutionary Computation Conference, Melbourne, VIC, Australia, 2024

Abs Bib

The ability to generate example instances from a domain is important in order to benchmark algorithms and to generate data that covers an instance-space in order to train machine-learning models for algorithm selection. Quality-Diversity (QD) algorithms have recently been shown to be effective in generating diverse and discriminatory instances with respect to a portfolio of solvers in various combinatorial optimisation domains. However these methods all rely on defining a descriptor which defines the space in which the algorithm searches for diversity: this is usually done manually defining a vector of features relevant to the domain. As this is a limiting factor in the use of QD methods, we propose a meta-QD algorithm which uses an evolutionary algorithm to search for a nonlinear 2D projection of an original feature-space such that applying novelty-search method in this space to generate instances improves the coverage of the instance-space. We demonstrate the effectiveness of the approach by generating instances from the Knapsack domain, showing the meta-QD approach both generates instances in regions of an instance-space not covered by other methods, and also produces significantly more instances.
@inproceedings{10.1145/3638529.3654028, author = {Marrero, Alejandro and Segredo, Eduardo and Le\'{o}n, Coromoto and Hart, Emma}, title = {Learning Descriptors for Novelty-Search Based Instance Generation via Meta-evolution}, year = {2024}, isbn = {9798400704949}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3638529.3654028}, doi = {10.1145/3638529.3654028}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference}, pages = {206–213}, numpages = {8}, keywords = {instance generation, instance-space analysis, knapsack problem, novelty search, evolutionary computation, neural-network}, location = {Melbourne, VIC, Australia}, series = {GECCO '24}, }
ECJ
Synthesising Diverse and Discriminatory Sets of Instances Using Novelty Search in Combinatorial Domains

Alejandro Marrero, Eduardo Segredo, Coromoto León, and 1 more author

Evolutionary Computation, Aug 2024

Abs Bib

Gathering sufficient instance data to either train algorithm-selection models or understand algorithm footprints within an instance space can be challenging. We propose an approach to generating synthetic instances that are tailored to perform well with respect to a target algorithm belonging to a predefined portfolio but are also diverse with respect to their features. Our approach uses a novelty search algorithm with a linearly weighted fitness function that balances novelty and performance to generate a large set of diverse and discriminatory instances in a single run of the algorithm. We consider two definitions of novelty: (1) with respect to discriminatory performance within a portfolio of solvers; (2) with respect to the features of the evolved instances. We evaluate the proposed method with respect to its ability to generate diverse and discriminatory instances in two domains (knapsack and bin-packing), comparing to another well-known quality diversity method, Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) and an evolutionary algorithm that only evolves for discriminatory behaviour. The results demonstrate that the novelty search method outperforms its competitors in terms of coverage of the space and its ability to generate instances that are diverse regarding the relative size of the “performance gap” between the target solver and the remaining solvers in the portfolio. Moreover, for the Knapsack domain, we also show that we are able to generate novel instances in regions of an instance space not covered by existing benchmarks using a portfolio of state-of-the-art solvers. Finally, we demonstrate that the method is robust to different portfolios of solvers (stochastic approaches, deterministic heuristics, and state-of-the-art methods), thereby providing further evidence of its generality.
@article{10.1162/evco_a_00350, author = {Marrero, Alejandro and Segredo, Eduardo and León, Coromoto and Hart, Emma}, title = {{Synthesising Diverse and Discriminatory Sets of Instances Using Novelty Search in Combinatorial Domains}}, journal = {Evolutionary Computation}, pages = {1-36}, year = {2024}, month = aug, issn = {1063-6560}, doi = {10.1162/evco_a_00350}, url = {https://doi.org/10.1162/evco\_a\_00350}, eprint = {https://direct.mit.edu/evco/article-pdf/doi/10.1162/evco\_a\_00350/2464257/evco\_a\_00350.pdf}, }
ULL
Evolutionary Computation Methods for Instance Generation in Optimisation Domains

Alejandro Marrero

Feb 2024

Abs Bib

The present thesis has been partially supported by Agencia Canaria de Investigación Innovación y Sociedad de la Información de la Consejería de Economía, Conocimiento y Empleo y por el Fondo Social Europeo (FSE) Programa Operativo Integrado de Canarias 2014-2020, Eje 3 Tema Prioritario 74 (85%) - under grant TESIS2020010005.
@phdthesis{marrerothesis, author = {Marrero, Alejandro}, title = {Evolutionary Computation Methods for Instance Generation in Optimisation Domains}, url = {http://riull.ull.es/xmlui/handle/915/37726}, year = {2024}, month = feb, type = {Doctoral Dissertation}, school = {Universidad de La Laguna}, language = {English}, address = {San Cristóbal de La Laguna, Spain}, }

2023

GECCO
Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space

Alejandro Marrero, Eduardo Segredo, Emma Hart, and 2 more authors

In Proceedings of the Genetic and Evolutionary Computation Conference, Lisbon, Portugal, Feb 2023

Abs Bib

Generating new instances via evolutionary methods is commonly used to create new benchmarking data-sets, with a focus on attempting to cover an instance-space as completely as possible. Recent approaches have exploited Quality-Diversity methods to evolve sets of instances that are both diverse and discriminatory with respect to a portfolio of solvers, but these methods can be challenging when attempting to find diversity in a high-dimensional feature-space. We address this issue by training a model based on Principal Component Analysis on existing instances to create a low-dimension projection of the high-dimension feature-vectors, and then apply Novelty Search directly in the new low-dimension space. We conduct experiments to evolve diverse and discriminatory instances of Knapsack Problems, comparing the use of Novelty Search in the original feature-space to using Novelty Search in a low-dimensional projection, and repeat over a given set of dimensions. We find that the methods are complementary: if treated as an ensemble, they collectively provide increased coverage of the space. Specifically, searching for novelty in a low-dimension space contributes 56% of the filled regions of the space, while searching directly in the feature-space covers the remaining 44%.
@inproceedings{Marrero2023_2, author = {Marrero, Alejandro and Segredo, Eduardo and Hart, Emma and Bossek, Jakob and Neumann, Aneta}, title = {Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space}, year = {2023}, isbn = {9798400701191}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference}, pages = {312–320}, numpages = {9}, keywords = {instance-space analysis, novelty search, knapsack problem, evolutionary computation, instance generation}, location = {Lisbon, Portugal}, series = {GECCO '23}, }
SoftX
DIGNEA: A tool to generate diverse and discriminatory instance suites for optimisation domains

Alejandro Marrero, Eduardo Segredo, Coromoto León, and 1 more author

SoftwareX, Feb 2023

Abs Bib

To advance research in the development of optimisation algorithms, it is crucial to have access to large test-beds of diverse and discriminatory instances from a domain that can highlight strengths and weaknesses of different algorithms. The DIGNEA tool enables diverse instance suites to be generated for any domain, that are also discriminatory with respect to a set of solvers of the user choice. Written in C++, and delivered as a repository and as a Docker image, its modular and template-based design enables it to be easily adapted to multiple domains and types of solvers with minimal effort. This paper exemplifies how to generate instances for the Knapsack Problem domain.
@article{Marrero2023, title = {DIGNEA: A tool to generate diverse and discriminatory instance suites for optimisation domains}, journal = {SoftwareX}, volume = {22}, pages = {101355}, year = {2023}, issn = {2352-7110}, author = {Marrero, Alejandro and Segredo, Eduardo and León, Coromoto and Hart, Emma}, keywords = {Instance generation, Novelty search, Evolutionary algorithm, Optimisation, Knapsack problem}, }

2022

PPSN

A Novelty-Search Approach to Filling an Instance-Space with Diverse and Discriminatory Instances for the Knapsack Problem

Alejandro Marrero, Eduardo Segredo, Coromoto León, and 1 more author

In Parallel Problem Solving from Nature – PPSN XVII, Feb 2022

Bib

@inproceedings{Marrero22,
  author = {Marrero, Alejandro and Segredo, Eduardo and Le{\'o}n, Coromoto and Hart, Emma},
  title = {A Novelty-Search Approach to Filling an Instance-Space with Diverse and Discriminatory Instances for the Knapsack Problem},
  booktitle = {Parallel Problem Solving from Nature -- PPSN XVII},
  year = {2022},
  publisher = {Springer International Publishing},
  address = {Cham},
  pages = {223--236},
  isbn = {978-3-031-14714-2}
}

2021

GECCO
A Parallel Genetic Algorithm to Speed up the Resolution of the Algorithm Selection Problem

Alejandro Marrero, Eduardo Segredo, and Coromoto Leon

In Proceedings of the Genetic and Evolutionary Computation Conference Companion, Lille, France, Feb 2021

Abs Bib

Deciding which optimisation technique to use for solving a particular optimisation problem is an arduous task that has been faced in the field of optimisation for decades. The above problem is known as the Algorithm Selection Problem (ASP). The optimisation techniques considered in previous works have been, mainly, approaches that can be executed rapidly. However, considering more sophisticated optimisation approaches for solving the ASP, such as Evolutionary Algorithms, drastically increases the computational cost. We are interested in solving the ASP by considering different configurations of a Genetic Algorithm (GA) applied to the well-known 0/1 Knapsack Problem (KNP). This involves the execution of a significant number of configurations of the GA, in order to evaluate their performance, when applied to a wide range of instances with different features of the KNP, which is a computationally expensive task. Therefore, the main aim of the current work is to provide, as first step for solving the ASP, an efficient parallel GA, which is able to attain competitive results, in terms of the optimal objective value, in a short amount of time. Computational results show that our approach is able to scale efficiently and considerably reduces the average elapsed time for solving KNP instances.
@inproceedings{Marrero2021, author = {Marrero, Alejandro and Segredo, Eduardo and Leon, Coromoto}, title = {A Parallel Genetic Algorithm to Speed up the Resolution of the Algorithm Selection Problem}, year = {2021}, isbn = {9781450383516}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference Companion}, pages = {1978–1981}, numpages = {4}, keywords = {algorithm selection problem, parallelism, knapsack problem, genetic algorithm}, location = {Lille, France}, series = {GECCO '21} }

2020

Math
A Memetic Decomposition-Based Multi-Objective Evolutionary Algorithm Applied to a Constrained Menu Planning Problem

Alejandro Marrero, Eduardo Segredo, Coromoto León, and 1 more author

Mathematics, Feb 2020

Abs Bib

Encouraging healthy and balanced diet plans is one of the most important action points for governments around the world. Generating healthy, balanced and inexpensive menu plans that fulfil all the recommendations given by nutritionists is a complex and time-consuming task; because of this, computer science has an important role in this area. This paper deals with a novel constrained multi-objective formulation of the menu planning problem specially designed for school canteens that considers the minimisation of the cost and the minimisation of the level of repetition of the specific courses and food groups contained in the plans. Particularly, this paper proposes a multi-objective memetic approach based on the well-known multi-objective evolutionary algorithm based on decomposition (MOEA/D). A crossover operator specifically designed for this problem is included in the approach. Moreover, an ad-hoc iterated local search (ILS) is considered for the improvement phase. As a result, our proposal is referred to as ILS-MOEA/D. A wide experimental comparison against a recently proposed single-objective memetic scheme, which includes explicit mechanisms to promote diversity in the decision variable space, is provided. The experimental assessment shows that, even though the single-objective approach yields menu plans with lower costs, our multi-objective proposal offers menu plans with a significantly lower level of repetition of courses and food groups, with only a minor increase in cost. Furthermore, our studies demonstrate that the application of multi-objective optimisers can be used to implicitly promote diversity not only in the objective function space, but also in the decision variable space. Consequently, in contrast to the single-objective optimiser, there was no need to include an explicit strategy to manage the diversity in the decision space in the case of the multi-objective approach.
@article{Marrero2020, author = {Marrero, Alejandro and Segredo, Eduardo and Le{\'{o}}n, Coromoto and Segura, Carlos}, issn = {2227-7390}, journal = {Mathematics}, number = {11}, title = {{A Memetic Decomposition-Based Multi-Objective Evolutionary Algorithm Applied to a Constrained Menu Planning Problem}}, volume = {8}, year = {2020}, numpages = {18} }

2019

GECCO

On the automatic planning of healthy and balanced menus

Alejandro Marrero, Eduardo Segredo, and Coromoto Leon

In GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion, Feb 2019

Bib

@inproceedings{Marrero2019,
  title = {On the automatic planning of healthy and balanced menus},
  isbn = {9781450367486},
  booktitle = {GECCO 2019 Companion - Proceedings of the 2019 Genetic and Evolutionary Computation Conference Companion},
  publisher = {Association for Computing Machinery, Inc},
  author = {Marrero, Alejandro and Segredo, Eduardo and Leon, Coromoto},
  year = {2019},
  pages = {71-72},
  address = {Prague, Czech Republic}
}