engleski

Solving the Task Assignment Problem with Ant Colony Optimization incorporating ideas from the Clonal Selection Algorithm

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.

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

nije evidentirano