Multi-objective optimisation of water distribution systems using a genetic algorithm embedded with an enhanced evolutionary direction crossover operator

Euan Barlow, Tiku Tanyimboh

Research output: Contribution to conferenceProceeding

59 Downloads (Pure)

Abstract

The optimal design of a water distribution system (WDS) is a non-linear multi-modal multi-objective problem which generally involves an extremely large discrete decision space. Genetic algorithms (GAs) present an intuitive approach to solving such problems. These algorithms are particularly suited to searching large decision spaces and can avoid convergence to local optima. The construction of a GA is designed to mimic the process of natural evolution. A large population of random networks will evolve through successive generations towards the pareto-optimal front; however, due to the stochastic nature of a GA, the number of network evaluations required for convergence can be extremely large. For a large WDS, each network evaluation can be time-consuming and a standard GA may require millions of solutions to be evaluated. It is therefore desirable to speed up the convergence of the GA in order to make the solution of large networks feasible. The evolutionary direction crossover (EDC) operator is a mechanism which is capable of following the natural course of evolution inherent to a GA. At a given generation, the direction of evolution between parents and children is identified. Progressive evolutionary directions are explored further to determine whether additional improvements can be made. This process will potentially advance the evolution, and thus achieve accelerated convergence. An enhanced EDC operator (EEDC) is proposed here, which is simpler to implement than EDC and is more suitable for application in a multi-objective environment. A modified GA is employed, with the EEDC operator embedded within the framework of a standard GA. In this paper, the EEDC operator is used in conjunction with the non-dominated sorting genetic algorithm II (NSGA II), although any GA could be used alternatively. Once the child population is generated, EEDC is applied to each child with a fixed probability. The fitness of each child is not assessed until after EEDC has been applied, thus ensuring that no additional fitness evaluations are required. The enhanced GA therefore incorporates the EEDC operator without significant increase in complexity or computation time. The performances of the enhanced algorithm and the standard NSGA II are compared for the solution of the Hanoi network, a benchmark problem from the WDS literature. The enhanced algorithm is shown to substantially improve the convergence of the population, particularly in the early stages of the evolution. Applied to a large WDS this improved convergence will dramatically reduce the required computation time. This paper therefore presents a progression towards the tractable optimisation of real-life water distribution systems.
Original languageEnglish
Number of pages8
Publication statusPublished - Jul 2012
Event10th International Conference on Hydroinformatics - Hamburg, Germany
Duration: 14 Jul 201218 Jul 2012

Conference

Conference10th International Conference on Hydroinformatics
CountryGermany
CityHamburg
Period14/07/1218/07/12

Fingerprint

Water distribution systems
Multiobjective optimization
Genetic algorithms
Mathematical operators
Sorting

Keywords

  • water distribution system
  • constarined multiobjective evolutionary optimization
  • evolutionary direction crossover
  • genetic algorithm
  • NSGA II
  • evolutionary algorithm

Cite this

@conference{42ae5ca609ad45ad94ed0649169a8cea,
title = "Multi-objective optimisation of water distribution systems using a genetic algorithm embedded with an enhanced evolutionary direction crossover operator",
abstract = "The optimal design of a water distribution system (WDS) is a non-linear multi-modal multi-objective problem which generally involves an extremely large discrete decision space. Genetic algorithms (GAs) present an intuitive approach to solving such problems. These algorithms are particularly suited to searching large decision spaces and can avoid convergence to local optima. The construction of a GA is designed to mimic the process of natural evolution. A large population of random networks will evolve through successive generations towards the pareto-optimal front; however, due to the stochastic nature of a GA, the number of network evaluations required for convergence can be extremely large. For a large WDS, each network evaluation can be time-consuming and a standard GA may require millions of solutions to be evaluated. It is therefore desirable to speed up the convergence of the GA in order to make the solution of large networks feasible. The evolutionary direction crossover (EDC) operator is a mechanism which is capable of following the natural course of evolution inherent to a GA. At a given generation, the direction of evolution between parents and children is identified. Progressive evolutionary directions are explored further to determine whether additional improvements can be made. This process will potentially advance the evolution, and thus achieve accelerated convergence. An enhanced EDC operator (EEDC) is proposed here, which is simpler to implement than EDC and is more suitable for application in a multi-objective environment. A modified GA is employed, with the EEDC operator embedded within the framework of a standard GA. In this paper, the EEDC operator is used in conjunction with the non-dominated sorting genetic algorithm II (NSGA II), although any GA could be used alternatively. Once the child population is generated, EEDC is applied to each child with a fixed probability. The fitness of each child is not assessed until after EEDC has been applied, thus ensuring that no additional fitness evaluations are required. The enhanced GA therefore incorporates the EEDC operator without significant increase in complexity or computation time. The performances of the enhanced algorithm and the standard NSGA II are compared for the solution of the Hanoi network, a benchmark problem from the WDS literature. The enhanced algorithm is shown to substantially improve the convergence of the population, particularly in the early stages of the evolution. Applied to a large WDS this improved convergence will dramatically reduce the required computation time. This paper therefore presents a progression towards the tractable optimisation of real-life water distribution systems.",
keywords = "water distribution system, constarined multiobjective evolutionary optimization, evolutionary direction crossover , genetic algorithm, NSGA II, evolutionary algorithm",
author = "Euan Barlow and Tiku Tanyimboh",
year = "2012",
month = "7",
language = "English",
note = "10th International Conference on Hydroinformatics ; Conference date: 14-07-2012 Through 18-07-2012",

}

