- Email: [email protected]

IFAC

~

Pu blications www.elsevier.comllocatelifac

MULTI-oBJECTIVE SENSOR NETWORK DESIGN USING GENETIC ALGORITHMS Viswanath, A. and Sbankar Narasimban Chemical Engineering Department, Indian Institute ojTechnology, Madras Chennai, India - 600036

Abstract: The selection of variables to be measured in a process, has to be made considering various objectives such as cost, observability and redundancy requirements, estimation accuracy, controllability and safety. Although, this multi-objective sensor network design problem can be formulated as a mixed integer nonlinear optimization problem, it requires special enumeration techniques for solution. In this work a Genetic Algorithm approach is proposed, which can be used to find designs that satisfy imposed limits on different objectives or to find Pareto-optimal solutions. Copyright Cl 2001 IFAC Keywords: Sensor systems, Genetic algorithms, Multiobjective optimization, Observability, Redundancy 1. INTRODUCTION

algebra or graph theory. Later Bagajewicz (1997) proposed a mixed integer non-linear optimization problem formulation for sensor network design simultaneously considering several different objectives. Since measures such as estimation accuracy and reliability cannot be written as an explicit algebraic function of the sensor network design, an implicit enumeration technique was proposed by Bagajewicz (1997). A genetic algorithm approach was also proposed by Sen et al. (1998) for this purpose which, however, is limited to only one objective and non-redundant sensor network design. Furthermore, the genetic operators were designed using graph theoretic principles and are specific to the type of objective function chosen.

The selection of variables to be measured in a plant, also referred to as the sensor network design, is usually undertaken during the design phase when the piping and instrwnentation diagram (P&ID) is developed. Generally, the measured variables are selected based on past experience to meet control and safety objectives. However, the sensor network also has an important impact on several data processing activities such as data reconciliation, process monitoring, and fault diagnosis. Increasingly, greater importance is being given to these issues when a sensor network is designed. Several different measures have been proposed to judge the quality of a sensor network design, such as observability, estimability, estimation accuracy, resilience and error detectability (Bagajewicz, 1997; Bagajewicz and Sanchez, 1999), reliability and availability (Ali and Narasimhan, 1993; Maquin et al. 1996; Bagajewicz, 1997). In addition, it is also necessary to consider the cost of the sensor network. Thus, the simultaneous consideration of these different objectives makes the sensor network design a multi-objective optimization problem.

In this paper, a general purpose genetic algorithm (GA) is proposed for sensor network design of linear (flow) processes by simultaneously considering several objectives. The proposed approach can be used to design both non-redundant and redundant sensor networks.

2. PROBLEM REPRESENTATION AND GA OPERATORS

The first algorithms for sensor network design considered a single objective such as observability (Vaclavek, 1976), cost (Madron and Veverka, 1992), estimation accuracy (Kretsovalis and Mah, 1987) or These reliability (Ali and Narasimhan, 1993). algorithms were developed either using matrix

In GAs, the problem solutions are usually coded using binary strings and crossover and mutation operators are applied on them (Goldberg, 1989). However, as pointed out by Sen et al. (1998), a simple binary string representation of sensor network design solution will not be adequate, since some

233

necessary structmal properties of the network will not be preserved during cross-over and mutation operations. For example, in simple flow processes, the streams whose flows are unmeasured should not form loops, to ensure observability of all variables. Sen et al. (1998) resolved this problem by designing GA operators for crossover and mutation using graph theoretic operations, which preserve the necessary structmal properties. However, their solution is limited to the design of non-redundant sensor networks and applicable only for optimizing a single objective. In applying GAs to solve combinatorial problems such as the travelling salesman problem (TSP), the structmal property of a closed tour needs to be preserved in order to obtain feasible solutions using crossover and mutation operators. In these problems, the solution is represented by a string of random numbers and GA operators are applied to these random number strings. The random number strings are suitably interpreted to give feasible solutions. As illustrated by Chatterjee et al. (1996), this representation has been used for various combinatorial optimization problems such as job shop scheduling, multiple choice integer progranuning, and task allocation. In the proposed method, the above representation is exploited and suitable modifications are made for decoding the solutions, such that multiple objectives can be handled.

