Algoritmo Genetico

Integrantes:Ernesto Macario

Dysbert TovarHumberto

NietoYen Po Chih

Introduccion

Los algoritmos genéticos (AG), fueron inventados en 1975 por John Holland, de la Universidad de Michigan. Los AG son, simplificando, algoritmos de optimización, es decir, tratan de encontrar la mejor solución a un problema dado entre un conjunto de soluciones posibles.

John Holland desde pequeño, se preguntaba cómo logra la naturaleza, crear seres cada vez más perfectos. No sabía la respuesta, pero tenía una cierta idea de como hallarla: tratando de hacer pequeños modelos de la naturaleza, que tuvieran alguna de sus características, y ver cómo funcionaban, para luego extrapolar sus conclusiones a la totalidad.

Por tanto, cuando Holland se enfrentó a los AG, los objetivos de su investigación fueron dos:• imitar los procesos adaptativos de los sistemas naturales.• diseñar sistemas artificiales (normalmente programas) que retengan los mecanismos importantes de los sistemas naturales.

Concepto de Algoritmo Genético

Los AG 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. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los mas fuertes, postulados por Darwin (1859). Por imitación de este proceso, los AG 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.

En la naturaleza los individuos de una población compiten entre si en la búsqueda de recursos tales como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en la búsqueda de un compañero. Aquellos individuos que tienen mas éxito en sobrevivir y en atraer compañeros tienen mayor probabilidad de generar un gran numero de descendientes. Por el contrario individuos poco dotados producirán un menor numero de descendientes.

Clase de Algoritmo Geneticos

Algoritmos Genéticos GeneracionalesSe asemejan a la forma de reproducción de los insectos, donde una generación pone huevos, se aleja geográficamente o muere y es substituida por una nueva. En este momento se realizan cruces en una piscina de individuos, los descendientes son puestos en otra, al final de la fase reproductiva se elimina la generación anterior y se pasa a utilizar la nueva. Este modelo también es conocido como Algoritmo Genético Canónico.

Algoritmos Genéticos de estado Fijo.Utilizan el esquema generacional de los

mamíferos y otros animales de vida larga, donde coexisten padres y sus descendientes, permitiendo que los hijos sean educados por sus progenitores, pero también que a la larga se genere competencia entre ellos. En este modelo, no solo se deben seleccionar los dos individuos a ser padres, si no también cuales de la población anterior serán eliminados, para dar espacio a los descendientes.

La diferencia esencial entre el reemplazo generacional y el modelo de estado fijo es que las estadísticas de la población son recalculadas luego de cada cruce y los nuevos descendientes están disponibles inmediatamente para la reproducción. Esto permite al modelo utilizar las características de un individuo prometedor tan pronto como es creado.

Algoritmos Genéticos Paralelos.Parte de la metáfora biológica que motivo a

utilizar la búsqueda genética consiste en que es inherentemente paralela, donde al evolucionar se recorren simultáneamente muchas soluciones, cada una representada por un individuo de la población.

Sin embargo, es muy común en la naturaleza que no solo sea una población evolucionando, si no varias poblaciones, normalmente aisladas geográficamente, que originan respuestas diferentes a la presión evolutiva. Esto origina dos modelos que toman es cuenta esta variación, y utilizan no una población como los anteriores si4 no múltiples concurrentemente.

Modelos de Islas.Si se tiene una población de individuos, esta se divide en subpoblaciones que evolucionan independientemente como un Algoritmo Genético normal. Ocasionalmente, se producen migraciones entre ellas, permitiéndoles intercambiar material genético. Con la utilización de la migración, este modelo puede explotar las diferencias en las subpoblaciones; esta variación representa una fuente de diversidad genética. Sin embargo, si un número de individuos emigran en cada generación, ocurre una mezcla global y se eliminan las diferencias locales, y si la migración es infrecuente, es probable que se produzca convergencia prematura en las subpoblaciones.

