Contenido
PalancaMétodos para evaluar heurísticas
El problema de evaluar la heurística es crucial. De hecho, la heurística no ofrece ninguna garantía de optimización: pueden encontrar el óptimo para ciertos datos o estar muy lejos de él.
Desempeño relativo
por un problema de minimización, Rh (d) ≥ 1. También podemos hablar de distancia al óptimo como porcentaje con la fórmula: 100 * (RH (d) - 1). El desempeño relativo es una evaluación de la heurística que puede estar acotada a priori (con las pruebas) o impredecible a posteriori (después de las pruebas).
Evaluación a priori
Esta es una garantía de desempeño obtenida por análisis teórico de H. Para esto limitamos RH (d) para cualquier dato d, entonces construimos un dato que muestre que este peor de los casos realmente se puede alcanzar. Este resultado es muy difícil de obtener y, a menudo, no es posible calcularlo, en particular para todas las heurísticas que no incluyen caracteres de elección matemática.
Tome un ejemplo de una heurística de minimización con PH = 1,5. Esto significa que sean cuales sean los datos de entrada, la heurística nunca dará un resultado más de 50% por encima del óptimo general. "Nunca" ya que ha sido probado matemáticamente.
Evaluación a posteriori: límites inferiores
Cuando la evaluación de la heurística antes de la ejecución es imposible, todavía es posible evaluar los resultados después de la ejecución de la heurística H. Hemos visto el rendimiento relativo, pero este método solo se aplica si es posible conocer el óptimo global.
Evaluación estadística
Las evaluaciones a priori y a posteriori de la heurística siguen planteando un problema: ¿cuándo hay problemas muy importantes? La evaluación heurística más simple consiste en comparar las soluciones con las que se dan en los puntos de referencia o los métodos de uso generalizado. El valor de la solución, sobre un gran conjunto de pruebas, en comparación con métodos conocidos, proporciona una buena aproximación de la eficiencia de la heurística.