2.1 Decoding ojSo/utions Consider the sensor network design of a simplified ammonia network process shown in Fig. I. Further, consider a sequence of random numbers equal to the number of streams in the process, 17-80-70-69-4382-16-51, with the first random number in this sequence corresponding to the edge numbered one, and so on. This sequence can be decoded to obtain a feasible sensor network design satisfying imposed constraints as follows. We will assume initially that all the flows are measured and temporarily delete the flow sensor corresponding to the least random number in this sequence. If the deletion does not violate any of the imposed constraints, then the deletion is accepted. Otherwise, the sensor is not deleted and we attempt to delete the sensor corresponding to the next lowest random number. We continue in this manner until we cannot delete any more sensors without violating one of the imposed constraints. The resulting solution is the decoded feasible solution corresponding to the random number sequence. The constraints imposed, can be the observability of all the important variables, maximum allowable estimation inaccuracy, or maximum number of sensors etc. For example, if we impose only the constraint that all variables should be

2

Fig. I. Simplified Ammonia Process Graph observable, then the decoded solution corresponding to the above random number sequence is to measure flows of streams 2, 4, and 6. In order to handle multiple objectives, we propose to use one of them, such as cost as an objective and formulate the others as constraints by imposing either upper or lower bounds on them. It should be noted that if we are unable to obtain a decoded solution, which can satisfy all the constraints, then it implies that there are no feasible solutions and it is necessary to relax one or more constraints.

2.2 Genetic Operators Based on the criterion chosen as the objective function, the tournament selection operator (Deb, 1995), is used to select a population for reproduction in our implementation. A two-point crossover operator is used for reproduction. In this crossover operator, two positions are randomly chosen in the strings representing the parent solutions, and the respective sequences between these positions are interchanged to obtain the two offspring. For example, consider the solutions represented by the two random number sequences 17-80-70-69-43-8216-51 and 81-58-47-62-79-11-10-78. If the crossover positions are 5 and 7, the offspring obtained will correspond to the random number sequences 17-8070-69-43-11-10-51 and 81-58-47-62-79-82-16-78. If the only constraint imposed is that of observability of all variables, then the decoded solutions of the parents are the sensor networks corresponding to measured sets [2, 4, 6], and [1, 5, 8], respectively. The solutions corresponding to the offspring are the measured sets [2, 4, 8], and [1, 5, 6], respectively. The mutation operator is implemented by exchanging the random numbers between any two randomly chosen positions in the string. Note that using the above problem representation and decoding method, it is possible to consider any number of objectives such as reliability, accuracy, availability as long as upper or lower limits can be prescribed to convert them into constraints.

234

Table I. Parameters for applying GA Parameter Population size Number of generations Tournament group size Crossover probability Mutation Probability

Steam Metering .Network 40 20

HDA process

5

5

0.97

0.97

0.3

0.3

25 15

3. RESULTS AND DISCUSSION

3.1 Design of non-redundant, observable, minimum cost sensor networks

Fig. 2. HDA Process Graph.

As a simple test, the proposed methodology was applied to the design of minimum cost non-redundant sensor networks. It is well known that a maximumweight spanning tree of the process graph gives the least cost non-redundant sensor network. The steam metering network along with the cost data given in Sen et al. (1998), is used as the test example. The parameters used in the genetic algorithm are given in the second column of Table 1. The proposed method was applied using cost as the objective and imposing the constraint that all variables should be observable. Note that by imposing this constraint, our proposed method will implicitly examine solutions corresponding to spanning trees of the process graph in every generation.

Table 2. Sensor Data for HDA Process Stream I 2 3 4 5 6 7 8 9 10 11 12 13 14

As reported by Sen et al. (1998), the unique global optimal solution for this process corresponds to the measured set [1,2,7,9,10,11,16-24,27,28], that has a cost of 555.46. More than 500!o of the final population generated by the proposed GA corresponded to the optimal solution. It should be noted that the number of non-redundant feasible sensor networks for this process is 1,243,845 (Ali and Narasimhan, 1993). The proposed GA examined less than 0.05% of these solutions in order to obtain the optimum.

Cost 3.7 4.5 132.2 129.2 65.3 132.4 5.0 193.9 2.06 62.8 20.2 80.2 130.0 109.8

