Article Preview
Top1. Introduction
Network Design Problems (NDPs) are combinatorial problems that must find the most appropriate network to solve applications of the real world. In general, these problems are modeled as graphs and can be found in the fields of engineering and sciences, as for example, the development of networks for telecommunications (Kershenbaum, 1993; Talbi & Meunier, 2006) design of electric circuits (Deo, 2004), vehicle routing (Golden et al., 2008), computer network applications (Deo, 2004), and phylogenetic trees (Mintz & Bakos, 2012). In the real world, NDPs have large numbers of elements (nodes) and interconnections (edges). Moreover, several constraints restrict the types of connections that an algorithm can use to design a network. For example, to solve a simple NDP called Minimum Spanning Tree Problem (MSTP), we can use polynomial time algorithms such as Prim (1957) and Kruskal (1956). However, the problem becomes NP-Hard if a degree constraint is added, which is known as Degree Constrained Minimum Spanning Tree Problem (dc-MSTP) (Martinez-Perez & Zimmermann, 2009; Garey & Johnson, 1979). In this case, it is very hard to find an adequate solution to the NDP in reasonable running time.
Several other extensions of the MSTP are also NP-Hard. For such NDPs, population-based metaheuristics that simultaneously investigate a large set of potential points of the search space have been researched. Several of them, as Evolutionary Algorithms (EAs), use the strategy of generating many network configurations (points in the search space) for the possible solutions of an NDP, testing whether the trees respect the constraints (Omara & Arafa, 2010).
However, such approach does not often provide satisfactory results for large scale problems, since the generation of a feasible network that respects all the constraints is rare for large networks. To develop efficient EAs for complex large-scale NDPs, new dynamic data structures (encodings) that exclusively generate feasible networks have been researched (Caminiti & Petreschi, 2010; Rothlauf, 2006). Those encodings allow a more suitable exploitation of the search space, increasing the quality of solutions of EAs. Among the encodings from the literature, the node-depth encoding (NDE) (Santos et al., 2010) can design networks in only 
average running time, whereas other encodings require at least O(n), O(n log(n)) and 
(Raidl & Julstrom, 2003a; Santos et al., 2010), where n is the number of graph nodes.
The discovery of the global optimum (or an adequate suboptimum) from a non-trivial large-scale NDP requires the construction and evaluation of thousands or millions of potential spanning trees to find an adequate network. As a consequence, the total running time needed to generate and evaluate all the spanning trees explored by a population-based metaheuristic is a bottleneck for the algorithm performance (dos Santos et al., 2008).
The implementation of a NDE directly in hardware can parallelize EAs properly, reducing their computational time. Thus, an EA with NDE implemented in hardware can enhance the performance of large scale NDPs. FPGAs (Field Programmable Gate Array) provide spatial computation allowing an high degree of parallelism and flexibility for developing solutions totally customized for a given application (Bobda, 2007; Middendorf et al., 2002).