The Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking and its real-world applications

• Tipo: Artigo em Revista Científica Internacional
• Data: 2021

Autores

Andrade, CE (Autor) Outra; Toso, RF (Autor) Outra; Jose Fernando Goncalves (Autor) Outra; Resende, MGC (Autor) Outra

Revista

Título: European Journal of Operational Research

Vol. 289

Páginas: 17-30

ISSN: 0377-2217

Editora: Elsevier

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 4 Citações

Outras Informações

ID Authenticus: P-00S-SP3

DOI: 10.1016/j.ejor.2019.11.037

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 14