Overview
Description and rationale
Insight is eWater’s multiple-objective optimisation decision support framework. This framework allows for more efficient evaluation of planning options than the traditional manual trial and error approach that modellers often use. The optimisation tool enables a more thorough examination of potential planning scenarios and the resulting trade-offs between desired outcomes.
...
Insight operates at the spatial and temporal scales of Source models. It runs Source models multiple times to search for optimal solutions.
Principal developer
The multi-objective optimiser used in Insight was developed by Deb et al (2002). It was originally adapted for use with Source by eWater CRC with permission.
Insight was originally developed by eWater CRC and has subsequently been enhanced by eWater Ltd to meet the needs of the Melbourne Water Corporation.
Scientific Provenance
The multi-objective optimiser used in Insight is the Non-dominated Sorting Genetic Algorithm II (NSGA-II) developed by Deb et al (2002). This is a Multi-Objective Evolutionary Algorithm (MOEA) that is based on the principles of the well known Genetic Algorithm (GA).
Version
Source v3.8.8.
Dependencies
Insight requires a functioning Source model to work with.
Availability/conditions
Use this heading if the functionality is a plugin or requires any 3rd party software applications.
Structure & processes
Theory of NSGA-II
Details of the derivation of the Non-dominated Sorting Genetic Algorithm II (NSGA-II), including pseudo-code, are available in Deb et al (2002). NSGA-II is a variant of the well known Genetic Algorithm (GA) and the principles of the GA are discussed in text books (e.g. Loucks and van Beek, 2005).
...
- A fast non-dominated sorting approach. This is used to find population members in the best, second best, third best, etc., non-domination levels.
- Diversity preservation based on a crowded distance estimation procedure and a crowded comparison operator. This approach does not require any user-defined parameter for maintaining diversity among population members.
A computational algorithm summarised as follows:
Initially create a random parent population, P1 of size N and sort this population using the fast non-dominated sorting approach.
Use binary tournament selection, recombination (crossover) and mutation operators, to create the first offspring population, Q1, of size N.
Noting that elitism is introduced by comparing the current population with previously found non-dominated solutions then the procedure after the initial generation can be summarised by considering the i’th generation:
- Create a combined population Ri = Pi U Qi, where Ri has size 2N, and sort this combined population using the fast non-dominated sorting approach.
- Start assembling a new population Pi+1 of size N. The assembly process begins by including solutions at the best non-dominated level. If the number of these is less than N then they are all included. This process continues with solutions from the second best, etc. levels as long as all the solutions from these levels can be included (i.e. the combined total of these solutions is less than N). For the last level (i.e. the one where not all solutions can be included to make up the numbers to N), the solutions are sorted using the crowded comparison operator to identify the best ones to include in the new population.
- The new population Pi+1 is used for selection, crossover and mutation to create a new offspring population Qi+1 of size N. For selection a binary tournament selection operator is used but the selection criterion is now based on the crowded comparison operator.
Definitions
Decision variables | The management levers which can be pulled in order to achieve the required objectives. Each decision variable must be defined as a global expression, with an allowable range of values it can take. |
Dominated solution | When comparing results from two Source runs (or group of runs), ‘A’ and ‘B’, Insight will treat ‘A’ as a “dominated solution” only if it is clearly inferior to ‘B’; that is, if ‘B’ performs better than ‘A’ on at least one of the statistics and there is no statistic where ‘A’ performs better than ‘B’. In this case ‘B’ is a “non-dominated solution” and is a potential candidate for the Pareto front of optimal solutions (e.g. see Figure 1). |
Generation | For each generation the decision variables are subject to selection, crossover and mutation. The number of generations is specified by the modeller. |
Individual | A solution obtained from a single run of Source with a given set of decision variable values (an individual is a group of runs when multiple scenarios are being investigated: one run for each scenario). |
Non-dominated solution | See definition of “dominated solution”. |
Objective function | Mathematical expression of the objectives required to be achieved (e.g. minimising the operating cost of the system, maximising environmental benefits, or minimising time spent in water restrictions). Objective Functions are set up as global expressions within Source. Note that only the value of the expression at the last time step is used for evaluating the objective function. Therefore, expressions should be defined in such a way that the value at the last time step of the simulation is the value that represents the required statistic for the entire simulation period. |
Population | The number of possible feasible solutions to be derived by changing decision variable values (within their value constraints) in Insight and running Source. The population size is specified by the modeller and is equal to the total number of individuals. |
Insight Functionality
User requirements are summarised in Table 1. Interactions between Insight and Source are shown in Figure 2.
Table 1. User requirements
Item number | Prioirity | Short description of task |
---|---|---|
1 | 1 | Allow optimisation over multiple scenarios |
2 | 4 | Suitable output for multi-replicate runs |
3 | 4 | A tool for analysing results from multi-replicate output |
4 | 6 | Allow sub-models of Source with different time steps |
5 | 5 | User-customisable water balance report |
6 | 1 | Allow objective functions to be a range of statistics |
7 | 3 | Insight to report the values of secondary objective functions |
8 | 2 | Pass user-selected decision variables from Insight to Source |
9 | 7 | Implement climate/component flexible restriction modelling |
10 | 8 | Allow 2-way flow |
11 | 9 | Implement sub-networks |
12 | 10 | Link models with different time steps, e.g. Urban Developer |
13 | 11 | Enable switching between rules-based and NetLP |
14 | 12 | Recycling of n years of historical data |
A single scenario in a Source model could represent a particular system configuration, inflow sequence, demand model, etc. Insight can optimise the decision variable(s) (DVs) over multiple scenarios. The DVs and objective functions are chosen by the modeller.
...
The functionality listed in Table 1 is all concerned with input and output data handling and how Insight and Source interact, and there is no new science involved. Therefore, the functionality in Insight is not discussed further here and reference should be made to the Insight: Objective optimisation for information on how to use it.
Process
(Also refer to Figure 2)
1st generation
...
- Insight processes decision variables and objective functions using the procedure described in the first two bullet points in Step 3(c) in the section on Theory of NSGA-II to create anew population (Pi+1). When comparing results from two Source runs (or group of runs), ‘A’ and ‘B’, Insight will treat ‘A’ as a “dominated solution” only if it is clearly inferior to ‘B’; that is, if ‘B’ performs better than ‘A’ on at least one of the statistics and there is no statistic where ‘A’ performs better than ‘B’. In this case ‘B’ is a “non-dominated solution” and is a potential candidate for the Pareto front of optimal solutions (e.g. see Figure 1).
- Values of each decision variable from the new population (Pi+1) are used for selection, crossover and mutation by Insight (i.e. the third bullet point in Step 3(c) in the section on Theory of NSGA-II) to create a new offspring population (Qi+1) of decision variables. The resultant values of decision variables are passed to Source.
- Source is run for each individual (or group of runs when multiple scenarios are being investigated).
- Values of objective functions and result variables needed for evaluating statistical objective functions are passed back from Source to Insight at the end of the run(s) for each individual.
- Insight processes decision variables and objective functions from the current and previous generations (i.e. repeats Step 1 above), searching for “dominated solutions” and “non-dominated solutions”.
- If all generations have been run, the resultant set of “non-dominated solutions” is the final set and is the Pareto front of optimal solutions. Otherwise the process repeats Steps 2-5 above.
Data
Input data
At a minimum, Insight requires the following information to run an optimisation:
...
More details on data are provided in the Source User Guide.
Parameters
Parameter | Description | Units | Default | Range |
---|---|---|---|---|
Population (N) | Number of individuals (i.e. sample size) in each generation. | none | none | Should be sufficiently large to enable statistically meaningful results to be obtained (e.g. 8 ≤ N ) but not so large that the additional samples contribute very little to finding the optimal solution set. |
Generations (ng) | Governs the number of times decision variables are to be subject to selection, crossover and mutation processes. | none | none | 1< ng but ng should not be so large that the later generations contribute very little to finding the optimal solution set. |
Output data
Outputs include values of decision variables and objective functions for each individual for each generation, to enable viewing in graphical displays and tables and further processing. The graphical displays include a plot that is updated after each individual is run in Source which shows the progressive development of the Pareto Front.
...
- Export to a separate file modeller selected time series selected by replicate number and/or item. This file has same format as above.
Reference list
Blackmore, J. M., Dandy, G. C., Kuczera, G. and Rahman, J. (2009). Making the most of modelling: a decision framework for the water industry. In 18th World IMACS / MODSIM International Congress on Modelling and Simulation, edited by R. S. Anderssen, et al. Cairns, Australia: Modelling and Simulation Society of Australia and New Zealand and International Association for Mathematics and Computers in Simulation.
...