Two novel gender-based meta-heuristic algorithm, Elephant Search Algorithm (ESA) and Rhinoceros Search Algorithm (RSA) are put forwarded in this paper. Inspired by natural behaviors of elephant herds, ESA emerges from the hybridization of evolutionary mechanism and dual balancing of exploitation and exploration. The name Elephant Search Algorithm which divides the search agents into two groups representing the dual search patterns. The male elephants are search agents that outreach to different dimensions of search space afar; the female elephants form groups of search agents doing local search at certain close proximities. By computer simulation, ESA is shown to outperform other metaheuristic algorithms over some benchmarking optimization functions. In terms of fitness values in optimization, ESA is ranked after Firefly algorithm showing superior performance over the other ones. The performance of ESA is most stable when compared to all other metaheuristic algorithms. ESA is fine-tuned by self-adaptive ratio method to help find a suitable gender ratio in a reasonable time. Moreover, a vitality-based ESA is proposed to help solve finetune the lifespan of search agents by using a vitality computation mechanism that grant the fit agents longer life at the expense of the mediocre agents’ life. Given the extra lifespan, the fit agents can have more time to continue enhancing the solutions. ESA is applied in solving TSP problem, clustering problem, time-series problem and achieve a good result compared with those classical method or current meta-heuristic algorithms. A novel metaheuristic search algorithm inspired by rhinoceros’ natural behavior is proposed, namely Rhinoceros Search Algorithm (RSA). Similar to our earlier version called Elephant Search Algorithm, RSA simplifies certain habitual characteristics and stream line the search operations, thereby reducing the number of operational parameters required to configure the model. Via computer simulation, it is shown that RSA is able to outperform certain classical metaheuristic algorithms. Different dimensions of optimization problems are tested, and good results are observed by RSA.