In this work optimal synthesis of heat exchanger networks (HENs) is focused on, namely the minimization of total annual costs (TAC). An efficient combination of optimization strategies for HEN synthesis is presented. A novel strategy for local optimization in the continuous space is developed and embedded in a stochastic global search with a tailored genetic algorithm using a stage-wise superstructure. The novel strategy is based on structure identification and changing the reference system for optimization. This strategy reduces the number of optimization variables and is able to simplify HEN structures thus enabling particularly well performing local search. Eight frequently studied medium- to large-scale problems from literature are investigated and evaluated. The application of the proposed algorithm was able to find configurations with consistently lower TAC compared to previously reported solutions.