Modelo CelularColoca cada individuo en una matriz, donde cada uno sólo podrá buscar reproducirse con los individuos que tenga a su alrededor (mas cerca de casa) escogiendo al azar o al mejor adaptado. El descendiente pasara a ocupar una posición cercana. No hay islas en este modelo, pero hay efectos potenciales similares. Asumiendo que el cruce esta restringido a individuos adyacentes, dos individuos separados por 20 espacios están tan aislados como si estuvieran en dos islas, este tipo de separación es conocido como aislamiento por distancia.

Luego de la primera evaluación, los individuos están todavia distribuidos al azar sobre la matriz. Posteriormente, empiezan a emerger zonas como cromosomas y adaptaciones semejantes. La reproducción y selección local crea tendencias evolutivas aisladas, luego de varias generaciones, la competencia local resultara en grupos mas grandes de individuos semejantes.

Elemento de un Algoritmo GeneticoComo los Algoritmos Genéticos se encuentra basados en los

procesos de evolución de los seres vivos, casi todos sus conceptos se basan en conceptos de biología y genética que son fáciles de comprender. 

• es un ser que caracteriza su propia especie.es un cromosoma y es el codigo de información sobre el cual opera el algoritmo. Cada solución parcial del problema a optimizar está codificada en forma de cadena o String en un alfabeto determinado, que puede ser binario. Una cadena representa a un cormosoma, por lo tanto tambien a un individuo y cada posición de la cadena representa a un gen.

Individuo

•A un conjunto de individuos (Cromosomas) se le denomina población. El método de A.G´s consiste en ir obteniendo de forma sucesiva distintas poblaciones. Por otra parte un Algoritmo Genético trabaja con un conjunto de puntos representativos de diferentes zonas del espacio de búsqueda y no con un solo punto (como lo hace Hillclimbing).

Población 

Operadores GeneticoSon los diferentes métodos u operaciones que se

pueden ejercer sobre una población y que nos permite obtener poblaciones nuevas. Una vez que se ha evaluado cada individuo sobre una función fitness, se aplican los operadores genéticos.

Operador de seleccion

• El paso siguiente a la evaluación es escoger los miembros de la población que serán utilizados para la reproducción. Su meta es dar mas oportunidades de selección a los miembros más aptos de la población.

Operador de Cruce

• Consiste en unir en alguna forma los cromosomas de los padres que han sido previamente selecciónados de la generación anterior para formar dos descendientes

• El operador cruce se aplica en dos pasos: en el primero los individuos se aparean (se seleccionan de dos a dos) aleatoriamente con una determinada probabilidad, llamada probabilidad de cruce Pc; en el segundo paso a cada par de individuos seleccionados anteriormente se le aplica un intercambio en su contenido desde una posición aleatoria K hasta el final, con K Î [1, m-1], donde m es la longitud de individuo

• El objetivo del operador de cruce es recombinar subcadenas de forma eficiente; esta gestión recibe el nombre de construcción de bloques.

Mutacion• El operador de mutación

consiste en la alteración aleatoria de cada uno de los genes del individuo con una probabilidad de mutación PM.

• El objetivo de la mutación es producir diversidad en la población. Si al generar aleatoriamente la población inicial o después de varias generaciones, en la misma posición de todos los cromosomas sólo aparece un único elemento del alfabeto utilizado, esto supondrá que con los operadores de reproducción y cruce, nunca cambiara dicho elemento, por lo que puede ocurrir que jamas se alcance la solución más optima a nuestro problema.

El Algoritmo Genetico SimpleBEGIN /* Algoritmo Genetico Simple */ Generar una poblacion inicial. Computar la funcion de evaluacion de cada individuo. WHILE NOT Terminado DO BEGIN /* Producir nueva generacion */ FOR Tamano~ poblacion/2 DO BEGIN /*Ciclo Reproductivo */ Seleccionar dos individuos de la anterior generacion, para el cruce (probabilidad de seleccion proporcional a la funcion de evaluacion del individuo). Cruzar con cierta probabilidad los dos individuos obteniendo dos descendientes. Mutar los dos descendientes con cierta probabilidad. Computar la funcion de evaluacion de los dos descendientes mutados. Insertar los dos descendientes mutados en la nueva generacion. END IF la poblacion ha convergido THEN Terminado := TRUE ENDEND

