This paper describes an application of fuzzy-logic and evolutionary computation to the optimization of the start-up phase of a combined cycle power plant. We modelled process experts’ knowledge with fuzzy sets over the process variables in order to get the needed cost function for the genetic algorithm (GA) we used to obtain the optimal regulations. Due to the obvious impossibility to test the resulting inputs on the real plant we used a complex software simulator to evaluate the performance of the solutions. In order to reduce the computational load of the whole procedure we implemented for the genetic algorithm a novel fitness approximation technique, cutting by 98% the number of fitness evaluations, i.e. software simulator runs with respect to a genetic algorithm without fitness approximation. Moreover, solutions found by our methods remarkably improved the solutions given by the plant operators.