Quality and Diversity in Evolutionary Modular Robotics

• URL: http://arxiv.org/abs/2008.02116v1
• Date: Wed, 5 Aug 2020 13:08:14 GMT
• Title: Quality and Diversity in Evolutionary Modular Robotics
• Authors: J{\o}rgen Nordmoen, Frank Veenstra, Kai Olav Ellefsen and Kyrre Glette
• Abstract summary: In Evolutionary Robotics a population of solutions is evolved to optimize robots that solve a given task. Quality Diversity algorithms try to overcome premature convergence by introducing additional measures that reward solutions for being different.
• Score: 1.290382979353427
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In Evolutionary Robotics a population of solutions is evolved to optimize robots that solve a given task. However, in traditional Evolutionary Algorithms, the population of solutions tends to converge to local optima when the problem is complex or the search space is large, a problem known as premature convergence. Quality Diversity algorithms try to overcome premature convergence by introducing additional measures that reward solutions for being different while not necessarily performing better. In this paper we compare a single objective Evolutionary Algorithm with two diversity promoting search algorithms; a Multi-Objective Evolutionary Algorithm and MAP-Elites a Quality Diversity algorithm, for the difficult problem of evolving control and morphology in modular robotics. We compare their ability to produce high performing solutions, in addition to analyze the evolved morphological diversity. The results show that all three search algorithms are capable of evolving high performing individuals. However, the Quality Diversity algorithm is better adept at filling all niches with high-performing solutions. This confirms that Quality Diversity algorithms are well suited for evolving modular robots and can be an important means of generating repertoires of high performing solutions that can be exploited both at design- and runtime.

Related papers

• Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search [61.08720171136229]
  We present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. Our techniques bring a new way of approaching the problem and a new level of precision to the field.
  arXiv  Detail & Related papers  (2024-07-22T23:24:03Z)
• Evolutionary Multi-Objective Diversity Optimization [14.930208990741129]
  We treat this problem as a bi-objective optimization problem, which is to obtain a range of quality-diversity trade-offs. We present a suitable general implementation scheme that is compatible with existing evolutionary multi-objective search methods. The resulting non-dominated populations exhibit rich qualitative features, giving insights into the optimization instances and the quality-diversity trade-offs they induce.
  arXiv  Detail & Related papers  (2024-01-15T03:59:42Z)
• Rank-Based Learning and Local Model Based Evolutionary Algorithm for High-Dimensional Expensive Multi-Objective Problems [1.0499611180329806]
  The proposed algorithm consists of three parts: rank-based learning, hyper-volume-based non-dominated search, and local search in the relatively sparse objective space. The experimental results of benchmark problems and a real-world application on geothermal reservoir heat extraction optimization demonstrate that the proposed algorithm shows superior performance.
  arXiv  Detail & Related papers  (2023-04-19T06:25:04Z)
• Computing High-Quality Solutions for the Patient Admission Scheduling Problem using Evolutionary Diversity Optimisation [10.609857097723266]
  We adapt the evolutionary diversity optimisation for a real-world problem, namely patient admission scheduling. We introduce an evolutionary algorithm to achieve structural diversity in a set of solutions subjected to the quality of each solution.
  arXiv  Detail & Related papers  (2022-07-28T14:26:45Z)
• Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem [11.590506672325668]
  We introduce a co-evolutionary algorithm to simultaneously explore the two spaces for the multi-component traveling thief problem. Results show the capability of the co-evolutionary algorithm to achieve significantly higher diversity compared to the baseline evolutionary diversity algorithms from the the literature.
  arXiv  Detail & Related papers  (2022-07-28T12:02:15Z)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We apply two procedures, a Greedy algorithm and a large scale neighborhood search, to solve the assignment problem. We find evidence that design-based multi-start can be more efficient as the size of databases grow large.
  arXiv  Detail & Related papers  (2021-12-06T20:34:55Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
  arXiv  Detail & Related papers  (2021-10-18T14:00:22Z)
• An Analysis of Phenotypic Diversity in Multi-Solution Optimization [118.97353274202749]
  We show that multiobjective optimization does not always produce much diversity, multimodal optimization produces higher fitness solutions, and quality diversity is not sensitive to genetic neutrality. An autoencoder is used to discover phenotypic features automatically, producing an even more diverse solution set with quality diversity.
  arXiv  Detail & Related papers  (2021-05-10T10:39:03Z)
• cMLSGA: A Co-Evolutionary Multi-Level Selection Genetic Algorithm for Multi-Objective Optimization [0.0]
  Multi-Level Selection Genetic Algorithm (MLSGA) already shows good performance on range of problems. This paper proposes a distinct set of co-evolutionary mechanisms, which defines co-evolution as competition between collectives rather than individuals.
  arXiv  Detail & Related papers  (2021-04-22T13:52:21Z)
• AdaLead: A simple and robust adaptive greedy search algorithm for sequence design [55.41644538483948]
  We develop an easy-to-directed, scalable, and robust evolutionary greedy algorithm (AdaLead) AdaLead is a remarkably strong benchmark that out-competes more complex state of the art approaches in a variety of biologically motivated sequence design challenges.
  arXiv  Detail & Related papers  (2020-10-05T16:40:38Z)
• Discovering Representations for Black-box Optimization [73.59962178534361]
  We show that black-box optimization encodings can be automatically learned, rather than hand designed. We show that learned representations make it possible to solve high-dimensional problems with orders of magnitude fewer evaluations than the standard MAP-Elites.
  arXiv  Detail & Related papers  (2020-03-09T20:06:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.