• Author / Uploaded
• Xclaudix Estefani

• Categories
• Algoritmo genético
• Algoritmos
• Mutación
• Gen
• Interfaz de paso de mensajes

Citation preview

ALGORITMOS GENETICOS Los Algoritmos Genético 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. Esto significa que los genes de los individuos mejor adaptados se propagaran en sucesivas generaciones hacia un número de individuos creciente. La combinación de buenas características provenientes de diferentes ancestros, puede a veces producir descendientes "superindividuos", cuya adaptación es mucho mayor que la de cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando unas características cada vez mejor adaptadas al entorno en el que viven. El poder de los AG proviene del hecho de que se trata de una técnica robusta, y pueden tratar con éxito una gran variedad de problemas provenientes de diferentes áreas, incluyendo aquellos en los que otros métodos encuentran dificultades. Si bien no se garantiza que el AG encuentre la solución optima del problema, existe evidencia empírica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimización combinatoria. En el caso de que existan técnicas especializadas para resolver un determinado problema, lo mas probable es que superen al AG, tanto en rapidez como en eficacia. El gran campo de aplicación de los AG se relaciona con aquellos problemas para los cuales no existen técnicas especializadas. Incluso en el caso en que dichas técnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas hibridándolas con los AG.

¿POR QUÉ UTILIZAR ALGORITMOS GENÉTICOS EN LA OPTIMIZACIÓN? La razón del creciente interés por los AG es que estos son un método global y robusto de búsqueda de las soluciones de problemas. La principal ventaja de estas características es el equilibrio alcanzado entre la eficiencia y eficacia para resolver diferentes y muy complejos problemas de grandes dimensiones. Lo que aventaja a los AG frente a otros algoritmos tradicionales de búsqueda es que se diferencian de estos en los siguientes aspectos: -

Trabajan con una codificación de un conjunto de parámetros, no con los parámetros mismos.

-

Trabajan con un conjunto de puntos, no con un único punto y su entorno (su técnica de búsqueda es global.) Utilizan un subconjunto del espacio total, para obtener información sobre el universo de búsqueda, a través de las evaluaciones de la función a optimizar. Esas evaluaciones se emplean de forma eficiente para clasificar los subconjuntos de acuerdo con su idoneidad.

-

No necesitan conocimientos específicos sobre el problema a resolver; es decir, no están sujetos a restricciones. Por ejemplo, se pueden aplicar a funciones no continuas, lo cual les abre un amplio campo de aplicaciones que no podrían ser tratadas por los métodos tradicionales.

-

Utilizan operadores probabilísticos, en vez de los tipicos operadores determinanticos de las técnicas tradicionales.

-

Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivas en paralelo.

VENTAJAS DE LOS ALGORITMOSGENÉTICOS 

intrínsecamente paralelos, es decir, operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales. Esto significa que mientras técnicas tradicionales sólo pueden explorar el espacio de soluciones hacia una solución en una dirección al mismo tiempo, y si la solución que descubren resulta subóptima, no se puede hacer otra cosa que abandonar todo el trabajo hecho y empezar de nuevo. Sin embargo, los algoritmos genéticos simplemente desechan esta solución subóptima y siguen por otros caminos.

2

-

de optimización resultan menos afectados por los máximos locales (falsas soluciones) que las técnicas tradicionales. Muchos algoritmos de búsqueda pueden quedar atrapados en los óptimos locales: si llegan a lo alto de una colina del paisaje adaptativo, descubrirán que no existen soluciones mejores en las cercanías y concluirán que han alcanzado la mejor de todas, aunque existan picos más altos en algún otro lugar del mapa, situación que no sucede para algoritmos genéticos.

-

para manipular muchos parámetros simultáneamente. Resulta interesante en caso de tener varios objetivos a resolver.

-

problema que intentan resolver. Realizan cambios aleatorios en sus soluciones candidatas y luego utilizan la función de aptitud para determinar si esos cambios producen una mejora o no.

-

arquitecturas masivas en paralelo.

-

operadores determinísticos de las otras técnicas.