El Algoritmo Genetico Simple, tambien denominado Canonico.Se necesita una codificacion o representacion del problema, que resulte adecuada al mismo. Ademas se requiere una funcion de ajuste o adaptacion al problema, la cual asigna un numero real a cada posible solucion codicada. Durante la ejecucion del algoritmo, los padres deben ser seleccionados para la reproduccion, a continuacion dichos padres seleccionados se cruzaran generando dos hijos, sobre cada uno de los cuales actuara un operador de mutacion. El resultado de la combinacion de las anteriores funciones sera un conjunto de individuos (posibles soluciones al problema), los cuales en la evolucion del Algoritmo Genetico formaran parte de la siguiente poblacion.

Ventajas de los Algoritmo Genetico

·Los algoritmos genéticos están íntimamente relacionados, pues operan de forma simultánea con varias soluciones y no de manera secuencial como lo hacen las técnicas tradicionales.·Los algoritmos genéticos explotan un sinnúmero de soluciones y si se llegan a encontrar con solucion4es suboptimas, simplemente desechan esta opción y continúan con otra opción de solución, caso contrario a los tradicionales pues estos tienen que abandonar su trabajo y empezar desde cero nuevamente.·La habilidad que poseen para manipular muchos parámetros simultáneamente, y se torna interesante cuando se presenta el caso de resolver varios objetivos a la vez.·No es necesario tener un conocimiento previo sobre el problema que se presenta para resolver.·Usan operadores probabilísticos, en vez de los típicos operadores deterministicos de las otras técnicas.·Cuando se usan para problemas de optimización maximizar una función objetivo- resultan menos afectados por los máximos locales (falsas soluciones) que las técnicas tradicionales.

Algunas Aplicaciones de los Algoritmos GenéticosComo hemos podido observar, el área de aplicación de los AG es muy

amplia, y en general sus aplicaciones se pueden implementar a muchos de los problemas de la vida cotidiana, de igual forma, se hayan aplicado a diversos problemas y modelos en ingeniaría, y en la ciencia en general cabe destacar entre ellos:

• Se trata de un campo especialmente abonado para el uso de los AG, por las características intrínsecas de estos problemas. No en vano fueron la fuente de inspiración para los creadores estos algoritmos. Los AG se han utilizado en numerosas tareas de optimización, incluyendo la optimización numérica, y los problemas de optimización combinatoria.

Optimizacion

• Los AG se han empleado para desarrollar programas para tareas específicas, y para diseñar otras estructuras computacionales tales como el autómata celular, y las redes de clasificación.

Programacion Automatica

• Los AG se han utilizado también en muchas de estas aplicaciones, tales como la predicción del tiempo o la estructura de una proteína. Han servido asimismo para desarrollar determinados aspectos de sistemas particulares de aprendizaje, como pueda ser el de los pesos en una red neuronal, las reglas para sistemas de clasificación de aprendizaje o sistemas de producción simbólica, y los sensores para robots.

Aprendizaje Maquina

• En este caso, se ha hecho uso de estos Algoritmos para modelizar procesos de innovación, el desarrollo estrategias de puja, y la aparición de mercados económicos.

Economia• A la hora de modelizar varios aspectos de los sistemas

inmunes naturales, incluyendo la mutación somática durante la vida de un individuo y el descubrimiento de familias de genes múltiples en tiempo evolutivo, ha resultado útil el empleo de esta técnica.

Sistema Inmunes

• En la modelización de fenómenos ecológicos tales como las carreras de armamento biológico, la coevolución de parásito-huesped, la simbiosis, y el flujo de recursos.Ecologia

• En el estudio de preguntas del tipo "¿Bajo qué condiciones será viable evolutivamente un gene para la recombinación?".

Genetica de Poblaciones

• Los AG se han utilizado en el estudio de las relaciones entre el aprendizaje individual y la evolución de la especie.

Evolucion y Aprendizaje

• En el estudio de aspectos evolutivos de los sistemas sociales, tales como la evolución del comportamiento social en colonias de insectos, y la evolución de la cooperación y la comunicación en sistemas multi-agentes.

Sistema Sociales

Entre otras aplicaciones tenemos:

•Diseño automatizado de equipamiento industrial.•Construcción de arboles filogeneticos.•Optimización de carga de contenedores.•Diseño de sistemas de distribución de aguas.•Diseño de topologías de circuitos impresos.•Diseño de topologías de redes computacionales.•En Teoria de juegos, resolución de equilibrios.•Aprendizaje de comportamiento de robots.•Aprendizaje de reglas de Logica Difusa.•Infraestructura de redes de comunicaciones móviles.•Planificación de producción multicriteria.•Predicción.•Aplicación de Algoritmos Genéticos al Direma del prisioneroIterado•Optimización de sistemas de compresión de datos, por ejemplo, usando wavelets.•Predicción de Plegamiento de proteinas•Optimización de Layout•Predicción de estructura de ARN.•En bioinformática, Alineamiento multiple de secuencias.•Selección óptima de modelos matemáticos para la descripción de sistemas biológicos.•Ingeniería de software.•Construcción de horarios en grandes universidades, evitando conflictos de clases.•Problema del viajante.•Hallazgo de errores en programas.•Optimización de producción y distribución de energía eléctrica.•Diseño de redes geodésicas (Problemas de diseño).

Estrategia de SeleccionEl operador de Selección es el encargado de transmitir y conservar aquellas características de la soluciones que se consideran valiosas a lo largo de las generaciones. El principal medio para que la información útil se transmita es que aquellos individuos mejor adaptados (mejor valor de función de evaluación) tengan más probabilidades de reproducirse. Sin embargo, es necesario también incluir un factor aleatorio que permita reproducirse a individuos que aunque no estén muy bien adaptados, puedan contener alguna información útil para posteriores generaciones, con el objeto de mantener así también una cierta diversidad en cada población. Algunas de las técnicas de las cuales se dispone son las siguientes:

• a cada individuo de la población se le asigna un rango numérico basado en su aptitud, y la selección se basa en este ranking, en lugar de las diferencias absolutas en aptitud. La ventaja de este método es que puede evitar que individuos muy aptos ganen dominancia al principio a expensas de los menos aptos, lo que reduciría la diversidad genética de la población y podría obstaculizar la búsqueda de una solución aceptable.

Por sorteo

• una forma de selección proporcional a la aptitud en la que la probabilidad de que un individuo sea seleccionado es proporcional a la diferencia entre su aptitud y la de sus competidores. (Conceptualmente, esto puede representarse como un juego de ruleta -cada individuo obtiene una sección de la ruleta, pero los más aptos obtienen secciones mayores que las de los menos aptos. Luego la ruleta se hace girar, y en cada vez se elige al individuo que ``posea'' la sección en la que se pare la ruleta).

Por rueda de ruleta

• Reporta un valor computacional muy bajo debido a su sencillez. Se selecciona un grupo de t individuos (normalmente t = 2, torneo binario) y se genera un número aleatorio entre 0 y 1. Si este número es menor que un cierto umbral K (usualmente 0,75), se selecciona para reproducirse al individuo con mejor adaptación, y si este número es menor que K, se selecciona, por el contrario, al individuo con peor adaptación. Esta técnica tiene la ventaja de que permite un cierto grado de elitismo -el mejor nunca va a morir, y los mejores tienen más probabilidad de reproducirse y de emigrar que los peores- pero sin producir una convergencia genética prematura, si la población es, al menos, un orden de magnitud superior al del número de elementos involucrados en el torneo

Por torneo

Tecnica de CruceEl operador de cruce permite realizar una exploración de toda

la información almacenada hasta el momento en la población y combinarla para crear mejores individuos. Dentro de los métodos habituales destacamos los siguientes:

Cruce de un punto

• Es el método de cruce más sencillo. Se selecciona una posición en las cadenas de los progenitores, y se intercambian los genes a la izquierda de esta posición.

Cruce de n punto

• Es una generalización del método anterior. Se seleccionan varias posiciones (n) en las cadenas de los progenitores y se intercambian los genes a ambos lados de estas posiciones.

Cruce de uniforme

• Se realiza un test aleatorio para decidir de cual de los progenitores se toma cada posición de la cadena.

MutacionSe define mutación como una variación de las

