nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Binary Harmony Search Algorithm for Solving Set-Covering Problem

verfasst von : Juan Salas, Broderick Crawford, Ricardo Soto, Álvaro Gómez Rubio, Adrián Jaramillo, Sebastián Mansilla Villablanca, Eduardo Olguín

Erschienen in: Trends in Applied Knowledge-Based Systems and Data Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper is intended to generate solutions to Set Covering Problem (SCP) through the use of a metaheuristic. The results were obtained using a variation of Harmony Search called Binary Global-Best Harmony Search Algorithm. To measure the effectiveness of the technique against other metaheuristics, Weasly benchmark was used.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel The Impact of Using Different Choice Functions When Solving CSPs with Autonomous Search

Nächstes Kapitel Differential Evolution for Multi-objective Robust Engineering Design

Crawford, B., Soto, R., Guzmán, N., Johnson, F., Paredes, F.: Recent harmony search algorithms for 0–1 optimization problems. In: Stephanidis, C., Tino, A. (eds.) HCII 2015 Posters. CCIS, vol. 528, pp. 567–572. Springer, Heidelberg (2015). doi:10.1007/978-3-319-21380-4_96 CrossRef

Karp, R.M.: Reducibility among combinatorial problems. In: 50 Years of Integer Programming 1958–2008 - From the Early Years to the State-of-the-Art, pp. 219–241 (2010)

Ali, A.I., Thiagarajan, H.: A network relaxation based enumeration algorithm for set partitioning. Eur. J. Oper. Res. 38(1), 76–85 (1989)MathSciNetCrossRefMATH

Bartholdi, J.J.: A guaranteed-accuracy round-off algorithm for cyclic scheduling and set covering. Oper. Res. 29(3), 501–510 (1981)MathSciNetCrossRefMATH

Walker, W.: Using the set-covering problem to assign fire companies to fire houses. Oper. Res. 22, 275–277 (1974)CrossRef

Vasko, F.J., Wilson, G.R.: Using a facility location algorithm to solve large set covering problems. Oper. Res. Lett. 3(2), 85–90 (1984)CrossRefMATH

Vasko, F.J., Wolf, F.E., Stott, K.L.: Optimal selection of ingot sizes via set covering. Oper. Res. 35, 346–353 (1987)CrossRef

Vasko, F.J., Wolf, F.E., Stott, K.L.: A set covering approach to metallurgical grade assignment. Eur. J. Oper. Res. 38(1), 27–34 (1989)MathSciNetCrossRef

Vasko, F.J., Wolf, F.E., Stott, K.L., Scheirer, J.W.: Selecting optimal ingot sizes for bethlehem steel. Interfaces 19(1), 68–84 (1989)CrossRef

10.

Balinski, M.L., Quandt, R.E.: On an integer program for a delivery problem. Oper. Res. 12(2), 300–304 (1964)CrossRef

11.

Foster, B.A., Ryan, D.M.: An integer programming approach to the vehicle scheduling problem. Oper. Res. 27, 367–384 (1976)MathSciNetCrossRefMATH

12.

Fisher, M.L., Rosenwein, M.B.: An interactive optimization system for bulk-cargo ship scheduling. Nav. Res. Logist. 36(1), 27–42 (1989)CrossRef

13.

Bellmore, M., Geenberg, H.J., Jarvis, J.J.: Multi-commodity disconnecting sets. Manage. Sci. 16(6), B427–B433 (1970)CrossRefMATH

14.

Bellmore, M., Ratliff, H.D.: Optimal defense of multi-commodity networks. Manage. Sci. 18(4-part-I), B174–B185 (1971)

15.

Freeman, B.A., Jucker, J.V.: The line balancing problem. J. Ind. Eng. 18, 361–364 (1967)

16.

Salveson, M.E.: The assembly line balancing problem. J. Ind. Eng. 6, 18–25 (1955)MathSciNet

17.

Ribeiro, C.C., Minoux, M., Penna, M.C.: An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment. Eur. J. Oper. Res. 41(2), 232–239 (1989)MathSciNetCrossRefMATH

18.

Ceria, S., Nobili, P., Sassano, A.: A lagrangian-based heuristic for large-scale set covering problems. Math. Program. 81(2), 215–228 (1998)MathSciNetCrossRefMATH

19.

Breuer, M.A.: Simplification of the covering problem with application to boolean expressions. J. Assoc. Comput. Mach. 17, 166–181 (1970)MathSciNetCrossRefMATH

20.

Christofides, N.: Zero-one programming using non-binary tree-search. Comput. J. 14(4), 418–421 (1971)MathSciNetCrossRefMATH

21.

Day, R.H.: Letter to the editor—on optimal extracting from a multiple file data storage system: an application of integer programming. Oper. Res. 13(3), 482–494 (1965)CrossRef

22.

Garfinkel, R.S., Nemhauser, G.L.: Optimal political districting by implicit enumeration techniques. Manage. Sci. 16(8), B495–B508 (1970)CrossRefMATH

23.

Housos, E., Elmroth, T.: Automatic optimization of subproblems in scheduling airline crews. Interfaces 27(5), 68–77 (1997)CrossRef

24.

Musliu, N.: Local search algorithm for unicost set covering problem. In: Ali, M., Dapoigny, R. (eds.) IEA/AIE 2006. LNCS (LNAI), vol. 4031, pp. 302–311. Springer, Heidelberg (2006)CrossRef

25.

Azimi, Z.N., Toth, P., Galli, L.: An electromagnetism metaheuristic for the unicost set covering problem. Eur. J. Oper. Res. 205(2), 290–300 (2010)MathSciNetCrossRefMATH

26.

Beasley, J.E.: OR-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990)CrossRef

27.

Geem, Z.W.: Music-Inspired Harmony Search Algorithm: Theory and Applications, 1st edn. Springer, Heidelberg (2009)CrossRef

28.

Geem, Z.W., Kim, J., Loganathan, G.V.: A new heuristic optimization algorithm: harmony search. Simulation 76(2), 60–68 (2001)CrossRef

29.

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press and McGraw-Hill Book Company, Cambridge (2001)MATH

30.

Omran, M.G.H., Mahdavi, M.: Global-best harmony search. Appl. Math. Comput. 198(2), 643–656 (2008)MathSciNetMATH

31.

Xiang, W., An, M., Li, Y., He, R., Zhang, J.: An improved global-best harmony search algorithm for faster optimization. Expert Syst. Appl. 41(13), 5788–5803 (2014)CrossRef

32.

Klenke, A.: Probability Theory: A Comprehensive Course. Springer, London (2008)CrossRefMATH

33.

Srinivas, M., Patnaik, L.: Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans. Syst. Man Cybern. 24, 656–667 (1994)CrossRef

34.

Crawford, B., Soto, R., Monfroy, E.: Cultural algorithms for the set covering problem. In: Tan, Y., Shi, Y., Mo, H. (eds.) ICSI 2013, Part II. LNCS, vol. 7929, pp. 27–34. Springer, Heidelberg (2013)CrossRef

Titel: Binary Harmony Search Algorithm for Solving Set-Covering Problem
verfasst von: Juan Salas
Broderick Crawford
Ricardo Soto
Álvaro Gómez Rubio
Adrián Jaramillo
Sebastián Mansilla Villablanca
Eduardo Olguín
Verlag: Springer International Publishing
Buch: Trends in Applied Knowledge-Based Systems and Data Science
Print ISBN: 978-3-319-42006-6

Electronic ISBN: 978-3-319-42007-3

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-42007-3_78

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"