DESVENTAJAS DE LOS ALGORITMOS GENETICOS -

Definir una representación del problema. El lenguaje utilizado para especificar soluciones candidatas debe ser robusto, debe ser capaz de tolerar cambios aleatorios que no produzcan constantemente errores fatales o resultados sin sentido. Se puede solucionar mediante la definición de los individuos como listas de números donde cada número representa algún aspecto de la solución candidata.

-

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.

-

Pueden converger prematuramente debido a una serie de problemas. Si un individuo que es más apto que la mayoría de sus competidores emerge muy pronto en el curso de la ejecución, se puede reproducir tan abundantemente que merme la diversidad de la población demasiado pronto, provocando que el algoritmo converja hacia el óptimo local que representa ese individuo, en lugar de rastrear el paisaje adaptativo lo bastante a fondo para encontrar el 3

óptimo global. Esto es un problema especialmente común en las poblaciones pequeñas, donde incluso una variación aleatoria en el ritmo de reproducción puede provocar que un genotipo se haga dominante sobre los otros.

El Algoritmo Genético Simple El Algoritmo Genético Simple, también denominado Canónico, se representa en la Figura 1. Como se verá a continuación, se necesita una codificación o representación del problema, que resulte adecuada al mismo. Además se requiere una función de ajuste ó adaptación al problema, la cual asigna un número real a cada posible solución codificada. Durante la ejecución del algoritmo, los padres deben ser seleccionados para la reproducción, a continuación dichos padres seleccionados se cruzarán generando dos hijos, sobre cada uno de los cuales actuará un operador de mutación. El resultado de la combinación de las anteriores funciones será un conjunto de individuos (posibles soluciones al problema), los cuales en la evolución del Algoritmo Genético formarán parte de la siguiente población.

BEGIN /* Algoritmo Genético Simple */ Generar una población inicial. Computar la función de evaluación de cada individuo. WHILE NOT Terminado DO BEGIN /* Producir nueva generación */ FOR Tamañopoblación/2 DO BEGIN /*Ciclo Reproductivo */ Seleccionar dos individuos de la anterior generación, para el cruce (probabilidad de selección proporcional a la función de evaluación del individuo). Cruzar con cierta probabilidad los dos individuos obteniendo dos descendientes. Mutar los dos descendientes con cierta probabilidad. Computar la función de evaluación de los dos Descendientes mutados. Insertar los dos descendientes mutados en la nueva generación. END IF la población ha convergido THEN Terminado := TRUE END END Figura :Pseudocódigo del Algoritmo Genético Simple

4

Anatomía de un algoritmo genético simple

Los algoritmos genéticos son métodos sistemáticos para la resolución de problemas de búsqueda y optimización que aplican a estos los mismos métodos de la evolución biológica: selección basada en la población, reproducción sexual y mutación. Los algoritmos genéticos son métodos de optimización, que tratan de resolver el mismo conjunto de problemas que se ha contemplado anteriormente, es decir, hallar (xi,...,xn) tales que F(xi,...,xn) sea máximo. En un algoritmo genético, tras parametrizar el problema en una serie de variables, (xi,...,xn) se codifican en un cromosoma. Todas los operadores utilizados por un algoritmo genético se aplicarán sobre estos cromosomas, o sobre poblaciones de ellos. En el algoritmo genético va implícito el método para resolver el problema; son solo parámetros de tal método los que están codificados, a diferencia de otros algoritmos evolutivos como la programación genética. Hay que tener en cuenta que un algoritmo genético es independiente del problema, lo cual lo hace un algoritmo robusto, por ser útil para cualquier problema, pero a la vez débil, pues no está especializado en ninguno.

Codificación

