The synthesis of heat exchanger networks (HENs) is one of the most studied problems in process synthesis, because a high level of integration of the internal heat transfer is necessary to reduce both primary energy consumption and total costs. This work develops a methodology for the multi-objective optimization of HEN synthesis. A two-level hybrid algorithm operating on a population of candidate HEN topologies is proposed to search for the best tradeoffs between the maximization of energy recovery and the minimization of total HEN costs. The advantages deriving from graph representations of a HEN are fully exploited in order to handle topologies with arbitrary complexity and to simplify the optimization procedure required to evaluate the objective functions for a given topology. The Aromatics Plant problem, a well-known test case in the literature about HEN synthesis, is used as a test case to show the potentialities of the proposed methodology.