A Mutation Ant Colony Algorithm for the Generalized Assignment Problem under the Special Constraints


Article Preview

A generalized assignment problem under the special constraints is proposed, which can be solved by the ant colony algorithm (ACA). But the ACA for the problem is easy to fall in local optima because the constraints are relatively complicated. In this paper, the diversity in the results is maintained and the convergent speed is elevated by an adaptive method of updating pheromone and a mutation strategy for clearing up invalid assignment. The computer experiments demonstrate that the optimization performance is improved by the proposed algorithm, which is more suitable for the real-time application.



Edited by:

Mohamed Othman




Y. H. Guo and D. Q. Shi, "A Mutation Ant Colony Algorithm for the Generalized Assignment Problem under the Special Constraints", Applied Mechanics and Materials, Vols. 229-231, pp. 1862-1865, 2012

Online since:

November 2012




[1] Chu P C and Beasley J E, A genetic algorithm for the generalised assignment problem, Computers and Operations Research, vol. 24, no. 1, pp.17-23, (1997).

DOI: https://doi.org/10.1016/s0305-0548(96)00032-9

[2] Sahin S and Gonzalez T, P-Complete approximation problems, Journal of the ACM, vol. 23, no. 3, pp.555-565, (1995).

[3] Colorni A, Dorigo M, and Maniezzo V, Distributed optimization by ant colonies, Proceedings of the 1st European Conference on Artificial Life, pp.134-142, (1991).

[4] Dorigo M, Maniezzo V, and Colorni A, Ant system: optimization by a colony of cooperating agents, IEEE Transaction on System, Man, and Cybernetics-Part B, vol. 26, no. 1, pp.29-41, (1996).

DOI: https://doi.org/10.1109/3477.484436

[5] Gambardella L, Taillard E, and Dorigo M, Ant colonies for the quadratic assignment problem, Journal of the Operational Research Society, vol. 50, no. 2, pp.167-176, (1999).

DOI: https://doi.org/10.1057/palgrave.jors.2600676

[6] Stutzle T and Hoos H, MAX-MIN ant system for the quadratic assignment problem, Technical Report AI-DA-97-4, FG Intellektik, TH Darmstadt, July (1997).

[7] Ramalhinho L H and Serra D. Adaptive Approach Heuristics for the Generalized Assignment Problem, Technical Report EWP Series No. 304, Department of Economics and Management, Universitat Pompeu Fabra, Barcelona, (1998).