Optimising Small-World Properties in VANETs with a Parallel Multi-Objective Coevolutionary Algorithm
Grégoire Danoy, Julien Schleich, Pascal Bouvry, Bernabè Dorronsoro · CLEI electronic journal · 2013
Cooperative coevolutionary evolutionary algorithms dier from standard evolutionary algorithms architecture in that the popu- lation 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 evaluate complete solutions. Cooperative coevolution has recently been used in evolutionary multi-objective optimisation, but few works have exploited its parallelisation capabilities or tackled real-world prob- lems. This article proposes to apply for the rst 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 optimisation problem, consists in nding the min- imal 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 compare the perfor- mance of the CCNSGA-II to the original NSGA-II in terms of both quality of the obtained Pareto front approximations and execution time speedup.