algoritmo genético presentacion

LOGO

ALGORITMO GENÉTICO

IVÁN BETANCOURT

PEDRO HURTADO

ANTECEDENTES [1]

Los Algoritmos Genéticos fueron introducidos por John Holland, investigador en la Universidad de Michigan, en 1970, inspirándose en el proceso observado en la evolución natural de los seres vivos. En un principio denominó a esta técnica como “planes reproductivos”, pero se hizo popular bajo el nombre de "algoritmos genéticos" tras la publicación de su libro (Holland, 1975).

DEFINICIÓN

Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas

CROMOSOMA: se refiere a un candidato a solución del problema, que a menudo se codifica como una cadena de bits.

GEN: son tanto un bit como bloques cortos de bits adyacentes que codifican un elemento particular del candidato.

ALELO en una cadena de bits será un 0 o un 1 (Las diferentes posibilidades de escoger un rasgo)

SIGNIFICADO EN UN AG[2]

ELEMENTOS Y FUNCIONAMIENTO [2]

1. UNA REPRESENTACIÓN CROMOSOMICA A MODO DE CODIGO

2. UNA POBLACION INICIAL

3. UNA MEDIDA DE EVALUACIÓN

4. UN CRITERIO DE SELECCIÓN DE CROMOSOMAS

5. UNA O VARIAS OPERACIONES DE RECOMBINACIÓN O CRUCE

6. UNA O VARIAS OPERACIONES DE MUTACIÓN.

7. UNA O VARIAS REGENERACIONES DE LA POBLACION.

8. UNA CONDICION DE FIN DEL ALGORITMO.

LA FUNCIÓN OBJETIVO: proporciona una medida de desempeño del sistema asociado a ciertos individuos en la población.

EVOLUCIÓN DE LA POBLACIÓN: es la responsable de asignarle valores altos o bajos de adaptación, puede decir que tal bueno o que tan malo será los resultados y la convergencia o no del método

OPERACIÓN DE SELECCIÓN: busca escoger ciertos individuos de la población, quienes darán origen a poblaciones futuras.

ELEMENTOS Y FUNCIONAMIENTO [2]

OPERACIÓN DE CRUCE: consiste en mezclar la información genética de dos individuos a fin de generar nuevos individuos

OPERACIÓN MUTACIÓN : consiste en alterar las características genéticas de un individuo, con el objetivo de aumentar la probabilidad de exploración

ELEMENTOS Y FUNCIONAMIENTO [2]

SITUACIÓN DINÁMICA

Población inicial.

cromosomas: [A, B, C, D, ].

Cromosomas y cadena de genesCromosoma A=<A1, A2, A3, A4, A5, A6, A7, A8, A9, A10 >

Cromosoma B=<B1, B2, B3, B4, B5, B6, B7, B8, B9, B10 >

HIJOS INTERCAMBIAR GENES ENTRE 1-K (GEN)

HIJO 1 =< B1, B2, B3, B4, B5, B6, A7, A8, A9, A10 >

HIJO 2 =< A1, A2, A3, A4, A5, A6, B7, B8, B9, B10 >

SITUACIÓN DINÁMICA

SITUACIÓN DINÁMICA

HIJO =< 0, 1, 1, 1, 1, 0, 1, 0, 0, 1 >

MUTACIÓN =< 0, 1, 1, 1, 0, 0, 1, 0, 0, 1 >

Ventajas

No necesitan conocimientos específicos sobre el problema que intentan resolver.

Operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales.

Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivamente

paralelas.

desventajas

Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen tamaño de la población, número de generaciones, etc

Pueden converger prematuramente debido a una serie de problemas de diversa índole.

 no se garantiza que el Algoritmo Genético encuentre la solución óptima

Cuando utilizar un algoritmo genético

La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables.

Parámetros a tener en cuenta Su espacio de búsqueda (i.e., sus posibles soluciones)

debe estar delimitado dentro de un cierto rango. Debe poderse definir una función de aptitud que nos

