A new approach for generating optimal heat exchanger networks (HENs) is described that does not use any heuristics. This approach involves generating the number of intermediate temperatures in each of the hot and cold streams and their values, randomly, using the binary coded NSGA-II-sJG. The substreams so generated are then matched randomly. This procedure results in a variable number of decision variables in each solution (chromosome). Dummy decision variables are introduced so as to make the length of each chromosome the same. A new crossover strategy, crossA, as well as a few other adaptations, are described that enable faster convergence to the optimal solution(s). Three single-objective problems involving the minimization of the annualized cost are solved and the results compared with those reported in the literature. Thereafter, a few problems with two- and three-objective functions are solved. In these, the objective functions are selected from among the annualized cost, the amount of (hot + cold) utilities required (these are important due the environmental issues associated with them), the energy recovery, and the total number of units. To the best of our knowledge, such multiobjective optimization of HENs has not been reported in the open literature yet. A decision maker can choose any of the solutions from among the set of several nondominated (equally good) Pareto-optimal solutions generated. These are more meaningful than those obtained using single objective functions. Though the algorithm developed is specific to HENs, it can easily be applied to other similar optimization problems.