  The main goal of the multitasking optimization paradigm is to solve multiple
and concurrent optimization tasks in a simultaneous way through a single search
process. For attaining promising results, potential complementarities and
synergies between tasks are properly exploited, helping each other by virtue of
the exchange of genetic material. This paper is focused on Evolutionary
Multitasking, which is a perspective for dealing with multitasking optimization
scenarios by embracing concepts from Evolutionary Computation. This work
contributes to this field by presenting a new multitasking approach named as
Coevolutionary Variable Neighborhood Search Algorithm, which finds its
inspiration on both the Variable Neighborhood Search metaheuristic and
coevolutionary strategies. The second contribution of this paper is the
application field, which is the optimal partitioning of graph instances whose
connections among nodes are directed and weighted. This paper pioneers on the
simultaneous solving of this kind of tasks. Two different multitasking
scenarios are considered, each comprising 11 graph instances. Results obtained
by our method are compared to those issued by a parallel Variable Neighborhood
Search and independent executions of the basic Variable Neighborhood Search.
The discussion on such results support our hypothesis that the proposed method
is a promising scheme for simultaneous solving community detection problems
over graphs.
