How Population Diversity Influences the Efficiency of Crossover
- URL: http://arxiv.org/abs/2404.12268v1
- Date: Thu, 18 Apr 2024 15:41:27 GMT
- Title: How Population Diversity Influences the Efficiency of Crossover
- Authors: Sacha Cerf, Johannes Lengler,
- Abstract summary: 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)$.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Our theoretical understanding of crossover is limited by our ability to analyze how population diversity evolves. In this study, we provide one of the first rigorous analyses of population diversity and optimization time in a setting where large diversity and large population sizes are required to speed up progress. 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(\sqrt{n}/\log^2 n)$. On the other hand, we show that even for $\mu=2$, if we simply break ties in favor of diversity then this increases diversity so much that optimization is accelerated by a constant factor.
Related papers
- The Factuality Tax of Diversity-Intervened Text-to-Image Generation: Benchmark and Fact-Augmented Intervention [61.80236015147771]
We quantify the trade-off between using diversity interventions and preserving demographic factuality in T2I models.
Experiments on DoFaiR reveal that diversity-oriented instructions increase the number of different gender and racial groups.
We propose Fact-Augmented Intervention (FAI), which instructs a Large Language Model (LLM) to reflect on verbalized or retrieved factual information about gender and racial compositions of generation subjects in history.
arXiv Detail & Related papers (2024-06-29T09:09:42Z) - Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem [10.697103866816958]
We prove evolutionary diversity optimization (EDO) on a 3-objective function LOTZ$_k$.
We show that the GSEMO computes a set of all Pareto-optimal solutions in $O(kn3)$ expected iterations.
We complement our theoretical analysis with an empirical study, which shows a very similar behavior for both diversity measures.
arXiv Detail & Related papers (2024-04-17T15:51:15Z) - Scaling Data Diversity for Fine-Tuning Language Models in Human Alignment [84.32768080422349]
Alignment with human preference prevents large language models from generating misleading or toxic content.
We propose a new formulation of prompt diversity, implying a linear correlation with the final performance of LLMs after fine-tuning.
arXiv Detail & Related papers (2024-03-17T07:08:55Z) - DARLEI: Deep Accelerated Reinforcement Learning with Evolutionary
Intelligence [77.78795329701367]
We present DARLEI, a framework that combines evolutionary algorithms with parallelized reinforcement learning.
We characterize DARLEI's performance under various conditions, revealing factors impacting diversity of evolved morphologies.
We hope to extend DARLEI in future work to include interactions between diverse morphologies in richer environments.
arXiv Detail & Related papers (2023-12-08T16:51:10Z) - Diversify Question Generation with Retrieval-Augmented Style Transfer [68.00794669873196]
We propose RAST, a framework for Retrieval-Augmented Style Transfer.
The objective is to utilize the style of diverse templates for question generation.
We develop a novel Reinforcement Learning (RL) based approach that maximizes a weighted combination of diversity reward and consistency reward.
arXiv Detail & Related papers (2023-10-23T02:27:31Z) - Rigorous Runtime Analysis of Diversity Optimization with GSEMO on
OneMinMax [13.026567958569965]
We study how the GSEMO algorithm with additional diversity-enhancing enhancements optimize a diversity of its population on a bi-objective benchmark problem OneMin.
We prove that it finds a population with optimal diversity in expected time $O(n2)$, when the problem size $n$ is odd.
For reaching our goal, we analyse the random walk of the population, which reflects the frequency of changes in the population and their outcomes.
arXiv Detail & Related papers (2023-07-14T09:43:29Z) - Analysing Equilibrium States for Population Diversity [0.0]
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.
arXiv Detail & Related papers (2023-04-19T14:30:20Z) - Source-free Domain Adaptation Requires Penalized Diversity [60.04618512479438]
Source-free domain adaptation (SFDA) was introduced to address knowledge transfer between different domains in the absence of source data.
In unsupervised SFDA, the diversity is limited to learning a single hypothesis on the source or learning multiple hypotheses with a shared feature extractor.
We propose a novel unsupervised SFDA algorithm that promotes representational diversity through the use of separate feature extractors.
arXiv Detail & Related papers (2023-04-06T00:20:19Z) - 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.