Se supone que los individuos (posibles soluciones del problema), pueden representarse como un conjunto de parámetros (que denominaremos genes), los cuales agrupados forman una lista de valores (a menudo referida como cromosoma). Si bien el alfabeto utilizado para representar los individuos no debe necesariamente estar constituido por el (0, l), buena parte de la teoría en la que se fundamentan los Algoritmos Genéticos utiliza dicho alfabeto. En términos biológicos, el conjunto de parámetros representando un cromosoma particular se denomina fenotipo. El fenotipo contiene la información requerida para construir un organismo, el cual se refiere como genotipo. Los mismos términos se utilizan en el campo de los Algoritmos Genéticos. La adaptación al problema de un individuo depende de la evaluación del genotipo. Esta última puede inferirse a partir del fenotipo, es decir puede ser computada a partir del cromosoma, usando la función de evaluación. La función de adaptación debe ser diseñada para cada problema de manera específica. Dado un cromosoma particular, la función de adaptación le asigna un número real, que se supone refleja el nivel de adaptación al problema del individuo representado por el cromosoma. Durante la fase reproductiva se seleccionan los individuos de la población para cruzarse y producir descendientes, que constituirán, una vez. mutados, la siguiente generación de individuos. La selección de 5

padres se efectúa al azar usando un procedimiento que favorezca a los individuos mejor adaptados, ya que a cada individuo se le asigna una probabilidadde ser seleccionado que es proporcional a su función de adaptación. Este procedimiento se dice que está basado en la ruleta sesgada. Según dicho esquema, los individuos bien adaptados se escogerán probablemente varias veces por generación, mientras que, los pobremente adaptados al problema, no se escogerán más que de vez en cuando. Una vez seleccionados dos padres, sus cromosomas se combinan, utilizando habitualmente los operadores de cruce y mutación. Las formas básicas de dichos operadores se describen a continuación.

El operador de cruce, coge dos padres seleccionados y corta sus ristras de cromosomas en una posición escogida al azar, para producir dos subristras iniciales y dos subristras finales. Después se intercambian las subristras finales, produciéndose dos nuevos cromosomas completos (véase la Figura 2). Ambos descendientes heredan genes de cada uno de los padres. Este operador se conoce como operador de cruce basado en un punto. Habitualmente el operador de cruce no se aplica a todos los pares de individuos que han

Figura 2

Los padres de individuos que han sido seleccionados para emparejarse, sino que se aplica de manera aleatoria, normalmente con una probabilidad comprendida entre 0.5 y 1.0. En el caso en que el operador de cruce no se aplique, la descendencia se obtiene simplemente duplicando los padres.

El operador de mutación se aplica a cada hijo de manera individual, y consiste en la alteración aleatoria (normalmente con probabilidad

6

pequeña) de cada gen componente del cromosoma. La Figura 3 muestra la mutación del quinto gen del cromosoma. Sí bien

Figura 3 puede en principio pensarse que el operador de cruce es más importante que el operador de mutación, ya que proporciona una exploración rápida del espacio de búsqueda, éste último asegura que ningún punto del espacio de búsqueda tenga probabilidad cero de ser examinado, y es de capital importancia para asegurar la convergencia de los Algoritmos Genéticos. Para criterios prácticos, es muy útil la definición de convergencia introducida en este campo por De Jong en su tesis doctoral. Si el Algoritmo Genético ha sido correctamente implementado, la población evolucionará a lo largo de las generaciones sucesivas de tal manera que la adaptación media extendida a todos los individuos de la población, así como la adaptación del mejor individuo se irán incrementando hacia el óptimo global. El concepto de convergencia está relacionado con la progresión hacia la uniformidad: un gen ha convergido cuando al menos el 95 % de los individuos de la población comparten el mismo valor para dicho gen. Se dice que la población converge cuando todos los genes han convergido. Se puede generalizar dicha definición al caso en que al menos un poco de los individuos de la población hayan convergido. La Figura 4 muestra como varía la adaptación media y la mejor adaptación en un Algoritmo Genético Simple típico.

7

Figura 4 A medida que el número de generaciones aumenta, es más probable que la adaptación media se aproxime a la del mejor individuo. 4 Ejemplo

