In this paper, a feasible optimization scheme for rectangular microchannel heat sinks, which incorporates the thermal resistance model and the Improved Strength Pareto Evolutionary Algorithm (SPEA2), is reported. An alternative coolant, namely, ammonia gas, is used to improve the overall thermal and hydrodynamic performances of the considered system. Results from the optimization showed significant reduction in the total thermal resistance compared to the conventional air-cooled systems up to 35% for the same allowable pumping power. The SPEA2 exhibited excellent performance when it was compared to another multiobjective algorithm, NSGA2. The results reported in this study open the door for the incorporation of some other algorithms, which have not been used in the optimization of microchannel heat sinks. Finally, the outcome of this paper predicts a promising future for the usage of ammonia gas in the area of electronics cooling.