Barlow, E & Tanyimboh, T 2012, 'Multi-objective optimisation of water distribution systems using a genetic algorithm embedded with an enhanced evolutionary direction crossover operator' 10th International Conference on Hydroinformatics, Hamburg, Germany, 14/07/12 - 18/07/12, .

Multi-objective optimisation of water distribution systems using a genetic algorithm embedded with an enhanced evolutionary direction crossover operator. / Barlow, Euan; Tanyimboh, Tiku.

2012. 10th International Conference on Hydroinformatics, Hamburg, Germany.

Research output: Contribution to conferenceProceeding

TY - CONF

T1 - Multi-objective optimisation of water distribution systems using a genetic algorithm embedded with an enhanced evolutionary direction crossover operator

AU - Barlow, Euan

AU - Tanyimboh, Tiku

PY - 2012/7

Y1 - 2012/7

N2 - The optimal design of a water distribution system (WDS) is a non-linear multi-modal multi-objective problem which generally involves an extremely large discrete decision space. Genetic algorithms (GAs) present an intuitive approach to solving such problems. These algorithms are particularly suited to searching large decision spaces and can avoid convergence to local optima. The construction of a GA is designed to mimic the process of natural evolution. A large population of random networks will evolve through successive generations towards the pareto-optimal front; however, due to the stochastic nature of a GA, the number of network evaluations required for convergence can be extremely large. For a large WDS, each network evaluation can be time-consuming and a standard GA may require millions of solutions to be evaluated. It is therefore desirable to speed up the convergence of the GA in order to make the solution of large networks feasible. The evolutionary direction crossover (EDC) operator is a mechanism which is capable of following the natural course of evolution inherent to a GA. At a given generation, the direction of evolution between parents and children is identified. Progressive evolutionary directions are explored further to determine whether additional improvements can be made. This process will potentially advance the evolution, and thus achieve accelerated convergence. An enhanced EDC operator (EEDC) is proposed here, which is simpler to implement than EDC and is more suitable for application in a multi-objective environment. A modified GA is employed, with the EEDC operator embedded within the framework of a standard GA. In this paper, the EEDC operator is used in conjunction with the non-dominated sorting genetic algorithm II (NSGA II), although any GA could be used alternatively. Once the child population is generated, EEDC is applied to each child with a fixed probability. The fitness of each child is not assessed until after EEDC has been applied, thus ensuring that no additional fitness evaluations are required. The enhanced GA therefore incorporates the EEDC operator without significant increase in complexity or computation time. The performances of the enhanced algorithm and the standard NSGA II are compared for the solution of the Hanoi network, a benchmark problem from the WDS literature. The enhanced algorithm is shown to substantially improve the convergence of the population, particularly in the early stages of the evolution. Applied to a large WDS this improved convergence will dramatically reduce the required computation time. This paper therefore presents a progression towards the tractable optimisation of real-life water distribution systems.

AB - The optimal design of a water distribution system (WDS) is a non-linear multi-modal multi-objective problem which generally involves an extremely large discrete decision space. Genetic algorithms (GAs) present an intuitive approach to solving such problems. These algorithms are particularly suited to searching large decision spaces and can avoid convergence to local optima. The construction of a GA is designed to mimic the process of natural evolution. A large population of random networks will evolve through successive generations towards the pareto-optimal front; however, due to the stochastic nature of a GA, the number of network evaluations required for convergence can be extremely large. For a large WDS, each network evaluation can be time-consuming and a standard GA may require millions of solutions to be evaluated. It is therefore desirable to speed up the convergence of the GA in order to make the solution of large networks feasible. The evolutionary direction crossover (EDC) operator is a mechanism which is capable of following the natural course of evolution inherent to a GA. At a given generation, the direction of evolution between parents and children is identified. Progressive evolutionary directions are explored further to determine whether additional improvements can be made. This process will potentially advance the evolution, and thus achieve accelerated convergence. An enhanced EDC operator (EEDC) is proposed here, which is simpler to implement than EDC and is more suitable for application in a multi-objective environment. A modified GA is employed, with the EEDC operator embedded within the framework of a standard GA. In this paper, the EEDC operator is used in conjunction with the non-dominated sorting genetic algorithm II (NSGA II), although any GA could be used alternatively. Once the child population is generated, EEDC is applied to each child with a fixed probability. The fitness of each child is not assessed until after EEDC has been applied, thus ensuring that no additional fitness evaluations are required. The enhanced GA therefore incorporates the EEDC operator without significant increase in complexity or computation time. The performances of the enhanced algorithm and the standard NSGA II are compared for the solution of the Hanoi network, a benchmark problem from the WDS literature. The enhanced algorithm is shown to substantially improve the convergence of the population, particularly in the early stages of the evolution. Applied to a large WDS this improved convergence will dramatically reduce the required computation time. This paper therefore presents a progression towards the tractable optimisation of real-life water distribution systems.

KW - water distribution system

KW - constarined multiobjective evolutionary optimization

KW - evolutionary direction crossover

KW - genetic algorithm

KW - NSGA II

KW - evolutionary algorithm

UR - http://hic2012.org/

M3 - Proceeding

ER -