Como ilustración de los diferentes componentes del Algoritmo Genético Simple, supongamos el problema .adaptado de Goldberg de encontrar el máximo de la función f(z) = x2 sobre los enteros (1,2,...,32). Evidentemente para lograr dicho óptimo, bastaría actuar por búsqueda exhaustiva, dada la baja cardinalidad del espacio de búsqueda. Se trata por tanto de un ejemplo con el que pretendemos ilustrar el comportamiento del algoritmo anteriormente descrito. Consultando él pseudocódigo de la Figura 1. Funcionamiento vemos que el primer paso a efectuar consiste en determinar el tamaño de la población inicial, para a continuación obtener dicha población al azar y computar la función de evaluación de cada uno de sus individuos. Suponiendo que el alfabeto utilizado para codificar los individuos esté constituido por (0, 1), necesitaremos ristras de longitud 5 para representar los 32 puntos del espacio de búsqueda. En la Tabla 1, hemos representado los 4 individuos que constituyen la población inicial, junto con su función de adaptación al problema, así como la probabilidad de que cada uno de dichos individuos sea seleccionado .según el modelo de ruleta sesgada. ara emparejarse. Volviendo a consultar el pseudocódigo expresado en la Figura 1, vemos que el siguiente paso consiste en la selección de 2 parejas de individuos. Para ello es suficiente, con obtener 4 números reales provenientes de una distribución de probabilidad uniforme en el intervalo

8

Tabla 1

Tabla 2 (0, 1), y compararlos con la última columna de la Tabla l. Así por ejemplo, supongamos que dichos 4 números hayan sido: 0.58; 0.84; 0.11 y 0.43. Esto significa que los individuos seleccionados para el cruce han sido: el individuo 2 junto con el individuo 4, así como el individuo 1 junto con el individuo 2. Para seguir con el Algoritmo Genético Simple, necesitamos determinar la probabilidad de cruce, p,. Supongamos que se fije en p, = 0.8. Valiéndonos al igual que antes de, 2 en este caso, números provenientes de la distribución uniforme, determinaremos si los emparejamientos anteriores se llevan a cabo. Admitamos, por ejemplo, que los dos números extraídos sean menores que 0.8, decidiéndose por tanto efectuar el cruce entre las dos parejas. Para ello escogeremos un número al azar entre l y 1 . 1 (siendo l la longitud de la ristra utilizada para representar el individuo). Notése que la restricción impuesta al escoger el número entre 1 y l .l, y no l, se realiza con la finalidad de que los descendientes no coincidan con los padres. Supongamos, tal y como se indica en la Tabla 2, que los puntos de cruce resulten ser 2 y 3. De esta manera obtendríamos los 4 descendientes descritos en la tercera columna de la Tabla 2. A continuación siguiendo el pseudocódigo de la Figura 1, mutaríamos con una probabilidad, p, cercana a cero, cada uno de los bit de las cuatro ristras de individuos. En este caso suponemos que el único bit mutado corresponde al primer gen del tercer individuo. En las dos últimas 9

columnas se pueden consultar los valores de los individuos, así como las funciones de adaptación correspondientes. Como puede observarse, tanto el mejor individuo como la función de adaptación media han mejorado sustancialmente al compararlos con los resultados de la Tabla 1.

Representación. Todos los organismos vivos están constituidos por células, y cada célula contiene uno o más cromosomas (cadenas de ADN), que le sirven como una especie de “plano” al organismo. Un cromosoma puede ser conceptualmente dividido en genes cada uno de los cuales codifica una proteína. En términos generales, se puede decir que un gen se codifica como si fuera un rasgo, como puede serlo el color de ojos. Cada gen se encuentra en una posición particular del cromosoma, y está formado por alelos.

Se supone que los individuos (posibles soluciones del problema), pueden representarse como un conjunto de parámetros (que denominaremos genes), los cuales agrupados forman una ristra de valores, a menudo referida como cromosoma. Debe existir una representación de estos genes para poder utilizarlos posteriormente en el algoritmo genético y dotarles de unos valores. Se pueden considerar tres tipos básicos de representación o codificación de los genes: 

Binaria: en ella se utiliza un vector cuya longitud es la del número de genes de cada individuo y el valor que puede tomar cada elemento es un número binario.



