Quality Diversity (QD) aims to evolve a population of solutions that are both diverse and of high quality. The Map-Elites QD approach partitions the search space according to a feature space and stores the best soluti...
详细信息
ISBN:
(纸本)9798400704949
Quality Diversity (QD) aims to evolve a population of solutions that are both diverse and of high quality. The Map-Elites QD approach partitions the search space according to a feature space and stores the best solution for each feature. Bossek & Sudholt (GECCO 2023) showed that a simple QD algorithm on the feature space defined by the number of selected elements efficiently computes (1 - 1/e)-approximations for maximising monotone submodular functions. We extend this approach by adding Boolean conjunctions to the feature space, which allow the user to enforce or to exclude certain elements. This enhanced feature space overlays several customised problems, which are optimised in parallel. We bound the expected time for QD to find ( 1 - 1/e)-approximations for all problems simultaneously and show that adding sub-problems mechanically via helper formulas guides the search and speeds up optimisation. Finally, we give instances on which the use of crossover yields drastic speedups. Our work contributes to the theoretical understanding of QD algorithms and suggests a way to maximise the potential of QD.
We study the problem of maximizing a monotonesubmodular function subject to a Multiple Knapsack constraint. The input is a set I of items, each has a non-negative weight, and a set of bins of arbitrary capacities. Al...
详细信息
We study the problem of maximizing a monotonesubmodular function subject to a Multiple Knapsack constraint. The input is a set I of items, each has a non-negative weight, and a set of bins of arbitrary capacities. Also, we are given a submodular, monotone and non-negative function f over subsets of the items. The objective is to find a packing of a subset of items A c I in the bins such that f (A) is maximized. Our main result is an almost optimal polynomial time (1 - e-1 - epsilon)-approximation algorithm for the problem, for any epsilon > 0. The algorithm relies on a structuring technique which converts a general multiple knapsack constraint to a constraint in which the bins are partitioned into groups of exponentially increasing cardinalities, each consisting of bins of uniform capacity. We derive the result by combining structuring with a refined analysis of techniques for submodular optimization subject to knapsack constraints. (c) 2021 Elsevier Inc. All rights reserved.
Given a ground set of items, the result diversification problem aims to select a subset with high "quality " and "diversity " while satisfying some constraints. It arises in various real world arti...
详细信息
Given a ground set of items, the result diversification problem aims to select a subset with high "quality " and "diversity " while satisfying some constraints. It arises in various real world artificial intelligence applications, such as web-based search, document summarization and feature selection, and also has applications in other areas, e.g., computational geometry, databases, finance and operations research. Previous algorithms are mainly based on greedy or local search. In this paper, we propose to reformulate the result diversification problem as a bi-objective maximization problem, and solve it by a multi objective evolutionary algorithm (EA), i.e., the GSEMO. We theoretically prove that the GSEMO can achieve the (asymptotically) optimal theoretical guarantees under both static and dynamic environments. For cardinality constraints, the GSEMO can achieve the optimal polynomial-time approximation ratio, 1/2. For more general matroid constraints, the GSEMO can achieve an asymptotically optimal polynomial-time approximation ratio, 1/2 - epsilon/(4n), where epsilon > 0 and n is the size of the ground set of items. Furthermore, when the objective function (i.e., a linear combination of quality and diversity) changes dynamically, the GSEMO can maintain this approximation ratio in polynomial running time, addressing the open question proposed by Borodin et al. [7]. This also theoretically shows the superiority of EAs over local search for solving dynamic optimization problems for the first time, and discloses the robustness of the mutation operator of EAs against dynamic changes. Experiments on the applications of web-based search, multi-label feature selection and document summarization show the superior performance of the GSEMO over the stateof-the-art algorithms (i.e., the greedy algorithm and local search) under both static and dynamic environments. (C) 2022 Published by Elsevier B.V.
The result diversification problem is to select an optimal subset with high “quality” and “diversity” from a given ground set of items, which is popular in various applications such as web-based search, multi-docu...
详细信息
暂无评论