00 IntroduccionGA

Breve introducción a la
computación evolutiva
Ing. Christian D. von Lücken Martínez
Facultad Politécnica
Universidad Nacional de Asunción

Presentación con parte de material extraído desde
www.lania.mx/~ccoello/

1

Temas
• Historia de la computación evolutiva
• Algoritmos genéticos

Técnicas Clásicas de Búsqueda y
Optimización
Existen muchas técnicas clásicas para resolver
problemas conciertas características específicas.
• optimización lineal: el método Simplex,
• optimización no lineal:
 métodos directos, ej. búsqueda aleatoria,
 métodos no directos, ej. el método del gradiente
conjugado,
 técnicas que construyen parcialmente una solución a
un problema, ej. la programación dinámica y el método
de ramificación y búsqueda (branch & bound).
3

Técnicas Clásicas de Búsqueda yOptimización

Necesidad de métodos alternativos:
problemas difíciles de resolver
• Existen problemas que no se pueden resolver
usando un algoritmo que requiere tiempo
polinomial.
• En muchas aplicaciones prácticas, no podemos
siquiera decir si existe una solución eficiente.
• Hay muchos problemas para los cuales el mejor
algoritmo que se conoce requiere tiempo
exponencial.

¿Qué hace a un problemadifícil de
resolver?
• El número de posibles soluciones en el espacio
de búsqueda es tan grande que imposibilita
realizar una búsqueda exhaustiva para encontrar
la mejor solución.
• El problema es tan complejo que para encontrar
una respuesta es necesario utilizar un modelo
muy simplificado y por ello posiblemente alejado
de la realidad, por lo que los resultados
obtenidos son de poca utilidadpráctica.
6

¿Qué hace a un problema difícil de
resolver?
• La función de evaluación que describe la calidad
de cualquier solución propuesta es ruidosa o
varía con el tiempo, por lo que es necesario
trabajar con un conjunto de soluciones posibles
en lugar de una única solución.

7

¿Qué hace a un problema difícil de
resolver?
• Las posibles soluciones poseen muchas
restricciones, por lo queincluso la construcción
de una posible solución es difícil, y más aún la
búsqueda de una solución óptima.
• La persona que resuelve el problema está
inadecuadamente preparada o imagina alguna
barrera psicológica que le impide descubrir una
solución.
8

El problema del viajero
Encontrar una permutación que represente el
recorrido de una serie de ciudades de tal forma que
todas sean visitadasminimizando la distancia total
viajada.
Si consideramos n ciudades:
• El tamaño del espacio de búsqueda es: (n-1)!/2
• Para n=10, hay unas 181,000 soluciones posibles
• Para n=20 hay 10,000,000,000,000,000
• Para n=50 hay unas 10 x 1025 soluciones posibles

Necesidad de heuristicas

10

¿Qué es una heurística?
La palabra "heurística" se deriva del griego heuriskein,
que significa "encontrar" o"descubrir".
El significado del término ha variado históricamente.
Algunos han usado el término como un antónimo de
"algorítmico".
"a un proceso que puede resolver un cierto problema,
pero que no ofrece ninguna garantía de lograrlo, se
le denomina una 'heurística' para ese problema“
Newell et al.

¿Qué es una heurística?
Las heurísticas fueron un área predominante en los
orígenes de la InteligenciaArtificial.
El término suele usarse como adjetivo, refiriéndose a:
cualquier técnica que mejore el desempeño en
promedio de la solución de un problema, aunque no
mejore necesariamente el desempeño en el peor caso
Russell & Norvig, 1995.

¿Qué es una heurística?
Una heurística es una técnica que busca soluciones
buenas (es decir, casi óptimas) a un costo
computacional razonable, aunque sin garantizarfactibilidad u optimalidad de las mismas. En
algunos casos, ni siquiera puede determinar qué
tan cerca del óptimo se encuentra una solución
factible en particular.
Reeves (1993)

Ejemplos de técnicas heurísticas
•
•
•
•
•

Simulated Annealing,
Tabu Search
Ant Systems
Particle Swarm Optimization
Computación Evolutiva (Algoritmos evolutivos):
– Evolutionary Programming (Programación evolutiva)
–...