Publicación:
AUTOMATIC GENERATION OF A HYBRID ALGORITHM FOR THE MAXIMUM INDEPENDENT SET PROBLEM USING GENETIC PROGRAMMING

Vista sencilla de ítem
dc.creatorCARLOS RODRIGO REY BARRA
dc.date2023
dc.date.accessioned2025-01-10T15:38:58Z
dc.date.available2025-01-10T15:38:58Z
dc.date.issued2023
dc.description.abstractONE OF GRAPH OPTIMIZATION?S FUNDAMENTAL AND MOST CHALLENGING PROBLEMS IS DETERMINING THE MAXIMUM SET OF UNCONNECTED VERTICES IN A GRAPH, CALLED THE MAXIMUM INDEPENDENT SET PROBLEM. THIS PROBLEM CONSISTS OF FINDING THE LARGEST INDEPENDENT SET IN A GRAPH, WHERE AN INDEPENDENT SET IS A SET OF VERTICES SUCH THAT NO TWO VERTICES ARE ADJACENT. THIS PAPER PRESENTS A NEW ARTIFICIALLY GENERATED ALGORITHM FOR THE MAXIMUM INDEPENDENT SET PROBLEM. THE NEW ALGORITHM IS GENERATED BY THE AUTOMATIC GENERATION OF ALGORITHMS, A TECHNIQUE THAT ALLOWS THE CONSTRUCTION OF NEW HYBRID ALGORITHMS, TAKING ADVANTAGE OF EXISTING ALGORITHMS. THUS, THE AUTOMATIC GENERATION OF ALGORITHMS COMBINES BASIC HEURISTICS FOR THE PROBLEM, A TABU SEARCH METHOD SELECTED FROM THE LITERATURE, AND AN EXACT METHOD THAT SOLVES THE PROBLEM?S MATHEMATICAL FORMULATION WORKING FOR A LIMITED COMPUTATIONAL TIME. WITH THESE COMPONENTS, THE SPACE OF POSSIBLE ALGORITHMS IS TRAVERSED BY EMPLOYING GENETIC PROGRAMMING. ALGORITHMS OF SMALL SIZES ARE GENERATED TO STUDY THEIR STRUCTURE AND DISCOVER NEW ALGORITHMIC COMBINATIONS. THEN, WE SELECT THE ALGORITHM THAT FINDS SOLUTIONS WITH THE BEST COMPUTATIONAL PERFORMANCE AMONG ALL THE GENERATED ALGORITHMS. THIS BEST ALGORITHM IS COMPARED WITH THREE STATE-OF-THE-ART ALGORITHMS FOR THE PROBLEM, PRESENTING THE BEST COMPUTATIONAL PERFORMANCE FOR THE 131 INSTANCES IN THE LITERATURE.
dc.formatapplication/pdf
dc.identifier.doi10.1016/j.asoc.2023.110474
dc.identifier.issn1872-9681
dc.identifier.issn1568-4946
dc.identifier.urihttps://repositorio.ubiobio.cl/handle/123456789/13010
dc.languagespa
dc.publisherAPPLIED SOFT COMPUTING
dc.relation.uri10.1016/j.asoc.2023.110474
dc.rightsPUBLICADA
dc.subjectMetaheuristics
dc.subjectMaximum independent set problem
dc.subjectInteger programming
dc.subjectHeuristics
dc.subjectGenetic programming
dc.subjectAutomatic generation of algorithm
dc.titleAUTOMATIC GENERATION OF A HYBRID ALGORITHM FOR THE MAXIMUM INDEPENDENT SET PROBLEM USING GENETIC PROGRAMMING
dc.typeARTÍCULO
dspace.entity.typePublication
ubb.EstadoPUBLICADA
ubb.Otra ReparticionDEPARTAMENTO DE INGENIERIA INDUSTRIAL
ubb.SedeCONCEPCIÓN
Archivos
Colecciones
Artículos científicos