Frost accumulation on tube-fin heat exchanger leads to reduction in evaporator capacity and deteriorates cycle efficiency. The conventional counter-flow heat exchanger circuitry has the disadvantage that more frost tends to accumulate in the first few banks exposed to the incoming air. This frost concentration makes the air side flow resistance increase rapidly, thus reduces the air flow rate and evaporator capacity under constant fan power. In this paper, a novel integer permutation based Genetic Algorithm is used to obtain optimal circuitry design with improved HX performance under frosting conditions. A dynamic HX model with the capability to account for non-uniform frost growth on a fan-supplied coil is used to assess the performance of optimal circuitry. The case study shows that the proposed circuitry design approach yields better circuitry with larger HX capacity, more uniform frost distribution, less air flow path blockage, and therefore longer evaporator operation time between defrost operations.