Efficient Genetic Algorithms for Optimal Assignment of Tasks to Teamsof Agents
(English)Manuscript (preprint) (Other academic)
The problem of optimally assigning agents (resources) to a given set oftasks is known as the Assignment Problem (AP). The classical AP and manyof its variations have been discussed extensively in the literature. In thispaper, we present a specific class of Assignment Problems (APs) in which eachtask is assigned to a group of collaborating agents. In this AP, collaborationof all agents is required to perform the task and an agent cannot individuallydo it.
We present a mathematical model for this type of AP and use GeneticAlgorithm (GA) to solve the model, since there are no known polynomial timealgorithms for this class of APs. We show that for larger instances of the problem,the GA with one-point crossover operator cannot efficiently find nearoptimalsolutions. In general, the efficiency of the GA depends on the choiceof genetic operators (selection, crossover, mutation) and associated parameters.In order to design an efficient GA for finding near optimal assignment oftasks to collaborative teams, we focus on construction of crossover operators.We compare and analyze the efficiency of several well-known crossover operatorssuch as one-point, two-point, three-point, position-based and order-basedcrossover operators. We suggest modifications to these operators by addinga shuffled repair list to them and show that their efficiency is enhanced forsolving the presented AP. Furthermore, we introduce two new crossover operators,team-based and team-based shuffled list crossover operators, whichsolve large-scale models of our AP efficiently.
Genetic algorithms, Combinatorial optimization, Evolutionary computations, Heuristics, Large scale optimization, Team assignment problem
Research subject Computer Science
IdentifiersURN: urn:nbn:se:kth:diva-143762OAI: oai:DiVA.org:kth-143762DiVA: diva2:708375
QS 20142014-03-272014-03-272014-03-28Bibliographically approved