Skip to main content
Top
Published in:

2019 | OriginalPaper | Chapter

A Binary Grasshopper Optimisation Algorithm Applied to the Set Covering Problem

Authors : Broderick Crawford, Ricardo Soto, Alvaro Peña, Gino Astorga

Published in: Cybernetics and Algorithms in Intelligent Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Many of the problems addressed at the industrial level are of a combinatorial type and a sub-assembly not less than these are of the NP-hard type. The design of algorithms that solve combinatorial problems based on the continuous metaheuristic of swarm intelligence is an area of interest at an industrial level. In this article, we explore a general binarization mechanism of continuous metaheuristics based on the percentile concept. In particular, we apply the percentile concept to the Grasshopper optimization algorithm in order to solve the set covering problem (SCP). The experiments are designed with the aim of demonstrating the usefulness of the percentile concept in binarization. Additionally, we verify the effectiveness of our algorithm through reference instances. The results indicate the binary grasshopper optimization algorithm (BGOA) obtains adequate results when evaluated with a combinatorial problem such as the SCP.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

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!

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!

Literature
1.
go back to reference Khatibinia, M., Yazdani, H.: Accelerated multi-gravitational search algorithm for size optimization of truss structures. Swarm Evol. Comput. (2017) Khatibinia, M., Yazdani, H.: Accelerated multi-gravitational search algorithm for size optimization of truss structures. Swarm Evol. Comput. (2017)
2.
go back to reference Barman, S., Kwon, Y.-K.: A novel mutual information-based boolean network inference method from time-series gene expression data. PloS one 12(2), e0171097 (2017)CrossRef Barman, S., Kwon, Y.-K.: A novel mutual information-based boolean network inference method from time-series gene expression data. PloS one 12(2), e0171097 (2017)CrossRef
3.
go back to reference Crawford, B., Soto, R., Monfroy, E., Astorga, G.. García, J., Cortes, E.: A meta-optimization approach for covering problems in facility location. In: Workshop on Engineering Applications, pp. 565–578. Springer (2017) Crawford, B., Soto, R., Monfroy, E., Astorga, G.. García, J., Cortes, E.: A meta-optimization approach for covering problems in facility location. In: Workshop on Engineering Applications, pp. 565–578. Springer (2017)
4.
go back to reference García, J., Crawford, B., Soto, R., Astorga, G.: A percentile transition ranking algorithm applied to knapsack problem. In: Proceedings of the Computational Methods in Systems and Software, pp. 126–138. Springer (2017) García, J., Crawford, B., Soto, R., Astorga, G.: A percentile transition ranking algorithm applied to knapsack problem. In: Proceedings of the Computational Methods in Systems and Software, pp. 126–138. Springer (2017)
5.
go back to reference García, J., Crawford, B., Soto, R., García, P.: A multi dynamic binary black hole algorithm applied to set covering problem. In: International Conference on Harmony Search Algorithm, pp. 42–51. Springer (2017) García, J., Crawford, B., Soto, R., García, P.: A multi dynamic binary black hole algorithm applied to set covering problem. In: International Conference on Harmony Search Algorithm, pp. 42–51. Springer (2017)
6.
go back to reference García, J., Crawford, B., Soto, R., Astorga, G.: A percentile transition ranking algorithm applied to binarization of continuous swarm intelligence metaheuristics. In: International Conference on Soft Computing and Data Mining, pp. 3–13. Springer (2018) García, J., Crawford, B., Soto, R., Astorga, G.: A percentile transition ranking algorithm applied to binarization of continuous swarm intelligence metaheuristics. In: International Conference on Soft Computing and Data Mining, pp. 3–13. Springer (2018)
7.
go back to reference Franceschetti, A., Demir, E., Honhon, D., Van Woensel, T., Laporte, G., Stobbe, M.: A metaheuristic for the time-dependent pollution-routing problem. Eur. J. Oper. Res. 259(3), 972–991 (2017)MathSciNetCrossRef Franceschetti, A., Demir, E., Honhon, D., Van Woensel, T., Laporte, G., Stobbe, M.: A metaheuristic for the time-dependent pollution-routing problem. Eur. J. Oper. Res. 259(3), 972–991 (2017)MathSciNetCrossRef
8.
go back to reference Crawford, B., Soto, R., Astorga, G., García, J., Castro, C., Paredes, F.: Putting continuous metaheuristics to work in binary search spaces. Complexity 2017 (2017)MathSciNetCrossRef Crawford, B., Soto, R., Astorga, G., García, J., Castro, C., Paredes, F.: Putting continuous metaheuristics to work in binary search spaces. Complexity 2017 (2017)MathSciNetCrossRef
9.
go back to reference Yang, X.-S., Deb, S.: Cuckoo search via lévy flights. In: 2009 World Congress on Nature and Biologically Inspired Computing, NaBIC 2009, pp. 210–214. IEEE (2009) Yang, X.-S., Deb, S.: Cuckoo search via lévy flights. In: 2009 World Congress on Nature and Biologically Inspired Computing, NaBIC 2009, pp. 210–214. IEEE (2009)
10.
go back to reference Hatamlou, A.: Black hole: a new heuristic optimization approach for data clustering. Inf. Sci. 222, 175–184 (2013)MathSciNetCrossRef Hatamlou, A.: Black hole: a new heuristic optimization approach for data clustering. Inf. Sci. 222, 175–184 (2013)MathSciNetCrossRef
11.
go back to reference Yang, X.-S.: A new metaheuristic bat-inspired algorithm. In: Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), pp. 65–74 (2010)CrossRef Yang, X.-S.: A new metaheuristic bat-inspired algorithm. In: Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), pp. 65–74 (2010)CrossRef
12.
go back to reference Saremi, S., Mirjalili, S., Lewis, A.: Grasshopper optimisation algorithm: theory and application. Adv. Eng. Softw. 105, 30–47 (2017)CrossRef Saremi, S., Mirjalili, S., Lewis, A.: Grasshopper optimisation algorithm: theory and application. Adv. Eng. Softw. 105, 30–47 (2017)CrossRef
13.
go back to reference Balaji, S., Revathi, N.: A new approach for solving set covering problem using jumping particle swarm optimization method. Nat. Comput. 15(3), 503–517 (2016)MathSciNetCrossRef Balaji, S., Revathi, N.: A new approach for solving set covering problem using jumping particle swarm optimization method. Nat. Comput. 15(3), 503–517 (2016)MathSciNetCrossRef
14.
go back to reference Gary, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness (1979) Gary, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness (1979)
15.
go back to reference Lu, Y., Vasko, F.J.: An or practitioner’s solution approach for the set covering problem. Int. J. Appl. Metaheuristic Comput. (IJAMC) 6(4), 1–13 (2015)CrossRef Lu, Y., Vasko, F.J.: An or practitioner’s solution approach for the set covering problem. Int. J. Appl. Metaheuristic Comput. (IJAMC) 6(4), 1–13 (2015)CrossRef
16.
go back to reference Li, Y., Cai, Z.: Gravity-based heuristic for set covering problems and its application in fault diagnosis. J. Syst. Eng. Electron. 23(3), 391–398 (2012)CrossRef Li, Y., Cai, Z.: Gravity-based heuristic for set covering problems and its application in fault diagnosis. J. Syst. Eng. Electron. 23(3), 391–398 (2012)CrossRef
17.
go back to reference Kasirzadeh, A., Saddoune, M., Soumis, F.: Airline crew scheduling: models, algorithms, and data sets. EURO J. Transp. Logist. 6(2), 111–137 (2017)CrossRef Kasirzadeh, A., Saddoune, M., Soumis, F.: Airline crew scheduling: models, algorithms, and data sets. EURO J. Transp. Logist. 6(2), 111–137 (2017)CrossRef
18.
go back to reference Horváth, M., Kis, T.: Computing strong lower and upper bounds for the integrated multiple-depot vehicle and crew scheduling problem with branch-and-price. Cent. Eur. J. Oper. Res. 1–29 (2017) Horváth, M., Kis, T.: Computing strong lower and upper bounds for the integrated multiple-depot vehicle and crew scheduling problem with branch-and-price. Cent. Eur. J. Oper. Res. 1–29 (2017)
19.
20.
go back to reference García, J., Crawford, B., Soto, R., Carlos, C., Paredes, F.: A k-means binarization framework applied to multidimensional knapsack problem. Appl. Intell. 1–24 (2017) García, J., Crawford, B., Soto, R., Carlos, C., Paredes, F.: A k-means binarization framework applied to multidimensional knapsack problem. Appl. Intell. 1–24 (2017)
21.
go back to reference García, J., Pope, C., Altimiras, F.: A distributed k-means segmentation algorithm applied to lobesia botrana recognition. Complexity 2017 (2017) García, J., Pope, C., Altimiras, F.: A distributed k-means segmentation algorithm applied to lobesia botrana recognition. Complexity 2017 (2017)
22.
go back to reference Graells-Garrido, E., García, J.: Visual exploration of urban dynamics using mobile data. In: International Conference on Ubiquitous Computing and Ambient Intelligence, pp. 480–491. Springer (2015) Graells-Garrido, E., García, J.: Visual exploration of urban dynamics using mobile data. In: International Conference on Ubiquitous Computing and Ambient Intelligence, pp. 480–491. Springer (2015)
23.
go back to reference Graells-Garrido, E., Peredo, O., García, J.: Sensing urban patterns with antenna mappings: the case of Santiago, Chile. Sensors 16(7), 1098 (2016)CrossRef Graells-Garrido, E., Peredo, O., García, J.: Sensing urban patterns with antenna mappings: the case of Santiago, Chile. Sensors 16(7), 1098 (2016)CrossRef
24.
go back to reference Peredo, O.F., García, J.A., Stuven, R., Ortiz, J.M.: Urban dynamic estimation using mobile phone logs and locally varying anisotropy. In: Geostatistics Valencia 2016, pp. 949–964. Springer (2017)CrossRef Peredo, O.F., García, J.A., Stuven, R., Ortiz, J.M.: Urban dynamic estimation using mobile phone logs and locally varying anisotropy. In: Geostatistics Valencia 2016, pp. 949–964. Springer (2017)CrossRef
Metadata
Title
A Binary Grasshopper Optimisation Algorithm Applied to the Set Covering Problem
Authors
Broderick Crawford
Ricardo Soto
Alvaro Peña
Gino Astorga
Copyright Year
2019
DOI
https://doi.org/10.1007/978-3-319-91192-2_1

Premium Partner