ALGORITMOS GENÉTICOS

INSTITUTO TECNOLÓGICO DE CIUDAD DELICIAS ING. EN SISTEMAS COMPUTACIONALES INTELIGENCIA ARTIFICIAL

ALGORITMOS GENÉTICOS

ROJAS HERNÁNDEZ JUAN MANUEL

24 de Noviembre del 2014

Introduccion

Una de las grandes capacidades que posee el ser humano, es poder predecir el comportamiento de su entorno, dicha capacidad se ha ido incrementando con el paso del tiempo. De igual modo, ha comprendido que, aparte posee la capacidad de poder alterar o condicionar ese entorno para mejorar algunos aspectos de su vida y la forma en que se comunica con otros aspectos de su entorno. Y son estas grandiosas capacidades las que se quieren ser replicadas en un agente artificial. Cuando se toca el tema de algoritmos genéticos, hay que hablar del Dr. John Henry Holland que en 1962 asienta las bases para sus posteriores desarrollos hasta llegar a lo que se conoce hoy por algoritmos genéticos. 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 para finalmente obtener la siguiente generación de individuos que estarán más adaptados que la anterior generación. El objetivo de Holland, no era diseñar algoritmos para resolver problemas concretos, sino estudiar, de un modo formal, el fenómeno de la adaptación tal y como ocurre en la naturaleza, y desarrollar vías de extrapolar esos mecanismos de adaptación natural a los sistemas computacionales. En uno de sus libros, Holland presentaba el algoritmo genético como una abstracción de la evolución biológica, y proporcionaba el entramado teórico para la adaptación bajo el algoritmo genético. El Algoritmo Genético de Holland era un método para desplazarse, de una población de cromosomas (bits) a una nueva población, utilizando un sistema similar a la “selección natural” junto con los operadores de cruces, mutaciones e inversión inspirados en la genética. En este primitivo algoritmo, cada cromosoma consta de genes (bits), y cada uno de ellos es una muestra de un alelo particular (0 o 1). El operador de selección escoge, entre los cromosomas de la población, aquellos con capacidad de reproducción, y entre éstos, los que sean más “compatibles”, producirán más descendencia que el resto. El de 24 de Noviembre del 2014

cruce extrae partes de dos cromosomas, imitando la combinación biológica de dos cromosomas aislados (gametos). La mutación se encarga de cambiar, de modo aleatorio, los valores del alelo en algunas localizaciones del cromosoma; y, por último, la inversión, invierte el orden de una sección contigua del cromosoma, recolocando por tanto el orden en el que se almacenan los genes. La mayor innovación de Holland fue la de introducir un algoritmo basado en poblaciones con cruces, mutaciones e inversiones. La forma más simple de algoritmo genético utiliza tres tipos de operadores: selección, cruce y mutación. 





Selección o reproducción: Este operador escoge cromosomas entre la población para efectuar la reproducción. Cuanto más capaz sea el cromosoma, más veces será seleccionado para reproducirse. Cruce: Se trata de un operador cuya labor es elegir un lugar, y cambiar las secuencias antes y después de esa posición entre dos cromosomas, para crear nueva descendencia (por ejemplo, las cadenas 10010011 y 11111010 pueden cruzarse después del tercer lugar para producir la descendencia 10011010 y 11110011). Imita la recombinación biológica entre dos organismos haploides. Mutación: Este operador produce variaciones de modo aleatorio en un cromosoma (por ejemplo, la cadena 00011100 puede mutar su segunda posición para dar lugar a la cadena 01011100). La mutación puede darse en cada posición de un bit en una cadena, con una probabilidad, normalmente muy pequeña (por ejemplo 0.001).

