The optimal selection of sensor structures improves the knowledge of the current plant state, which is a central issue for the decision making process. Instrumentation design is a challenging optimization problem that involves a huge amount of binary variables that represent the possible sensor locations. In this work, the limitations of the current design strategies are discussed, and they support the application of evolutionary solution methods. Among them, the estimation of distribution algorithms (EDAs) arises as a convenient alternative to solving the problem. These are stochastic optimization strategies devised to capture complex interactions among problem variables by learning the probabilistic model of candidate solutions and its sampling to generate the next population. From the broad spectrum of EDAs that use multivariate models, two representative procedures are selected that significantly differ in the methods used for learning and sampling those models. Furthermore, a comparative performance study is conducted to evaluate the benefits of increasing the complexity of the distribution model with respect to a memetic procedure based on univariate models.