Clase1

• Resolución de Problemas
• Métodos de Búsqueda
• Evolución Natural
• Programas Evolutivos
• Técnicas de Representación Genética

Resoluciónde Problemas

La resoluciónde problemas puede ser considerada como un proceso de búsqueda enun espacio de estados o espacio de configuración.

	Conjunto de Parámetros
	Trayectorias entreEstados
Soluciones buscadas	Estrategias
	Reglas
	Acciones, etc.

Losproblemas de la vida real involucran sistemas sumamente complejos, quepueden caracterizarse por.

• Intratabilidad
• Alta dimensionalidad
• Muchos subsistemas
• Realimentación
• Multimodalidad
• Ruido y/o incertidumbre
• Presencia de singularidades, etc.

En sintesis, losespacios de estados asociados son de muy alta dimensionalidad y complejaestructura.  Dificultando el proceso de busqueda de soluciones.

Métodosde Búsqueda

La búsquedaes un proceso básico en la operación de un computador.

Los métodos tradicionales de búsqueda son, por lo general:

• Basados en cálculo
• Enumerativos
• Estocásticos

Limitaciones: sonmuy dependientes de información sobre eldominio del problema yla alta dimensionalidad del espacio de estado los tornaineficientes. Estaslimitaciones generan lanecesidad por nuevas alternativas de búsqueda...

Los seres vivoshan utilizadouna estrategia sumamente exitosa para resolver el complejo problemadebúsqueda de especies sobrevivientes.

Método : EvoluciónNatural

Proceso : Adaptarse alambiente

Recompensa: Supervivencia

EvoluciónNatural

	Especializaciónestructural y funcional.
Propiedades Emergentes	Organizaciónde información.
	Representaciónparticular del conocimiento.

AspectosBásicos de la Evolución Natural

Dosprocesos primarios:

Selecciónnatural: determina los individuos aptos que deben participar en reproducción.
Reproducción: asegura recombinación y mezcla de razgos de los padres en los hijos.

Larecombinaciónde la informacion paterna permite una evolución más rápida.
Todos los aspectosdel proceso no están lo suficientemente claros, tampoco lo estánlas posibles causas que lo impulsaron.

• La evoluciónocurre a nivel de los cromosomas.
• Los cromosomas codificanla estructura de los seres.
• La codificacióny decodificación de la información anivel genetico es esencialpara la existencia.
• La selecciónnatural relaciona los cromosomas con la calidad de ejecución delser codificado.
• Durante la reproducciónocurre la evolución.
• Mutacióny recombinación del material genético son los mecanismosbasicos de reproducción.
• La evolucion naturalno posee memoria. en el banco genético de la población actualestá todo lo que se conoce sobre la especie.

ProgramasEvolutivos

Varios investigadoresreconocieron que este proceso podría ser muypoderoso en la resoluciónde problemas complejos:

Rechemberg(1973) Fogel (1966) Glover (1977) Holland(1975) Koza (1991) asi surgen:

• Estrategias Evolutivas
• ProgramaciónEvolutiva
• Técnicasde Búsqueda Dispersivas
• Algoritmos Genéticos
• ProgramaciónGenética

Los programas evolutivosenfocan el proceso de resolución de problemas a través deuna dinámica evolutiva, emulando la selección de los másaptos y la reproducción de las especies.

La dinámicaevolutiva genera trayectorias en el espacio de estados. Es de esperarseque se logre una "poda" apreciable del espacio de búsqueda, obviandotrayectorias que no son productivas.

Definiciónde los Programas Evolutivos

Son procesosestocásticos de cómputo iterativo ejecutados sobreuna población de estructuras representando solucionespotencialesa un problema. En cada ciclo del proceso (generacion) se evalúan las estructuras en la poblacion actual en cuanto a su efectividad comosoluciones del problema. En base a esta evaluación se implementauna estrategia reproductiva que genera una nueva población,en la cual se le da más importancia a las mejores estructurasprevias. El proceso se ejecuta hasta alcanzar soluciones satisfactorias.

Aspectos aemular en los Programas Evolutivos

Codificacióny decodificación de estructuras de información tipo  cromosomas(soluciones potenciales).

Poblaciónde estructuras (banco genético)

Mecanismo de seleccióncon su función de aptitud asociada (ambiente).

Un proceso de reproducciónque permita la alteración parcial y recombinación de la informaciónen las estructuras. Implica definición de operadores de evoluciónque emulen las mutaciones y la reproducción sexual.

Anatomíade los Programas Evolutivos

Componentes básicos:

Representación(Genética)	Problema
PoblaciónInicial	Problema y/o DinámicaEvolutiva
Funciónde Aptitud	Problema
Mecanismos deSelección	DinámicaEvolutiva
Operadores Evolutivos	DinámicaEvolutiva
Parámetrosde Control	Dinámicaevolutiva

Pseudocódigo de losProgramas Evolutivos

inicio
	t= 0
	inicializarP(t)
	evaluarP(t)
	mientras(nocumpla condición de terminación) hacer
	inicio
	t =t+1
	seleccionarP(t) a partir de P(t-1)
	modificarP(t)
	evaluarP(t)
	fin
fin

Técnicasde Representación Genética

En general larepresentación de las potenciales soluciones depende delproblema considerado.

Jerga:	Individuoso genotipos
	Cromosomas(uno por individuo)

A pesar de existiralgunas estructuras comúnmente utilizadas, la tendencia modernaes a emplear estructuras de datos que o bien no difieran de las ya utilizadasen el dominio del problema o se adapten convenientemente a éste.

La forma máscomún es la de una cadena de símbolos de longitud fija.

Símbolospertenecientes a un alfabeto finito de la menor cardinalidad posible.

La representaciónmás antigua, estudiada y empleada es la binaria. (cadenade bits). Hayevidencias de que puede ser óptima.

AlgorítmosGenéticos: programas evolutivos que emplean exclusivamente representaciónbinaria.

Otras metodologíasevolutivas usan diferentes formas de representación:

• n-tuplas de númerosreales
• listas de símbolosde longitud variable
• listas de listas
• grafos en particularárboles (variables) etc.

Su estudio teóricoha sido muy pobre.
Los operadoresgeneticos asociados no son de implementación trivial. (lenguaje).

Ejemplos de RepresentaciónGenética

Cadena de bits:

11001010100001110010011100100100(32 bits)

Posible semántica:Depende de los problemas considerados. Algunos ejemplos para ciertos  problemas tipos:

Optimizacion:valor de uno o mas parametros en un rango de busqueda.
Dilema del prisionero:estrategia de juego para un jugador.
TSP: ordenamientode las ciudades.
Control: valoresde los parametros del dispositivo de control.
Knapsack: listade objetos a empacar.

Otros esquemasde representación:

Opt.:	1.34 5.772.03 0.76	N-tupla de reales
TSP:	C D F E A G IH B J	Lista de ciudades
Control:	7 4 5 3 2 1 56 2 3	Lista de octales
TSP:	Matrices de Hopfield.

En general cualquierestructura de datos sobre la cual se puedan definir operadores adecuadosde evolución es viable,