Microsoft Word - 425simasatitkul.doc CHEMICAL ENGINEERING TRANSACTIONS VOL. 74, 2019 A publication of The Italian Association of Chemical Engineering Online at www.cetjournal.it Guest Editors: Sauro Pierucci, Jiří Jaromír Klemeš, Laura Piazza Copyright © 2019, AIDIC Servizi S.r.l. ISBN 978-88-95608-71-6; ISSN 2283-9216 Hybrid Simulated Annealing for Optimal Cost Instrumentation in Chemical Plants José Hernándeza*, Carolina Saltob, Gabriela Minettib, Mercedes Carneroa, Mabel Sánchezc aGrupo de Optimización - Facultad de Ingeniería – Universidad Nacional de Río Cuarto, Rio Cuarto, Argentina bLaboratorio de Investigación en Sistemas Inteligentes (LISI) - Facultad de Ingeniería - Universidad Nacionalde La Pampa– General Pico, Argentina cDepartamento de Ingeniería Química, Universidad Nacional del Sur (UNS) and Planta Piloto de Ingeniería Química - PLAPIQUI (UNS-CONICET), (8000) Bahía Blanca, Argentina jlh@ing.unrc.edu.ar Process information is the foundation upon which many common tasks in chemical plants are based. To satisfy information requirements regarding its quality and availability, it is essential to locate an appropriate set of instruments or sensor network (SN) in the plant. The SN designer should decide whether to measure each process variable or not. These decisions are mathematically formulated in terms of binary variables. This results in a combinatorial optimization problem that usually involves many decision binary variables and exhibits multiple solutions locally or globally optimal. In this work, a metaheuristic based on simulated annealing hybridized with strategic oscillation, named HSA_SOTS, is proposed to solve the tackled problem. The performance of HSA_SOTS is evaluated considering several high scale designs with increasing complexities. The results of this metaheuristic outperform the ones presented in the literature. 1. Introduction The main activities in a chemical plant, such as monitoring, control, optimization, planning and scheduling, fault diagnosis, among others, are based on the process information given by the key process variables. A process in this kind of plants is usually depicted by hundreds of variables, and only a limited number of these variables can be measured, owing to the nature of the process and the cost of measurement. To satisfy the information requirements regarding its quality and availability, it is essential to locate an appropriate set of instruments or sensor network (SN) in the plant. The selection of the set of variables to be measured, which is optimal with respect to the specified criteria and simultaneously satisfies the information requirements, is called the sensor network design problem (SNDP). The SN designer should decide whether to measure each process variable or not. These decisions are mathematically formulated in terms of binary variables. Consequently, the result is a combinatorial optimization problem that is usually multimodal and involves many binary variables. This type of problems is tackled using exact methods like tree search algorithms (Nguyen and Bagajewicz, 2011), that uses intelligent forms of exploration by defining appropriate levels and stop criteria. Other approaches have formulated the problem as a mixed integer nonlinear programming problem (MINLP) (Kelly and Zyngier, 2008), and they have solved it using a branch and bound or branch and cut algorithms. Different methodologies based on metaheuristic algorithms can be found in the literature to solve SN design problem. Bio-inspired strategies such as Genetic Algorithms (GAs) enhanced with local search (Carnero et al., 2005), parallel GAs (Gerkens and Heyen, 2005), Ant Colony (He and Ma, 2014), and Bee Colony optimization algorithms are used for single or multiobjective problems. The applicability of a metaheuristic approach, called PBIL_SOTS, to solve SNDP has been studied (Carnero et al., 2013). PBIL_SOTS is based on the Estimation of Distribution Algorithms (EDA) and the use of a strategy within the framework of Tabu Search (TS) that used DOI: 10.3303/CET1974119 Paper Received: 30 June 2018; Revised: 13 December 2018; Accepted: 28 April 2019 Please cite this article as: Hernandez J., Salto C., Minetti G., Carnero M., Sanchez M.C., 2019, Hybrid Simulated Annealing for Optimal Cost Instrumentation in Chemical Plants, Chemical Engineering Transactions, 74, 709-714 DOI:10.3303/CET1974119 709 a strategic oscillation (SO) technique called SOTS. This algorithm works adding and removing measures in such way to allow the search crosses the feasibility boundary and continues in the infeasible region until certain depth. It showed a rewarding performance when it was compared with other algorithms (Carnero et al., 2018). Among the less studied metaheuristics to solve the problem at hand is the Simulated Annealing (SA), a simple, general purpose Monte-Carlo method, which was developed for combinatorial optimization (Kirkpatrick and Vecchi, 1983). In contrast with the population-based metaheuristics aforementioned, it may be classified into the trajectory-based group and it has proved to be an efficient method to solve many hard combinatorial optimization problems (Talbi, 2009). The aim of this work is to solve the SN where the objective is to minimize the overall cost of instrumentation for a process plant subject to observability and precision constraint over a set of key variables using a SA algorithm hybridized with a subordinate heuristic based on TS. A comparison with other methods and numerical results of tests on several instances are given, and the effectiveness of the proposed method is analyzed. The rest of this article is organized as follows. In Section 2 the SNDP is described. Section 3 introduces and explains the approach proposed in this work. Section 4 refers to the experimental analysis and the methodology used. Then, a study and analysis of the results obtained are presented. Finally, the main conclusions and future lines of research are drawn in Section 5. 2. Sensor network design problem The SNDP is summarized as a problem of finding the minimum cost network that satisfies precision and estimability constraints. Formally, an SNDP solution has to satisfy these constraints for a set of key variable estimates, as stated by Eq(1), where q is an n-dimensional vector of binary variables such that qi = 1 if variable i is measured, and qi = 0 otherwise, cT is the cost vector; k is the estimate standard deviation of the k-th variable contained in Sσ after a data reconciliation procedure is applied, and El stands for the degree of estimability of the l-th variable included in SE. Furthermore, Sσ and SE are the set of key process variables with requirements in precision and ability to be estimated, respectively: { } k k l E n k S E l S * min s.t. ˆ ( ) ( ) ( ) 1 0,1 σσ σ≤ ∀ ∈ ≥ ∀ ∈ ∈ Tc q q q q q (1) In this formulation, there is only one potential measuring device for each variable, and there are no restrictions for the localization of instruments. The feasibility of the constraints can be checked by executing a variable classification and data reconciliation procedure (Romagnoli and Sánchez, 2000). 3. Proposal approach to solve the SNDP in chemical plants SA is a simple trajectory-based metaheuristics (Kirkpatrick and Vecchi, 1983), which is based on a thermal process for obtaining low energy states of a solid in a heat bath. At the beginning, with a high initial temperature, T0, SA accepts solutions with high cost values under a certain probability determined by the Boltzmann distribution in order to explore the search space and escape from local optima. During the annealing process, this probability decreases according to temperature cooling, intensifying the search and re enforcing the exploitation of a restricted area within the space of solutions. SA evolves by a sequence of transitions between states and these transitions are generated by transition probabilities. Consequently, SA can be mathematically modelled by finite Markov chains where a sequence of chains of length MCL is generated by a transition probability, which is calculated involving the current temperature, T. In this work, an adapted and hybridized SA algorithm to solve the SNDP in chemical plants is proposed. SA works as main heuristics with a subordinated local search designed ad-hoc, the SOTS technique, giving rise to the Hybrid Simulated Annealing (HSA_SOTS) algorithm. HSA_SOTS uses an n-dimensional vector of binary variables, q={q1, q2, ..., qn}, as an SNDP solution, where each variable qi = 1 if the variable i is measured, and qi= 0 otherwise, as is explained in Section 2. In order to evaluate a solution, the Eq(2) is used as an objective function, where 1 n i i ic q= is the upper bound of the SNDP objective function. When constraints are not satisfied, the Eq(3) computes S( )q , where rno and rnp stand for the number of unsatisfied observability and precision constraints for a solution vector q. 710 n i i i n i i c q if is feasible H c S if is infeasible 1 1 (1 ( )) = =  =   +   q q q (2)   rnp i i i iE rno S S rnp *1 ( ) # σ σ σ −= + q (3) The hybridization in HSA_SOTS is applied in two levels: in the first one to generate an initial solution, and in the second level to improve the solution during the annealing process, as is shown in Figure 1. In order to create an initial solution, three steps are followed: i) a uniform random vector q0 is generated, ii) q0 is improved using a specific-heuristic proposed in Carnero et al. (2013), and finally iii) q0 is enhanced by the application of the SOTS technique, which is a local search algorithm introduced in Carnero et al. (2013).The second hybridization level is carried out during the annealing process in two steps. First, an alternative solution q1 is generated by applying SOTS over q0, under a certain probability (called Pso). Finally, q0 is replaced by q1 if the Boltzmann criterion is satisfied. The perturbation scheme of the current solution is carried out through a certain swapping number of measured variables to unmeasured ones and vice versa in order to generate a candidate solution q2 from q0. This swap mutation is applied over each variable with a certain probability (called Pswap). Furthermore, the temperature is updated using the geometric criterion (Du and Swamy, 2016). t = 0; T0=init_temp(Ts) initialize T=T0; {temperature} generate q0 by means of the first hybridization level; evaluate q0 in H0; Repeat Repeat t = t + 1; {begin of the second hybridization level} If random(0,1) random(0,1)) q0= q1; H0=H1; end end {end of the second hybridization level} generate q2 from q0 applying the Swap mutation under Pswap; evaluate q2 in H2; {Boltzmann criterion to accept a new solution} If (H2 random(0,1)) q0= q2; H0=H2; end until (t mod MCL) == 0 update T; until stop criterion is met Return q0; Figure 1: Pseudocode of HSA_SOTS Algorithm to solve the SNDP The initial temperature is obtained by the procedure shown in Figure 2. Output T0 is determined such that, when applying the Boltzmann criterion, worse solutions are accepted with a high probability value. To achieve this, the algorithm starts from a Ts seed temperature that is iteratively increased until the aforementioned acceptance is reached. 711 Function init_temp(Ts) initialize T0 = Ts; while (acceptability rate is not reached) Increment T0; generate a solution q1 ; evaluate q1 in H1 for i=0 to test generate a new solution q2from q1 applying Swap mutation under Pswap; evaluate q2 in H2; Apply Boltzmann criterion and count solutions that was accepted; end end return T0; Figure 2: Pseudocode of algorithm for setting initial temperature T0 4. Experimentation and results In order to evaluate HSA_SOTS performance, a test set of 5 design problems were considered which comprise processes of different complexity and size and whose operation can be represented by both linear and non-linear models. The first one involves 11 units and 28 streams and two designs of different complexity are considered (named as 1.a and 1.b). Case study 2 is a continuous stirred tank reactor (CSTR) (Bhushan and Rengaswamy, 2000) which is composed of 13 variables (total flow rates, compositions, and temperatures) and 5 mass and energy balances. The mineral flotation problem (Smith and Ichiyen, 1973), MFP, is selected as case study 3, considering two designs of different complexity (named as 3.a and 3.b). Its model is bilinear and composed of 24 variables (8 flow rates and 16 compositions) related by total and component mass balances. For case studies 2 and 3, the model is linearized around the nominal operation point of the process. Finally, case studies 4 and 5 correspond to large-scale process flow sheets, and variables are related by total mass balances (case study 4, 19 units and 52 streams; case study 5, 47 units and 82 streams). The interested readers can gain access to the file containing information about the case studies from https://www.ing.unrc.edu.ar/archivos/sndp_cases.doc. The standard deviation of flow meters is 2.5%, 1%, 2%, 2%, and 2% of the corresponding true flow rates for case studies 1-5, respectively. The complexity of the set of constraints imposed on all case studies can be found in Carnero et al. (2018). The computational environment used in this work to carry out the experimentation consists of computers with Processor Intel Core i5 CPU 4440 @ 3.10 GHz, 4GB RAM, using MatLab R2011b. Because of the stochastic nature of the algorithms, 100 independent runs of each instance were performed to gather meaningful experimental data and statistical confidence metrics were applied to validate the results and conclusions. As a result, a total of 700 executions were carried out. Only for case studies 1.a and 1.b, well-known global optimal values are available. For this reason, a comparison is proposed of the objective function values achieved by SA with the best values obtained by PBIL_SOTS, an algorithm that has been shown to be effective in solving the aforementioned problems (Carnero et al., 2018). Regarding the HSA_SOTS parametric configuration, preliminary experiences were carried out in order to observe how sensitive their behavior was in relation to the values assigned to these parameters. A value of MCL = 30, recommended in the literature, was appropriate in all cases under study. Pswap was set through a growing and bounded function of n, so as to maintain the exploratory efficiency provided by the perturbation operator, as the size of the search space grows. Their values range from 0.03, for the smallest instance, to 0.06 for the instance of 82 variables. A value for Ts equal to 1 gave favorable results for small and medium- sized cases. However, in case 5 it was necessary to experimentally adjust this parameter due to its great incidence on the performance of the algorithm. A set of tests was carried out until the best value of seed Ts = 900 was obtained. The stop criterion adopted is to reach a maximum number of iterations, Maxiter. In order to make a fair comparison between PBIL_SOTS and HSA_SOTS, they must do the same computational effort in each run. This can be achieved if they both generate the same number of solutions in the main metaheuristic, without considering the ones created by subordinate local search (SOTS). In this way, algorithms evolve taking advantage of their own features, until the stop criterion is achieved. Maxiter value is fixed to meet this condition. 712 Next, the quality of the solutions found by HSA_SOTS is analyzed. The set of the best values of evaluation function reached in each experience was compared with those reported in Carnero et al. (2018) using the Kruskal-Wallis (KW) test. This statistical study allows to assess whether or not there were meaningful differences between the compared algorithms with a certain confidence level, α. The results of the test for each of the 7 designs under study are depicted in Table 1. A similar behavior between the algorithms is detected, obtaining the optimal solution for all the case studies. Analyzing the KW column, the statistical test has pointed out that differences are not significant between the algorithms for the six first case studies with a confidence level α=0.01. For these cases, HSA_SOTS found the best solution for all the runs while PBIL_SOTS obtained it in only 5 of them. As a consequence, the standard error, SE, for HSA_SOTS is zero in these experiences, which demonstrates an excellent ability of the method to replicate good solutions in each run. Table 1: Best solution statistics for each case study. Case study Best solution Mean best solution±SE KW PBIL-SOTS HSA_SOTS PBIL-SOTS HSA_SOTS 1.a 752.26 752.26* 752.26±0.00 752,26±0.00 = 1.b 1106.50 1106.50* 1106.50±0.00 1106,46±0.00 = 2 735.00 735.00 735.00±0.00 735,00±0.00 = 3.a 1448.00 1448.00 1448.00±0.00 1448,00±0.00 = 3.b 2928.00 2928.00 2929.20±0.69 2928,00±0.00 = 4 1154.34 1154.34 1154.34±0.00 1154,34±0.00 = 5 50845.16 50845.16 50886.63±41.29 50850,94±1.62 ≠ * Corresponds to the well-known global optimum Concerning case 5, it is interesting to analyze in more detail the distribution of solutions found in the 100 executions performed by HSA_SOTS. As shown in Figure 3, the best cost 50845.16 was obtained in 36% of the times, while a slightly higher value, 50845.37, could be observed in 18% of the runs. Both costs belong to solutions that differ in only three measurements and, from the point of view of cost, they constitute almost identical solutions. The 75th percentile corresponds to a value of 50846.39, while the 99th percentile is located at 50940.34. Although for this larger case HSA_SOTS does not replicate exactly the best value in each execution, it is able to obtain solutions of very high quality and with a standard error even lower than PBIL_SOTS. Figure 3: Best cost distribution HSA_SOTS for case 5 713 Regarding the execution times from Table 2, an important difference between the algorithms is observed: HSA_SOTS needs less execution time than PBIL_SOTS for all the case studies. In average, HSA_SOTS is 6 times faster than PBIL_SOTS, thus, the difference between the hardware used for the experimentation by each algorithm becomes insignificant. Table 2: Execution times (in sec) of PBIL_SOTS and HSA_SOTS for each case study Case study 1.a 1.b 2 3.a 3.b 4 5 PBIL_SOTS 185.38 197.00 117.97 85.86 87.88 610.80 1507.20 HSA_SOTS 25.12 23.27 7.39 18.90 20.08 314.13 960.86 5. Conclusions In this article, an optimization technique based on SA algorithm that can find successful solutions for the SNDP is proposed. This new technique, called HSA_SOTS, combines an SNDP-adapted SA with an SNDP specific local search technique, SOTS. For this study, 7 different instances have been tested to evaluate the robustness and scaling capacity of the proposed methodology. HSA_SOTS presents good exploration capacity due to its feature of accepting, with some probability, worse solutions than the current one while the local search allows a quick convergence towards good solutions. As a result, in all the examples addressed, HSA_SOTS is able to find the best known value or the best value reported in the literature. Since HSA-SOTS is a trajectory algorithm, the computational effort required is significantly lower than those reported for population-type algorithms with which it has been contrasted. This constitutes another of the strengths observed in the proposed method. In future works, the SNDP will be tackled improving the HSA_SOTS by introducing a specific heuristics into the perturbation operator for testing larger dimension instances, as close to real scenarios as possible. Acknowledgments The authors acknowledge the support of Universidad Nacional de Rio Cuarto, Universidad Nacional de La Pampa, Universidad Nacional del Sur and the Incentive Program from MINCyT. The second author is also funded by CONICET. References Bhushan M., Rengaswamy R., 2000, Design of Sensor Network Based on the Signed Directed Graph of the Process for Efficient Fault Diagnosis, Ind. Eng. Chem. Res., 39, 999. Carnero M., Hernández J.L., Sánchez M., 2018, Optimal sensor location in chemical plants using the estimation of distribution algorithms, Industrial & Engineering Chemistry Research, vol. 57(36), 12149– 12164. Carnero M., Hernández J., Sánchez M., 2013, A new metaheuristic based approach for the design of sensor networks, Comput. Chem. Eng. 55, 83. Carnero M., Hernández J., Sánchez M., Bandoni A.,2005, On the solution of the instrumentation selection problem. Industrial and Engineering Chemistry Research, 44, 358–367. Gerkens C., Heyen G., 2005, Use of parallel computers in rational design of redundant sensor networks, Comput. Chem. Eng, 29, 1379-1387. Du Ke-Lin, Swamy M. N. S. (Ed), 2016, Search and Optimization by Metaheuristics, Techniques and Algorithms Inspired by Nature, Springer International Publishing, Switzerland. He Y.J., Ma Z.F, 2014, Optimal Design of Linear Sensor Networks for Process Plants: A Multi-Objective Ant Colony Optimization Approach, Chemometrics and Intelligent Laboratory Systems, 135, 37-47. Kelly J., Zyngier D.,2008, A new and improved MILP formulation to optimize observability, redundancy and precision for sensor network problems, AIChE Journal, 54,1282–1291. Kirkpatrick S., Gelatt C., Vecchi M.P., 1983, Optimization by simulated annealing, Science, 220, 671-680. NguyenD. Q., Bagajewicz M., 2011, New efficient breath-first/level traversal methodology for the design and upgrade of sensor networks, AIChE Journal, 57(5), 1302-1309. Romagnoli J., Sánchez M., 2000, Data Processing and Reconciliation for Chemical Process Operations, Academic Press: San Diego, CA. Smith H. W., Ichiyen, N., 1973, Computer Adjustment of Metallurgical Balances. Can. Znst. Mining Metall Bull. 66, 97-100. Talbi E. G., 2009, Metaheuristics: From Design to Implementation, Wiley. 714