Human heuristics, or ‘rules-of-thumb’, can guide optimisation algorithms in an intelligent way towards innovative solutions to complex real-world problems. This article presents four heuristics proven to improve optimisation solution performance while reducing computational overheads.

What is optimisation?

Optimisation is a computational problem solving and decision support approach that attempts to find the best solution(s) to a complex problem according to some defined objective(s). It has become a key decision-making tool in engineering systems planning and design practice.

Evolutionary algorithms [1] are popular optimisation algorithms that work with populations of solutions and progressively improve them by mimicking natural evolutionary processes. They generally work in conjunction with a simulation model that can be used to assess the performance of individual solutions.

Algorithms iterate through many solutions while aiming to maximise or minimise the value of  some objective function, e.g. net present value, environmental benefit, or failure rate. The performance and decisions of previous solution trials inform solution improvements in later iterations.

In this way, optimisation gives human designers access to very large computational processing power to search for innovative solutions to complex problems.

In practice, optimisation approaches have saved water utilities millions of dollars in capital and operating costs [2], and improved performance for a variety of design and planning problems.

Water and environmental applications include:

  • water distribution systems design
  • environmental flow scheduling
  • stormwater management and planning
  • water distribution operation
  • project scheduling.

Heuristics handle quick decisions, Optimisation handles complexity

Humans rely on general rules-of-thumb or ‘heuristics’ for quick decision-making.

Human visual perception relies on a hard-wired heuristic: smaller objects are generally farther away. This heuristic allows us to react to catch a cricket ball or avoid an obstacle on the road.

But, the heuristic fails when viewing objects in a car’s rear-view mirror. The mirror’s convexity distorts an object’s appearance, making it appear further away than it is. Relying on the proximity heuristic in this situation could lead to dangerous errors in judgement.

Human visual heuristics allow quick assessments of visual stimuli, but fail in complex visual perception problems.. Heuristics can be combined with optimisation to handle complexities in engineering decisions. This image is of a rear-vision mirror with the potential to distort perception, by way of representing this idea.

Image source: Wikipedia

Similarly, humans use heuristics based on past experience for planning and design problems. For example, stormwater detention basins servicing larger catchments generally need to be larger. Combining this rule with modelling trial-and-error quickly generates reasonable stormwater management plans.

But for complex, distributed networks of detention basins, general heuristics may lead to sub-optimal solutions.

Complex systems demonstrate emergent behaviour that can’t be explained by simple rules. Computational effort applied intelligently through optimisation can generate innovative designs that deal with these complex behaviours.

So, heuristics can be a reliable starting point for decision-making. But, computational effort using an optimisation approach can produce better performing solutions.

Four intelligent heuristic methods to boost optimisation performance

Standard optimisation algorithms don’t have knowledge or awareness of the problems they solve. Consequently, they can waste computational effort simulating solutions that are obviously infeasible or inferior.

We can incorporate problem-specific heuristics into optimisation algorithms. The heuristics guide algorithm search behavior to concentrate computational effort on evaluating promising solutions.

This means that we can identify better solutions with less computational effort and in less time, and solve previously unsolvable problems.

Here are four ways to use heuristics to improve optimisation algorithm performance:

  1. seed the initial population
  2. preemptively screen out infeasible solutions
  3. progressively remove infeasible decision options
  4. provide bias towards known good decisions.

1. Seeding the initial population: start from good stock

Evolutionary algorithms generally start with an initial population of randomly generated solutions. These are progressively improved through evolutionary operators.

Studies published by the Intelligent Water Decisions group show initial populations generated using rules-of-thumb result in quicker generation of optimal solutions than those from random initial populations [3] [4] .

Some ways of generating these initial populations include:

  • Manually developing a set of good solutions based on heuristics from previous design experience
  • Including solutions with extreme objective function values e.g. the known highest and lowest cost solutions. This encourages a wider coverage of the search space
  • Implementing formal optimisation ‘seeding’ approaches [3] [4] – for more information contact the Intelligent Water Decisions optimisation team

2. Model preemption: IF(infeasible.OR.previously evaluated)THEN don’t evaluate

Model preemption is a conditional operator that prevents the simulation of known infeasible or previously evaluated solutions.

This method is extremely effective where model simulation is computationally expensive [5].

Implementation of model preemption is easy

If a solution is known to violate a performance constraint or condition without simulating its performance, then assign a penalty to the solution and continue.

In addition, keep a look-up table with performance data of previously simulated solutions. Check the look-up table for each solution before simulating it. This will prevent simulating the same solution more than once.

3. Pruning options: focus on the feasible

