Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms

• URL: http://arxiv.org/abs/2306.02611v3
• Date: Sun, 16 Feb 2025 09:42:12 GMT
• Title: Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms
• Authors: Chao Bian, Yawen Zhou, Miqing Li, Chao Qian,
• Abstract summary: 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.
• Score: 23.248796792928204
• License:
• Abstract: Evolutionary algorithms (EAs) have been widely and successfully applied to solve multi-objective optimization problems, due to their nature of population-based search. Population update, a key component in multi-objective EAs (MOEAs), is usually performed in a greedy, deterministic manner. That is, the next-generation population is formed by selecting the best solutions from the current population and newly-generated solutions (irrespective of the selection criteria used such as Pareto dominance, crowdedness and indicators). In this paper, we analytically present that stochastic 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, OneJumpZeroJump and bi-objective RealRoyalRoad, can be exponentially decreased if replacing its deterministic population update mechanism by a stochastic one. Empirical studies also verify the effectiveness of the proposed population update method. This work is an attempt to show the benefit of introducing randomness into the population update of MOEAs. Its positive results, which might hold more generally, should encourage the exploration of developing new MOEAs in the area.

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)
• 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)
• Non-Elitist Evolutionary Multi-Objective Optimisation: Proof-of-Principle Results [2.5352713493505785]
  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.
  arXiv  Detail & Related papers  (2023-05-26T12:24:09Z)
• A Large-scale Multiple-objective Method for Black-box Attack against Object Detection [70.00150794625053]
  We propose to minimize the true positive rate and maximize the false positive rate, which can encourage more false positive objects to block the generation of new true positive bounding boxes. We extend the standard Genetic Algorithm with Random Subset selection and Divide-and-Conquer, called GARSDC, which significantly improves the efficiency. Compared with the state-of-art attack methods, GARSDC decreases by an average 12.0 in the mAP and queries by about 1000 times in extensive experiments.
  arXiv  Detail & Related papers  (2022-09-16T08:36:42Z)
• 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)
• 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)
• JKOnet: Proximal Optimal Transport Modeling of Population Dynamics [69.89192135800143]
  We propose a neural architecture that combines an energy model on measures, with (small) optimal displacements solved with input convex neural networks (ICNN) We demonstrate the applicability of our model to explain and predict population dynamics.
  arXiv  Detail & Related papers  (2021-06-11T12:30:43Z)
• Large Scale Many-Objective Optimization Driven by Distributional Adversarial Networks [1.2461503242570644]
  We will propose a novel algorithm based on RVEA framework and using Distributional Adversarial Networks (DAN) to generate new offspring. The propose new algorithm will be tested on 9 benchmark problems in Large scale multi-objective problems (LSMOP)
  arXiv  Detail & Related papers  (2020-03-16T04:14:15Z)

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.