Mathematical modeling and improved memetic algorithm for the extended simplified discounted {0-1} knapsack problem with randomness

In this paper, we first extended the extended simplified discount {0-1} backpack problem (ESD {0-1} KP) and proposed the extended simplified discounted {0-1} knapsack problem with randomness (ESD {0-1} KP-R) model. Compared with the ordinary ESD {0-1} KP model, it increases the size and randomness of the term set, which is more suitable for the actual concept of "discount" and has stronger generalization. Then we used the improved memetic algorithm to solve the ESD {0-1} KP-R model. First, a greedy strategy with a relax variable was first designed to obtain the initial solution. Second, designed a crossover strategy with fuzzy sets to generate a good offspring population. Third, in order to overcome the shortcoming of memetic algorithms falling into local optimization, we designed a population diversity adjustment strategy with an information vector. This strategy combines the parent and child populations into a set of candidate solutions, and then divides all the solutions in the set into four categories according to the fitness and diversity of the solutions. Different selection methods can be used to adjust the diversity of the population while ensuring the quality of the solutions selected. In addition, based on the profit density for combinations of terms, three kinds of neighborhood structures were designed. They were used to improve the algorithm's searching ability, explore the neighborhood of local solutions, and jump out of the local optimum, respectively. The local search was performed by the variable neighborhood search algorithm. Finally, the effectiveness of the proposed improvement strategy and the feasibility of the proposed algorithm for solving the ESD {0-1} KP-R were demonstrated through experimental analysis on four types of instances.