Many planning and design problems have a number of decision variables with interdependencies between them. Selecting one decision option may cause another to become unavailable or undesirable.

Commonly, optimisation approaches construct infeasible solutions that violate these dependencies. They then apply penalties to discourage similar solutions in future iterations. This is not always effective where there are complex dependencies.

However, humans would avoid constructing infeasible solutions in the first place. Removing or ‘pruning’ options at each decision step can be used to ensure the feasibility of trial solutions.

About the pruning approach

The Intelligent Water Decisions group has used the dynamic constraint handling of Ant Colony Optimisation to implement the pruning approach.

Pruning ensures computational effort concentrates wholly on feasible solutions. Optimal solutions are then isolated from extremely large numbers of possible options.

The approach has been used to solve difficult Murray-Darling environmental flow scheduling [6], hydropower maintenance scheduling [7], crop irrigation allocation [8], and stormwater management plan optimisation problems.

Ant colony optimisation uses the searching behaviour of ants to find optimal solutions. This image depics a swarm of ants to represent this methodology.

Image Source: Wikipedia

4. Greedy bias towards locally optimal solutions

When constructing solutions, sometimes common sense indicates some options are better than others.

For example, when deciding on where to direct a stormwater flood, the closest available location is usually the best option to minimize cost and risk. This heuristic is useful, but if universally applied at each flood control location it may result in sub-optimal, overly redundant and costly flood management plans.

Some optimisation methods, such as Ant Colony Optimisation, allow bias towards locally optimal solutions whilst promoting the selection of innovative options [9].

A ‘greedy bias’ or weighting increases the selection probability of low cost or best performing solutions at each decision comprising a solution. The bias can be proportional to the known cost or performance attributed to the available options.

Can you use heuristics to reduce your optimisation overheads?

If you use optimisation, remember that you can improve the efficiency and reduce computational budget using heuristics.

Contact the Intelligent Water Decisions team for more information about practical approaches for improving water and environmental decision-making.

References

[1] H.R. Maier, Z. Kapelan, J. Kasprzyk, J. Kollat, L.S. Matott, M.C. Cunha, G.C. Dandy, M.S. Gibbs, E. Keedwell, A. Marchi, A. Ostfeld, D. Savic, D.P. Solomatine, J.A. Vrugt, A.C. Zecchin, B.S. Minsker, E.J. Barbour, G. Kuczera, F. Pasha, A. Castelletti, M. Giuliani, P.M. Reed, (2014)  Evolutionary algorithms and other metaheuristics in water resources: Current status, research challenges and future directions, Environmental Modelling & Software, 62, 271-299, DOI: 10.1016/j.envsoft.2014.09.013.

[2] Future Water magazine (2016) Leading the way in water innovation. [ONLINE] Available at:http://www.futurewater.com.au/news/general-news/leading-the-way-in-water-innovation. [Accessed 06 March 2016].

[3] Bi W., Dandy G.C. and Maier H.R. (2016) Use of domain knowledge to increase the convergence rate of evolutionary algorithms for optimizing the cost and resilience of water distribution systems, Journal of Water Resources Planning and Management, in press.

[4] Bi W., Dandy G.C. and Maier H.R. (2015) Improved genetic algorithm optimization of water distribution system design by incorporating domain knowledge, Environmental Modelling and Software, 69, 370-381, DOI: 10.1016/j.envsoft.2014.09.010

[5] Di Matteo M., Dandy G.C. and Maier H.R. (2016) Multi-objective optimization of distributed stormwater harvesting systems, Journal of Water Resources Planning and Management, under review.

[6] Szemis J.M., Maier H.R. and Dandy G.C. (2012) A framework for using ant colony optimization to schedule environmental flow management alternatives for rivers, wetlands and floodplains, Water Resources Research, 48(8), DOI:10.1029/2011WR011276.

[7] Foong W.K., Maier H.R. and Simpson A.R. (2008) Power plant maintenance scheduling using ant colony optimisation: an improved formulation. Engineering Optimization, 40(4), 309-329, DOI: 10.1080/03052150701775953.

[8] Nguyen D.C.H., Maier H.R., Dandy G.C. and Ascough II, J.C. (2016) Framework for computationally efficient optimal crop and water allocation using ant colony optimization, Environmental Modelling and Software, 76, 37-53, DOI:10.1016/j.envsoft.2015.11.003.

[9] Nguyen D.C.H., Dandy G.C., Maier H.R. and Ascough II J.C. (2016)  Improved ant colony optimization for optimal crop and irrigation water allocation by incorporating domain knowledge, Journal of Water Resources Planning and Management, in press.