PADDS Algorithm Assessment for Biobjective Water Distribution System Benchmark Design Problems

摘要

Two implementations of the Pareto archived dynamically dimensioned search (PADDS) algorithm using different selection metrics are applied to 12 water distribution network (WDN) design benchmark problems from the literature. Convex hull contribution (CHC) and hypervolume contribution (HVC) are used as selection metrics for PADDS making this study the first to assess their relative performance on WDN design problems. Past research applied five state-of-the-art multiobjective evolutionary algorithms (MOEAs) to these 12 benchmark problems to generate the best-known Pareto fronts (PFs). The PADDS-CHC and PADDS-HVC both find all solutions on the known true PFs of the first three problems. Together, both PADDS results augment the previously best-known PFs in the nine other benchmark problems with new PF solutions, some of which dominate previous best-known PF solutions, to define updated best-known PFs. Comparative results against five state-of-the-art MOEAs show PADDS derived best-known PFs are equal or better than all other algorithms in 11 of 12 WDN design problems. A comprehensive comparison between PADDS-CHC and PADDS-HVC performance on the largely convex benchmark problem Pareto fronts reveals the different responses of PADDS algorithm to increment of computational budget. An innovative measure called effective archive size (EAS) is introduced to quantify the portion of PADDS archived solutions that play the dominant role in directing PADDS toward the final PF. Tracking the EAS value throughout the search revealed that compared with PADDS-HVC, the EAS of PADDS-CHC is typically close to an order of magnitude smaller. In fact, the PADDS-CHC algorithm generates candidate solutions from a surprisingly small effective archive size that ranges from only 16 to 73 solutions across the 12 benchmark WDN problems while being only 24 for the largest problem. (C) 2017 American Society of Civil Engineers.