Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Efficient genetic algorithms for optimal assignment of tasks to teams of agents
KTH, School of Electrical Engineering and Computer Science (EECS). Swedish Defence Research Agency, Stockholm Sweden.
2018 (English)In: Neurocomputing, ISSN 0925-2312, E-ISSN 1872-8286, Vol. 314, p. 409-428Article in journal (Refereed) Published
Abstract [en]

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 near-optimal 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. 

Place, publisher, year, edition, pages
Elsevier B.V. , 2018. Vol. 314, p. 409-428
Keywords [en]
Combinatorial optimization, Genetic algorithms, Large scale optimization, Shuffled list crossover, Team assignment problem, Team-based crossover, Particle swarm optimization (PSO), Polynomial approximation, Differential evolution algorithms, Efficient genetic algorithms, Large-scale optimization, Near-optimal solutions, Polynomial-time algorithms, Team assignment, Problem solving, article, controlled study, crossover procedure, genetic algorithm, human, mutation
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-236598DOI: 10.1016/j.neucom.2018.07.008ISI: 000443718400039Scopus ID: 2-s2.0-85050090827OAI: oai:DiVA.org:kth-236598DiVA, id: diva2:1265745
Note

Export Date: 22 October 2018; Article; CODEN: NRCGE; Correspondence Address: Younas, I.; Department of Computer Science, National University of Computer and Emerging SciencesPakistan; email: irfan.younas@nu.edu.pk; Funding details: KTH, Kungliga Tekniska Högskolan; Funding text: We would like to thank Prof. Rassul Ayani for supervising this research and Prof. Christian Schulte at the KTH Royal Institute of Technology for his valuable comments and suggestions. QC 20181126

Available from: 2018-11-26 Created: 2018-11-26 Last updated: 2018-11-26Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Schubert, J.
By organisation
School of Electrical Engineering and Computer Science (EECS)
In the same journal
Neurocomputing
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 41 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf