Ant colony optimization algorithm for the set covering problem

• Autorzy: Schiff K.

Warianty tytułu

PL

Algorytm mrówkowy dla zagadnienia pokrycia zbioru

• Języki publikacji: EN

Abstrakty

EN

This article describes a new hybrid ant colony optimization algorithms for the set covering problem. The problem is modeled by means of a bipartite graph. New heuristic patterns, which are used in order to choose a vertex to a created covering set have been incorporated into modified hybrid algorithms. Results of tests on investigated algorithms are discussed.

PL

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.

Słowa kluczowe

EN

set covering problem; ant colony optimization; heuristic rule

PL

zagadnienie pokrycia zbioru; algorytm mrówkowy; heurystyka

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Automatyka
• Rocznik: 2013
• Tom: R. 110, z. 1-AC
• Strony: 39--52
• Opis fizyczny: Bibliogr. 27 poz., wz., wykr., tab.

Twórcy

autor

Schiff K.

• Department of Automatic Control and Information Technology, Faculty of Electrical and Computer Engineering, Cracow University of Technology

Bibliografia

• [1] 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.
• [2] 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.
• [3] Lessing L., Dumitrescu I., Stutze T., A comparision between ACO algorithms for the set covering problem, LNCS, vol. 3172, 2004, 1-12.
• [4] 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.
• [5] 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.
• [6] 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.
• [7] Dechter R, Frost D., Backjump-based backtracking for constraint satisfaction problems, Artificial Intelligence, vol. 136/2, 2002, 147-188.
• [8] Dorigo M., Di Caro G., The Ant Colony Optimization meta-heuristics. New Ideas in Optimization, McGraw Hill, New York 1999.
• [9] 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.
• [10] Housos E., Elmoth T., Automatic optimization of subproblems in scheduling airlines crews, Interfaces, vol. 27/5, 1997, 68-77.
• [11] 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.
• [12] Vasko F.J., Wolf F.E., Optimal selection of ingot sizes via set covering, Operations Research, vol. 35/3, 1987, 346-353.
• [13] Balas E., Carrera M.C., A dynamic subgradient-based branch-and-bound procedure for set covering, Operations Research, vol. 44/6, 1996, 875-890.
• [14] Fisher M.L., Kedia P., Optimal solution of set covering/partitioning problems using dual heuristics, Management Science, vol. 36/6, 1990, 674-688.
• [15] Chvatal V., A greedy heuristic for the set-covering problem, Mathematics of Operations Research, vol. 4/3, 1979, 233-235.
• [16] 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.
• [17] Ceria S., Nobili P., Sassano A., A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programming, vol. 81, 1998, 215-228.
• [18] Caprara A., Fischetti M., Toth P., A heuristic method for the set covering problem, Operations Research, vol. 47/5, 1999, 730-743.
• [19] 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.
• [20] 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.
• [21] 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.
• [22] 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.
• [23] 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.
• [24] 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.
• [25] 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.
• [26] 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.
• [27] 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.