A computational study for the optimal design of heat exchangers (HX) used in a high temperature and high pressure system is presented. Two types of air to air HX are considered in this study. One is a single-pass cross-flow type with straight plain tubes and the other is a two-pass cross-counter flow type with plain U-tubes. These two types of HX have the staggered arrangement of tubes. The design models are formulated using the number of transfer units ($varepsilon$-NTU method) and optimized using a genetic algorithm. In order to design compact light weight HX with the minimum pressure loss and the maximum heat exchange rate, the weight of HX core is chosen as the object function. Dimensions and tube pitch ratio of a HX are used as design variables. Demanded performance such as the pressure loss (${Delta}P$) and the temperature drop (${Delta}T$) are used as constraints. The performance of HX is discussed and their optimal designs are presented with an investigation of the effect of design variables and constraints.