Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

ALGORITMOS GENÉTICOS

Selección por Rango

Selección por Rueda de Ruleta

Selección

Selección Elitista

Selección por Estado Estacionario

En este método a cada cromosoma se le asigna un rango numérico basado en su aptitud y la selección se realiza en base a este ranking.

Selección por Torneo

Puede suceder que tras el cruce y la mutación, perdamos el cromosoma con mejor adaptación. Este método de selección copia el mejor cromosoma o alguno de los mejores en la nueva población. El resto se realiza de la misma forma que hemos visto anteriormente.

Es necesario hacer una selección con los individuos más capacitados para que éstos sean los que se reproduzcan con más probabilidad.

Por lo tanto una vez evaluado cada cromosoma y obtenida su puntuación, se tiene que crear la nueva población teniendo en cuenta que los buenos rasgos de los mejores se transmitan a ésta.

Esta selección se puede realizar de varias formas como se verá a continuación.

Se crea para esta selección una ruleta con los cromosomas presentes en una generación.

Cada cromosoma tendrá una parte de esa ruleta mayor o menor en función a la puntuación que tenga cada uno.

Se hace girar la ruleta y se selección el cromosoma en el que se para la ruleta.

Obviamente el cromosoma con mayor puntuación saldrá con mayor probabilidad, y si es mucha la diferencia se reduciría la diversidad genética.

Se escogen de forma aleatoria un número de individuos de la población, y el que tiene puntuación mayor se reproduce, sustituyendo su descendencia al que tiene menor puntuación.

La descendencia de los individuos seleccionados en cada generación vuelve a la población genética preexistente, reemplazando a algunos de los miembros menos aptos de la anterior generación.

Algoritmos Genéticos

El tamaño de la población debe ser lo suficientemente grande para garantizar la diversidad de soluciones.

Se aconseja que la población sea generada de forma aleatoria para obtener dicha diversidad.

En caso de que la población no sea generada de forma aleatoria habrá que tener en cuenta que se garantice una cierta diversidad en la población generada.

Algoritmos Genéticos

Parámetros de los Algoritmos Genéticos

Tamaño de la Población: indica el número de cromosomas que tenemos en nuestra población para una generación determinada.

Probabilidad de Cruce: indica la frecuencia con la que se producen cruces entre los cromosomas padre es decir, que haya probabilidad de reproducción entre ellos.

Probabilidad de Mutación: indica la frecuencia con la que los genes de un cromosoma son mutados.

Un algoritmo genético es un método de búsqueda que imita la teoría de la evolución biológica de Darwin para la resolución de problemas. Para ello, se parte de una población inicial de la cual se seleccionan los individuos más capacitados para luego reproducirlos y mutarlos y finalmente obtener la siguiente generación de individuos que estarán más adaptados que la anterior generación.

Algoritmos Genéticos

Crossover 2 Puntos

Reproducción o Crossover

Crossover 1 Punto

Crossover Uniforme

Crossover Aritmético

Los dos cromosomas padres se cortan por un punto. Se copia la información genética de uno de los padres desde el inicio hasta el punto de cruce y el resto se copia del otro progenitor.

Este caso los padres se cortan por dos puntos. Se copiará al descendiente los genes de un cromosoma progenitor desde el principio hasta el primer punto de cruce, los genes del otro

progenitor desde el primer punto de cruce hasta el segundo y del segundo punto de cruce hasta el final se copiará del otro progenitor.

Cada gen del descendiente se obtiene de cualquiera de los padres de forma aleatoria. Una opción es generar un número aleatorio. Si este número supera un cierto umbral se elegirá un padre determinado y si no lo supera se elige al otro.

Los progenitores se recombinan según algún operador aritmético para generar su descendiente.

Una vez se realiza la selección de los cromosomas se procede a realizar la reproducción o cruce entre dos de estos cromosomas Más concretamente, el crossover consiste en el intercambio de material genético entre dos cromosomas. El objetivo del cruce es conseguir que el descendiente mejore la aptitud de sus padres.

Para aplicar el cruce habrá que seleccionar con anterioridad dos individuos de la población con una de las diversas técnicas de selección que hemos mencionado en el punto anterior

Mutación

La mutación depende de la codificación y de la reproducción. Si se abusa de la mutación podemos caer en el uso del algorito genético como una simple búsqueda aleatoria.

Por lo tanto antes de aumentar las mutaciones, conviene estudiar otras soluciones que aporten diversidad a la población como podría ser el aumento del tamaño de la población o garantizar la aleatoriedad de la población inicial.

La mutación consiste en modificar ciertos genes de forma aleatoria atendiendo a la probabilidad de mutación establecida con anterioridad.

Para el caso de una codificación binaria, la mutación consiste simplemente en la inversión del gen mutado que corresponderá con un bit.

Referencias

Integrantes

García Colín Oscar Iván

Hernandez Moreno Osiris Yael

Arranz de la Peña, J., Truyol, A. ALGORITMOS GENÉTICOS [archivo PDF]. Obtenido en http://www.it.uc3m.es/jvillena/irc/practicas/06-07/05.pdf

Gestal M,, Rivero D., Rabuñal J. Introducción a los Algoritmos Genéticos y la Programación Genética [archivo PDF]. Obtenido en http://www.galeon.com/dantethedestroyer/algoritmos.pdf

Learn more about creating dynamic, engaging presentations with Prezi