Caminata de muestreo adaptativo: una búsqueda local autónoma simple y eficiente

Área de la Ciencia:

• La inteligencia artificial es la inteligencia artificial.
• Operaciones Investigación Investigación
• Ciencias de la computación Ciencias de la computación

Sus antecedentes:

• Los métodos tradicionales de búsqueda local a menudo requieren una extensa sintonización de parámetros para un rendimiento óptimo.
• El desarrollo de algoritmos de búsqueda autónomos que se adapten a las características del problema es un desafío clave.

Objetivo del estudio:

• Introducir y explorar algoritmos de búsqueda local de vecindario parcial automatizados y adaptativos.
• Diseñar métodos de búsqueda local que funcionen con requisitos previos mínimos y sin ajuste de parámetros.

Principales métodos:

• Algoritmos extendidos de caminata de muestras y caminata de ID.
• Cálculos basados en la distancia incorporados en una ventana deslizante para determinar dinámicamente el tamaño de la evaluación del vecindario.
• Se desarrollaron técnicas de búsqueda local libres de parámetros.

Principales resultados:

• Métodos libres de parámetros evaluados empíricamente en cuatro clases de problemas de optimización combinatoria de referencia.
• Comparación del rendimiento con las versiones de parámetros fijos.
• Demostró resultados robustos y competitivos en diversos problemas con diferentes representaciones de soluciones, estructuras de vecindario y paisajes de fitness.

Conclusiones:

• Los enfoques de búsqueda local sin parámetros son viables y efectivos.
• Los métodos de búsqueda local autónoma ofrecen una alternativa genérica y robusta a los algoritmos sintonizados por parámetros.
• Los métodos propuestos validan el potencial de la búsqueda local genérica autónoma.