Non-Elitist Evolutionary Multi-Objective Optimisation: Proof-of-Principle Results

• URL: http://arxiv.org/abs/2305.16870v1
• Date: Fri, 26 May 2023 12:24:09 GMT
• Title: Non-Elitist Evolutionary Multi-Objective Optimisation: Proof-of-Principle Results
• Authors: Zimin Liang and Miqing Li and Per Kristian Lehre
• Abstract summary: Elitism, which constructs the new population by preserving best solutions out of the old population and newly-generated solutions, has been a default way for population update since the late 1990s. We take an opposite perspective to conduct the population update in MOEAs by simply discarding elitism. Preliminary experimental results show that NE-MOEA can compete with well-known elitist MOEAs.
• Score: 2.5352713493505785
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Elitism, which constructs the new population by preserving best solutions out of the old population and newly-generated solutions, has been a default way for population update since its introduction into multi-objective evolutionary algorithms (MOEAs) in the late 1990s. In this paper, we take an opposite perspective to conduct the population update in MOEAs by simply discarding elitism. That is, we treat the newly-generated solutions as the new population directly (so that all selection pressure comes from mating selection). We propose a simple non-elitist MOEA (called NE-MOEA) that only uses Pareto dominance sorting to compare solutions, without involving any diversity-related selection criterion. Preliminary experimental results show that NE-MOEA can compete with well-known elitist MOEAs (NSGA-II, SMS-EMOA and NSGA-III) on several combinatorial problems. Lastly, we discuss limitations of the proposed non-elitist algorithm and suggest possible future research directions.

Related papers

• Stochastic Population Update Provably Needs An Archive in Evolutionary Multi-objective Optimization [20.883780207120783]
  We show that using an archive can allow a small population and accelerate the search of SPU-based MOEAs substantially. Specifically, we analyze the expected running time of two well-established MOEAs, SMS-EMOA and NSGA-II for solving a commonly studied bi-objective problem OneJumpZero.
  arXiv  Detail & Related papers  (2025-01-28T06:21:38Z)
• A Two-stage Evolutionary Framework For Multi-objective Optimization [8.253379910879795]
  Two-stage Evolutionary Framework For Multi-objective Optimization (TEMOF) One classic MOEA and two state-of-the-art MOEAs are integrated into the framework to form three new algorithms. Winner among three new algorithms is compared with several existing MOEAs and shows better results.
  arXiv  Detail & Related papers  (2024-07-09T04:14:59Z)
• Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms [23.248796792928204]
  Population update is a key component in multi-objective Evolutionary algorithms (MOEAs) In this paper, we analytically present that population update can be beneficial for the search of MOEAs. Specifically, we prove that the expected running time of two well-established MOEAs, SMS-EMOA and NSGA-II, for solving two bi-objective problems, OneJumpZero and bi-RoyalRoad, can be exponentially decreased if replacing its deterministic population update mechanism with a randomness one.
  arXiv  Detail & Related papers  (2023-06-05T05:54:56Z)
• Adaptive Identification of Populations with Treatment Benefit in Clinical Trials: Machine Learning Challenges and Solutions [78.31410227443102]
  We study the problem of adaptively identifying patient subpopulations that benefit from a given treatment during a confirmatory clinical trial. We propose AdaGGI and AdaGCPI, two meta-algorithms for subpopulation construction.
  arXiv  Detail & Related papers  (2022-08-11T14:27:49Z)
• Towards Explainable Metaheuristic: Mining Surrogate Fitness Models for Importance of Variables [69.02115180674885]
  We use four benchmark problems to train a surrogate model and investigate the learning of the search space by the surrogate model. We show that the surrogate model picks out key characteristics of the problem as it is trained on population data from each generation.
  arXiv  Detail & Related papers  (2022-05-31T09:16:18Z)
• Effective Mutation Rate Adaptation through Group Elite Selection [50.88204196504888]
  This paper introduces the Group Elite Selection of Mutation Rates (GESMR) algorithm. GESMR co-evolves a population of solutions and a population of MRs, such that each MR is assigned to a group of solutions. With the same number of function evaluations and with almost no overhead, GESMR converges faster and to better solutions than previous approaches.
  arXiv  Detail & Related papers  (2022-04-11T01:08:26Z)
• 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)
• 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)
• Bloom Origami Assays: Practical Group Testing [90.2899558237778]
  Group testing is a well-studied problem with several appealing solutions. Recent biological studies impose practical constraints for COVID-19 that are incompatible with traditional methods. We develop a new method combining Bloom filters with belief propagation to scale to larger values of n (more than 100) with good empirical results.
  arXiv  Detail & Related papers  (2020-07-21T19:31:41Z)
• Hybrid Adaptive Evolutionary Algorithm for Multi-objective Optimization [0.0]
  This paper proposed a new Multi-objective Algorithm as an extension of the Hybrid Adaptive Evolutionary algorithm (HAEA) called MoHAEA. MoHAEA is compared with four states of the art MOEAs, namely MOEA/D, pa$lambda$-MOEA/D, MOEA/D-AWA, and NSGA-II.
  arXiv  Detail & Related papers  (2020-04-29T02:16:49Z)
• Differential Evolution with Reversible Linear Transformations [8.873449722727026]
  We propose to generate new candidate solutions by utilizing reversible linear transformation applied to a triplet of solutions from the population. In other words, the population is enlarged by using newly generated individuals without evaluating their fitness.
  arXiv  Detail & Related papers  (2020-02-07T16:05:54Z)

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.