The optimal design of sensor networks consists in selecting the type, number and location of sensors that provide the required quantity and quality of process information by optimizing an appropriate objective function. The problem is multimodal and involves many binary variables, therefore a huge combinatorial optimization problem results. In this work, the design is solved using a metaheuristic based approach. A strategy that combines the advantages of Tabu Search and Estimation of Distribution Algorithms is presented, which is able to solve high scale designs since it can be implemented to run in parallel. Application results of the methodology to the optimal selection of instruments for networks of incremental size are provided. (C) 2013 Elsevier Ltd. All rights reserved.