Emergence of Novelty in Evolutionary Algorithms

• URL: http://arxiv.org/abs/2207.04857v1
• Date: Mon, 27 Jun 2022 13:49:41 GMT
• Title: Emergence of Novelty in Evolutionary Algorithms
• Authors: David Herel, Dominika Zogatova, Matej Kripner, Tomas Mikolov
• Abstract summary: We introduce our approach to the maze problem and compare it to the previously proposed solution. We find that our solution leads to an improved performance while being significantly simpler. Building on that, we generalize the problem and apply our approach to a more advanced set of tasks, Atari Games.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One of the main problems of evolutionary algorithms is the convergence of the population to local minima. In this paper, we explore techniques that can avoid this problem by encouraging a diverse behavior of the agents through a shared reward system. The rewards are randomly distributed in the environment, and the agents are only rewarded for collecting them first. This leads to an emergence of a novel behavior of the agents. We introduce our approach to the maze problem and compare it to the previously proposed solution, denoted as Novelty Search (Lehman and Stanley, 2011a). We find that our solution leads to an improved performance while being significantly simpler. Building on that, we generalize the problem and apply our approach to a more advanced set of tasks, Atari Games, where we observe a similar performance quality with much less computational power needed.

Related papers

• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• Fast Re-Optimization of LeadingOnes with Frequent Changes [0.9281671380673306]
  We show that the re-optimization approach suggested by Doerr et al. reaches a limit when the problem instances are prone to more frequent changes. We propose a modification of their algorithm which interpolates between greedy search around the previous-best and the current-best solution.
  arXiv  Detail & Related papers  (2022-09-09T16:51:41Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• ROMAX: Certifiably Robust Deep Multiagent Reinforcement Learning via Convex Relaxation [32.091346776897744]
  Cyber-physical attacks can challenge the robustness of multiagent reinforcement learning. We propose a minimax MARL approach to infer the worst-case policy update of other agents.
  arXiv  Detail & Related papers  (2021-09-14T16:18:35Z)
• Online reinforcement learning with sparse rewards through an active inference capsule [62.997667081978825]
  This paper introduces an active inference agent which minimizes the novel free energy of the expected future. Our model is capable of solving sparse-reward problems with a very high sample efficiency. We also introduce a novel method for approximating the prior model from the reward function, which simplifies the expression of complex objectives.
  arXiv  Detail & Related papers  (2021-06-04T10:03:36Z)
• Scalable, Decentralized Multi-Agent Reinforcement Learning Methods Inspired by Stigmergy and Ant Colonies [0.0]
  We investigate a novel approach to decentralized multi-agent learning and planning. In particular, this method is inspired by the cohesion, coordination, and behavior of ant colonies. The approach combines single-agent RL and an ant-colony-inspired decentralized, stigmergic algorithm for multi-agent path planning and environment modification.
  arXiv  Detail & Related papers  (2021-05-08T01:04:51Z)
• Guided Exploration with Proximal Policy Optimization using a Single Demonstration [5.076419064097734]
  We train an agent on a combination of demonstrations and own experience to solve problems with variable initial conditions. The agent is able to increase its performance and to tackle harder problems by replaying its own past trajectories. To the best of our knowledge, learning a task in a three-dimensional environment with comparable difficulty has never been considered before using only one human demonstration.
  arXiv  Detail & Related papers  (2020-07-07T10:30:32Z)
• Sequential Transfer in Reinforcement Learning with a Generative Model [48.40219742217783]
  We show how to reduce the sample complexity for learning new tasks by transferring knowledge from previously-solved ones. We derive PAC bounds on its sample complexity which clearly demonstrate the benefits of using this kind of prior knowledge. We empirically verify our theoretical findings in simple simulated domains.
  arXiv  Detail & Related papers  (2020-07-01T19:53:35Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  This paper presents an approach named MineReduce, which uses mined patterns to perform problem size reduction. We present an application of MineReduce to improve a for the heterogeneous fleet vehicle routing problem.
  arXiv  Detail & Related papers  (2020-05-15T08:49:50Z)

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.