Entera: en ella se utiliza un vector cuya longitud es la del número de genes de cada individuo y el valor que puede tomar cada elemento es un número entero.



Real: en ella se utiliza un vector cuya longitud es la del número de genes de cada individuo y el valor que puede tomar cada elemento es un 10

número

real.

Un individuo es una solución potencial al problema que se trata. Cada individuo contiene un cromosoma. A un conjunto de individuos se le denomina población. El fitness de un individuo es la evaluación de la función de evaluación e indica qué tan bueno es el individuo (es decir, la solución al problema) con respecto a los demás.

Algoritmo. Desarrollado por John H. Holland, el algoritmo genético opera entonces a nivel de genotipo de las soluciones mediante la siguiente secuencia:    

 

1. Comenzar con una población inicial, la cual puede ser generada de manera aleatoria. 2. Calcular el fitness (aptitud) de cada individuo. 3. Aplicar el operador de selección con base en el fitness de la población. 4. Aplicar los operadores genéticos de reproducción, cruce y mutación a la población actual para generar a la población de la siguiente generación. 5. Ir al paso 2 hasta que la condición de parada se satisfaga. 6. Cuando se cumple la condición de parada, se devuelve al mejor individuo encontrado (bien el mejor de todas las generaciones, bien el mejor de la última generación).

Operadores genéticos. En su forma más simple, un algoritmo genético consta de los siguientes operadores genéticos: selección, reproducción, cruce (crossover) y mutación. Selección El proceso de selección sirve para escoger a los individuos de la población mejor adaptados, para que actúen de progenitores de la siguiente generación. En la naturaleza existen varios factores que intervienen para que un individuo pueda tener descendencia. El primero de todos es que consiga sobrevivir, ya sea porque no es devorado por depredadores, o porque sea capaz de procurarse alimento. Lo segundo es que encuentre pareja para reproducirse. El 11

último factor es que la combinación de ambos individuos sea apta para crear un nuevo individuo. Sin embargo, en la realidad es posible que “el mejor” individuo no pueda reproducirse, pero otro individuo de “peor calidad” pueda conseguirlo. Aunque este hecho es menos probable, sigue siendo posible. En los algoritmos genéticos, la selección es un conjunto de reglas que sirven para elegir a los progenitores de la siguiente generación. Estos progenitores se reproducirán (cruzamiento genético) y generarán descendencia. Un sistema muy utilizado en los algoritmos genéticos es la selección por torneo. Este sistema consiste en escoger aleatoriamente de la población un cierto número de individuos. De esos individuos se escoge el mejor de todos para ser el padre. Para escoger la madre se repite el proceso: se escoge aleatoriamente a un número de individuos de la población y se elige al individuo con mejor calidad. Este sistema garantiza un mínimo de diversidad, ya que no siempre se elegirá al mejor individuo de la población para tener descendencia. Pero, por el contrario, existen grandes posibilidades de que éste tenga descendencia, ya que si es escogido en algún torneo, será el vencedor. Reproducción En este contexto, se entenderá por “reproducción” la clonación de un individuo. Es decir, un individuo pasará a la siguiente generación sin modificación. De esta manera, la reproducción es un operador genético que se contrapone al cruce y la mutación, puesto que estos últimos modifican los individuos que pasan a la siguiente generación. El objetivo de la reproducción es mantener en la siguiente generación a individuos con fitness alta de la presente generación. Relacionado con el concepto de reproducción está el de “elitismo”, el cual mantiene a los mejores individuos de una generación a la siguiente, para que no se pierda su información. Cruce Durante esta fase se cruzan o mezclan los individuos seleccionados en la fase anterior. Es decir, los genes de los dos padres se mezclan entre sí para dar lugar a los diferentes hijos. Existen diversos métodos de cruce, pero los más utilizados son los siguientes: 



