The multi-parent biased random-key genetic algorithm with implicit path-relinking and its real-world applications. (English) Zbl 1487.90646
Summary: In this paper, we present the Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking (BRKGA-MP-IPR), a variant of the Biased Random-Key Genetic Algorithm that employs multiple (biased) parents to generate offspring instead of the usual two, and is hybridized with a novel, implicit path-relinking local search procedure. By operating over the standard unit hypercube, such path-relinking mechanism leverages the population representation of the BRKGA and thus provides complete independence between the local search procedure and the problem definition and implementation. This approach contrasts with traditional path-relinking procedures that are tied to the problem structure. Having both BRKGA and IPR operate over the same solution space not only makes the intensification/diversification paradigm more natural but also greatly simplifies the development effort from the perspective of the practitioner, as one only needs to develop a decoder to map unit random-key vectors to the solution space of the problem on hand. Apart from such key benefits, extensive computational experiments solving real-world problems, such as over-the-air software upgrade scheduling, network design problems, and combinatorial auctions, show that the BRKGA-MP-IPR offers performance benefits over the standard BRKGA as well as the BRKGA with multiple parents.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Aiex, R. M.; Binato, S.; Resende, M. G.C., Parallel GRASP with path-relinking for job shop scheduling, Parallel Computing, 29, 4, 393-430 (2003) |
| [2] | Andrade, C. E.; Ahmed, S.; Nemhauser, G. L.; Shao, Y., A hybrid primal heuristic for finding feasible solutions to mixed integer programs, European Journal of Operational Research, 263, 1, 62-71 (2017) · Zbl 1380.90193 |
| [3] | Andrade, C. E.; Byers, S. D.; Gopalakrishnan, V.; Halepovic, E.; Poole, D. J.; Tran, L. K.; Volinsky, C. T., Connected cars in a cellular network: A measurement study, Proceedings of the 2017 internet measurement conference. Proceedings of the 2017 internet measurement conference, IMC ’17, 235-241 (2017), ACM: ACM New York, NY, USA |
| [4] | Andrade, C. E.; Byers, S. D.; Gopalakrishnan, V.; Halepovic, E.; Poole, D. J.; Tran, L. K.; Volinsky, C. T., Managing massive firmware-over-the-air updates for connected cars in cellular networks, Proceedings of the second ACM international workshop on smart, autonomous, and connected vehicular systems and services. Proceedings of the second ACM international workshop on smart, autonomous, and connected vehicular systems and services, CarSys ’17, 65-72 (2017), ACM |
| [5] | Andrade, C. E.; Byers, S. D.; Gopalakrishnan, V.; Halepovic, E.; Poole, D. J.; Tran, L. K.; Volinsky, C. T., Scheduling software updates for connected cars with limited availability, Applied Soft Computing, 82, 105575 (2019) |
| [6] | Andrade, C. E.; Miyazawa, F. K.; Resende, M. G.C., Evolutionary algorithm for the k-interconnected multi-depot multi-traveling salesmen problem, Proceedings of the fifteenth annual conference on genetic and evolutionary computation. Proceedings of the fifteenth annual conference on genetic and evolutionary computation, GECCO’13, 463-470 (2013), ACM: ACM New York, NY, USA |
| [7] | Andrade, C. E.; Resende, M. G.C.; Karloff, H. J.; Miyazawa, F. K., Evolutionary algorithms for overlapping correlation clustering, Proceedings of the sixteenth conference on genetic and evolutionary computation. Proceedings of the sixteenth conference on genetic and evolutionary computation, GECCO’14, 405-412 (2014), ACM: ACM New York, NY, USA |
| [8] | Andrade, C. E.; Resende, M. G.C.; Zhang, W.; Sinha, R. K.; Reichmann, K. C.; Doverspike, R. D.; Miyazawa, F. K., A biased random-key genetic algorithm for wireless backhaul network design, Applied Soft Computing, 33, 150-169 (2015) |
| [9] | Andrade, C. E.; Silva, T.; Pessoa, L. S., Minimizing flowtime in a flowshop scheduling problem with a biased random-key genetic algorithm, Expert Systems with Applications, 128, 67-80 (2019) |
| [10] | Andrade, C. E.; Toso, R. F.; Resende, M. G.C.; Miyazawa, F. K., Biased random-key genetic algorithms for the winner determination problem in combinatorial auctions, Evolutionary Computation, 23, 279-307 (2015) |
| [11] | Bean, J. C., Genetic algorithms and random keys for sequencing and optimization, ORSA Journal On Computing, 2, 6, 154-160 (1994) · Zbl 0807.90060 |
| [12] | Beiräo, N. C. L. F. (1997). Sistema de apoio à decisão para sequenciamento de operações em ambientes job shop. https://repositorio-aberto.up.pt/handle/10216/12242. |
| [13] | Birattari, M.; Yuan, Z.; Balaprakash, P.; Stützle, T., F-Race and iterated F-race: an overview, Experimental methods for the analysis of optimization algorithms, 311-336 (2010), Springer Berlin Heidelberg · Zbl 1204.68280 |
| [14] | Bresina, J. L., Heuristic-biased stochastic sampling, Proceedings of the thirteenth national conference on artificial intelligence. Proceedings of the thirteenth national conference on artificial intelligence, AAAI’96, 1, 271-278 (1996), AAAI Press |
| [15] | Caserta, M.; Reiners, T., A pool-based pattern generation algorithm for logical analysis of data with automatic fine-tuning, European Journal of Operational Research, 248, 2, 593-606 (2016) · Zbl 1347.62107 |
| [16] | Chan, T. M.; Pătraşcu, M., Counting inversions, offline orthogonal range counting, and related problems, Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, 161-173 (2010) · Zbl 1288.68105 |
| [17] | Conover, W. J., Practical nonparametric statistics (1980), John Wiley & Sons |
| [18] | Ericsson, M.; Resende, M. G.C.; Pardalos, P. M., A genetic algorithm for the weight setting problem in OSPF routing, Journal of Combinatorial Optimization, 6, 3, 299-333 (2002) · Zbl 1068.90092 |
| [19] | Fay, M. P.; Proschan, M. A., Wilcoxon-Mann-Whitney or t-test? On assumptions for hypothesis tests and multiple interpretations of decision rules, Statistics Surveys, 4, 1-39 (2010) · Zbl 1188.62154 |
| [20] | Festa, P.; Pardalos, P. M.; Pitsoulis, L. S.; Resende, M. G.C., GRASP with path relinking for the weighted MAXSAT problem, Journal of Experimental Algorithmics, 11 (2007) · Zbl 1140.68403 |
| [21] | Glover, F., Tabu search and adaptive memory programming — advances, applications and challenges, 1-75) (1997), Springer US: Springer US Boston, MA · Zbl 0882.90111 |
| [22] | Gonçalves, J. F.; Beirão, N. C.L. F., Um algoritmo genético baseado em chave aleatórias para sequenciamento de opearções, Investigação Operacional, 19, 123-137 (1999) |
| [23] | ISSN 1381-1231 |
| [24] | Gonçalves, J. F.; Resende, M. G.C., Biased random-key genetic algorithms for combinatorial optimization, Journal of Heuristics, 17, 487-525 (2011) |
| [25] | Gonçalves, J. F.; Resende, M. G.C., A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem, Journal of Combinatorial Optimization, 22, 2, 180-201 (2011) |
| [26] | Holland, J. H., Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence (1975), University of Michigan press · Zbl 0317.68006 |
| [27] | Kendall, M., A new measure of rank correlation, Biometrika, 30, 81-89 (1938) · Zbl 0019.13001 |
| [28] | Kramer, O., Genetic algorithm essentials (2017), Springer International Publishing AG · Zbl 1390.68003 |
| [29] | Lopes, M. C.; Andrade, C. E.; Queiroz, T. A.; Resende, M. G.C.; Miyazawa, F. K., Heuristics for a hub location-routing problem, Networks, 68, 1, 54-90 (2016) |
| [30] | López-Ibáñez, M.; Dubois-Lacoste, J.; Cáceres, L. P.; Birattari, M.; Stützle, T., The IRACE package: Iterated racing for automatic algorithm configuration, Operations Research Perspectives, 3, 43-58 (2016) |
| [31] | Lucena, M. L.; Andrade, C. E.; Resende, M. G.C.; Miyazawa, F. K., Some extensions of biased random-key genetic algorithms, Proceedings of the forty-sixth brazilian symposium of operational research. Proceedings of the forty-sixth brazilian symposium of operational research, XLVI SBPO, 2469-2480 (2014) |
| [32] | Mateus, G. R.; Resende, M. G.C.; Silva, R. M.A., GRASP with path-relinking for the generalized quadratic assignment problem, Journal of Heuristics, 17, 527-567 (2011) · Zbl 1233.90213 |
| [33] | Pessoa, L. S.; Andrade, C. E., Heuristics for a flowshop scheduling problem with stepwise job objective function, European Journal of Operational Research, 266, 3, 950-962 (2018) · Zbl 1403.90359 |
| [34] | Pessoa, L. S.; Resende, M. G.; Ribeiro, C. C., A hybrid Lagrangean heuristic with GRASP and path-relinking for set k-covering, Computers & Operations Research, 40, 12, 3132-3146 (2013) · Zbl 1348.90643 |
| [35] | Resende, M. G.C.; Ribeiro, C. C., A GRASP with path-relinking for private virtual circuit routing, Networks, 41, 2, 104-114 (2003) · Zbl 1028.90502 |
| [36] | Resende, M. G.C.; Ribeiro, C. C., Optimization by GRASP (2016), Springer-Verlag New York · Zbl 1356.90001 |
| [37] | Resende, M. G.C.; Toso, R. F.; Gonçalves, J. F.; Silva, R. M.A., A biased random-key genetic algorithm for the Steiner triple covering problem, Optimization Letters, 1-15 (2011) |
| [38] | Ribeiro, C. C.; Resende, M. G.C., Path-relinking intensification methods for stochastic local search algorithms, Journal of Heuristics, 18, 192-214 (2011) |
| [39] | Rochman, A. N.; Prasetyo, H.; Nugroho, M. T., Biased random key genetic algorithm with insertion and gender selection for capacitated vehicle routing problem with time windows, AIP Conference Proceedings, 1855, 1, 020025 (2017) |
| [40] | Stefanello, F.; Aggarwal, V.; Buriol, L. S.; Gonçalves, J. F.; Resende, M. G.C., A biased random-key genetic algorithm for placement of virtual machines across geo-separated data centers, Proceedings of the 2015 on genetic and evolutionary computation conference. Proceedings of the 2015 on genetic and evolutionary computation conference, GECCO ’15, 919-926 (2015), ACM: ACM New York, NY, USA |
| [41] | Whitley, D.; Rana, S.; Heckendorn, R. B., The island model genetic algorithm: On separability, population size and convergence, Journal of Computing and Information Technology, 7, 33-47 (1998) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
