Abstract
The ant colony optimization (ACO) algorithms are being applied successfully to diverse heavily constrained problems: traveling salesman problem, quadratic assignment problem. Early applications of ACO algorithms have been mainly concerned with solving ordering problems. In this paper, the principles of the ACO algorithm are applied to the multiple knapsack problem (MKP). In the first part of the paper we explain the basic principles of ACO algorithm. In the second part of the paper we propose different types of heuristic information and we compare the obtained results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chu, P.C., Beasley, J.E.: A genetic algorithm for the multiple knapsack problem. Journal of Heuristics, 4 (1998) 63–86.
Dorigo, M., Di Caro, G.: The ant colony optimization metaheuristic. In: Corne, D., Dorigo, M., Glover, F. (eds.): New Idea in Optimization, McGrow-Hill (1999) 11–32.
Dorigo, M., Gambardella, L.M.: Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1 (1999) 53–66.
Dorigo, M., Di Caro, G., Gambardella, L.M.: Ant algorithms for distributed discret optimization. Artificial Life, 5 (1999) 137–172.
Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: Optimization by a colony of cooperating agents. IEEE Transaction on Systems, Man. and Cibernetics-Part B, 26 (1996) 29–41
Fogel, B.: Evolutionary computation: Toward a new philosophy of machine intelligence. IEEE Press, New York (1994)
Gambardella, M.L., Taillard, E.D., Agazzi, G.: A multiple ant colony system for vehicle routing problems with time windows. In: Corne, D., Dorigo, M., Glover, F. (eds.): New Ideas in Optimization, McGraw-Hill (1999) 63–76.
Gambardella, L.M., Taillard, E.D., Dorigo, M.: Ant colonies for the QAP. J. of Oper. Res. Soc. 50 (1999) 167–176.
Glover, F.: Tabu search. ORSA J. of Comput. 1 (1989)
Kirkpatrick, S., Gelatt, C.D., Vechi, M.P.: Optimization by simulated annealing. Scienece, 220 (1983) 671–680.
Kochenberger, G., McCarl, G., Wymann, F.: A heuristic for general integer programming. Decision Sciences, 5 (1974) 36–44.
Leguizamon, G., Michalevich, Z.: A new version of the ant system for subset problems. In: Proceedings of Int. Conf. on Evolutionary Computations, Washington (1999)
Michel, R., Middendorf, M.: An island based ant system with lookahead for the shortest common super-sequence problem. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H-P. (eds.): Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Vol. 1498 (1998) 692–708.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fidanova, S. (2003). ACO Algorithm for MKP Using Various Heuristic Information. In: Dimov, I., Lirkov, I., Margenov, S., Zlatev, Z. (eds) Numerical Methods and Applications. NMA 2002. Lecture Notes in Computer Science, vol 2542. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36487-0_49
Download citation
DOI: https://doi.org/10.1007/3-540-36487-0_49
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00608-4
Online ISBN: 978-3-540-36487-0
eBook Packages: Springer Book Archive