463245 Hybrid Algorithms for the Design of Sensor Networks of Nonlinear Systems

Monday, November 14, 2016
Grand Ballroom B (Hilton San Francisco Union Square)
José Hernández1, Mercedes Carnero1 and Mabel C. Sánchez2, (1)Grupo de Optimización, Facultad de Ingeniería UNRC, Río Cuarto, Argentina, (2)PLAPIQUI - (UNS - CONICET), Bahía Blanca, Argentina

The design of the instrumentation system of a chemical plant is a complex multilevel task, which comprises the definition of the global objectives, the selection of the measured variables, and the specification of the implementation details, such as measurement intervals, sample procedures, interfaces, maintenance activities, etc.

During the on-line operation, the quality and availability of process knowledge essentially depends on the instrumentation selection performed on the second design stage. The structure of a sensor network (SN) is defined by the type, amount, precision, reliability and location of its instruments.

To determine the optimal SN that minimizes the total instrumentation cost and simultaneously satisfies the information requirements, a combinatorial optimization problem is stated that involves binary variables. The difficulties associated to the solution of that problem come from the dimension of the search space, which increases significantly for large scale processes, and the type of mathematical relationship among the process variables.

Nguyen and Bagajewicz (2008) addressed the design of SNs that provide information about the operation of processes described by a set of non-linear algebraic equations. They proposed the equations-based tree search method, which guarantees to find an optimal solution and is computationally efficient for small and middle scale problems. However, its performance is not always satisfactory for dealing with large scale problems (47 binary variables). At the same time Kelly and Zyngier (2008) presented a MILP formulation for designing sensor structures that satisfy observability, software/hardware redundancy and precision. But to deal with a problem that involves 34 binary variables, some heuristics were used. Then Nguyen and Bagajewicz (2011) exploited certain cost properties of the different nodes in the tree search to efficiently prune nonoptimal nodes using a breadth-first/level traversal tree search method to obtain the global optimum, and proved the efficiency of the algorithm using a benchmark that comprises 24 binary variables. Finally the aforementioned authors combined the tree search procedure with a local search heuristics to reduce the computational time (Nguyen and Bagajewicz (2013).

Regarding the application of stochastic optimization problems to solve the design problem, Gerkens and Heyen (2005) presented two ways of parallelizing the classic GA to reduce the solution time, and applied them on large scale problems (212 and 618 binary variables), but a solution reproducibility analysis is missed.

In this work, the metaheuristic proposed by Carnero et al. (2013) is extended to the design of SNs of processes whose operation is described using the set of non-linear algebraic equations associated to the mass, component and energy balances. The approach uses an Estimation of Distribution Algorithm (Hauschild and Pelikan, 2011), i.e. a global search engine, in combination with a local search heuristic. This is Strategic Oscillations within the framework of Tabu Search. Application results of the hybrid technique have demonstrated a rewarding performance for solving the same problem for linear systems of incremental size. It achieves a high reproducibility of the good solutions using a controlled computational time.

The incorporation of the process knowledge contained in the balance equations is extremely useful to guide the search. In this work, a technique is presented to form the initial population of the Estimation of Distribution Algorithm in such a way that at least the observability constraints of the key variables are satisfied. The performance of the proposed design methodology is evaluated and compared with the corresponding ones to other existing strategies for small and medium size benchmarks. Regarding a large scale case study, best known solutions are provided, and their reproducibility is analyzed.


Baluja S, Caruana R. Removing the genetics from the standard genetic algorithm. Technical Report CMU-CS-95-141; Carnegie Mellon University, 1995.

Carnero M, Hernández J, Sánchez M. A new metaheuristic based approach for the design of sensor networks. Comp. Chem. Eng. 2013; 55: 83-96.

Gerkens C, Heyen G. Use of parallel computers in rational design of redundant sensor networks. Comput. Chem. Eng. 2005; 29: 1379-87.

Hauschild M, Pelikan M. An introduction and survey of estimation of distribution algorithms. Swarm and Evolutionary Computation 2011,1: 111–28.

Nguyen D, Bagajewicz M. Design of nonlinear sensor networks for process plants. Ind. Eng. Chem. Res. 2008; 47: 5529-42.

Nguyen D, Bagajewicz M. New efficient breadth_first/level traversal tree search method for the design and upgrade of sensor networks. AIChE J. 2011; 57: 1302-9.

Nguyen D, Bagajewicz M. Efficient Approximate Methods for the Design and Upgrade of Sensor Networks. Ind. Eng. Chem. Res. 2013; 52: 83-90.

Kelly JD, Zyngier D. A new and improved MILP formulation to optimize observability, redundancy and precision for sensor network problems. AIChE J. 2008; 54: 1282-92.

Extended Abstract: File Not Uploaded
See more of this Session: Interactive Session: Systems and Process Control
See more of this Group/Topical: Computing and Systems Technology Division