1. OPERADORES GENÉTICOS

Para el paso de una generación a la siguiente se aplican una serie de operadores genéticos. Los más empleados son los operadores de selección, cruce, copia y mutación.

A continuación se verán con mayor detalle.







1.1 OPERADORES DE SELECCIÓN


bre_seleccion.jpg
Transmitir y conservar caracteristicas valiosas
El 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 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.
Un algoritmo genético puede utilizar muchas técnicas diferentes para seleccionar a los individuos que deben copiarse hacia la siguiente generación. Algunos de estos métodos son mutuamente exclusivos, pero otros pueden utilizarse en combinación, algo que se hace a menudo.







Algunas de las Selecciones más comunes son:


1.1.1. Selección elitista:


elitista2-760-x-760.jpg
Selección Elistista


Esta trata de garantiza la selección de los miembros más aptos de cada generación. La mayoría de los algoritmos geneticos no utilizan elitismo puro, sino que usan una forma modificada por la que el individuo mejor, o algunos de los mejores, son copiados hacia la siguiente generación en caso de que no surja nada mejor.



1.1.2. Selección proporcional a la aptitud:


Los individuos más aptos tienen más probabilidad de ser seleccionados, pero no la certeza.



1.1.3. Selección por rueda a ruleta:

Juego-La-rueda-de-la-fortuna-150x150.jpg
Ejemplo de como podria ser la seleccion

Llamada tambien Selección de Montecarlo.

Con este método la probabilidad que tiene un individuo de reproducirse es proporcional a la diferencia entre su aptitud y la de sus competidores. Conceptualmente, esto puede representarse como un juego de ruleta donde cada individuo obtiene una sección o parte de la ruleta, pero los más aptos obtienen secciones mayores que las de los menos aptos. Luego la
ruleta se hace girar, y cada vez se elige al individuo que tenga la sección en la que se pare la ruleta.

Apesar de ser un método muy sencillo, es ineficiente a medida que aumenta el tamaño de la población ya que se vuvlve muy compleja. Además presenta el inconveniente de que el peor individuo sea eligida más de una vez al estar al azar.


1.1.4. Selección escalada:


Al incrementarse la aptitud media de la población, la fuerza de la presión selectiva también aumenta y la función de aptitud se hace más discriminadora. Este método puede ser útil para seleccionar más tarde cuando todos los individuos tengan una aptitud relativamente alta y sólo les distingan pequeñas diferencias en la aptitud.



1.1.5. Selección por torneo:



Seleccion_de_Torneo.gif
Ejemplo de Selección de Torneo


Se eligen subgrupos de individuos de la población, y los miembros de cada subgrupo compiten entre ellos. Sólo se elige a un individuo de cada subgrupo para la reproducción. Este método tiene un cierto grado de elitismo donde se elige el mejor.



1.1.6. Selección por rango:


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.



1.1.7. Selección generacional:


La descendencia de los individuos seleccionados en cada generación se convierte en toda la siguiente generación. No se conservan individuos entre las generaciones.



1.1.8. Selección por estado estacionario:


La descendencia de los individuos seleccionados en cada generación vuelven al acervo genético preexistente, reemplazando a algunos de los miembros menos aptos de la siguiente generación. Se conservan algunos individuos entre generaciones.



1.1.9. Selección jerárquica:


Los individuos atraviesan múltiples rondas de selección en cada generación. Las evaluaciones de los primeros niveles son más rápidas y menos discriminatorias, mientras que los que sobreviven hasta niveles más altos son evaluados más rigurosamente. La ventaja de este método es que reduce el tiempo total de cálculo al utilizar una evaluación más rápida y menos selectiva para eliminar a la mayoría de los individuos que se muestran poco o nada prometedores, y sometiendo a una evaluación de aptitud más rigurosa y computacionalmente más costosa sólo a los que sobreviven a esta prueba inicial.




1.2. OPERADORES DE CRUCE



Una vez seleccionados los individuos, éstos son recombinados para producir la descendencia que se insertará en la siguiente generación. Tal y como se ha indicado anteriormente el cruce es una estrategia de reproducción sexual.
Su importancia para la transición entre generaciones es elevada puesto que las tasas de cruce con las que se suele trabajar rondan el 90%.

El operador cruce se aplica en dos pasos: los individuos se aparean, esto es que se seleccionan de dos a dos, de manera aleatoria con una determinada probabilidad, la cual la nombraremos como probabilidad de cruce Pc; y en el segundo paso a cada par de individuos seleccionados anteriormente se le aplica un intercambio en su contenido

La idea principal del cruce se basa en que, si se toman dos individuos correctamente adaptados al medio y se obtiene una descendencia que comparta genes de ambos, existe la posibilidad de que los genes heredados sean precisamente los causantes de la bondad de los padres. Al compartir las características buenas de dos individuos, la descendencia, o al menos parte de ella, debería tener una bondad mayor que cada uno de los padres por separado.

Existen muchas maneras de cruces en las que se destacan:


1.2.1. Cruce de un punto


