An optimization procedure was applied to the search process of a previously developed predictor-corrector method for solving inverse convection heat transfer problems. A genetic algorithm was utilized to minimize the area of acceptable error for the inverse methodology over the entire relevant domain. The optimization resulted in a new search shape for the inverse methodology. This substantially reduced the required sample size. An important additional advantage of the optimization was the elimination of alternative local minimums. The new and old sampling pattern were used to solve an inverse problem of a thermal plume in a crosswind. The results were that the maximum error from the original search shape was 10% while the new search shape reduced the error to under 1% for the entire usable domain. Also of importance is the significantly increased spatial range of the methodology down stream. This approach could be extended to many applied areas such as environmental flows, room fires, and thermal management systems. (C) 2014 Elsevier Ltd. All rights reserved.