A self-adaptive biogeography-based algorithm to solve the set covering problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 3, pp. 1033-1059.

Using the approximate algorithms, we are faced with the problem of determining the appropriate values of their input parameters, which is always a complex task and is considered an optimization problem. In this context, incorporating online control parameters is a very interesting issue. The aim is to vary the parameters during the run so that the studied algorithm can provide the best convergence rate and, thus, achieve the best performance. In this paper, we compare the performance of a self-adaptive approach for the biogeography-based optimization algorithm using the mutation rate parameter with respect to its original version and other heuristics. This work proposes altering some parameters of the metaheuristic according to its exhibited efficiency. To test this approach, we solve the set covering problem, which is a classical optimization benchmark with many industrial applications such as line balancing production, crew scheduling, service installation, databases, among several others. We illustrate encouraging experimental results, where the proposed approach is capable of reaching various global optimums for a well-known instance set taken from the Beasleys OR-Library, and sometimes, it improves the results obtained by the original version of the algorithm.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2019039
Classification : 68W25, 90C27, 93B40
Mots-clés : Metaheuristics, biogeography-based optimization algorithm, set covering problem
Crawford, Broderick 1 ; Soto, Ricardo 1 ; Olivares, Rodrigo 1 ; Riquelme, Luis 1 ; Astorga, Gino 1 ; Johnson, Franklin 1 ; Cortés, Enrique 1 ; Castro, Carlos 1 ; Paredes, Fernando 1

1 
@article{RO_2019__53_3_1033_0,
     author = {Crawford, Broderick and Soto, Ricardo and Olivares, Rodrigo and Riquelme, Luis and Astorga, Gino and Johnson, Franklin and Cort\'es, Enrique and Castro, Carlos and Paredes, Fernando},
     title = {A self-adaptive biogeography-based algorithm to solve the set covering problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1033--1059},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {3},
     year = {2019},
     doi = {10.1051/ro/2019039},
     zbl = {07127062},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2019039/}
}
TY  - JOUR
AU  - Crawford, Broderick
AU  - Soto, Ricardo
AU  - Olivares, Rodrigo
AU  - Riquelme, Luis
AU  - Astorga, Gino
AU  - Johnson, Franklin
AU  - Cortés, Enrique
AU  - Castro, Carlos
AU  - Paredes, Fernando
TI  - A self-adaptive biogeography-based algorithm to solve the set covering problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 1033
EP  - 1059
VL  - 53
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2019039/
DO  - 10.1051/ro/2019039
LA  - en
ID  - RO_2019__53_3_1033_0
ER  - 
%0 Journal Article
%A Crawford, Broderick
%A Soto, Ricardo
%A Olivares, Rodrigo
%A Riquelme, Luis
%A Astorga, Gino
%A Johnson, Franklin
%A Cortés, Enrique
%A Castro, Carlos
%A Paredes, Fernando
%T A self-adaptive biogeography-based algorithm to solve the set covering problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 1033-1059
%V 53
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2019039/
%R 10.1051/ro/2019039
%G en
%F RO_2019__53_3_1033_0
Crawford, Broderick; Soto, Ricardo; Olivares, Rodrigo; Riquelme, Luis; Astorga, Gino; Johnson, Franklin; Cortés, Enrique; Castro, Carlos; Paredes, Fernando. A self-adaptive biogeography-based algorithm to solve the set covering problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 3, pp. 1033-1059. doi : 10.1051/ro/2019039. http://www.numdam.org/articles/10.1051/ro/2019039/

S. Al-Shihabi, M. Arafeh and M. Barghash, An improved hybrid algorithm for the set covering problem. Comput. Ind. Eng. 85 (2015) 328–334.

F. Amini and P. Ghaderi, Hybridization of harmony search and ant colony optimization for optimal locating of structural dampers. App. Soft Comput. 13 (2013) 2272–2280.

E. Balas and M.C. Carrera, A dynamic subgradient-based branch-and-bound procedure for set covering. Oper. Res. 44 (1996) 875–890. | Zbl

J. Beasley, An algorithm for set covering problem. Eur. J. Oper. Res. 31 (1987) 85–93. | Zbl

J. Beasley and K. Jørnsten, Enhancing an algorithm for set covering problems. Eur. J. Oper. Res. 58 (1992) 293–300. | Zbl

A. Caprara, M. Fischetti, P. Toth, D. Vigo and P.L. Guida, Algorithms for railway crew management. Math. Program. 79 (1997) 125–141. | Zbl

M. Caserta, Tabu search-based metaheuristic algorithm for large-scale set covering problems. In: Metaheuristics. Springer Nature, Basingstoke (2007) 43–63. | Zbl

B. Crawford, R. Soto, G. Astorga, J. Garca, C. Castro and F. Paredes, Putting continuous metaheuristics to work in binary search spaces. Complexity 2017 (2017) 1–19. | Zbl

B. Crawford, R. Soto, N. Berros, F. Johnson and F. Paredes, Solving the set covering problem with binary cat swarm optimization. In: Advances in Swarm and Computational Intelligence, Springer Nature, Basingstoke (2015) 41–48.

B. Crawford, R. Soto, N. Berros, F. Johnson, F. Paredes, C. Castro and E. Norero, A binary cat swarm optimization algorithm for the non-unicost set covering problem. Math. Prob. Eng. 2015 (2015) 1–8. | Zbl

B. Crawford, R. Soto, R. Cuesta and F. Paredes, Application of the artificial bee colony algorithm for solving the set covering problem. Sci. World J. 2014 (2014) 1–8.

B. Crawford, R. Soto, E. Monfroy, W. Palma, C. Castro and F. Paredes, Parameter tuning of a choice-function based hyperheuristic using particle swarm optimization. Expert Syst. App. 40 (2013) 1690–1695.

B. Crawford, R. Soto, E. Monfroy, F. Paredes and W. Palma, A hybrid ant algorithm for the set covering problem. Int. J. Phys. Sci. 6 (2011) 4667–4673.

B. Crawford, R. Soto, C. Olea, F. Johnson and F. Paredes, Binary bat algorithms for the set covering problem. In 2015 10th Iberian Conference on Information Systems and Technologies (CISTI). Institute of Electrical and Electronics Engineers (IEEE) (2015).

B. Crawford, R. Soto, M. Olivares-Suárez and F. Paredes, A binary firefly algorithm for the set covering problem. In Advances in Intelligent Systems and Computing. Springer Nature, Basingstoke (2014) 65–73.

B. Crawford, R. Soto, M. Olivares-Suárez and F. Paredes, A binary firefly algorithm for the set covering problem. In: 3rd Computer Science On-line Conference 2014 (CSOC 2014). Vol. 285 of Advances in Intelligent Systems and Computing. Springer International Publishing, Cham (2014) 65–73.

B. Crawford, R. Soto, C. Peña, W. Palma, F. Johnson and F. Paredes, Solving the set covering problem with a shuffled frog leapingalgorithm. In: Intelligent Information and Database Systems. Springer Nature, Basingstoke (2015) 41–50.

B. Crawford, R. Soto, C. Torres-Rojas, C. Peña, M. Riquelme-Leiva, S. Misra, F. Johnson and F. Paredes, A binary fruit fly optimization algorithm to solve the set covering problem. In: Computational Science and Its Applications – ICCSA 2015. Springer Nature, Basingstoke (2015) 411–420.

R. Cuesta, B. Crawford, R. Soto and F. Paredes, An artificial bee colony algorithm for the set covering problem. In: Advances in Intelligent Systems and Computing. Springer Nature, Basingstoke (2014) 53–63.

M.L. Fisher and P. Kedia, Optimal solution of set covering/partitioning problems using dual heuristics. Manage. Sci. 36 (1990) 674–688. | Zbl

B.A. Foster and D.M. Ryan, An integer programming approach to the vehicle scheduling problem. Oper. Res. Q. (1970–1977) 27 (1976) 367. | Zbl

T.W. Francesca Rossi And P. Vanbeek, Handbook of Constraint Programming (Foundations of Artificial Intelligence). Elsevier Science, Amsterdam (2006). | Zbl

M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1979). | Zbl

L. Han, G. Kendall and P. Cowling, An adaptive length chromosome hyper-heuristic genetic algorithm for a trainer scheduling problem. In: Recent Advances in Simulated Evolution and Learning. World Scientific Pub Co Pte Lt (2004) 506–525.

A. Jaramillo, B. Crawford, R. Soto, S. Misra, E. Olgun, Á.G. Rubio, J. Salas and S.M. Villablanca, An approach to solve the set covering problem with the soccer league competition algorithm. In: Computational Science and Its Applications – ICCSA 2016. Springer Nature, Basingstoke (2016) 373–385.

G. Lan, G.W. Depuy and G.E. Whitehouse, An effective and simple heuristic for the set covering problem. Eur. J. Oper. Res. 176 (2007) 1387–1403. | Zbl

A.H. Land and A.G. Doig, An automatic method of solving discrete programming problems. Econometrica 28 (1960) 497. | Zbl