Se establece un punto de intercambio en un lugar aleatorio del genoma de los dos individuos, y uno de los individuos contribuye todo su código anterior a ese punto y el otro individuo contribuye todo su código a partir de ese punto para producir una descendencia. Ejemplo:


CRUCE.gif
Ejemplo de Cruce de un punto





1.2.2. Cruce de dos puntos:


Se establecen dos puntos de intercambio en un lugar aleatorio del genoma de los dos individuos, y uno de los individuos contribuye todo su código anterior al primer punto y posterior al segundo punto y el otro individuo contribuye todo su código entre los puntos.


CRUCE2.gif
Ejemplo de Cruce de dos puntos



1.2.3. Cruce uniforme:


Los genes de los padres son intercambiados de forma aleatoria.


CRUCE3.gif
Ejemplo de Cruce uniforme



1.2.4. Cruce aritmético:


El hijo es generado por una operación aritmética entre los genes de los padres.





1.2.5. Cruce Uniforme:


Cada gen de la descendencia tiene las mismas probabilidades de pertenecer a uno u otro padre.

external image img15.gif





1.3. Algoritmos de Reemplazo


Cuando se trabaja con con una única población, sobre la que se realizan las selecciones e inserciones, deberá tenerse en cuenta que para insertar un nuevo individuo deberá de eliminarse previamente otro de la población. Existen diferentes métodos de reemplazo:


  • Aleatorio: el nuevo individuo se inserta en un lugar cualquiera de la población.
  • Reemplazo de padres: se obtiene espacio para la nueva descendencia liberando el espacio ocupado por los padres.
  • Reemplazo de similares: una vez obtenido el ajuste de la descendencia se selecciona un grupo de individuos (entre seis y diez) de la población con un ajuste similar. Se reemplazan aleatoriamente los que sean necesarios.
  • Reemplazo de los peores: de entre un porcentaje de los peores individuos de la población se seleccionan aleatoriamente los necesarios para dejar sitio a la descendencia.




1.3. Copia


external image clon.gifA diferencia del cruce, se trata de una estrategia de reproducción asexual. Consiste simplemente en la copia de un individuo en la nueva generación. El porcentaje de copias de una generación a la siguiente es relativamente reducido, pues en caso contrario se corre el riesgo de una convergencia prematura de la población hacia ese individuo. De esta manera el tamaño efectivo de la población se reduciría notablemente y la búsqueda en el espacio del problema se focalizaría en el entorno de ese individuo.
Lo que generalmente se suele hacer es seleccionar dos individuos para el cruce, y si éste finalmente no tiene lugar, se insertan en la siguiente generación los individuos seleccionados.






1.4. Mutación



external image mutacion-genes.jpg


La mutación de un individuo provoca que alguno de sus genes, generalmente uno sólo, varíe su valor de forma aleatoria.
Aunque se pueden seleccionar los individuos directamente de la población actual y mutarlos antes de introducirlos en la nueva población, la mutación se suele utilizar de manera conjunta con el operador de cruce. Primeramente se seleccionan dos individuos de la población para realizar el cruce. Si el cruce tiene éxito entonces uno de los descendientes, o ambos, se muta con cierta probabilidad Pm. Se imita de esta manera el comportamiento que se da en la naturaleza, pues cuando se genera la descendencia siempre se produce algún tipo de error, por lo general sin mayor trascendencia, en el paso de la carga genética de padres a hijos.

La probabilidad de mutación es muy baja, generalmente menor al 1%. Esto se debe sobre todo a que los individuos suelen tener un ajuste menor después de mutados. Sin embargo se realizan mutaciones para garantizar que ningún punto del espacio de búsqueda tenga una probabilidad nula de ser examinado.
Tal y como se ha comentado, la mutación más usual es el reemplazo aleatorio. Este consiste en variar aleatoriamente un gen de un cromosoma. Si se trabaja con codificaciones binarias consistirá simplemente en negar un bit. También es posible realizar la mutación intercambiando los valores de dos alelos del cromosoma. Con otro tipo de codificaciones no binarias existen otras opciones:

  • Incrementar o decrementar a un gen una pequeña cantidad generada aleatoriamente.
  • Multiplicar un gen por un valor aleatorio próximo a 1.

Aunque no es lo más común, existen implementaciones de Algoritmos Genéticos en las que no todos los individuos tienen los cromosomas de la misma longitud. Esto implica que no todos ellos codifican el mismo conjunto de variables. En este caso existen mutaciones adicionales como puede ser añadir un nuevo gen o eliminar uno ya existente.





BIBLIOGRAFIA


http://sabia.tic.udc.es/mgestal/cv/AAGGtutorial/node8.html
http://the-geek.org/docs/algen/
http://es.wikipedia.org/wiki/Algoritmo_gen%C3%A9tico
http://www.monografias.com/trabajos-pdf/algoritmos-geneticos/algoritmos-geneticos.pdf
http://catarina.udlap.mx/u_dl_a/tales/documentos/lat/cuspinera_c_vh/capitulo2.pdf