Proyecto gysanbcni I ,qeKa6pR 02, 2010 29 pagos TRABAJO FINAL ESPECIALIDAD EN INGENIERÍA DE SISTEMAS EXPERTOS Estudio de una Herramienta de Obtención de Sub-óptimos Basada en Algoritmos Genéticos Autor: Lic. Andrea Cottone Directora: M. lng. Paola Britos octubre 2004 basada en Algoritmos Genéticos Lic. Andrea Cottone PACE 1 or2g 2 to View nut*ge Estudio de una Herr Sub-óptimos basada en Algoritmo Contenido Capitulo 1 : Introducción A Los Algoritmos Genéticos Los algoritmos .. 5 Evaluación de la Aptitud……. Selección. • • • • • • • • • • • • • • • • • .. Cruza o Capitulo 2: Manual De Usuario De La Herramienta Sección 1 – Requisitos e Instalación del Sistema…. . Operadores.. ……… 15 Operadores provistos. • • • • • • • • • • • • • 17 Selecclón…………….. ….. 17 Combinación . 17 Mutación…. … 17 sección 3 – Menúes, Diálogos y 19 Archivo………. . .. 21 Edit. . … 21 … 23 Reports… …… 23 Run Diálogos…. ….. 25 Graph Axis Configuratio …. 25 Graph Axis Configuration…. . … 25 Combination. …… 26 File Open / DL L.. • • • • • • • • • • • • • • • • • • • … 27
Function Details…. ……. 27 punctions Status……… — — 28 …… 29 Evaluation Functions……………. . …. 29 Log File 24 — Selection…… Status….. 27 Ventanas……….. — … 29 Fitness Current Status……. …. 29 Overal distribution of ……. 36 Current distribution of … 36 Sección 4 – Escribiendo Funciones de Evaluación… …… 36 Sección 4 Escribiendo Funciones de Evaluación. Introducción.. • • • • • • • • • • • • … 39 pasaje de información….. ….. 39 Qué información debe proveer .. 40 Definiciones del 40 Ejemplos de 42 Código fuente del ejemplo en
Pascal…. …. 42 Lic. Andrea Cottone 3 basada en Algoritmos Genéticos Sección 5 – Comienzo 45 Seleccionar la 47 Configuración. Pantalla. • • • • • • • • • Capitulo 3: Aplicación Práctica Definición del pro blema. . . . . . . . . 49 Espacio de Búsqueda. . . . . . . . . . . 49 Aproximación de la solución…….. . Utilizando el programa Wing so lución.. . . . . . . . . . . 49 Utilizando el programa Winga • • • • • • • • • • Capitulo 4: Conclusiones………… …. 55 Capitulo 5: Bibliografía. 57 4 Capitulo 1: Introducción A Los Algoritmos Genéticos
Los Algoritmos Genéticos Los algoritmos genéticos son métodos sistemáticos para la resolución de problemas de búsqueda y optimización que aplican los mismos métodos de la evolución biológica: selección basada en la población, reproducción y mutación. Fueron desarrollados por John Holland, junto a su equipo de investigación, en la universidad de Michigan en la década de 1970. El objetivo de un AG es buscar una «buena» solución a un problema determinado. El cromosoma es el representante, dentro del algoritmo genético, de una posible solución al problema.
Para comenzar la competición, se generan leatoriamente una serie de cromosomas. El algoritmo genético procede de la forma siguiente: Pasos 1. Evaluar la aptitud de cada uno de los individuos. 2. Permitir a cada uno reproducirse, de acuerdo con su puntuaclón. 3. Emparejar los individuos de la nueva población, haciendo que intercambien material genético, y que alguno de los bits de un gen se vea alterado debido a una mutación espontánea. De esta manera el algoritmo genético va creando nuevas «generaci blación, cuyos individuos son cada vez mejores solu lema.
Cada uno de los mejores soluciones al problema. Cada uno de los pasos consiste n hacer algo con las cadenas de bits, es decir, la aplicación de un operador a una cadena binaria. A estos operadores se los denominan, operadores genéticos, y los tres principales son: selección, cruza (crossover o recombinación) y mutación. Un algoritmo genético tiene también una serie de parámetros que se tienen que fijar para cada ejecución, como los siguientes: Tamaño de la población: debe de ser suficiente para garantizar la diversidad de las soluciones.
Poblaciones pequeñas corren el riesgo de no cubrir adecuadamente el espacio de búsqueda y poblaciones grandes llevan a un excesivo costo computacional. Condición de terminación: lo más habitual es que además de la convergencia exista otra condición de terminación como ser el número máximos de generaciones. Evaluación de la Aptitud En el sistema biológico el material genético, sobrevive a cada generación, combinándose y ampliando su presencia en la población, en la medida en que las estructuras que lo contienen manifiesten aptitud relativamente buena.
Llevando esto al ámbito de la solución de problemas, un individuo representaría una solución posible y su aptitud indicaría cuan buena es la solución. Durante la evaluación, se decodifica el en, convirtiéndose en una serie de parámetros de un problema, se halla la solución del problema a partir de esos parámetros, y se le da una puntuación a esa solución en función de lo cerca que esté de la mejor solución. A esta puntuación se le llama aptitud (en ingles fitness).
La aptitud ayuda a determinar los cromosomas que se van a reproducir, y se van a eliminar, pero hay varias formas de consi alor reproducir, y aquellos que se van a eliminar, pero hay varias formas de considerar a este valor durante la selección Selección Una vez evaluada la aptitud, se tiene que crear la nueva población eniendo en cuenta que los buenos rasgos de los mejores individuos. Esta selección, y la consiguiente reproducción, se puede hacer de las siguientes formas principales: Rueda de ruleta: Este método consiste en construir una ruleta particionada en ranuras de igual tamaño, las cuales se numeran.
A cada individuo de la población se le asigna una cantidad de ranuras proporcional a su aptitud El proceso se repite hasta completar la cantidad de individuos deseados. Este método de selecclón otorga mayor probabilidad de contribuir a la siguiente generación a los individuos con mayor aptitud. Hay algunas otras variantes como por ejemplo, incluir en la nueva generación el mejor representante de la generación actual. En este caso, se denomina método elitista. Selección por torneo: En este caso dos individuos son elegidos al azar de la población actual y el mejor o más apto de los dos se coloca en la generación siguiente.
Esto continúa hasta que se complete la nueva población. • Basado en el rango: en este esquema se mantiene un porcentaje de la población, generalmente la mayoría, para la siguiente generación. Se coloca toda la población por orden de aptitud, y los M menos dignos on eliminados y sustituidos por la descendencia de alguno de los M mejores con algún otro individuo de la población. A este esquema se le pueden aplicar otros criterios; por ejemplo, se crea la descendencia de uno de los padres, y esta sustituye al más parecido entre los perdedores. Esto se denomina crowdin% y fue introducido por DeJong.
En realidad, para este esquema se escoge un crowding factor, CF. Cuando nace una nueva criatura, se sel para este esquema se escoge un crowding factor, CF. Cuando nace una nueva criatura, se seleccionan CF individuos de la población, y se elimina al más parecido a la nueva criatura. JMG] Método Estocástlco: por cada Individuo se calcula la aptitud relativa al promedio de aptitudes de la población, y en función de esto se asignan las copias. por ejemplo, si la aptitud promedio de la población es 15 y la aptitud del individuo es 10; entonces su aptitud relativa es 1. . Esto significa que se colocará una copia en la próxima generación y que se tiene el 0. 5 (50 %) de chance de colocar una segunda copia. 6 Cruza o Crossover Consiste en el intercambio de material genético entre dos cromosomas La cruza es el principal operador genético, hasta l punto que se puede decir que no es un algoritmo genético si no tiene cruza, y, sin embargo, puede serlo perfectamente sin mutación, según descubrió Holland_ para aplicar la cruza (crossover o recombinación), se escogen aleatoriamente dos miembros de la población.
Dos descendiente de los mismos padres pueden cruzarse; ello garantiza la perpetuación de un individuo con buena puntuación (y, además, algo parecido ocurre en la realidad; es una práctica utilizada, por ejemplo, en la cria de ganado, llamada inbreeding, y destinada a potenciar ciertas características frente a otras). Sin embargo, si esto sucede emasiado a menudo, puede crear problemas: toda la pob ación puede aparecer dominada por los descendientes de algún gen, que, además, puede tener caracteres no deseados.
Esto se suele denominar en otros méto ción atranque en un mínimo local, y es uno de I problemas con los que uno de los principales problemas con los que se enfrentan los que aplican algoritmos genéticos [JMG]. El operador de cruza es el encargado de mezclar bloques buenos que se encuentren en los diversos progenitores, y que serán los que den a los mismos una buena puntuación. La presión selectiva se encarga de que ólo los buenos bloques se perpetúen, y poco a poco vayan formando una buena solución.
El teorema de los esquemas dice que la cantidad de buenos bloques se va incrementando con el tiempo de ejecución de un algoritmo genético, y es el resultado teórico más importante en algoritmos genéticos. El intercambio genético se puede llevar a cabo de muchas formas, pero los grupos principales son: • Cruza Simple: los dos cromosomas padres se cortan por un punto, y el material genético sltuado entre ellos se intercambia [RGM]. Dada las siguientes estructuras de longitud 1 = 8, y eligiendo 3 como el punto de cruza se ntercambian los segmentos de cromosoma separados por este punto.
XYX WXXYXYX I • Cruza de dos puntos: En este método de cruza de dos puntos, se seleccionan dos puntos aleatoriamente a lo largo de la longitud de los cromosomas y los dos padres intercambian los segmentos entre estos puntos. Cruza Multipunto: el cromosoma es considerado un anillo, y se eligen n puntos de cruza en forma aleatoria. Si la cantidad de puntos de cruza es par, se intercambian las porciones de cromosomas definidas entre cada par de puntos consecutivos, si es impar se asume un punto de cruza adicional en la posición cero y se procede de igual modo RGM].
Dadas dos estructuras de longitud 1 = 8, con n = 4 puntos de cruza. Intercambiando los segmentos de la posición 2 a 4 y 6 a Lic. Andrea Cottone 7 X YXYIYIXXIXY YXXY YXX YIWIXYIYWIYIXX Y X YXYIYIXXIXYIYXX Cruza binomial: Para generar un cromosoma hijo por cruza binomial, se define la probabilidad PO como la probabilidad de que el Alelo de cualquier posición del descendiente se herede del padre, y 1 — PO como la probabilidad de que lo herede de la madrel. En este caso se puede construlr un único hijo por cada aplicación del operador, o bien generar un segundo hijo como complemento del primero.
Cuando existe igual probabilidad de heredar del padre como de la madre, PO = 0,5 la cruza se denomina uniforme. Para estructuras de longitud I la cruza uniforme implica un promedio de 1/2 puntos de cruza [DEJ/92]. Mutación En la Evolución, una mutación es un suceso bastante poco común (sucede aproximadamente una de cada mll replicaciones), en la mayoría de los casos las mutaciones son letales, pero en promedio, contribuyen a la diversidad genética de la especie. En un algoritmo genético tendrán el mismo papel, y la misma frecuencia (es decir, muy baja).
IJna vez establecida la frecuencia e mutación, por ejemplo, uno por mil, se examina cada bit de cada cadena. Si un numero generado aleatoriamente está por debajo de esa probabilidad, se cambiará el bit (es decir, de Oa 1 o de 1 a 0). Si no, se dejará como está. Dependiendo del número de individuos que haya y del número de bits por individuo, puede resultar que las mutaciones sean extremadamente raras en una sola generación. No hace falta decir que no conviene abusar de la mutación. Es cierto que es un mecanismo generador de diversidad, y, por tanto, la do un algoritmo genético está estancado, pero tam ue reduce el algoritmo
