This paper deals with a significant problem affecting embedded system design methods based on parameterized systems on a chip (SOCs). It proposes a strategy for exploration of the configuration space of a parameterized SOC architecture to determine an accurate approximation of the power/performance Pareto-front. The strategy is based on genetic algorithms and is thoroughly evaluated in terms of accuracy, efficiency, and scalability using SOC platforms that differ as regards both architectural model and complexity. The results obtained show that the proposed approach gives an excellent approximation of the Pareto-optimal front in very short exploration times (up to two orders of magnitude shorter than those required by one of the best known and widely referenced approaches in the literature). In addition, our approach possesses a good degree of scalability as performance levels are maintained even when the architectural complexity increases.