Naturally, to analyze an image accurately, all the similar objects within it should be separated to pay attention to the most important object for reaching more details and hence achieving better accuracy. Therefore, multilevel thresholding is an indispensable image processing technique in the field of image segmentation and is employed widely to separate those similar objects. However, with increasing thresholds, the existing image segmentation techniques might suffer from exponentially-grown computational cost and low accuracy due to local optima shortage. Therefore, in this paper, a new image segmentation algorithm based on the improved marine predators algorithm (MPA) is proposed. MPA is improved using a strategy to find a number of the worst solutions within the population then tries to search for other better ones for those solutions by moving them gradually towards the best solutions to avoid accelerating to local optima and randomly within the search space based on a certain probability. In addition, this number of the worst solutions is increased with the iteration. This strategy is known as the linearly increased worst solutions improvement strategy (LIS). Also, we suggested that apply the ranking strategy based on a novel updating scheme, namely ranking-based updating strategy (RUS), on the solutions that could find better solutions in the last number iterations, perIter, in the hope of finding better solutions near it. RUS updates the particles/solutions which could not find better solutions than the best-local one in a number of consecutive iterations, with those that are generated based on a novel updating strategy. LIS is integrated with MPA to produce a new segmentation meta-heuristic algorithm abbreviated as MPALS. Also, MPALS and RUS are combined to tackle ISP in a strong variant abbreviated as HMPA for overcoming the image segmentation problem. The two proposed algorithms are validated on 14 test images and compared with seven state-of-the-arts meta-heuristic algorithms. The experimental results show the effectiveness of HMPA with increasing the threshold levels compared to the seven state-of-the-arts algorithms when segmenting an image, while their performance is roughly the same for the image with a small threshold level.