Paper ID: 2403.11307

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

Yang Yang

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.

Submitted: Mar 17, 2024