Ant colony optimization algorithm for the set covering problem

Krzysztof Schiff


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

Słowa kluczowe: zagadnienie pokrycia zbioru, algorytm mrówkowy, heurystyka

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.