Simulated annealing is a useful heuristic for finding good solutions for difficult combinatorial optimization problems. In some engineering applications the quality of a solution is based upon how tolerant the solution is to changes in the environment. The concept of simulated annealing is based upon the metallurgical process of annealing where a material is tempered by heating and cooling. Genetic algorithms have been used to evolve solutions to complex problems by imitating the biological process of evolution using crossover and mutation to modify the candidate solutions. In coevolution a candidate solution is composed of multiple species each of which provides a portion of the candidate solution. Those individuals of a species that, in collaboration with the individuals from the other species, are evaluated as providing the most fit solution are the preferred individuals of a species. This work investigated whether robustness, defined as the ability of a solution to tolerate changes to the problem environment, could be improved by defining a neighborhood of fitness functions that are centered in the neighborhood of the nominal objective function. Simulated annealing was used to manage the subsequent narrowing of the neighborhood of fitness functions. Two robustness measures were developed that used samples from the neighborhood of objective functions; one employed the minimum fitness value, and the other employed the average fitness value. Coevolutionary genetic algorithms were used to generate candidate solutions employing the robustness measures. This study used three benchmark functions to evaluate the effects of the robustness measures. The results indicated that the robustness measures could produce solutions that were robust and, often, globally optimal for benchmark functions employed in the testing. Future work includes applying this framework to a broader class of optimization problems, investigating new neighborhood strategies, and devising new robustness measures.