Analysing Equilibrium States for Population Diversity
- URL: http://arxiv.org/abs/2304.09690v1
- Date: Wed, 19 Apr 2023 14:30:20 GMT
- Title: Analysing Equilibrium States for Population Diversity
- Authors: Johannes Lengler and Andre Opris and Dirk Sudholt
- Abstract summary: Population diversity is crucial in evolutionary algorithms as it helps with global exploration and facilitates the use of crossover.
We study how population diversity of $(mu+1)$ algorithms, measured by the sum of pairwise Hamming distances, evolves in a fitness-neutral environment.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Population diversity is crucial in evolutionary algorithms as it helps with
global exploration and facilitates the use of crossover. Despite many runtime
analyses showing advantages of population diversity, we have no clear picture
of how diversity evolves over time. We study how population diversity of
$(\mu+1)$ algorithms, measured by the sum of pairwise Hamming distances,
evolves in a fitness-neutral environment. We give an exact formula for the
drift of population diversity and show that it is driven towards an equilibrium
state. Moreover, we bound the expected time for getting close to the
equilibrium state. We find that these dynamics, including the location of the
equilibrium, are unaffected by surprisingly many algorithmic choices. All
unbiased mutation operators with the same expected number of bit flips have the
same effect on the expected diversity. Many crossover operators have no effect
at all, including all binary unbiased, respectful operators. We review
crossover operators from the literature and identify crossovers that are
neutral towards the evolution of diversity and crossovers that are not.
Related papers
- Harnessing Hierarchical Label Distribution Variations in Test Agnostic Long-tail Recognition [114.96385572118042]
We argue that the variation in test label distributions can be broken down hierarchically into global and local levels.
We propose a new MoE strategy, $mathsfDirMixE$, which assigns experts to different Dirichlet meta-distributions of the label distribution.
We show that our proposed objective benefits from enhanced generalization by virtue of the variance-based regularization.
arXiv Detail & Related papers (2024-05-13T14:24:56Z) - How Population Diversity Influences the Efficiency of Crossover [0.0]
We give a formal and general criterion which amount of diversity is necessary and sufficient to speed up the $(mu+1)$ Genetic Algorithm on LeadingOnes.
We show that the naturally evolving diversity falls short of giving a substantial speed-up for any $mu=O(sqrtn/log2 n)$.
arXiv Detail & Related papers (2024-04-18T15:41:27Z) - A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
We investigate learning the equilibria in non-stationary multi-agent systems.
We show how to test for various types of equilibria by a black-box reduction to single-agent learning.
arXiv Detail & Related papers (2023-06-12T23:48:24Z) - Learning signatures of decision making from many individuals playing the
same game [54.33783158658077]
We design a predictive framework that learns representations to encode an individual's 'behavioral style'
We apply our method to a large-scale behavioral dataset from 1,000 humans playing a 3-armed bandit task.
arXiv Detail & Related papers (2023-02-21T21:41:53Z) - A Unified Theory of Diversity in Ensemble Learning [4.773356856466191]
We present a theory of ensemble diversity, explaining the nature of diversity for a wide range of supervised learning scenarios.
This challenge has been referred to as the holy grail of ensemble learning, an open research issue for over 30 years.
arXiv Detail & Related papers (2023-01-10T13:51:07Z) - Diverse Weight Averaging for Out-of-Distribution Generalization [100.22155775568761]
We propose Diverse Weight Averaging (DiWA) to average weights obtained from several independent training runs rather than from a single run.
DiWA consistently improves the state of the art on the competitive DomainBed benchmark without inference overhead.
arXiv Detail & Related papers (2022-05-19T17:44:22Z) - What can phylogenetic metrics tell us about useful diversity in
evolutionary algorithms? [62.997667081978825]
Phylogenetic diversity metrics are a class of metrics popularly used in biology.
We find that, in most cases, phylogenetic metrics behave meaningfully differently from other diversity metrics.
arXiv Detail & Related papers (2021-08-28T06:49:14Z) - Unifying Behavioral and Response Diversity for Open-ended Learning in
Zero-sum Games [44.30509625560908]
In open-ended learning algorithms, there are no widely accepted definitions for diversity, making it hard to construct and evaluate the diverse policies.
We propose a unified measure of diversity in multi-agent open-ended learning based on both Behavioral Diversity (BD) and Response Diversity (RD)
We show that many current diversity measures fall in one of the categories of BD or RD but not both.
With this unified diversity measure, we design the corresponding diversity-promoting objective and population effectivity when seeking the best responses in open-ended learning.
arXiv Detail & Related papers (2021-06-09T10:11:06Z) - Effective Diversity in Population Based Reinforcement Learning [38.62641968788987]
We introduce an approach to optimize all members of a population simultaneously.
Rather than using pairwise distance, we measure the volume of the entire population in a behavioral manifold.
Our algorithm Diversity via Determinants (DvD) adapts the degree of diversity during training using online learning techniques.
arXiv Detail & Related papers (2020-02-03T10:09:16Z)
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.