## 3.5 ALGORITMOS DE APROXIMACIÓN

Existen problemas muy complicados para los que no sabemos como encontrar su solución óptima, o bien, conocemos el algoritmo que permite encontrar la solución óptima, pero requiere una cantidad excesiva de tiempo (tiene un tiempo de ejecución no polinómico). En estos casos utilizaremos algoritmos heurísticos o aproximados que proporcionan soluciones más o menos próximas a la óptima en un tiempo de ejecución polinómico permiten resolver ejemplares del problema de tamaños que serían inabordables utilizando el algoritmo óptimo. Muchos de los algoritmos heurísticos y aproximados son algoritmos ávidos.

Fundamentos de los Algoritmos de Aproximación

Los algoritmos de aproximación surgen de la inquietud de la comunidad científica en los años 70's, donde se pensó que las dos clases P y NP eran distintas y que por lo tanto no había algoritmos de tiempo polinomial que fuesen capaces de resolver estos problemas de optimización derivados de problemas NP. Sin embargo dado que existían muchos problemas que tenían fuertes aplicaciones en la práctica era importante determinar la tratabilidad computacional de ellos, por lo que muchos investigadores comenzaron a considerar relajaciones de estos problemas de manera que se obtuvieran versiones que fueran tratables. Así nace la primera relajación considerada que fue la condición de "optimabilidad", por lo que se enfocaron a la construcción de algoritmos de aproximación que trabajan en tiempo polinomial y que calculan soluciones cercanas al óptimo global en un tiempo pequeño; es decir, soluciones que garantizaran estar dentro de un factor multiplicativo de la solución óptima.

Lo interesante de la solución de estos problemas es, que si son algoritmos de aproximación, ¿qué tanto se aproximan a su solución real y cuál es un valor garantizado de exactitud?, para ello existe una métrica teórica estándar para medir la calidad de un algoritmo de aproximación, que es el cociente para el peor de los casos que indica que tan cerca del valor óptimo están las soluciones encontradas por un algoritmo de aproximación. Dicha cercanía puede ser expresada como el cociente del valor obtenido por el algoritmo de aproximación sobre el valor de la solución óptima.

Características de los Algoritmos de aproximación

- Son un tipo especial de heurísticos que siempre encuentran una solución. El error máximo de la solución obtenida está acotado. Esta cota puede ser:

- valor máximo de la diferencia (en valor absoluto) entre la solución obtenida y la óptima.

- valor máximo de la razón entre la solución óptima y la obtenida.

- Es un algoritmo que corre en tiempo polinomial (idealmente) y que produce una solucion que está dentro de un factor garantizado de la solución óptima.
- Debemos encontrar una demostración matemática de la existencia de la cota. No existe un algoritmo aproximado para todos los problemas para los que existe un heurístico.

En la Naturaleza existen muchos procesos que buscan un estado estable. Dichos procesos pueden contemplarse como procesos naturales de optimización. En los últimos años se han propuesto varios algoritmos de optimización global que simulan estos procesos naturales de optimización. Tres ejemplos clásicos, son:

a) Recocido Simulado (Simulated Annealing), basado en el proceso natural de enfriamiento de un sólido hasta que alcanza su punto de equilibrio.

b) Algoritmos Evolutivos, basados en el concepto de evolución biológica. Entre los mismos se pueden considerar las siguientes ramas : Algoritmos Genéticos, Estrategias Evolutivas, Programación Evolutiva y Programación Genética.

c) Redes Neuronales Artificiales, basadas en procesos relacionados con el sistema nervioso central.

###