Eso se podría decir que son los operadores base, ya que conforme fue avanzando el estudio de estos conceptos de desarrollaron nuevos operadores que son versiones mejoradas y rediseñadas de los principales para resolver problemas específicos:  Codificación de las Variables.- Los cromosomas de alguna manera deberán contener información acerca de la solución que representa. La codificación se puede realizar de varias formas. La más utilizada es mediante una cadena de números binarios (1s o 0s). Pero también se puede realizar la codificación mediante números enteros o incluso cadenas de palabras. La codificación se puede dar por:  Codificación Binaria.  Codificación Numérica.  Codificación por Valor Directo.  Codificación en Árbol. 24 de Noviembre del 2014

 Selección. Como ya se explicó 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 de acuerdo con la teoría de Darwin en la cual los más capacitados son los que deben sobrevivir y crear una nueva descendencia más facultada. La selección de puede dar por:  Selección por Rueda de Ruleta.  Selección por Rango.  Selección Elitista.  Selección por Estado Estacionario.  Selección por Torneo.  Selección Escalda.  Selección Jerárquica.  Reproducción o Crossover. 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. El cruce se puede dar por:  Crossover 1 Punto.  Crossover 2 Puntos.  Crossover Uniforme.  Crossover Aritmético.  Operadores de Nicho. Estos operadores están encaminados a mantener la diversidad genética de la población, de forma que cromosomas similares sustituyan sólo a cromosomas similares, y son especialmente útiles en problemas con muchas soluciones. Un algoritmo genético con estos operadores es capaz de hallar todos los máximos, dedicándose a cada especie un máximo. Más que operadores genéticos, son formas de enfocar la selección y la evaluación de la población.

Como se puede observar, los Algoritmos Genéticos difieren de los métodos tradicionales de búsqueda y optimización, en cuatro cuestiones esenciales: 1. Trabajan con un código del conjunto de parámetros, no con el conjunto mismo (necesitan que el conjunto de parámetros del problema de optimización esté codificado en cadenas finitas sobre un determinado alfabeto). Por trabajar a nivel

24 de Noviembre del 2014

de código, y no con las funciones y sus variables de control, como los otros métodos, son más difíciles de “engañar”. 2. Buscan una población de puntos, no un único punto. Manteniendo una población de puntos muéstrales bien adaptados, se reduce la probabilidad de caer en una cima falsa. 3. Emplean la función objetivo, no necesitan derivadas ni otra información complementaria, tan difícil a veces de conseguir. De este modo ganan en eficiencia y en generalidad. 4. Se valen de reglas de transiciones estocásticas, no deterministas. Los Algoritmos Genéticos se valen de operadores aleatorios para guiar la búsqueda de los mejores puntos; puede parecer extraño, pero la Naturaleza está llena de precedentes al respecto.

¿Qué son los Algoritmos Genéticos? Los objetivos que perseguían John Holland y sus colegas de la Universidad de Michigan cuando concibieron los algoritmos genéticos, eran dos: 1) Abstraer y explicar rigurosamente el proceso adaptativo de los sistemas naturales. 2) Diseñar sistemas artificiales que retuvieran los mecanismos más importantes de los sistemas naturales. En este sentido, podemos decir que los algoritmos genéticos son “Algoritmos de búsqueda basados en los mecanismos de selección natural y genética natural. Combinan la supervivencia de los más compatibles entre las estructuras de cadenas, con una estructura de información ya aleatorizada, intercambiada para construir un algoritmo de búsqueda con algunas de las capacidades de innovación de la búsqueda humana”, (Goldberg, D. (1989) Genetics Algorithms in Search, Optimization and Machine Learning. Addison Wesley). Básicamente, el Algoritmo Genético funciona como sigue: en cada generación, se crea un conjunto nuevo de “criaturas artificiales” (cadenas) utilizando bits y partes más adecuadas del progenitor. Esto involucra un proceso aleatorio que no es, en absoluto, simple. La novedad que introducen los Algoritmos Genéticos es que explotan eficientemente la información histórica para especular sobre nuevos puntos de búsqueda, esperando un funcionamiento mejorado. 24 de Noviembre del 2014

