Efficient genetic algorithms for optimal assignment of tasks to teams of agents

The problem of optimally assigning agents (resources) to a given set of tasks is known as the assignment problem (AP). The classical AP and many of its variations have been extensively discussed in the literature. In this paper, we examine a specific class of the problem, in which each task is assigned to a group of collaborating agents. APs in this class cannot be solved using the Hungarian or other known polynomial time algorithms. We employ the genetic algorithm (GA) to solve the problem. However, we show that if the size of the problem is large, then standard crossover operators cannot efficiently find nearoptimal solutions within a reasonable time. In general, the efficiency of the GA depends on the choice of genetic operators (selection, crossover, and mutation) and the associated parameters. In order to design an efficient GA for determining the near-optimal assignment of tasks to collaborative agents, we focus on the construction of crossover operators. We analyze why a naive implementation with standard crossover operators is not capable of sufficiently solving the problem. Furthermore, we suggest modifications to these operators by adding a shuffled list and introduce two new operators (team-based and team-based shuffled list). We demonstrate that the modified and new operators with shuffled lists perform significantly better than all operators without shuffled lists and solve the presented AP more efficiently. The performance of the GA can be further enhanced by using chaotic sequences. Moreover, the GA is also compared with the particle swarm optimization (PSO) and differential evolution (DE) algorithms, demonstrating the superiority of the GA over these search algorithms. (C) 2018 Elsevier B.V. All rights reserved.