This paper describes a heuristic optimization approach using genetic algorithms. The method solves general network design problems to optimality, or near-optimality, with respect to reliability. The optimization formulation in this paper relaxes the previous restrictions that appear in the literature. Network design is expanded to include links of differing reliability and to select from multiple choices for each possible link component. This significantly expands the search space, necessitating a heuristic approach, but also is much more reflective of actual communications network design problems. The approach can use either exact or approximate network reliability calculations and its flexibility, effectiveness and efficiency are demonstrated on a series of increasingly constrained all-terminal reliability test problems.