Evaluación heurística

Mé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

Supongamos que estamos estudiando un problema combinatorio para el que ya tenemos un método de referencia exacto (óptimo). Por una heurístico H y un dato d, notamos H(d) el costo de la solución heurística y OPT(d) el costo óptimo. Llamamos desempeño relativo de H en d al cociente: RH (d) = H (d) / OPT (d).

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 heurística

Evaluación a priori

Llamamos a la relación de rendimiento del peor caso PH de una heurística H su peor desempeño relativo en el conjunto de datos posibles: PH = max {RH (d), para cualquier d} válido.

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.

Sin embargo, podemos obtener una evaluación si tenemos una evaluación predeterminada B (d) para el OPT óptimo (d) con: RH (d) = H (d) / OPT (d) ≤ H (d) / B (d). En particular, si H (d) = B (d), entonces hemos alcanzado el óptimo global. Siempre es posible encontrar un límite al óptimo global mediante un método ingenuo o codicioso.

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.

Compartir, repartir