CUDA-Based Genetic Algorithm for Set Union Knapsack Optimization with Hybrid Initialization

This paper proposes a CUDA-based hybrid genetic algorithm framework that combines heuristic and random initialization with mutation, crossover, and parallel local search to efficiently solve the SUKP. The framework mainly uses heuristic initialization to generate high-quality solutions while using a small proportion of randomly generated solutions to maintain population diversity. Specifically, 20% of the elite population is used for heuristic initialization, with 99.5% of the GPU threads starting from heuristically generated solutions and the remaining 0.5% starting from randomly generated solutions. A mutation operator is then applied to improve population diversity and explore the search space. Each GPU thread independently performs parallel local search, while the crossover operator enables information exchange among individuals by using the best solution identified within each GPU block.