A Wasserstein distance based multiobjective evolutionary algorithm for the risk aware optimization of sensor placement
In this paper we propose a new algorithm for the identification of optimal “sensing spots”, within a network, for monitoring the spread of “effects” triggered by “events”. This problem is referred to as “Optimal Sensor Placement” and many real-world problems fit into this general framework. In this...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2021-07-01
|
| Series: | Intelligent Systems with Applications |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2667305321000363 |
| _version_ | 1818247319102947328 |
|---|---|
| author | Andrea Ponti Antonio Candelieri Francesco Archetti |
| author_facet | Andrea Ponti Antonio Candelieri Francesco Archetti |
| author_sort | Andrea Ponti |
| collection | DOAJ |
| description | In this paper we propose a new algorithm for the identification of optimal “sensing spots”, within a network, for monitoring the spread of “effects” triggered by “events”. This problem is referred to as “Optimal Sensor Placement” and many real-world problems fit into this general framework. In this paper sensor placement (SP) (i.e., location of sensors at some nodes) for the early detection of contaminants in water distribution networks (WDNs) will be used as a running example. Usually, we have to manage a trade-off between different objective functions, so that we are faced with a multi objective optimization problem. (MOP). The best trade-off between the objectives can be defined in terms of Pareto optimality. In this paper we model the sensor placement problem as a multi objective optimization problem with boolean decision variables and propose a Multi Objective Evolutionary Algorithm (MOEA) for approximating and analyzing the Pareto set.The evaluation of the objective functions requires the execution of a simulation model: to organize the simulation results in a computationally efficient way we propose a data structure collecting simulation outcomes for every SP which is particularly suitable for visualization of the dynamics of contaminant concentration and evolutionary optimization.This data structure enables the definition of information spaces, in which a candidate placement can be represented as a matrix or, in probabilistic terms as a histogram.The introduction of a distance between histograms, namely the Wasserstein (WST) distance, enables to derive new genetic operators, indicators of the quality of the Pareto set and criteria to choose among the Pareto solutions. The new algorithm MOEA/WST has been tested on two benchmark water distribution networks and a real world network. Preliminary results are compared with NSGA-II and show a better performance, in terms of hypervolume and coverage, in particular for relatively large networks and low generation counts. |
| first_indexed | 2024-12-12T15:02:49Z |
| format | Article |
| id | doaj.art-df8c81974e3343baa2150b73eb01a500 |
| institution | Directory Open Access Journal |
| issn | 2667-3053 |
| language | English |
| last_indexed | 2024-12-12T15:02:49Z |
| publishDate | 2021-07-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Intelligent Systems with Applications |
| spelling | doaj.art-df8c81974e3343baa2150b73eb01a5002022-12-22T00:20:47ZengElsevierIntelligent Systems with Applications2667-30532021-07-0110200047A Wasserstein distance based multiobjective evolutionary algorithm for the risk aware optimization of sensor placementAndrea Ponti0Antonio Candelieri1Francesco Archetti2University of Milano-Bicocca, Department of Computer Science, Systems and Communication, Italy; Corresponding author.University of Milano-Bicocca, Department of Economics, Management and Statistics, ItalyUniversity of Milano-Bicocca, Department of Computer Science, Systems and Communication, ItalyIn this paper we propose a new algorithm for the identification of optimal “sensing spots”, within a network, for monitoring the spread of “effects” triggered by “events”. This problem is referred to as “Optimal Sensor Placement” and many real-world problems fit into this general framework. In this paper sensor placement (SP) (i.e., location of sensors at some nodes) for the early detection of contaminants in water distribution networks (WDNs) will be used as a running example. Usually, we have to manage a trade-off between different objective functions, so that we are faced with a multi objective optimization problem. (MOP). The best trade-off between the objectives can be defined in terms of Pareto optimality. In this paper we model the sensor placement problem as a multi objective optimization problem with boolean decision variables and propose a Multi Objective Evolutionary Algorithm (MOEA) for approximating and analyzing the Pareto set.The evaluation of the objective functions requires the execution of a simulation model: to organize the simulation results in a computationally efficient way we propose a data structure collecting simulation outcomes for every SP which is particularly suitable for visualization of the dynamics of contaminant concentration and evolutionary optimization.This data structure enables the definition of information spaces, in which a candidate placement can be represented as a matrix or, in probabilistic terms as a histogram.The introduction of a distance between histograms, namely the Wasserstein (WST) distance, enables to derive new genetic operators, indicators of the quality of the Pareto set and criteria to choose among the Pareto solutions. The new algorithm MOEA/WST has been tested on two benchmark water distribution networks and a real world network. Preliminary results are compared with NSGA-II and show a better performance, in terms of hypervolume and coverage, in particular for relatively large networks and low generation counts.http://www.sciencedirect.com/science/article/pii/S2667305321000363Sensor placementWater networkMulti objective optimizationEvolutionary optimizationWasserstein distance |
| spellingShingle | Andrea Ponti Antonio Candelieri Francesco Archetti A Wasserstein distance based multiobjective evolutionary algorithm for the risk aware optimization of sensor placement Intelligent Systems with Applications Sensor placement Water network Multi objective optimization Evolutionary optimization Wasserstein distance |
| title | A Wasserstein distance based multiobjective evolutionary algorithm for the risk aware optimization of sensor placement |
| title_full | A Wasserstein distance based multiobjective evolutionary algorithm for the risk aware optimization of sensor placement |
| title_fullStr | A Wasserstein distance based multiobjective evolutionary algorithm for the risk aware optimization of sensor placement |
| title_full_unstemmed | A Wasserstein distance based multiobjective evolutionary algorithm for the risk aware optimization of sensor placement |
| title_short | A Wasserstein distance based multiobjective evolutionary algorithm for the risk aware optimization of sensor placement |
| title_sort | wasserstein distance based multiobjective evolutionary algorithm for the risk aware optimization of sensor placement |
| topic | Sensor placement Water network Multi objective optimization Evolutionary optimization Wasserstein distance |
| url | http://www.sciencedirect.com/science/article/pii/S2667305321000363 |
| work_keys_str_mv | AT andreaponti awassersteindistancebasedmultiobjectiveevolutionaryalgorithmfortheriskawareoptimizationofsensorplacement AT antoniocandelieri awassersteindistancebasedmultiobjectiveevolutionaryalgorithmfortheriskawareoptimizationofsensorplacement AT francescoarchetti awassersteindistancebasedmultiobjectiveevolutionaryalgorithmfortheriskawareoptimizationofsensorplacement AT andreaponti wassersteindistancebasedmultiobjectiveevolutionaryalgorithmfortheriskawareoptimizationofsensorplacement AT antoniocandelieri wassersteindistancebasedmultiobjectiveevolutionaryalgorithmfortheriskawareoptimizationofsensorplacement AT francescoarchetti wassersteindistancebasedmultiobjectiveevolutionaryalgorithmfortheriskawareoptimizationofsensorplacement |