Title: Solving the task assignment problem with ant colony optimisation incorporating ideas from the clonal selection algorithm
Authors: Goran Martinović; Dražen Bajer
Addresses: Faculty of Electrical Engineering, Josip Juraj Strossmayer University of Osijek, Kneza Trpimira 2b, 31000 Osijek, Croatia ' Faculty of Electrical Engineering, Josip Juraj Strossmayer University of Osijek, Kneza Trpimira 2b, 31000 Osijek, Croatia
Abstract: The task assignment problem commonly appears in distributed computing environments. It asks an assignment of tasks to processors is found such that it satisfies the imposed constraints and that the total execution and communication cost of the tasks is minimal. This paper presents an algorithm based on ant colony optimisation that incorporates ideas from the clonal selection algorithm. Namely, the ant colony optimisation algorithm includes the cloning of the iteration-best ant and mutation of its clones' solutions; the goal being a better exploitation of promising parts of the search space. Besides that, the solution construction procedure is modified to take the memory constraints into account and the pheromone update mechanism is modified to enable the best clone to deposit pheromone. The experimental analysis, conducted on a large number of problem instances, showed that the proposed algorithm performs better compared to the MAX-MIN ant system, a differential evolution and a particle swarm optimisation algorithm.
Keywords: ant colony optimisation; ACO; clonal selection algorithm; CSA; clones; cloning; differential evolution; iteration-best ant; MAX-MIN ant system; MMAS; memory constraints; mutation; particle swarm optimisation; PSO; pheromone update mechanism; solution construction procedure; task assignment problem; TAP.
International Journal of Bio-Inspired Computation, 2015 Vol.7 No.2, pp.129 - 143
Received: 14 Jan 2014
Accepted: 03 Jun 2014
Published online: 08 May 2015 *