Actas de congresos
A Max Min Ant System Applied To The Capacitated Clustering Problem
Registro en:
780386086
Machine Learning For Signal Processing Xiv - Proceedings Of The 2004 Ieee Signal Processing Society Workshop. , v. , n. , p. 755 - 764, 2004.
2-s2.0-17644416124
Autor
De Franca F.O.
Von Zuben F.J.
De Castro L.N.
Institución
Resumen
This work introduces a modified MAX MIN Ant System (MMAS) designed to solve the Capacitated Clustering Problem (CCP). Some improvements on the original MMAS algorithm are proposed, such as the use of a density model on the information heuristic and a local search adapted from the uncapacitated p-medians problem. Also the MMAS ability to deal with large scale instances is improved by means of a new proposal for the pheromone updating rule. Some simulations are performed using instances available from the literature, for benchmarking purposes. As a practical application, given a hypothetical demand proportional to the number of inhabitants of the 186 most populated Brazilian cities, the optimal allocation for a varied number of clustering centers is properly determined by the proposed algorithm, with a superior performance when compared with the original MMAS algorithm. © 2004 IEEE.
755 764 Osman, I.H., Christofides, N., Capacitated clustering problems by hybrid simulated annealing and tabu search (1994) Int. Trans. Opl. Res., 1 (3), pp. 317-336. , Pergamons Press, England, 1994 Garey, M.R., Johnson, D.S., (1979) Computers and Intractability: A Guide to the Theory of NT-completeness, , San Francisco: Freeman Dorigo, M., (1992) Optimization, Learning and Natural Algorithms, , Ph.D.Thesis, Politecnico di Milano, Italy, in Italian Stützle, T., Hoos, H.H., The MAX-MIN ant system and local search for the traveling salesman problem (1997) Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC'97), pp. 309-314. , T. Back, Z. Michalewicz, and X. Yao, editors, IEEE Press, Piscataway, NJ, USA Blum, C., Roli, A., Dorigo, M., HC-ACO: The hyper-cube framework for Ant Colony Optimization (2001) Proceedings of MIC'2001 - Meta-heuristics International Conference, 2, pp. 399-403. , Porto, Portugal Blum, C., Dorigo, M., The hyper-cube framework for ant colony optimization (2004) IEEE Transactions on Systems, Man and Cybernetics, Part B, 34 (2), pp. 1161-1172 Corne, D., Dorigo, M., Glover, F., (1999) EvoWeb - New Ideas in Optimization, , McGraw-Hill Ahmadi, S., Osman, I.H., Density based problem space search for the capacitated clustering problem (2004) Annals for Operational Research, , in press Resende, G.C.M., Werneck, F.R., On the implementation of a swap-based local search procedure for the p-median problem (2003) Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments (ALENEX'03), pp. 119-127. , Richard E. Ladner (Ed.), SIAM, Philadelphia Teitz, M.B., Bart, P., Heuristic methods for estimating the generalized vertex median of a weighted graph (1968) Operation Research, 16 (5), pp. 955-961 Lorena, L.A.N., Senne, E.L.F., Local search heuristics for capacitated P-median problems (2003) Networks and Spatial Economics, 3, pp. 407-419 De França, F.O., Von Zuben, F.J., De Castro, L.N., A Max Min Ant System Applied to the Capacitated P-Medians Problem, , in preparation Gomes, L.C.T., Von Zuben, F.J., Multiple criteria optimization based on unsupervised learning and fuzzy inference applied to the vehicle routing problem (2003) Journal of Intelligent & Fuzzy Systems, 13 (2-4), pp. 143-154. , IOS Press