GRASP: procedimientos de búsquedas miopes aleatorizados y adaptativos

• Autores: José Luis González Velarde, Mauricio G.C. Resende
• Localización: Inteligencia artificial: Revista Iberoamericana de Inteligencia Artificial, ISSN-e 1988-3064, ISSN 1137-3601, Vol. 7, Nº. 19, 2003, págs. 61-76
• Idioma: español
• Enlaces
  • Texto completo
• Resumen

  • Una entre las metaheuristicas mas exitosas que aparecieron en los ultimos aos del siglo pasado es GRASP,un metodo multi-arranque dise~ nado para resolver problemas dificiles en optimizacion combinatoria. En su version basica cada iteracion consiste en dos fases: una fase constructiva cuyo producto es una solucion factible buena, aunque no necesariamente un optimo local, y una busqueda local, durante la cual se examinan vecindades de la solucion, al llegar a un optimo local la iteracion termina. La iteraciones continuan, guardando la mejor soluci on encontrada en cada una de ellas, hasta que se alcanza un criterio de terminacion. En este capitulo se revisan las componentes basicas de GRASP, junto con algunas estrategias para el ajuste de parametros como es GRASP reactivo. De aqui sigue una discusion acerca del uso de reencadenamiento de trayectorias como una forma de introducir aspectos de memoria dentro de la busqueda local. El capitulo concluye con una descripcion de GRASP en paralelo, con una extensa experimentacion para comparar implementaciones independientes contra ooperativas.