Ant colony optimization algorithm for the set covering problem
cytuj
pobierz pliki
RIS BIB ENDNOTEChoose format
RIS BIB ENDNOTEAnt colony optimization algorithm for the set covering problem
Publication date: 2013
Technical Transactions, 2013, Automatic Control Issue 1-AC (2) 2013 , pp. 39 - 52
https://doi.org/10.4467/2353737XCT.14.004.1992Authors
Ant colony optimization algorithm for the set covering problem
Algorytm mrówkowy dla zagadnienia pokrycia zbioru
W artykule przedstawiono nowy hybrydowy algorytm mrówkowy dla problemu zagadnienia pokrycia zbioru o minimalnym koszcie. Problem jest zamodelowany za pomocą grafu dwudzielnego. W modyfikowanym algorytmie wprowadzono nową heurystykę wyboru wierzchołków do podzbioru wierzchołków pokrywających. Opracowany algorytm przetestowano i porównano, a wyniki tych badań omówiono
Valenzuela C., Crawford B., Soto R., Monfroy E., Paredes F., A 2-level Metaheuristic for the Set Covering Problem, International Journal of Computers, Communications & Control, vol. 7/2, 2012, 377-387.
Ren Z.G., Feng Z.R., Ke L.J., Zhang Z.J., New ideas for applying ant colony optimization to the set covering problem, Journal Computers and Industrial Engineering, vol. 58/4, 2010, 774-784.
Lessing L., Dumitrescu I., Stutze T., A comparision between ACO algorithms for the set covering problem, LNCS, vol. 3172, 2004, 1-12.
Ren Z.G., Ke L.J., Chang H., A fast and efficient Ant colony Optimization Approach for the Set covering problem, Proc. of IEEE World Congress on Computational Intelligence, Hong Kong 2008, 1839-1844.
Hadji R., Rahoual M., Talbi E., Bachelet V., Ant colonies for the set covering problem, [in:] Abstract Proc. of From Ant Colonies to Artificial Ants: Second International Workshop on Ant Colony Optimization, Brussels 2000, 63-66.
Crawford B., Soto R., Monfroy E., Paredes F., Palma W., A hybrid Ant algorithm for the set covering problem, International Journal of the Physical Sciences, vol. 6/19, 2011, 4667-4673.
Dechter R, Frost D., Backjump-based backtracking for constraint satisfaction problems, Artificial Intelligence, vol. 136/2, 2002, 147-188.
Dorigo M., Di Caro G., The Ant Colony Optimization meta-heuristics. New Ideas in Optimization, McGraw Hill, New York 1999.
Mihelic J., Robic B., Facility Location and Covering Problems, Proc. of the 7th International Multiconference Information Society, Volume D – Theoretical Computer Science, Ljubljana, Slovenia 2004.
Housos E., Elmoth T., Automatic optimization of subproblems in scheduling airlines crews, Interfaces, vol. 27/5, 1997, 68-77.
Vasko F.J., Wilson G.R., Using a facility location algorithm to solve large set covering problems, Operations Research Letters, vol. 3/2, 1984, 85-90.
Vasko F.J., Wolf F.E., Optimal selection of ingot sizes via set covering, Operations Research, vol. 35/3, 1987, 346-353.
Balas E., Carrera M.C., A dynamic subgradient-based branch-and-bound procedure for set covering, Operations Research, vol. 44/6, 1996, 875-890.
Fisher M.L., Kedia P., Optimal solution of set covering/partitioning problems using dual heuristics, Management Science, vol. 36/6, 1990, 674-688.
Chvatal V., A greedy heuristic for the set-covering problem, Mathematics of Operations Research, vol. 4/3, 1979, 233-235.
Lan G., DePuy G.W., On the effectiveness of incorporating randomness and memory into a multi-start meta-heuristic with application to the set covering problem, Computer & Industrial Engineering, vol. 51/3, 2006, 362-374.
Ceria S., Nobili P., Sassano A., A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programming, vol. 81, 1998, 215-228.
Caprara A., Fischetti M., Toth P., A heuristic method for the set covering problem, Operations Research, vol. 47/5, 1999, 730-743.
Beasley J.E., Chu P.C., A genetic algorithm for the set covering problem, European Journal of Operational Research, vol. 94/2, 1996, 392-404.
Brusco M.J., Jacobs L.W., Thompson G.M., A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems, Annals of Operations Research, vol. 86, 1999, 611-627.
Caserta M., Tabu search-based meta-heuristic algorithm for large-scale set covering problems, [in:] Doerner K.F., Gendreau M., Greistorfer P., Gutjahr W., Hartl R., Reimann M. (Eds.), Metaheuristics: Progress in complex systems optimization, Springer, New York 2007, 43-63.
Lessing L., Dumitrescu I., Stützle T., A comparison between ACO algorithms for the set covering problem, [in:] Dorigo M., Mauro Birattari M., Blum C., Gambardella L.M., Mondada F., Stützle T. (Eds.), Ant Colony Optimization and Swarm Intelligence, LNCS, vol. 3172, Springer-Verlag, Berlin, Heidelberg, 2004, 1-12.
Crawford B., Castro C., Integrating look ahead and post processing procedures with ACO for solving set partitioning and covering problems, [in:] Rutkowski L., Tadeusiewicz R., Zadeh L.A., Żurada J.M. (Eds.), Proc. of the 8th international conference on Artificial Intelligence and Soft Computing, Springer-Verlag, Berlin, Heidelberg 2006, 1082-1090.
Finger M., Stützle T., Ramalhinho H., Exploiting fitness distance correlation of set covering problems, [in:] Cagnoni S., Gottlieb J., Hart E., Middendorf M.R., Raidl G.R. (Eds.), Proc. of the Applications of Evolutionary Computing on EvoWorkshops, LNCS, vol. 2279, Springer, Berlin, Heidelberg 2002, 61-71.
Dorigo M., Gambardella L.M., Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, vol. 1/1, 1997, 53-66.
Gagne C., Gravel M., Price W., A look-ahead addition to the ant colony optimization metaheuristic and its application to an industrial scheduling problem, Proc. of the fourth Metaheuristics International Conference, vol. 1, Proto 2001, 79-84.
Michel R., Middendorf M., An island model based ant system with lookahead for the shortest super sequence problem, [in:] Eiben A.E., Bäck T., Schoenauer M., Schwefel H.P. (Eds.), Parallel Problem Solving from Nature, LNCS, Springer Verlag, vol. 1498, 1998, 692-701.
Information: Technical Transactions, 2013, Automatic Control Issue 1-AC (2) 2013 , pp. 39 - 52
Article type: Original article
Titles:
Ant colony optimization algorithm for the set covering problem
Ant colony optimization algorithm for the set covering problem
Department of Automatic Control and Information Technology, Faculty of Electrical and Computer Engineering, Cracow University of Technology
Published at: 2013
Article status: Open
Licence: None
Percentage share of authors:
Article corrections:
-Publication languages:
EnglishView count: 2572
Number of downloads: 1449