Metaheuristic algorithms have become popular for addressing complex optimization challenges in recent years. The Artificial Protozoa Optimization (APO) algorithm is one such metaheuristic, drawing inspiration from the behavior of protozoa, simulating their survival mechanisms through behaviors like foraging, dormancy, and reproduction. The parallel strategy enhances the algorithm’s performance by dividing the population into subgroups and allowing inter-group communication. Opposition-based learning enables population members to reach more promising regions by simultaneously considering candidate solutions and their opposite counterparts. Lévy flight merges short-range local searching with long-range global searching through a random walk with a probabilistic step size distribution. In this paper, we apply parallel strategies, Lévy flight, and opposition-based learning to improve the APO algorithm, further enhancing its global search capabilities. We tested the improved Artificial Protozoa Optimization algorithm on a set of 12 benchmark functions from the IEEE CEC 2022 suite. The outcomes of the experiments demonstrate that the proposed improved Artificial Protozoa Optimization algorithm is competitive.