Research On Ant Colony Optimization Algorithm For Task Allocation Problem In Distributed System

The task allocation problem is a typical combinatorial optimization problem. The research about the optimal task allocation on multi-processor system is a hotspot problem of making use of system resources to solve practical problem effectively. In theory, the task allocation problem is a recognized NP-hard problem, so how to construct effective heuristic or approximate algorithm is an important domain of research until now.Inspired by foraging behavior of ants in the nature, the ant colony optimization algorithm was proposed as a novel bionic evolutionary algorithm for solving complicated combinatorial optimization problems, such as the traveling salesman problem, the quadratic assignment problem. At present, the research about ant colony optimization algorithm has already aroused attention from more scholars and experts gradually. They have made a lot of researches on it, extended it to many optimization domains and acquired considerably abundant research achievements.Although application scope of the ant colony optimization algorithm is almost related to every optimization domain, there still exists deficiency. For example, the research on solving the task allocation problem in distributed system by the ant colony optimization algorithm is carried out under the premise of simplified experiment condition or constrained condition.In this thesis, the ant colony optimization algorithm is applied to solve the task allocation problem with more complicated constrained condition, which each task can be assigned to only one processor, but each processor with capacity constraint and fixed cost can execute a number of tasks. The task allocation problem is expressed as a complete bipartite graph, sub-optimal solutions are obtained by ants which search sub-optimal routes in the graph. Several groups of data with different scales are chose to make experiments, for every group of data, optimum configuration of concerned parameters, are speculated by trial-test repeatedly, furthermore, the results of ant colony optimization algorithm is compared to tabu search and random method. The experimental results manifest that the ant colony optimization algorithm performs better under different problem scales and has great advantages over tabu search and random method in performance.Another task allocation problem is turned into a new graph representation which is different from the bipartite graph. Aiming at easily plunging into local optimization of the ant colony optimization algorithm, a hybrid algorithm which combined ant colony optimization algorithm with tabu search for task allocation problem is proposed. Owing to the stronger local search ability of tabu search, the proposed hybrid algorithm can enhance optimization ability of the ant colony optimization algorithm and improve quality of solution of the task allocation problem. The simulation results demonstrate that the hybrid algorithm performs significantly better than ant colony algorithm in performance.In the end, the conclusion is given and the further research direction is pointed out.