A Parallel Multi-Objective Cooperative Coevolutionary Algorithm for Optimising Small-World Properties in VANETs

Abstract

Cooperative coevolutionary evolutionary algorithms differ from standard evolutionary algorithms’ architecture in that the population is split into subpopulations, each of them optimising only a sub-vector of the global solution vector. All subpopulations cooperate by broadcasting their local partial solutions such that each subpopulation can evalu- ate complete solutions. Cooperative coevolution has recently been used in evolutionary multi-objective optimisation, but few works have exploited its parallelisation capabil- ities or tackled real-world problems. This article proposes to apply for the first time a state-of-the-art parallel asynchronous cooperative coevolutionary variant of the non- dominated sorting genetic algorithm II (NSGA-II), named CCNSGA-II, on the injection network problem in vehicular ad hoc networks (VANETs). This multi-objective optimi- sation problem, consists in finding the minimal set of nodes with backend connectivity, referred to as injection points, to constitute a fully connected overlay that will optimise the small-world properties of the resulting network. Recently, the well-known NSGA- II algorithm was used to tackle this problem on realistic instances in the city-centre of Luxembourg. In this work we analyse the performance of the CCNSGA-II when using different numbers of subpopulations, and compare them to the original NSGA-II in terms of both quality of the obtained Pareto front approximations and execution time speedup.