This paper proposes and implements a new methodology for optimizing Finned-Tube Heat Exchangers (FTHEs) using a Volume Averaging Theory (VAT) physical model and a Genetic Algorithm (GA) optimizer. This method allows for multiple-parameter constrained optimization of FTHEs by design of their basic morphological structures. A consistent model is used to describe transport phenomena in a FTHE based on VAT, which allows for the volume averaged conservation of mass, momentum, and energy equations to be solved point by point, with the morphology of the structure directly incorporated into the field equations and full conjugate effects included. The equations differ from those often presented and are developed using a rigorous averaging technique, hierarchical modeling methodology, and fully turbulent models with Reynolds stresses and fluxes in every pore space. These averaged equations have additional integral and differential terms that must be dealt with in order for the equation set to be closed, and recent work has provided this closure for FTHEs. The resulting governing equation set is relatively simple and is discretized and quickly solved numerically. Such a computational algorithm is fast running, but still able to present a detailed picture of the temperature fields in both of the fluid flows as well as in the solid structure of the heat exchanger. A GA is integrated with the VAT-based solver to carry out the FTHE numerical optimization, which is a ten parameter problem, and the FTHE is optimized subject to imposed constraints. This method of using the VAT-based solver fully integrated with a GA optimizer results in a new all-in-one tool for performing multiple-parameter constrained optimization on FTHEs.