H. Lilliefors, On the kolmogorov-smirnov test for normality with mean and variance unknown. J. Am. Stat. Assoc. 62 (1967) 399–402.

H. Ma and D. Simon, Biogeography-based optimization with blended migration for constrained optimization problems. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation. Association for Computing Machinery (ACM) (2010).

H. Ma and D. Simon, Evolutionary Computation with Biogeography-based Optimization. Wiley-ISTE (2017).

H. Mann and W. Donald, On a test of whether one of two random variables is stochastically larger than the other. Ann. Math. Stat. 18 (1947) 50–60. | Zbl

Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Springer Nature, Basingstoke (1996). | Zbl

S. Mirjalili and A. Lewis, S-shaped versus v-shaped transfer functions for binary particle swarm optimization. Swarm Evol. Comput. 9 (2013) 1–14.

H. Mo and L. Xu, Biogeography migration algorithm for traveling salesman problem. Int. J. Intel. Comput. Cybern. 4 (2011) 311–330. | Zbl

D.N. Mudaliar and N.K. Modi, Unraveling travelling salesman problem by genetic algorithm using m-crossover operator. In: 2013 International Conference on Signal Processing, Image Processing & Pattern Recognition. Institute of Electronics Engineers IEEE (2013).

M.G.R. Panos and M. Pardalos, Handbook of Applied Optimization, Oxford University Press, Oxford (2002). | Zbl

S.H.A. Rahmati and M. Zandieh, A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem. Int. J. Adv. Manuf. Technol. 58 (2011) 1115–1129.

Á.G. Rubio, B. Crawford, R. Soto, E. Olgun, S. Misra, A. Jaramillo, S.M. Villablanca and J. Salas, Solving the set covering problem with a binary black hole inspired algorithm . In: Computational Science and Its Applications – ICCSA 2016. Springer Nature, Basingstoke (2016) 207–219.

B.M. Smith, Impacs – a bus crew scheduling system using integer programming. Math. Program. 42 (1988) 181–187.

R. Soto, B. Crawford, S. Misra, W. Palma, E. Monfroy, C. Castro and F. Paredes, Choice functions for autonomous search in constraint programming: GA vs PSO. Tech. Gazette 20 (2013) 621–629.

R. Soto, B. Crawford, A. Muñoz, F. Johnson and F. Paredes, Pre-processing, repairing and transfer functions can help binary electromagnetism-like algorithms. In: Advances in Intelligent Systems and Computing. Springer Nature, Basingstoke (2015) 89–97.

R. Soto, B. Crawford, R. Olivares, J. Barraza, F. Johnson and F. Paredes, A binary cuckoo search algorithm for solving the set covering problem. In: Lecture Notes in Computer Science. Springer Nature, Basingstoke (2015) 88–97.

R. Soto, B. Crawford, W. Palma, K. Galleguillos, C. Castro, E. Monfroy, F. Johnson and F. Paredes, Boosting autonomous search for CSPs via skylines. Inf. Sci. 308 (2015) 8–48.

R. Soto, B. Crawford, W. Palma, E. Monfroy, R. Olivares, C. Castro and F. Paredes, Top-k based adaptive enumeration in constraint programming. Math. Prob. Eng. 2015 (2015) 1–12.

R. Soto, B. Crawford, E. Vega and F. Paredes, Solving manufacturing cell design problems using an artificial fish swarm algorithm. In: Lecture Notes in Computer Science. Springer Nature, Basingstoke (2015) 282–290.

S. Sundar and A. Singh, A hybrid heuristic for the set covering problem. Oper. Res. 12 (2010) 345–365. | Zbl

G.M. Thompson, A simulated-annealing heuristic for shift scheduling using non-continuously available employees. Comput. Oper. Res. 23 (1996) 275–288. | Zbl

C. Toregas, R. Swain, C. Revelle and L. Bergman, The location of emergency service facilities. Oper. Res. 19 (1971) 1363–1373. | Zbl

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

X. Zhang, Q. Kang, J. Cheng and X. Wang, A novel hybrid algorithm based on biogeography-based optimization and grey wolf optimizer. App. Soft Comput. 67 (2018) 197–214.

B. Zhao, C. Deng, Y. Yang and H. Peng, Novel binary biogeography-based optimization algorithm for the knapsack problem. In: Lecture Notes in Computer Science. Springer Nature, Basingstoke (2012) 217–224.

F. Zhao, S. Qin, Y. Zhang, W. Ma, C. Zhang and H. Song, A two-stage differential biogeography-based optimization algorithm and its performance analysis. Expert Syst. App. 115 (2019) 329–345.

Cité par Sources :