Heat-sink with air-cooling fan is the simplest and the most effective way to disperse generated heat of a high-tech device. A common approach to optimize heat sinks is based on the minimization of the entropy generation rate that takes the two major heat dissipation factors, heat transfer rate and air resistance, into consideration. However, a lower entropy generation rate often corresponds to a larger size of the designed heat sink. To have a balance design of heat sinks for heat dissipation, this paper considers the simultaneously minimization of the entropy generation rate and the material cost of the heat sinks. A multi-objective real-coded genetic algorithm using a novel direction-based crossover operator is developed for the formulated optimal heat sink design problem. With the proposed design framework, we compare and evaluate the performance of the plate-fins equipped with flow-through and impingement-flow air cooling systems. Extensive simulation results show that the balance design for heat sinks can achieve both the benefits of light weight and excellent heat dissipation.