indique qué tan buena o mala es una cierta respuesta.

Cuando utilizar un algoritmo genético

Es recomendable intentar resolver problemas que tengan espacios de búsqueda discretos aunque éstos sean muy grandes. Sin embargo, también podrá intentarse usar la técnica con espacios de búsqueda continuos, pero preferentemente cuando exista un rango de soluciones relativamente pequeño.

Aplicación en el ajuste de controladores con el fin de obtener resultados adecuada. Ejemplo: valores adecuados en las variables un controlador PID

OPERADORES GENÉTICOS

Etilismo: evita que la población mas apta desaparezca en caso de no generar descendencia.

Reinicialización: permite una nueva ejecución tras una convergencia tomando como punto de partida una nueva población aleatoria.

Repoblación: se emplea cuando el algoritmo se estanca para generar nueva poblacion.

Clonación: se duplican genes de algunos cromosomas para garantizar la supervivencia para la generacion siguiente.

INCONVENIENTES

Convergencia prematura: el espacio de búsqueda se presenta alrededor de un punto descuidando otros que tambien son de interés por ser posibles soluciones.

Terminación lenta: no garantiza siempre encontrar una solución factible en un tiempo plausible.

Inhabilidad frente a soluciones no factibles: puede llegar a una solución sin respetar las restricciones la solución es introducir un elemento de penalización.

Referencias

[1] Tolmos Rodríguez Piedad. Introducción a los algoritmos geneticos y sus aplicaciones. tolmos@poseidon.fcjs.urjc.es

[2] Baños Marín Ignacio. Programación de la secuencia de fabricación en una maquina, con tiempos de preparación variables, mediante la aplicación de algoritmos genéticos. Escuela técnica superior d’Enginyeria industrial de Barcelona. 2003. pág. 22-32

[3] Amador Díaz Pedro. inteligencia artificial. Universitat Oberta De Catalunya 2011

[4]http://openaccess.uoc.edu/webapps/o2/bitstream/10609/11313/1/pamadorTFC0112memoria.pdf

[5 ]Banzhaf W. Reeves C. (editors) (1999) Foundations of Genetic Algorithms.5Morgan Kaufmann Publishers

ESTRUCTURA GENERAL ALGORITMO GENÉTICO

EJEMPLO ALGORITMO GENÉTICO EN EL CONTROL

Sintonizar un control PID mediante algoritmos genéticos.

El cometido del AG es el de buscar una combinación óptima de los coeficientes Kp, Ki y Kd (proporcional, integral y derivativo) del control PID.

EJEMPLO ALGORITMO GENÉTICO EN EL CONTROL

Codificación cromosoma

Cada coeficiente corresponde a un gen

EJEMPLO ALGORITMO GENÉTICO EN EL CONTROL

Función objetivo

el valor calidad corresponde a la media de los valoresabsolutos del error del sistema de control PID, durante la vida del individuo

vida de cada individuo= 2 seg

Con este límite de vida, se evalúan 55 individuos en unos 2 minutos.

EJEMPLO ALGORITMO GENÉTICO EN EL CONTROL

En una primera etapa se genera una población inicial que en el caso que nos ocupa es de 5 individuos, estos surgen de sucesivas mutaciones de un cromosoma semilla.

En la primera iteración del bucle, no se pasa por la etapa de valuación ni selección y se

llega directamente a la de reproducción.

EJEMPLO ALGORITMO GENÉTICO EN EL CONTROL

La reproducción consisten en cruzar los 5 individuos mejor adaptados entre si, de forma que obtenemos 10 individuos más.

Una vez tenemos 15 individuos en la población, se evalúa cada uno durante 2 segundos y se les otorga una calidad que denota con que bondad se han adaptado al medio.

Más tarde, en la etapa de selección, se marcan los 5 individuos mejor adaptados almedio, estos son los que tendrán derecho a reproducirse en el ciclo siguiente.

Ejemplo [3]

DEFINICIÓN

Los Algoritmos Genéticos son métodos adaptativos usados para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.