algoritmos geneticos

4.1.3 Algoritmos Genéticos
1. Introducción
Los algoritmos genéticos (AG) proporcionan un método de aprendizaje basado en la analogía con la evolución de las especies. Los AG generan un conjunto de hipótesis mediante la mutación y recombinación de parte del conjunto de hipótesis conocido. En cada paso el conjunto de hipótesis conocido como "población actual" se renueva remplazando unaproporción de esta población por los sucesores de las hipótesis más "adecuadas" (mediante el uso de una función de evaluación).
La popularidad de los AG se debe en parte a que la evolución es un método robusto y bien probado dentro de los sistemas biológicos naturales. Además son fácilmente paralelizables, lo que supone una ventaja gracias al abaratamiento actual de los costes en hardware. Por otraparte, los AG pueden realizar búsquedas en espacios de hipótesis que contienen complejas interacciones entre las distintas partes, donde el impacto de cada parte sobre la función de evaluación es difícil de especificar.
Aunque no se garantice encontrar la solución óptima, los AG generalmente encuentran soluciones con un alto grado de acierto.
2. Algoritmos Genéticos
El objetivo de los AG es buscardentro de un espacio de hipótesis candidatas la mejor de ellas. En los AG la "mejor hipótesis" es aquella que optimiza a una métrica predefinida para el problema dado, es decir, la que más se aproxima a dicho valor numérico una vez evaluada por la función de evaluación.
El comportamiento básico de un algoritmo genético es el siguiente: de forma iterativa va actualizando la población dehipótesis. En cada iteración, todos los miembros de la población son procesados por la función de evaluación, tras lo cual una nueva población es generada. La nueva generación estará compuesta por:
Las mejores hipótesis de la población actual (seleccionadas probabilísticamente)
Y el resto de hipótesis necesarias para mantener el número, que se consiguen mediante el cruce de individuos. A partir de doshipótesis padre (seleccionadas probabilisticamente a partir de la población actual) se generan dos hipótesis hijas recombinando sus partes siguiendo algún criterio establecido.
Una vez llegados a este punto (con una nueva población con el mismo número de individuos), a un determinado porcentaje de la población se le aplica un operador de mutación.
Representación de Hipótesis
Las hipótesis en losAG se suelen representar mediante cadenas de bits, de forma que puedan ser fácilmente manipulables por los operadores genéticos de mutación y cruce. 
Primero veamos como usar una cadena de bits para representar los posibles valores de un atributo. Si un atributo puede tomar tres valores posibles (A,B y C), una manera de representarlo es mediante tres bits de forma que: 
Atributo (100) = puedetomar el valor A 
Atributo (010) = puede tomar el valor B 
Atributo (001) = puede tomar el valor C 
Atributo (110) = puede tomar el valor A ó B (A or B) 
Atributo (111) = puede tomar el valor A, B ó C (A or B or C). No importa el valor del atributo. 
De esta forma podemos representar fácilmente conjunciones de varios atributos para expresar restricciones (precondiciones) mediante laconcatenación de dichas cadenas de bits.
Ejemplo: 
"Tiempo" puede ser Despejado, Nublado o Lluvioso. 
"Viento" puede ser Fuerte o Moderado.
(Tiempo = Nublado ó Lluvioso) y (Viento = Fuerte) se representaría con la siguiente cadena: 011 10.
Las postcondiciones de las reglas se pueden representar de la misma forma. Por ello una regla se puede describir como la concatenación de la precondición y lapostcondición.
Ejemplo: 
"JugaralTenis" puede ser Cierto o Falso. 
Si Viento = Fuerte entonces JugaralTenis = Cierto se representaría mediante la cadena 111 10 10. Donde los tres primeros bits a uno indican que el atributo "Tiempo" no afecta a nuestra regla.
Cabe destacar que una regla del tipo 111 10 11 no tiene demasiado sentido, puesto que no impone restricciones en la postcondición. Para...