informaciones contenidas en el código genético -habitualmente, un cambio de un gen a otro producido por algún factor exterior al algoritmo genético-. En Biología se definen dos tipos de mutaciones: las generativas, que se heredan y las somáticas, que no se heredan. En los algoritmos genéticos sólo nos serán interesantes las mutaciones generativas. Algunas de las razones que pueden motivar a incorporar son:

Desbloqueo del algoritmo.

• Si el algoritmo se bloqueó en un mínimo parcial, una mutación puede sacarlo al incorporar nuevos fenotipos de otras zonas del espacio.

Incrementar el número de saltos evolutivos.• Puede ocurrir que, bien por haber un cuasi-mínimo, bien porque en pasos

iniciales apareció un individuo demasiado bueno que acabó con la diversidad genética, la población tenga los mismos fenotipos.  Si se ha llegado a una población degenerada, es preciso que las mutaciones introduzcan nuevos genomas.

Incrementar el número de saltos evolutivos

• Los saltos evolutivos -aparición de un fenotipo especialmente valioso, o, dicho de otra forma, salida de un mínimo local- son muy poco probables en un genético puro para un problema genérico. La mutación permite explorar nuevos subespacios de soluciones, por lo que, si el subespacio es bueno en términos de adaptación, se producirá un salto evolutivo después de la mutación que se expanderá de forma exponencial por la población.

Enriquecer la diversidad genética.

• Es un caso más suave que el de una población degenerada -por ejemplo, que la población tenga una diversidad genética pobre-, la mutación es un mecanismo de prevención de las poblaciones degeneradas.

Sin embargo, si la tasa de mutación es excesivamente alta tendremos la ya conocida deriva genética. Una estrategia muy empleada es una tasa de mutación alta al inicio del algoritmo, para aumentar la diversidad genética, y una tasa de mutación baja al final del algoritmo, para conseguir que converga.

Existen varias técnicas distintas de mutación. Algunas de éstas son:

Mutación de bit

• Existe una única probabilidad de que se produzca una mutación de algún bit. De producirse, el algoritmo toma aleatoriamente un bit, y lo invierte.

Mutación multibit

• Cada bit tiene una probabilidad de mutarse o no, que es calculada en cada pasada del operador de mutación multibit.

Mutación de gen• Igual que la mutación de bit, solamente que, en vez de cambiar un bit, cambia un gen

completo. Puede sumar un valor aleatorio, un valor constante, o introducir un gen aleatorio nuevo.

Mutación multigen• Igual que la mutación de multibit, solamente que, en vez de cambiar un conjunto de

bits, cambia un conjunto de genes. Puede sumar un valor aleatorio, un valor constante, o introducir un gen aleatorio nuevo.

Mutación de intercambio

• Existe una probabilidad de que se produzca una mutación. De producirse, toma dos bits/genes aleatoriamente y los intercambia.

Mutación de barajado• Existe una probabilidad de que se produzca una mutación. De producirse, toma dos bits

o dos genes aleatoriamente y baraja de forma aleatoria los bits -o genes, según hubieramos escogido- comprendidos entre los dos.

ConclusionComo se ha podido observar, una de las principales ventajas

de los AG puede observarse en su sencillez; puesto que se necesita muy poca información sobre el espacio de búsqueda ya que se trabaja sobre un conjunto de soluciones o parámetros codificados (hipótesis o individuos). Al igual que sus campos de aplicación, se puede afirmar que es un método muy completo de optimización, puesto que sus áreas de estudio son muy amplias, y se puede ver generalizado en muchos sucesos cotidianos.

Se ha observado de igual forma que los AG están indicados para resolver todo tipo de problemas que se puedan expresar como un problema de optimización donde se define una representación adecuada para las soluciones y para la función a optimizar. Se busca una solución por aproximación de la población, en lugar de una aproximación punto a punto。

Bibliografia

Informacion Evolutiva: Algoritmo geneticohttp://geneura.ugr.es/~jmerelo/ie/

ags.htm

Wikipedia: Algoritmo Geneticohttp://es.wikipedia.org/wiki/

Algoritmo_genético

Algorimo Genetico:http://www.it.uc3m.es/jvillena/irc/practicas/06-

07/05.pdf