Bosquejo Básico En la naturaleza todo el proceso de evolución biológica se hace de forma natural pero para aplicar el algoritmo genético al campo de la resolución de problemas habrá que seguir una serie de pasos. Una premisa es conseguir que el tamaño de la población sea 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. Los pasos básicos de un algoritmo genético son:  Evaluar la puntuación de cada uno de los cromosomas generados.  Permitir la reproducción de los cromosomas siendo los más aptos los que tengan más probabilidad de reproducirse.  Con cierta probabilidad de mutación, mutar un gen del nuevo individuo generado.  Organizar la nueva población. Estos pasos se repetirán hasta que se dé una condición de terminación. Se puede fijar un número máximo de iteraciones antes de finalizar el algoritmo genético o detenerlo cuando no se produzcan más cambios en la población (convergencia del algoritmo). Esta última opción suele ser la más habitual. Veamos el esquema general de un algoritmo genético simple:

24 de Noviembre del 2014

Parámetros de los Algoritmos Genéticos 1. Tamaño de la población. Este parámetro nos indica el número de cromosomas que tenemos en nuestra población para una generación determinada. En caso de que esta medida sea insuficiente, el algoritmo genético tiene pocas posibilidades de realizar reproducciones con lo que se realizaría una búsqueda de soluciones escasa y poco óptima. Por otro lado si la población es excesiva, el algoritmo genético será excesivamente lento. Para ellos se ha determinado un límite de población sugerido que de ser sobrepasado el algoritmo será ineficiente en cuanto a tiempo de resolución. 2. 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. En caso de que no exista probabilidad de reproducción, los hijos serán copias exactas de los padres. En caso de haberla, los hijos tendrán partes de los cromosomas de los padres. Si la probabilidad de cruce es del 100% el hijo se crea totalmente por cruce, no por partes. 3. Probabilidad de Mutación. Nos indica la frecuencia con la que los genes de un cromosoma son mutados. Si no hay mutación, los descendientes son los mismos que había tras la reproducción. En caso de que haya mutaciones, parte del cromosoma descendiente es modificado y si la probabilidad de mutación es del 100%, la totalidad del cromosoma se cambia. En este caso, no se cambian simplemente unos bits del cromosoma sino que se cambian todos, lo que significa que se produce una inversión en el cromosoma y no una mutación por lo que la población degenera muy rápidamente.

24 de Noviembre del 2014

Ejemplo Sencillo de Implementación de un Algoritmo Genético Sea X el problema a resolver. Dada una representación de candidatas a soluciones en una cadena de bits, un algoritmo genético simple, tal y como se describe en Mitchell M. (1998), trabajaría del siguiente modo: 1. Comenzar con una población P generada aleatoriamente de n cromosomas del bit. 2. Calcular la capacidad f(x) para cada cromosoma x de P. 3. Repetir los siguientes pasos hasta que se hayan creado n descendiente: a. Seleccionar un par de cromosomas padre de P, siendo la probabilidad de selección una función creciente de la capacidad. La selección se realiza “con remplazamiento”, es decir, que el mismo cromosoma puede ser seleccionado en más de una ocasión para ser padre. b. Con probabilidad pc (probabilidad de cruce, o tasa de cruce), cruzar el par en un punto elegido aleatoriamente (con probabilidad uniforme) para formar dos descendientes. Si no tiene lugar ningún cruce, formar dos descendientes que sean copias exactas de sus respectivos padres. (Obsérvese que aquí la probabilidad de cruce se define como la probabilidad de que dos padres se crucen sobre un único punto. Hay otras versiones de algoritmos genéticos que son de “cruces en múltiples puntos”, en los que la tasa de cruce para una pareja de padres es el n º de puntos en los que tiene lugar un cruce).

c. Mutar los dos descendientes en cada lugar con probabilidad pm (probabilidad de mutación, o tasa de mutación), y colocar los cromosomas resultantes en la nueva población P’. Si n es impar, se puede rechazar aleatoriamente a un miembro de la nueva población. 4. Remplazar la población actual P con la nueva P’. 5. Volver al paso 2.

24 de Noviembre del 2014