Medidas de calidad de un algoritmo

Universidad Politécnica de Tulancingo
Medidas de calidad de un algoritmo

Ingeniería Industrial ll71
Equipo 3 & Equipo 4

Octubre de 2014

Ingeniería Industrial ll71

(Institute)Investigación de operaciones ll

10/14

1/8

Medidas de calidad de un algoritmo

Un buen algoritmo heurístico debe de tener las siguientes propiedades:
1

E…ciente: un esfuerzo computacionalrealista para la obtención de la
solución.

2

Bueno: La solución debe de estar cerca del algoritmo

3

Robusto: La probabilidad de obtener una mala solución.

Para medir la calidad de unheurístico existen diversos procedimientos:

Ingeniería Industrial ll71

(Institute)

Investigación de operaciones ll

10/14

2/8

Comparación de la solución óptima

Este procedimiento nospermite medir la calidad del método
heurístico. Normalmente se mide, para cada uno de los ejemplos, la
deviación porcentual de la solución heurística frente a la optima.
Llamando :
Ch al coste de lasolución del algoritmo heurístico.
En un problema de minimización la desviación porcentual viene dada por:
Ch

Copt
Copt

Ingeniería Industrial ll71

(Institute)

100

Investigación deoperaciones ll

10/14

3/8

Comparación de la solución óptima

Este procedimiento nos permite medir la calidad del método
heurístico. Normalmente se mide, para cada uno de los ejemplos, ladeviación porcentual de la solución heurística frente a la optima.
Llamando :
Ch al coste de la solución del algoritmo heurístico.
Copt al coste d de la solución optima de un ejemplo dado.
En unproblema de minimización la desviación porcentual viene dada por:
Ch

Copt
Copt

Ingeniería Industrial ll71

(Institute)

100

Investigación de operaciones ll

10/14

3/8

Comparacióncon una cota

Cuando el optimo del problema no esta disponible ni para un conjunto
limitado de ejemplos, el método alternativo consiste en comparar el
valor de la solución que proporciona el...