The optimization of a water distribution network (WDN) is a highly nonlinear, multi-modal, and constrained combinatorial problem. Particle swarm optimization (PSO) has been shown to be a fast converging algorithm for WDN optimization. An improved estimation of distribution algorithm (EDA) using historic best positions to construct a sample space is hybridized with PSO both in sequential and in parallel to improve population diversity control and avoid premature convergence. Two water distribution network benchmark examples from the literature are adopted to evaluate the performance of the proposed hybrid algorithms. The experimental results indicate that the proposed algorithms achieved the literature record minimum (6.081 M$) for the small size Hanoi network. For the large size Balerma network, the parallel hybrid achieved a slightly lower minimum (1.921M?) than the current literature reported best minimum (1.923M?). The average number of evaluations needed to achieve the minimum is one order smaller than most existing algorithms. With a fixed, small number of evaluations, the sequential hybrid outperforms the parallel hybrid showing its capability for fast convergence. The fitness and diversity of the populations were tracked for the proposed algorithms. The track record suggests that constructing an EDA sample space with historic best positions can improve diversity control significantly. Parallel hybridization also helps to improve diversity control yet its effect is relatively less significant.