An upper bound of the mutation probability in the genetic algorithm for general 0-1 knapsack problem

• URL: http://arxiv.org/abs/2403.11307v1
• Date: Sun, 17 Mar 2024 19:05:40 GMT
• Title: An upper bound of the mutation probability in the genetic algorithm for general 0-1 knapsack problem
• Abstract summary: We propose a novel reduction method for the 0-1 knapsack problem(0-1 KP) and an improved mutation operator (IMO) We prove that the IMO hitting the optimal solution within only a single iteration in large-scale instances is superior to that of the traditional mutation operator.
• Score: 4.368211287521716
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: As an important part of genetic algorithms (GAs), mutation operators is widely used in evolutionary algorithms to solve $\mathcal{NP}$-hard problems because it can increase the population diversity of individual. Due to limitations in mathematical tools, the mutation probability of the mutation operator is primarily empirically set in practical applications. In this paper, we propose a novel reduction method for the 0-1 knapsack problem(0-1 KP) and an improved mutation operator (IMO) based on the assumption $\mathcal{NP}\neq\mathcal{P}$, along with the utilization of linear relaxation techniques and a recent result by Dey et al. (Math. Prog., pp 569-587, 2022). We employ this method to calculate an upper bound of the mutation probability in general instances of the 0-1 KP, and construct an instance where the mutation probability does not tend towards 0 as the problem size increases. Finally, we prove that the probability of the IMO hitting the optimal solution within only a single iteration in large-scale instances is superior to that of the traditional mutation operator.

Related papers

• Mathematical perspective on genetic algorithms with optimization guided operators [11.520406711750757]
  Recent work in ML applies genetic algorithms at inference time to iteratively improve solutions to optimization problems.<n>We introduce a general model of genetic algorithms and formulating optimization in this model as a query-complexity problem.<n>We show that some optimization problems require generation, mutation, and recombination to be solved.
  arXiv  Detail & Related papers  (2026-06-10T16:18:36Z)
• Generalized Heavy-tailed Mutation for Evolutionary Algorithms [0.45880283710344055]
  The heavy-tailed mutation operator is proposed by Doerr, Le, Makhmara, and Nguyen for evolutionary algorithms.<n>We generalize the power-law assumption using a regularly varying constraint on the distribution function of mutation rate.<n>A new version of the heavy-tailed mutation operator is proposed, satisfying the generalized conditions.
  arXiv  Detail & Related papers  (2026-04-01T05:33:12Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  We show that two evolutionary algorithms can tolerate constant noise probabilities without increasing the runtime on the OneMax benchmark. Our results are based on a novel proof argument that the noiseless offspring can be seen as a biased uniform crossover between the parent and the noisy offspring.
  arXiv  Detail & Related papers  (2024-04-02T16:35:52Z)
• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  In this paper, we analyze the usefulness of using genetic algorithms depending on the approximation class the problem belongs to. In particular, we use the standard approximability hierarchy, showing that genetic algorithms are especially useful for the most pessimistic classes of the hierarchy.
  arXiv  Detail & Related papers  (2024-02-01T09:18:34Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  Evolutionary algorithms are known to be robust to noise in the evaluation of the fitness. We analyze to what extent the $(lambda,lambda)$ genetic algorithm is robust to noise.
  arXiv  Detail & Related papers  (2023-05-08T08:49:01Z)
• Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions [0.44241702149260353]
  Witt showed that the (1+1) Evolutionary Algorithm with standard bit mutation needs time to find the optimum of any linear function. We investigate how this result generalizes if standard bit mutation is replaced by an arbitrary unbiased mutation operator.
  arXiv  Detail & Related papers  (2023-02-23T21:09:15Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  Chemotherapy treatment for cancer is a complex optimisation problem with a large number of interacting variables and constraints. We show that the more sophisticated algorithm would yield better performance on a complex problem like this. We hypothesise that this is caused by the more sophisticated algorithm being impeded by the large number of interactions in the problem.
  arXiv  Detail & Related papers  (2022-05-17T15:28:46Z)
• A Rank based Adaptive Mutation in Genetic Algorithm [0.0]
  This paper presents an alternate approach of mutation probability generation using chromosome rank to avoid any susceptibility to fitness distribution. Experiments are done to compare results of simple genetic algorithm (SGA) with constant mutation probability and adaptive approaches within a limited resource constraint.
  arXiv  Detail & Related papers  (2021-04-18T12:41:33Z)
• Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem [12.098400820502635]
  We consider the Spanning Tree (MST) problem in a single- and multi-objective version. We introduce a biased mutation, which puts more emphasis on the selection of edges of low rank in terms of low domination number. We show that a combined mutation operator which decides for unbiased or biased edge selection exhibits an upper bound -- as unbiased mutation -- in the worst case.
  arXiv  Detail & Related papers  (2020-04-22T07:47:00Z)
• The $(1+(\lambda,\lambda))$ Genetic Algorithm for Permutations [0.0]
  We show that the $(lambda,lambda)$ genetic algorithm finds the optimum in $O(n2)$ fitness queries. We also present the first analysis of this algorithm on a permutation-based problem called Ham.
  arXiv  Detail & Related papers  (2020-04-18T17:04:57Z)
• Fast Mutation in Crossover-based Algorithms [8.34061303235504]
  Heavy-tailed mutation operator proposed in Doerr, Le, Makhmara and Nguyen (GECCO) A heavy-tailed mutation operator proposed in Doerr, Le, Makhmara and Nguyen (GECCO) An empirical study shows the effectiveness of the fast mutation also on random satisfiable Max-3SAT instances.
  arXiv  Detail & Related papers  (2020-04-14T14:16:42Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17: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.