Inaccuracy 0.04 0.76 0.92 0.47 0.79 0.21 0.12 0.20 0.18 0.21 0.12 0.52 0.29 0.16

The GA was also required to be observable. implemented using cost as the objective to be minimized and the parameters are chosen as shown in the last column of Table 1. It should be noted that the solutions in any population could correspond to either redundant or non-redundant sensor network designs. The least cost solution obtained by the GA corresponds to the measured set [1,2,6,7,9,10,11,12], which has a cost of 310.66. If this cost is more than what is acceptable to the design engineer, then the upper bound on the inaccuracy can be relaxed to find a lower cost solution. Besides the least cost solution satisfying the inaccuracy limit, the final population may also contain other solutions, that have acceptable cost while satisfying the limit on inaccuracy.

3.2 Multi-objective sensor network design The design of a sensor network for the HDA process shown in Fig. 2, considering cost and overall estimation inaccuracy as objectives to be minimized is considered. The cost and inaccuracy of the sensors (expressed as the standard deviation of measurement error) data for this process are shown in Table 2. The measure of overall estimation accuracy proposed by Kretsovalis and Mah (1987) was used. The proposed GA was applied using an upper bound of 5 on estimation accuracy. Furthermore, all variables were

If all Pareto optimal solutions satisfying an upper limit of 5 on estimation inaccuracy and 400 on cost are desired for the above process, then the proposed GA can be applied repeatedly in the following

235

5. REFERENCES

Table 3. Pareto-ootimal Solutions obtained using GA Run 1 2 3 4

Measured Set 1,2,6,7,9,10, 11,12 1,7,9,10,11, 13,14 1,2,7,9,10,11, 13,14 1,2,6,7,9,10, 11,13

Cost 310.66

Inaccuracy 4.89

333.96

4.75

338.46

4.22

361.06

3.82

manner. The GA is first run with the given inaccuracy limit and the least cost solution is obtained. This solution has a cost of 310.66, and an inaccuracy of 4.89. In the next run of the GA, an upper limit of 4.89 on inaccuracy is imposed as a strict inequality, and a new least cost solution is obtained. This method is repeated until the least cost solution in a particular run is greater than 400. If it is assumed that the GA is successful in finding the minimum cost solution in every run, then the set of Pareto-optimal solutions correspond to the least cost solutions obtained in the different runs. Table 3 shows the least cost solutions obtained using this method. It was verified by complete enumeration of all sensor network solutions for this problem that the GA was successful in obtaining all the four Paretooptimal solutions satisfying the imposed limits.

Ali, Y., and S. Narasimhan (1993). Sensor Network Design for Maximizing Reliability of Linear Processes. AlChE J., 39, 820-828. Bagajewicz, M. J. (1997). Design and Retrofit of Sensor Networks in Process Plants. AIChE J., 43, 2300-2306. Bagajewicz, M. J., and M. C. Sanchez (1999). Design and Upgrade of Nonredundant and Redundant Linear Sensor Networks. AIChE J., 45,1927-1937. Kretsovalis, A. and R. S. H. Mah (1987). Effect of Redundancy and Estimation Accuracy in Process Data Reconciliation. Chem. Engng. Sci., 42, 21152121. Maquin, D., M. Luong, and J. Ragot (1996). About the Design of Measurement Systems and Fault Accomodation. Engineering Simulation, 13, 10091024. Madron, F. and V. Veverka (1992). Optimal Selection of Measuring Points in Complex Plants by Linear Model. AlChE J., 38, 227-236. Sen, S., S. Narasimhan, and K. Deb (1998). Sensor Network Design of Linear Processes using Genetic Algorithms. Comput. Chem. Engngg. 22, 385-390.

4. CONCLUSIONS

Chatterjee, S., C. Carrera, L. A. Lynch (1996). Genetic algorithms and travelling salesman problems. European Journal for Operational Research, 93, 490-510.

In this study, a generalized GA has been developed for non-redundant and redundant sensor network designs of flow processes, considering multiple objectives. The proposed GA can also be used to find Pareto-optimal points.

Deb, K.., (1995). Optimization for Engineering Design, Prentice Hall of India, New Delhi. Goldberg, D.E., (1989). Genetic algorithms in Search, Optimization and Machine Learning, Addison Wesley, Massachusetts.

236