Cruce basado en un punto: los dos individuos seleccionados para jugar el papel de padres, son recombinados por medio de la selección de un punto de corte, para posteriormente intercambiar las secciones que se encuentran a la derecha de dicho punto. Es decir, los genes del padre1 a la izquierda del punto de corte forman parte del hijo1 y los situados a la derecha formaran parte del hijo2, mientras que con el padre2 sucederá lo contrario. Cruce punto a punto: este tipo de cruce es similar al anterior pero realizándose para cada gen de los padres. Por tanto, en este cruce los 12





genes pares del padre1 formarán parte del hijo1 y los genes impares formarán parte del hijo2, mientras que para el padre2 sucederá lo contrario. Cruce multipunto: en este tipo de cruce se selecciona aleatoriamente la cantidad de puntos que se van a utilizar para el cruce. De esta forma, y de manera análoga al anterior cruce, se irán intercambiando los genes para formar los dos nuevos hijos. Cruces específicos de codificaciones no binarias: Para este tipo de codificación se pueden definir, además de los anteriores, otros tipos de operadores de cruce: o Media: el gen de la descendencia toma el valor medio de los genes de los padres. Tiene la desventaja de que únicamente se genera un descendiente en el cruce de dos padres. o Media geométrica: cada gen de la descendencia toma como valor la raíz cuadrada del producto de los genes de los padres. Presenta el problema añadido de qué signo dar al resultado si los padres tienen signos diferentes. o Extensión: se toma la diferencia existente entre los genes situados en las mismas posiciones de los padres y se suma el valor más alto o se resta del valor más bajo. Solventa el problema de generar un único descendiente.

Mutación La mutación se considera un operador básico, que proporciona un pequeño elemento de aleatoriedad en los individuos de la población. Si bien se admite que el operador de cruce es el responsable de efectuar la búsqueda a lo largo del espacio de posibles soluciones, el operador de mutación es el responsable del aumento o reducción del espacio de búsqueda dentro del algoritmo genético y del fomento de la variabilidad genética de los individuos de la población. Existen varios métodos para aplicar la mutación a los individuos de una población, pero el más comúnmente utilizado es el de mutar un porcentaje de los genes totales de la población. Este porcentaje de genes a mutar se puede seleccionar de dos maneras, de forma fija, especificando el mismo porcentaje de mutación a todas las generaciones del algoritmo genético y de forma variable, es decir, modificando el porcentaje de mutación de una generación a otra, por ejemplo reduciéndolo. De esta manera, se consigue hacer una búsqueda más amplia y global al principio e ir reduciéndola en las siguientes generaciones. Con otro tipo de codificaciones (por ejemplo codificación real) existen otras opciones de mutación, aplicadas con una probabilidad generalmente pequeña: 



Mutación al azar: Modifica el valor de un gen asignando con un nuevo valor que se encuentra dentro de un determinado rango. El nuevo valor es independiente del valor previo del gen. Mutación gaussiana: Dado un cromosoma p con un gen seleccionado para la mutación i, se le aplica una distribución normal N de media pi y

13

desviación estándar s (parámetro). Alternativamente se puede disminuir el valor de s a medida que aumenta el número de generaciones.

EXTENSIÓN Y MODELO DE ALGORITMO SIMPLE #define POBLACION 11 #define LONG_COD 20 #define LIMITE -5.12 #define PROB_CRUCE 0.3 #define PROB_MUTACION 0.001 #define INTERVALO 10.24/pow(2,LONG_COD/2) #include #include #include

typedef struct { int genotipo[LONG_COD]; double aptitud; } Individuo; void decoder (double *, double *, int *); double fitness (double, double); int generarBinario (void); Individuo generarIndividuo (void); Individuo * generarPoblacion (void); Individuo * seleccionTorneos(Individuo * pob);

void mutacionHijos (Individuo *); void cruzarSeleccion (Individuo *); Individuo elite(Individuo *); void AG(); 14

void imprimePoblacion (Individuo *); void imprimeGenotipo(Individuo); void generarGraficoGeneracional(void);

int main() { srand(time(NULL)); AG(); return 0; } void decoder (double * x, double * y, int * genotipo) { int i; *x = *y = 0.0; // calcula el primer decimal for(i=0; i