Procedimiento de búsqueda adaptativa aleatoria voraz

El procedimiento de búsqueda adaptativa aleatoria voraz (también conocido como GRASP ) es un algoritmo metaheurístico comúnmente aplicado a problemas de optimización combinatoria . GRASP generalmente consiste en iteraciones formadas por construcciones sucesivas de una solución aleatoria voraz y mejoras iterativas subsiguientes de la misma mediante una búsqueda local . ^[¹^] Las soluciones aleatorias voraces se generan agregando elementos al conjunto de soluciones del problema a partir de una lista de elementos clasificados por una función voraz según la calidad de la solución que lograrán. Para obtener variabilidad en el conjunto de soluciones voraces candidatas, los elementos candidatos bien clasificados a menudo se colocan en una lista de candidatos restringida (RCL) y se eligen al azar al construir la solución. Este tipo de método de construcción aleatoria voraz también se conoce como heurística semivoraz , descrita por primera vez en Hart y Shogan (1987). ^[²^]

GRASP se introdujo por primera vez en Feo y Resende (1989). ^{[ 3 ]} Los artículos de revisión sobre GRASP incluyen Feo y Resende (1995), ^{[ 1 ]} y Resende y Ribeiro (2003). ^{[ 4 ]}

Existen variaciones del algoritmo clásico, como el GRASP reactivo. En esta variación, el parámetro básico que define la restricción del RCL durante la fase de construcción se autoajusta según la calidad de las soluciones encontradas previamente. ^{[ 5 ]} También existen técnicas para acelerar la búsqueda, como perturbaciones de costos, funciones de sesgo, memorización y aprendizaje, y búsqueda local en soluciones parcialmente construidas. ^{[ 4 ]}

Véase también

Referencias

1 2 Feo, Thomas A.; Resende, Mauricio GC (1995). "Procedimientos de búsqueda adaptativa aleatoria voraz". Journal of Global Optimization . 6 (2): 109– 133. doi : 10.1007/BF01096763 . S2CID 2110014 .
↑ Hart, JP; Shogan, AW (julio de 1987). "Heurísticas semicodiciosas: un estudio empírico". Operations Research Letters . 6 (3): 107– 114. doi : 10.1016/0167-6377(87)90021-6 .
↑ Feo, Thomas A.; Resende, Mauricio GC (abril de 1989). "Una heurística probabilística para un problema de cobertura de conjuntos computacionalmente difícil". Operations Research Letters . 8 (2): 67– 71. doi : 10.1016/0167-6377(89)90002-3 .
1 2 Resende, Mauricio GC; Ribeiro, Celso C. (2003). "Procedimientos de búsqueda adaptativa aleatoria voraz". Manual de metaheurísticas . Springer. pp. 219–249 . ISBN 978-0-306-48056-0.
↑ Prais, Marcelo; Ribeiro, Celso C. (2000). "GRASP reactivo: una aplicación a un problema de descomposición matricial en la asignación de tráfico TDMA". INFORMS Journal on Computing . 12 (3): 164– 176. doi : 10.1287/ijoc.12.3.164.12639 .

[Feo1995-1] 1 2 Feo, Thomas A.; Resende, Mauricio GC (1995). "Procedimientos de búsqueda adaptativa aleatoria voraz". Journal of Global Optimization . 6 (2): 109– 133. doi : 10.1007/BF01096763 . S2CID 2110014 .

[2] Hart, JP; Shogan, AW (julio de 1987). "Heurísticas semicodiciosas: un estudio empírico". Operations Research Letters . 6 (3): 107– 114. doi : 10.1016/0167-6377(87)90021-6 .

[3] Feo, Thomas A.; Resende, Mauricio GC (abril de 1989). "Una heurística probabilística para un problema de cobertura de conjuntos computacionalmente difícil". Operations Research Letters . 8 (2): 67– 71. doi : 10.1016/0167-6377(89)90002-3 .

[Resende2003-4] 1 2 Resende, Mauricio GC; Ribeiro, Celso C. (2003). "Procedimientos de búsqueda adaptativa aleatoria voraz". Manual de metaheurísticas . Springer. pp. 219–249 . ISBN 978-0-306-48056-0.

[5] Prais, Marcelo; Ribeiro, Celso C. (2000). "GRASP reactivo: una aplicación a un problema de descomposición matricial en la asignación de tráfico TDMA". INFORMS Journal on Computing . 12 (3): 164– 176. doi : 10.1287/ijoc.12.3.164.12639 .

[

[

[ 3 ]

[ 4 ]

[ 5 ]