¿que son los algoritmos geneticos?
citando al libro "Introducción a los Algoritmos Genéticos y la Programación Genética" dice que "Los Algoritmos Genéticos son métodos adaptativos, generalmente usados en problemas de búsqueda y optimización de parámetros, basados en la reproducción sexual y en el principio de supervivencia del más apto (Fogel, 2000) (Fogel, 2006).
Más formalmente, y siguiendo la definición dada por Goldberg, "los Algoritmos Genéticos son algoritmos de búsqueda basados en la mecánica de selección natural y de la genética natural. Combinan la supervivencia del más apto entre estructuras de secuencias con un intercambio de información estructurado, aunque aleatorizado, para constituir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas" (Goldberg, 1989).
Para alcanzar la solución a un problema se parte de un conjunto inicial de individuos, llamado población, generado de manera aleatoria. Cada uno de estos individuos representa una posible solución al problema. Estos individuos evolucionarán tomando como base los esquemas propuestos por Darwin sobre la selección natural, y se adaptarán en mayor medida tras el paso de cada generación a la solución requerida (Darwin, 2007)"
como se programa un problema
Cualquier solución potencial a un problema puede ser presentada dando valores a una serie de parámetros. El conjunto de todos los parámetros (genes en la terminología de Algoritmos Genéticos) se codifica en una cadena de valores denominada cromosoma. El conjunto de los parámetros representado por un cromosoma particular recibe el nombre de genotipo. El genotipo contiene la información necesaria para la construcción del organismo, es decir, la solución real al problema, denominada fenotipo. Por ejemplo, en términos biológicos, la información genética contenida en el ADN de un individuo sería el genotipo, mientras que la expresión de ese ADN (el propio individuo) sería el fenotipo. Desde los primeros trabajos de John Holland la codificación suele hacerse mediante valores binarios. Se asigna un determinado número de bits a cada parámetro y se realiza una discretización de la variable representada por cada gen. El número de bits asignados dependerá del grado de ajuste que se desee alcanzar. Evidentemente no todos los parámetros tienen por qué estar codificados con el mismo número de bits. Cada uno de los bits pertenecientes a un gen suele recibir el nombre de alelo.
Sin embargo, también existen representaciones que codifican directamente cada parámetro con un valor entero, real o en punto flotante. A pesar de que se acusa a estas representaciones de degradar el paralelismo implícito de las representaciones binarias, permiten el desarrollo de operadores genéticos más específicos al campo de aplicación del Algoritmo Genético. En la Figura 1.4, se muestra un ejemplo típico de la aplicación de los Algoritmos Genéticos: cómo representar una red de neuronas artificiales para posteriormente realizar el proceso de optimización de los pesos sinápticos. Codificar una red de neuronas artificiales en forma de cromosoma es tan sencillo como asignar un gen del cromosoma a cada uno de los pesos de la red. También se podrían añadir genes que indiquen el número de capas y el número de elementos de procesado en cada una.
Algoritmo Principal
Los Algoritmos Genéticos trabajan sobre una población de individuos. Cada uno de ellos representa una posible solución al problema que se desea resolver. Todo individuo tiene asociado un ajuste de acuerdo a la bondad con respecto al problema de la solución que representa (en la naturaleza el equivalente sería una medida de la eficiencia del individuo en la lucha por los recursos). Una generación se obtiene a partir de la anterior por medio de los operadores de reproducción. Existen 2 tipos:
Cruce. Se trata de una reproducción de tipo sexual. Se genera una descendencia a partir del mismo número de individuos (generalmente 2) de la generación anterior. Existen varios tipos que se detallarán en un
punto posterior.
Copia. Se trata de una reproducción de tipo asexual. Un determinado número de individuos pasa sin sufrir ninguna variación directamente a la siguiente generación.
Inicializar población actual aleatoriamente
MIENTRAS no se cumpla el criterio de terminación crear población temporal vacía
SI elitismo: copiar en población temporal mejores individuos
MIENTRAS población temporal no llena seleccionar padres cruzar padres con probabilidad Pc
SI se ha producido el cruce mutar uno de los descendientes (prob. Pm) evaluar descendientes añadir descendientes a la población temporal
SINO añadir padres a la población temporal
FIN SI
FIN MIENTRAS aumentar contador generaciones establecer como nueva población actual la población temporal
FIN MIENTRAS
El funcionamiento genérico de un Algoritmo Genético puede apreciarse en el pseudocódigo, Si desea optarse por una estrategia elitista, los mejores individuos de cada generación se copian siempre en la población temporal, para evitar su pérdida.
A continuación comienza a generarse la nueva población en base a la aplicación de los operadores genéticos de cruce y/o copia. Una vez generados los nuevos individuos se realiza la mutación con una probabilidad Pm. La probabilidad de mutación suele ser muy baja, por lo general entre el 0.5% y el 2%. Se sale de este proceso cuando se alcanza alguno de los criterios de parada fijados. Los más usuales suelen ser:
Los mejores individuos de la población representan soluciones suficientemente buenas para el problema que se desea resolver.
La población ha convergido. Un gen ha convergido cuando el 95% de la población tiene el mismo valor para él, en el caso de trabajar con codificaciones binarias, o valores dentro de un rango especificado en
el caso de trabajar con otro tipo de codificaciones. Una vez que todos los genes alcanzan la convergencia se dice que la población ha convergido. Cuando esto ocurre la media de bondad de la población se aproxima a la bondad del mejor individuo.
Se ha alcanzado el número de generaciones máximo especificado. Sobre este algoritmo inicialmente propuesto por Holland se han definido numerosas variantes. Quizás una de las más extendidas consiste en prescindir de la población temporal de manera que los operadores genéticos de cruce y mutación se aplican directamente sobre la población genética. Con esta variante el proceso de cruces varía ligeramente. Ahora no basta, en el caso de que el cruce se produzca, con insertar directamente la descendencia en la población. Puesto que el número de individuos de la población se ha de mantener constante, antes de insertar la descendencia en la población se le ha de hacer sitio. Es decir, para ubicar a los descendientes generados previamente se han de eliminar otros individuos de la población genética. Existen para ello diversas opciones, que se comentarán con más detalle en un punto posterior. Evidentemente, trabajando con una única población no se puede decir que se pase a la siguiente generación cuando se llene la población, pues siempre está llena. En este caso el paso a la siguiente generación se producirá una vez que se hayan alcanzado cierto número de cruces y mutaciones. Este número dependerá de la tasa de cruces y mutaciones especificadas por el usuario y del tamaño de la población. Así, con una tasa de cruces del 90%, una tasa de 18 Introducción a los Algoritmos Genéticos y la Programación Genética mutaciones del 2% y trabajando con 100 individuos se pasará a la siguiente generación cuando se alcanzasen 45 cruces (cada cruce genera 2 individuos con lo que se habrían insertado en la población 90 individuos, esto es el 90%) o 2 mutaciones. Otra variación común consiste en la modificación del esquema de selección de los individuos que serán mutados. En el esquema mostrado, sólo los descendientes originados a partir de un cruce son mutados (proceso que imita los errores de transcripción del ADN que tienen lugar en la naturaleza); otra opción habitual es la selección aleatoria del individuo a mutar entre todos los que forman parte de la población genética
esto nos sirve para poder recrear las cadenas de ADN mediante la programación utilizando el código binario
citando al libro "Introducción a los Algoritmos Genéticos y la Programación Genética" dice que "Los Algoritmos Genéticos son métodos adaptativos, generalmente usados en problemas de búsqueda y optimización de parámetros, basados en la reproducción sexual y en el principio de supervivencia del más apto (Fogel, 2000) (Fogel, 2006).
Más formalmente, y siguiendo la definición dada por Goldberg, "los Algoritmos Genéticos son algoritmos de búsqueda basados en la mecánica de selección natural y de la genética natural. Combinan la supervivencia del más apto entre estructuras de secuencias con un intercambio de información estructurado, aunque aleatorizado, para constituir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas" (Goldberg, 1989).
Para alcanzar la solución a un problema se parte de un conjunto inicial de individuos, llamado población, generado de manera aleatoria. Cada uno de estos individuos representa una posible solución al problema. Estos individuos evolucionarán tomando como base los esquemas propuestos por Darwin sobre la selección natural, y se adaptarán en mayor medida tras el paso de cada generación a la solución requerida (Darwin, 2007)"
como se programa un problema
Cualquier solución potencial a un problema puede ser presentada dando valores a una serie de parámetros. El conjunto de todos los parámetros (genes en la terminología de Algoritmos Genéticos) se codifica en una cadena de valores denominada cromosoma. El conjunto de los parámetros representado por un cromosoma particular recibe el nombre de genotipo. El genotipo contiene la información necesaria para la construcción del organismo, es decir, la solución real al problema, denominada fenotipo. Por ejemplo, en términos biológicos, la información genética contenida en el ADN de un individuo sería el genotipo, mientras que la expresión de ese ADN (el propio individuo) sería el fenotipo. Desde los primeros trabajos de John Holland la codificación suele hacerse mediante valores binarios. Se asigna un determinado número de bits a cada parámetro y se realiza una discretización de la variable representada por cada gen. El número de bits asignados dependerá del grado de ajuste que se desee alcanzar. Evidentemente no todos los parámetros tienen por qué estar codificados con el mismo número de bits. Cada uno de los bits pertenecientes a un gen suele recibir el nombre de alelo.
Sin embargo, también existen representaciones que codifican directamente cada parámetro con un valor entero, real o en punto flotante. A pesar de que se acusa a estas representaciones de degradar el paralelismo implícito de las representaciones binarias, permiten el desarrollo de operadores genéticos más específicos al campo de aplicación del Algoritmo Genético. En la Figura 1.4, se muestra un ejemplo típico de la aplicación de los Algoritmos Genéticos: cómo representar una red de neuronas artificiales para posteriormente realizar el proceso de optimización de los pesos sinápticos. Codificar una red de neuronas artificiales en forma de cromosoma es tan sencillo como asignar un gen del cromosoma a cada uno de los pesos de la red. También se podrían añadir genes que indiquen el número de capas y el número de elementos de procesado en cada una.
Algoritmo Principal
Los Algoritmos Genéticos trabajan sobre una población de individuos. Cada uno de ellos representa una posible solución al problema que se desea resolver. Todo individuo tiene asociado un ajuste de acuerdo a la bondad con respecto al problema de la solución que representa (en la naturaleza el equivalente sería una medida de la eficiencia del individuo en la lucha por los recursos). Una generación se obtiene a partir de la anterior por medio de los operadores de reproducción. Existen 2 tipos:
Cruce. Se trata de una reproducción de tipo sexual. Se genera una descendencia a partir del mismo número de individuos (generalmente 2) de la generación anterior. Existen varios tipos que se detallarán en un
punto posterior.
Copia. Se trata de una reproducción de tipo asexual. Un determinado número de individuos pasa sin sufrir ninguna variación directamente a la siguiente generación.
Inicializar población actual aleatoriamente
MIENTRAS no se cumpla el criterio de terminación crear población temporal vacía
SI elitismo: copiar en población temporal mejores individuos
MIENTRAS población temporal no llena seleccionar padres cruzar padres con probabilidad Pc
SI se ha producido el cruce mutar uno de los descendientes (prob. Pm) evaluar descendientes añadir descendientes a la población temporal
SINO añadir padres a la población temporal
FIN SI
FIN MIENTRAS aumentar contador generaciones establecer como nueva población actual la población temporal
FIN MIENTRAS
El funcionamiento genérico de un Algoritmo Genético puede apreciarse en el pseudocódigo, Si desea optarse por una estrategia elitista, los mejores individuos de cada generación se copian siempre en la población temporal, para evitar su pérdida.
A continuación comienza a generarse la nueva población en base a la aplicación de los operadores genéticos de cruce y/o copia. Una vez generados los nuevos individuos se realiza la mutación con una probabilidad Pm. La probabilidad de mutación suele ser muy baja, por lo general entre el 0.5% y el 2%. Se sale de este proceso cuando se alcanza alguno de los criterios de parada fijados. Los más usuales suelen ser:
Los mejores individuos de la población representan soluciones suficientemente buenas para el problema que se desea resolver.
La población ha convergido. Un gen ha convergido cuando el 95% de la población tiene el mismo valor para él, en el caso de trabajar con codificaciones binarias, o valores dentro de un rango especificado en
el caso de trabajar con otro tipo de codificaciones. Una vez que todos los genes alcanzan la convergencia se dice que la población ha convergido. Cuando esto ocurre la media de bondad de la población se aproxima a la bondad del mejor individuo.
Se ha alcanzado el número de generaciones máximo especificado. Sobre este algoritmo inicialmente propuesto por Holland se han definido numerosas variantes. Quizás una de las más extendidas consiste en prescindir de la población temporal de manera que los operadores genéticos de cruce y mutación se aplican directamente sobre la población genética. Con esta variante el proceso de cruces varía ligeramente. Ahora no basta, en el caso de que el cruce se produzca, con insertar directamente la descendencia en la población. Puesto que el número de individuos de la población se ha de mantener constante, antes de insertar la descendencia en la población se le ha de hacer sitio. Es decir, para ubicar a los descendientes generados previamente se han de eliminar otros individuos de la población genética. Existen para ello diversas opciones, que se comentarán con más detalle en un punto posterior. Evidentemente, trabajando con una única población no se puede decir que se pase a la siguiente generación cuando se llene la población, pues siempre está llena. En este caso el paso a la siguiente generación se producirá una vez que se hayan alcanzado cierto número de cruces y mutaciones. Este número dependerá de la tasa de cruces y mutaciones especificadas por el usuario y del tamaño de la población. Así, con una tasa de cruces del 90%, una tasa de 18 Introducción a los Algoritmos Genéticos y la Programación Genética mutaciones del 2% y trabajando con 100 individuos se pasará a la siguiente generación cuando se alcanzasen 45 cruces (cada cruce genera 2 individuos con lo que se habrían insertado en la población 90 individuos, esto es el 90%) o 2 mutaciones. Otra variación común consiste en la modificación del esquema de selección de los individuos que serán mutados. En el esquema mostrado, sólo los descendientes originados a partir de un cruce son mutados (proceso que imita los errores de transcripción del ADN que tienen lugar en la naturaleza); otra opción habitual es la selección aleatoria del individuo a mutar entre todos los que forman parte de la población genética
esto nos sirve para poder recrear las cadenas de ADN mediante la programación utilizando el código binario