This paper presents a new evolutionary planner for optimizing the input commands of multiple Unmanned Aircraft Vehicles (UAVs) in target search missions. This planner minimizes the target detection time and maximizes the UAVs performance, given 1) the uncertainty in the target location and sensor information, and 2) the UAV motion and sensorial payload models. On one hand, it calculates the detection time related criteria using Bayesian theory to handle the uncertainty of the problem. On the other hand, it measures the UAVs performance against a real kinematic model that takes into account some environmental effects. Besides, it exploits the typical versatility and good performance of evolutionary algorithms to tackle this search problem as a multi-objective and multi-stepped receding horizon controller, capable of providing acceptable long term (less-myopic) decisions due to a novel optimization criterium that weights the future expected observations with the UAV manoeuvrability constraints. All these properties let it handle successfully the minimum time target detection task in real world scenarios, as the results analyzed in this paper, obtained over different setups, show.