Free Web Hosting by Netfirms
 Web Hosting by Netfirms | Free Domain Names by Netfirms

E.T.O.D. Argentina

Equipo de Traducción con Organización Distribuida

setstats 1 Prólogo Al principio, encontré a encontré a David Goldberg como un joven PhD-bound ingeniero civil, investigador de mi curso "Introducción a Sistemas Adaptativos". Me pareció algo extraño que su experiencia muy práctica del campo en la industria de las tuberías de gas, y su interés evidente en esa industria, no parecía desalentar su interés en lo que era, después de todo, un curso abstracto que involucra mucho "material biológico". Después de que se inscribió en el curso, comprendí pronto que sus súbitos intereses en el control, tuberías de gas, e Inteligencia Artificial, era la sólo la superficie de una gran curiosidad y un talento para el análisis cuidadoso. Él era, y es, ingeniero interesado en construcciones, pero él estaba, y está, igualmente interesado en ideas. No mucho después, Dave me preguntó si me gustaría compartir la cátedra (con Ben Wylie, el presidente de nuestro Departamento de Ingeniería Civil) sobre una disertación que investigara el uso de algoritmos genéticos y sistemas del clasificación en el control de transmisión de tuberías de gas. Mi primera reacción fue que esto era un problema demasiado difícil para una disertación. No hay ninguna solución analítica concluída a incluso las versiones simples del problema, y el funcionamiento real involucra mucho tiempo de aprendizaje del oficio [craftsmanlike]. Dave persistió, y en un tiempo sorprendentemente corto produjo una disertación que, a su vez produjo para él el Premio 1985 del National Science Foundation "Presidential Young Investigator Award". Tanto para mi intuición acerca de lo que constituye una disertación razonable. En los últimos años los Algoritmos Genéticos han pasado de ser un tema misterioso conocido por algunos de mis estudiantes, y sus estudiantes, a un tema que compromete la curiosidad de muchas comunidades de la investigación diferentes que abarcan a investigadores en economía, ciencia política, psicología, lingüística, inmunolgía, biología, e informática. La razón principal para este interés es que los Algoritmos Genéticos realmente funcionan. El libro de David Goldberg proporciona una entrada a este territorio. Uno no puede estar mucho tiempo en torno a David Goldberg sin ser contagiado por su entusiasmo y energía. Ese entusiasmo llega a través de este libro. También es una incorporación de su pasión por las explicaciones claras y ejemplos cuidadosamente trabajados. Su libro hace un trabajo excepcional de producir los métodos de Algoritmos Genéticos y sistemas de clasificación disponibles para un amplio público. Dave está profundamente interesado en los problemas intelectuales de Algoritmos Genéticos y sistemas de clasificación, pero él está más aun interesado en ver a estos sistemas siendo utilizados. Este libro, yo pienso, será un instrumento para la realización de esa ambición. John Holland Ann Arbor, Michigan Prefacio Este libro trata sobre procedimientos de búsqueda de algoritmos genéticos basados en las mecánicas de selección natural y las genéticas naturales. Al escribirlo, yo he intentado reunir las técnicas de computación, herramientas matemáticas, y resultados de la investigación que le permitirán que aplique algoritmos genéticos a los problemas en su campo. Si usted escoge hacerlo así, usted se introducirá en un grupo creciente de investigadores y practicantes que han venido a apreciar las analogías naturales, análisis matemáticos, y técnicas de computación comprendidos por la metodología de los Algoritmos Genéticos. El libro se idea para ser un libro de texto y una guía del auto aprendizaje. He probado el borrador del texto en un un semestre, con estudiantes de la clase del último año y primer año dedicados a los algoritmos genéticos. Aunque los estudiantes vinieron de áreas diferentes (bioquímica, ingeniería química, informática, ingeniería eléctrica, diseño de mecánica, inglés, matemática, ingeniería mecánica, y físicas) y tenían amplias diferencias en matemática y conocimiento computacional, todos adquirieron una comprensión del algoritmo básico y su teoría de funcionamiento. Para llegar a semejante diversidad de público, el tono del libro es intencionalmente casual, y el rigor casi siempre es sacrificado en el interés de establecer intuición y entender. Ejemplos funcionando ilustran los temas principales, y las aplicaciones están disponibles al final de cada capítulo. He minimizado los conocimientos de matemática, genéticas, y conocimientos de fondo de computación necesarios para leer este libro. Se supone una comprensión de las matemáticas de nivel universitario introductorio (álgebra y pequeños cálculos). Se usan nociones elementales de cálculos y la probabilidad finita, y el Apéndice resume los conceptos importantes brevemente, no asumo ningún conocimiento particular de genéticas y defino en el texto toda la terminología necesaria sobre genética y demás conceptos. Por último, se necesita cierta capacidad para programar computadoras. Si usted ha programado en algún lenguaje, usted deberá poder seguir los ejemplos de computación que yo presento. Todo el código de computación en este libro se escribe en Pascal, y el Apéndice B presenta una introducción breve a las bases de ese lenguaje. Aunque yo no he subdividido el libro explícitamente en partes separadas, los capítulos pueden agruparse en dos categorías principales: aquellos que trantan de búsqueda y optimización y aquellos que tratan el aprendizaje de las máquinas. Los primeros cinco capítulos se dedican a los algoritmos genéticos en búsqueda y optimización. El Capítulo 1 introduce el tema de algoritmos genéticos en las búsquedas; también describe un algoritmo genético simple e ilustra la aplicación de un Algoritmo Genético a través de un cálculo manual. El Capítulo 2 introduce la base teórica esencial de Algoritmos Genéticos, tema que cubre incluso los esquemas, el teorema fundamental, y el análisis extenso. Si usted tiene aversión a teoría, puede saltar el Capítulo 2 seguramente sin pérdida excesiva de continuidad; sin embargo, antes de hacer esto, sugiero que pruebe leyéndolo de cualquier modo. Los fundamentos matemáticos de Algoritmos Genéticos no son difíciles seguir, pero sus ramificaciones son sutiles; un poco de atención al análisis inicial en el estudio de Algoritmos Genéticos favorece una comprensión más completa de la fuerza del algoritmo. El Capítulo 3 introduce a la implementación en computación de algoritmos genéticos a través de ejemplos. Específicamente, se presenta a lo largo del capítulo un código en Pascal llamado Algoritmo Genético Simple (SGA) con varias extensiones. El Capítulo 4 presenta informes históricos de algoritmos genéticos iniciales junto con un popurrí de aplicaciones actuales. El Capítulo 5 examina los operadores genéticos más avanzados y presenta varias aplicaciones que ilustran su uso. Éstos incluyen aplicaciones de micro-nivel y operadores del macro-nivel así como las técnicas híbridas. Los Capítulos 6 y 7 presentan la aplicación de algoritmos genéticos en sistemas de aprendizaje de máquinas. El Capítulo 6 da una descripción genérica de un tipo de sistema GBML (Genetics Based Machine Learning), un sistema clasificador. La teoría de funcionamiento de semejante sistema se repasa brevemente, se muestra una aplicación en Pascal llamada Sistema Clasificador Simple (SCS) y se aplica al aprendizaje de una función del buleana. El Capítulo 7 redondea en general sobre GBML presentando una revisión histórica de sistemas de GBML iniciales junto con un estudio selectivo de otros temas y sistemas actuales. Algoritmos genéticos Que son los algoritmos geneticos? Los algoritmos geneticos son algoritmos de búsquedas basados en mecanismos de selección natural y genetica natural. Ellos combinan una supervivencia adecuada en medios de cadenas de estructura con una estructurada informacion aleatoria intercambiada para formar un algoritmo con algunas de las innovaciones especiales de la búsqueda humana. En toda generacion, un nuevo grupo de criaturas artificiales son creadas usando bits y piezas de [FITTEST] lo nuevo y lo viejo: una nueva parte ocasional es probada para buenas medidas. Mientras [RANDOMIZED], los algoritmos geneticos no son simples [RANDOM WALK}. Ellos explotan informacion historica eficientemente para especular un nuevo punto de búsqueda con una esperada realización mejorada. Los algoritmos geneticos han sido desarrollados por John Holand, sus colegas y sus estudiantes de la universidad de Michigan. La meta de sus investigaciones han sido incrementadas: 1) para abstraer y explicar rigurosamente el proceso de adaptación del sistema natural, 2) designar sistemas de software artificial que retienen los mecanismos importantes del sistema natural. Este acercamiento llevo a importantes descubrimientos en ambos sistemas de la ciencia natural y artificial. El tema central de la investigación sobre los algoritmos geneticos es la robustez [ROBUSTNESS], el balance entre eficiencia y eficacia necesaria para la supervivencia en algunos diferentes medio ambientes. Las explicaciones de la robustez [ROBUSTNESS] para el sistema artificial son [MANIFOLD]. Si el sistema artificial puede ser hecho mas robusto, rediseños costosos pueden ser reducidos o eliminados. Si el nivel de altura de adaptación puede ser alcanzado los sistemas existente pueden realizar sus funciones por mucho tiempo y mejor. Diseñadores de sistemas artificiales , ambos software y hardware, sistemas de ingenieria, sistemas de computación o sistemas de negocios, pueden solamente maravillar [AT THE ROBUSTNESS], la eficiencia y la flexibilidad de los sistemas biologicos. Caracteristicas para autoreparacion, autodireccion y reproducción son las reglas en los sistemas biologicos, mientras ellos apenas existen en los sistemas artificiales mas sofisticados. De este modo, estamos sacando una interesante conclusión: cuando una robusta realización es deseada (y cundo no lo es?), la naturaleza hace lo mejor; los secretos de adaptación y la supervivencia son mejor aprendidas desde el cuidadoso estudio del ejemplo biologico. Sin embargo no aceptamos los metodos de los algoritmos geneticos de apelar a esta belleza de la naturaleza solamente argumentada. Los algoritmos geneticos estan teóricamente y empíricamente provistos de proporcionar búsquedas robustas en espacios complejos. La monografía principal sobre el tema es adaptation in nature and artificial system, Holanda 1975. Muchos documentos y disertaciones demuestran la validez de la tecnica en optimizacion de funciones y aplicaciones de control. Habiendo quedado establecido como una valida aproximación a los problemas requiriendo una búsqueda eficiente y efectiva, los algoritmos geneticos se estan extendiendo mas generalmente en aplicaciones de negocios, cientificas y circulos de ingenieria. Las razones detrás de los crecientes numeros de aplicaciones son claras. Estos algoritmos son todavía computacionalmente simples, poderosos en sus búsquedas para el mejoramiento. Mas, ellos no estan fundamentalmente limitados por sus posisiones restrictivas a cerca de la búsqueda de espacio. Nosotros investigaremos las razones detrás de esas cualidades atractivas, pero antes de esto, nossotros necesitmos explorar la robustez de los muy aceptados procedimientos de búsqueda. LA ROBUSTES DE LOS METODOS DE BUSQUEDA Y OPTIMIZACION TRADICIONAL. Este libro no es un estudio comparativo sobre las tecnicas de búsqueda y optimizacion. No obstante, es importante preguntarse si los metodos convencionales de búsqueda satisfacen los requerimientos de robustez. La literatura corriente explica tres metodos principales de búsqueda, 1)basados en calculos 2)enumerativos y 3)aleatorios. 1)Basados en calculos han sido estudiados intensivamente. Estos se subdividen en dos clases principales: directos e indirectos. Metodos indirectos buscan maximos locales mediante la resolucion de un conjunto de ecuaciones lineales resultadas de setear la funcion objetivo de la gradiente a cero. Es una generalización multidimensional de los calculos elementales de los puntos maximos como se ilustran en la figura 1.1, es decir, existe una funcion que permite encontrar una posible cima mediante la restricción de las búsquedas a esos puntos con la pendiente a cero en toda las direcciones. Metodos directos buscan optimos locales mediante saltos en la funcion y moviendose en direccion hacia la gradiente local. Mientras ambos metodos de base de calculos han sido mejorados, prolongados, [HASHED, y REHASHED], algunos simples razonamientos muestran su falta de robustes. Primero, ambos metodos son de alcance local, el optimo que buscan es el mejor en un vecindario del punto actual. Por ejemplo, la figura 1.1 muestra una porcion del completo dominio de interes: un cuadro mas completo es mostrado en la figura 1.2. claramente, empezando la búsqueda o procedimientos para la búsqueda del cero [ZERO-FINDING PROCEDURE] en el vecindario a la cima minima nos causara perdernos del evento central (cima maxima). Una vez que se alcanzo el pico minimo un mejoramiento mayor debe ser buscado a traves de [RANDOM RESTART] u otro engaño [TRICKERY]. Segundo, los metodos de base de calculo dependen de la existencia de derivadas (valores de pendientes bien definidas) aunque nosotros permitamos aproximaciones numerales en las derivadas esto es un severo defecto, algunos espacios de parámetros prácticos (NO SE COMO SIGUE) Teorias interesadas en optimizacion han sido muy deseadas para aceptar la legalidad de los grandes matematicos de los siglos 18 y 19 que pintaron un mundo limpio de funciones objetivas cuadraticas, restricciones ideales y las presentes derivadas. El mundo real de la búsqueda es encargado de un discontinuo y vasto multimodal, la búsqueda del ruido en el espacio es representado como una funcion de calculos amigables, en la figura numero 1.3. Estos metodos dependen sobre los requerimientos restrictivos de la continuidad y la existencia de derivadas son inapropiados para todo problema de domino limitado. Por esta razon y por su alcance local de la búsqueda, deberemos rechazar los metodos basados en calculos. Ellos son inuficientemente robustos en dominios [UNINTENDED] 2) Los metodos enumartivos han sido considerados en muchas formas y tamaños. La idea es que sean sencillos, búsquedas en espacios finitos o espacios infinitos de búsquedas discretos. Estos metodos empiezan buscando una valor para la funcion objetivo en todos los puntos en el espacio, uno por vez. Aunque la simplicidad de estos tipos de algoritmos es atractiva y la una búsqueda [MUY HUMANA] (cuando el numero de posibilidades es muy pequeño) tales esquemas deberan ser discontinuos en la carrera de la robustes por una simple razon: perdida de eficiencia. Muchos espacios practicos son simplemente muy largos para buscar uno por vez y aun tiene una chance de buscar alguna practica final. Incluso los mas elevados alcances del esquema enumerativo (programación dinamica) se descomponene en problemas de tamaño moderado y complejo sufriendo la etiqueta de “curse of dimensionality” por su creador Bellman. Nosotros debemos concluir que los esquemas enumerativos poco inteligentes o poco listos abundan en los problemas reales. 3) Los algoritmos de búsqueda aleatorio han logrado alcanzar su popularidad como las investigaciones han reconocido los [SHORTCOMINGS] de metodos basados en calculos y esquemas enumerativos. Todavía, [RANDOM WALKS AND RANDOM SCHEMES] que buscan y guardan lo mejor, deberan tambien ser descontados por los requerimientos de eficiencia. Las búsquedas aleatorias en un periodo largo pueden no resultar ser las mejores que los esquemas enumerativos. En nuestro apresuramiento en descontar estrictamente metodos de búsqueda aleatoria nosotros deberiamos tener cuidado de separarlos de las tecnicas aleatorias. Los algoritmos geneticos son un ejemplo de los procedimientos de búsqueda que usan una selección aleatoria como una herramienta para guiar una búsqueda de exploracion a traves de la codificacion de los parámetros del espacio. Usando la selección aleatoria como una herramienta en el proceso directo de búsqueda puede parecer extraño al principio pero naturalmnente tiene muchos ejemplos. Otra tecnica actual de búsqueda popular es [SIMULATED ANNEALING] que usa el proceso aleatorio para ayudar a guiarse en la búsqueda de los estados minimos de energia. Lo importante es reconocer en este momento que la búsqueda aleatoria no necesariamente implica búsquedas direccionales. Mientras nuestra discusión no fue una examinacion exhaustiva sobre los metodos de [MIRYAD] de optimizacion tradicional nosotros dejamos una conclusión inestable: los metodos de búsqueda convencionales no son robustos. Esto no implica que no sean utiles. Los esquemas mensionados, innumerables combinaciones hibridas y permutaciones son usadas exitosamente en varias aplicaciones; sin embargo, con problemas mas complejos emprendidos, otros metodos seran necesarios. Para poner este punto en una mejor perspectiva, inspeccione el problema de la figura 1.4. En la figura un indice efectivo mitico es trazado a lo largo del problema continuo para un esquema especializado, un esquema enumerativo y un esquema robuesto idealizado. La tecnica gradiente actua de forma adecuada en un problema de clase angosta, como esperamos, pero se convierte altamente ineficiente en otra parte. Por otra porte, el esquema enumerativo actua con [EGALITARIAN] ineficiencia a lo largo del problema, como es mostrado en la cuerva de bajo rendimiento. Mucho mas deseable seria una curva de rendimiento como la curva etiquetada “esquema robusto”. Merece la pena sacrificar un pico de rendimiento en un problema particular para alcanzar un nivel relativamente alto de rendimiento a lo largo del espectro del problema (por supuesto, con metodos eficientes y amplios podremos crear esquema hibridos que combinen lo mejor del metodo de búsqueda local, con un esquema robusto mas general. Tendremos mas que decir en el capitulo 5). Pronto veremos como con los algoritmos genetico ayudan a llenar este vacio de robustes. Las Metas de Optimización Antes de examinar los mecanismos y atributos de un simple algoritmo genético, debemos aclarar nuestras metas cuando queremos optimizar una función o un proceso. ¿Que tratamos de lograr cuando optimizamos? La vista convencional es presentada por Beightler, Phillips y Wilde (1979): “El deseo de perfección del hombre encuentra expresión en la teoría de la optimización. Estudia como se describe y alcanza lo mejor. Una vez que uno sabe como se mide y modifica lo que es bueno o malo. La teoría de la optimización abarca la cantidad de estudio optima y los métodos para encontrarlos.” De este modo la optimización busca mejorar la performance del funcionamiento para algo óptimo punto por punto. Esta definición tiene dos partes: 1.- Buscamos mejora / perfeccionamiento acerca de algo. 2.- Punto optimo. Hay una clara diferencia entre el proceso de perfeccionamiento y su propia optimización. Aun así nos enfocamos comúnmente en la convergencia (¿el método alcanza la optimización?) y se olvida por completo del funcionamiento interino. Este énfasis se origina en los cálculos de optimización. No es, de cualquier modo, un énfasis natural. Considerar una decisión humana artífice de, por ejemplo, un hombre de negocios. ¿Cómo podemos juzgar sus decisiones? Qué criterio usualmente decimos que el ha hecho bien cuando él hace selecciones adecuadas en el tiempo y con los recursos asignados. La bondad es juzgada con relación a su competencia. ¿Produce lo mejor? ¿Lo consigue mas eficientemente?¿Con la mejor promoción? Nunca juzgamos a un hombre de negocios por la cualidad del mejor criterio. La perfección es también la tarea principal. Como resultad concluimos que converger a lo mejor no es una consecuencia en los negocios de la vida, solo estamos preocupados por hacer lo mejor con relación a otros. De este modo si queremos mas herramientas humanas de optimización van en primer lugar a recordad las prioridades de la optimización. La más importante meta de la optimización es el perfeccionamiento. Podemos conseguir rápidamente un nivel de perfeccionamiento satisfactorio (Simon 1969). La cualidad de lo optimo es menos importante que los sistemas complejos. Seria lindo y perfecto, mientras tanto, poder hacer solo lo posible para perfeccionar. En el próximo tópico veremos el algoritmo genético para estas categorías. Aquí resaltaremos algunas diferencias entre los A. G. Y los métodos tradicionales. ¿Porque los algoritmos genéticos difieren de los métodos tradicionales? La regla para que los algoritmos genéticos superen a sus pares tradicionales se diferencian en algunos usos fundamentales. Los algoritmos genéticos son diferentes en cuanto a la búsqueda de procedimientos en cuatro formas: 1.- Los algoritmos genéticos se codifican en los parámetros, no en sí mismos. 2.- Los algoritmos genéticos buscan desde una población de puntos, no desde un solo punto. 3.- Los algoritmos genéticos usan la información a tener en cuenta, (funcion objetivo), no a otro conocimiento auxiliar. 4.- Los algoritmos genéticos usan reglas de transición probabilística, no reglas deterministicas. Los algoritmos genéticos requieren del set de parámetros naturales de optimizacion de problemas a ser codificado como un string de largo finito sobre algun alfabeto finito. Como ejemplo, considérese el problema de optimizacion de la figura 5. Si queremos maximizar la funcion f(x)=x2 en el intervalo de enteros [0, 31]. Con los metodos tradicionales probaríamos girar con el parámetro x, hasta que alcancemos el mayor valor de la funcion objetivo. Con los algoritmos genéticos el primer paso de nuestro proceso de optimizacion es codificar el parámetro x como un string de largo finit. Hay muchas formas de codificar el parámetro x. En el capitulo 3 las veremos con mayor detalle. Por ahora vamos a considerar un problema de optimizacion donde la codificación se realiza mas naturalmente. Considerar como una caja negra el problema ilustrado en la figura 1.6. Este problema conciste en una unidad de caja negra con un banco de cinco llaves cambiantes . Para cada una de estas 5 entradas, hay una señal f de salida, matemáticamente f=f(s), donde s es una configuración particular de las 5 llaves. El objetivo de este problema es setear las entradas para obtener el máximo valor posible de f con otro metodo de optimizacion, podemos trabajar directamente con el set de parámetros entradas desde una configuración a otra usando las reglas de transición de nuestro metodo. Con algoritmos genéticos primero codificamos las entradas con un string de largo finito. Un simple codigo puede ser generado considerando un string de cinco 1s y 0s donde cada una de las 5 entradas es representada por un 1 si esta esta encendida, y por un 0 si esta apagada. Con esta codificación el string 11110 representa las entradas donde las primeras 4estan encendidas y la 5ta esta apagada. Algunas de las codificaciones introducidas luego no seran tan obvias, pero en esta situación admitiremos que los algoritmos genéticos utilizan codificación. En muchos metodos de optimizacion, pasamos desde un solo punto en el espacio de decisión al siguiente usando alguna regla de transición para determinar el siguiente punto. Este metodo punto a punto es peligroso porque es una perfecta receta para ubicar falsos picos en el espacio de búsqueda multimodal (de muchos picos). En contraste, los algoritmos genéticostrabajan desde una base de datos importante de puntos simultaneos escalando muchos picos en paralelo. De este modo la probabilidad de encontrar un pico falso es reducida en relacion a otros metodos que van punto por punto. Por ejemplo consideremos nuestro problema de la caja negra (fig 1.6) Otras técnicas para resolver estos problemas dan opciones para comenzar con una configuración de entradas, aplicar las reglas de transformación, y generar una nueva experiencia con esta configuración de entrada. Un algoritmo genético comienza con una población de strings y luego va generando sucesivas poblaciones. Por ejemplo en una población de 5 entradas, con un comienzo aleatoreo usando sucesivas tiradas de moneda (cabeza 1 cola 0) genera la población iniciadle tamaño n=4 01101 11000 01000 10011 Luego de este inicio sucesivas poblaciones son generadas usando algoritmos genéticos. Trabajando en una población diversa bien adaptada, en lugar de un simple punto, los algoritmos genéticos se adieren al viejo adagio que hay seguridad en los numeros, pronto veremos estos recorridos paralelos contribuyen con las habilidades de los algoritmos genéticos. Muchas técnicas de búsqueda requieren información auxiliar en orden para trabajar apropiadamente. Por ejemplo, la técnica del gradiente necesita derivadas (calculadas analíticamente o numéricamente) en orden para ser capaz de alcanzar la cima correcta y otras búsquedas proceden como la técnica ávida de optimización combinatoria que requiere acceso al mejor, y no a todos, los parámetros tabulados. En contraste los algoritmos genéticos no han necesitado de toda esta información adicional. Los algoritmos genéticos son brillantes. Para ejecutar una búsqueda efectiva para mejorar las estructuras, ellos solo requieren valores de salida (valores de funciones objetivo) asociadas con cadenas individuales. Estas características hacen de un algoritmo genetico un metodo mas canonico (con reglas y preceptos), que muchos esquemas de búsqueda. Después de todo, cada problema de búsqueda tiene una métrica relevante para la búsqueda, de cualquier modo, diferentes problemas de búsqueda tienen diferentes formas de información auxiliar. Solo si nos reusamos a usar esta información auxiliar podemos esperar desarrollar apoyados solo en el esquema base. Por otra parte, el recazo de utilizar conocimiento especifico cuando este existe puede dar lugar a un limite superior sobre el funcionamiento del algoritmo cuando este va cabeza a cabeza con los metodos designados para aquel problema. En el capitulo 5 examinaremos diversas formas de usar información sin valor llamada algoritmos genéticos de conocimiento dirigido. De cualquier modo en esta situación subrayamos la importancia del supuesto de la pureza de las habilidades de los algoritmos genéticos. A diferencia de muchos otros metodos los algoritmos genéticos usan reglas de transición probabilística para guiar sus búsquedas. Con metodos deterministicos esto parece lo mas probable, pero el uso de probabilidad no sugiere que el metodo sea una búsqueda aleatoria simple. Esto no es como la decisión de lanzar una moneda, los algoritmos genéticos usan puntos aleatoris como una herramienta para guiar la búsqueda de asia diferentes regiones en el espacio de búsqueda con mejoras. Deducimos juntos estas cuatro diferencias. Uso directo de una codificación, buqueda de una población, desechar la información auxiliar y aleatorizar operadores. Estos contribuyen a las habilidades de los algoritmos genéticos y resultando ventajoso sobre otras técnicas de búsqueda. En la proxima seccion nos introduciremos en un simple algoritmo genetico de tres operaciones. UN ALGORITMO GENÉTICOS SIMPLE (A SIMPLE GENETIC ALGORITHMS ) La mecánica de un algoritmo genético simple es sorprendentemente sencillo, involucra cero complicación mas que copiar series e intercambiar series parciales. La explicación es que este proceso simple de trabajo es mucho mas apto y poderoso. La simplicidad de operación y potencia de su efecto son dos de las principales atracciones de el advenimiento del algoritmo genético. La sección previa no mostraba como el algoritmo genético procesa la población en series. Recordando el problema de permutación de la caja negra, la población inicial tenía cuatro series: 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 1 También recuerde que esta población se elegía al azar a través de 20 sucesivos lanzamiento imparciales de una moneda. Ahora debemos definir un conjunto de operaciones simples que tomen esta población inicial y generen sucesivas poblaciones que mejoren en el tiempo. Un algoritmo genético simple que produce buen rendimiento en muchos problemas prácticos, esta compuesto por tres operaciones: 1- Reproducción 2- Cruce (croosover) 3- Mutación Reproducción es un proceso en el cual series individuales son reproducidas de acuerdo con su valor de función objetivo. F(los biólogos llaman a esta función, función conveniente [fitness]). Intuitivamente podemos pensar en la función f como alguna medida de beneficio o utilidad que queremos para maximizar. Reproduciendo series de acuerdo a su valor medio conveniente, aquellas series con un alto valor tienen una alta probabilidad de contribución única o mas descendencia en la próxima generación. Este operador, de curso, es una versión artificial de selección natural, a Darwinian survival of the fittest among string creatures. En poblaciones naturales convenientes se determina para una criatura habilidad para sobrevivir a depredadores, pestes y otros obstáculos en adultez y subsiguiente reproducción. En nuestro escenario artificial , la función objetivo es el juez final de la vida o muerte de las series de criaturas. El operador de reproducción puede ser implementado en algoritmo constituido en un número de procedimientos. Quizá el más sencillo es crear una rueda de ruleta donde tome series actuales en la población y asignen un lugar de tamaño proporcionado a su valor conveniente en la rueda de la ruleta. Suponga la muestra poblacional de cuatro series en el problema de la caja negra, el valor de la función conveniente f es mostrada en Tabla 1.1 (por ahora aceptamos estos valores como la salida de algo desconocido y arbitrario de la caja negra - luego examinaremos una función y codificación que generan estos mismos valores). Tabla 1.1 Muestra del problema, series y valores convenientes Nro Serie Fitness % del Total 1 0 1 1 0 1 169 14.4 2 1 1 0 0 0 576 49.2 3 0 1 0 0 0 64 5.5 4 1 0 0 1 1 361 50.9 Total 1170 100.0 Sumando la conveniencia general de las cuatro series, obtenemos un total de 1170. El porcentaje de población total conveniente es también mostrada en la tabla. La correspondiente carga de la rueda de ruleta para esta generación de reproducción es mostrada en la figura 1.7. Para reproducir, simplemente damos vuelta la rueda de la ruleta cargada y así definimos cuatro veces. Para el problema de ejemplo, la serie número 1 tiene un valor conveniente de 169, el cual representa un 14.4% de el total de valores convenientes. Como resultado, la serie 1 da un 14.4 por ciento de la predisposición de la rueda de ruleta., y cada giro ocurre la serie 1 con probabilidad 0.144. Cada vez que requerimos otro descendiente una simple vuelta de la rueda de ruleta cargada producirá la reproducción candidata. En este forma, las series mas adecuadas tienen un alto número de descendientes en acertar la generación. Una vez que una serie ha sido seleccionada para la reproducción, una réplica exacta de la serie es producida. Esta serie es entonces ingresada dentro del cruce combinado [mating pool], una nueva población tentativa, para favorecer la acción del operador genético. 30.9% 14.4% 5.5% 49.2% Figura 1.7 Reproducción simple destina series descendente usando una rueda de ruleta con tamaños de lugares de acuerdo a la conveniencia [fitnnes]. La rueda de muestra es para dimensionar el problema de la tabla 1.1 y 1.2. Después de reproducir, un simple cruce [crossever] (figura 1.8) puede hacerse en dos pasos. Primero, el miembro de la serie reproducida recientemente en el mating pool es cruzada al azar. Segundo, cada par de series experimenta cruce como sigue: una posición entera k junto a la serie es seleccionada uniformemente al azar entre 1 y la longitud de la serie menos uno [1, longitud serie –1]. Dos nuevas series son creadas para intercambiar todos los caracteres entre posición k +1 y l (longitud de la serie) inclusive. Por ejemplo, considere la serie A1 y A2 desde nuestro ejemplo de población inicial. A1 = 0 1 1 0 | 1 A2 = 1 1 0 0 | 0 Suponga elegir un número aleatorio entre 1 y 4, obtenemos a k = 4 ( como indica el símbolo separador | ). El resultado del cruce produce dos nuevas series donde la prime (‘ ) denota que la serie es parte de la nueva generación. A’1 = 0 1 1 0 0 A’2 = 1 1 0 0 1 Figura 1.8 Un esquema de simple cruce muestra la alineación de dos series y el cambio parcial de información, usando un cruce de sitio [croos site] elegido al azar. La mecánica de reproducción y cruce es sorprendentemente simple, involucra generación de números al azar, reproducción de series, y algún intercambio parcial en las series. No obstante, el énfasis por combinar reproducción y la estructura, a través de aleatorización, intercambio de información por cruces[crossover] concede al algoritmo genético mucho de su poder. Al principio parece sorprendente. ¿Como pueden dos operadores tan simples resultar tan útil, y mucho menos, un rápido y robusto método de búsqueda? ¿Además, no parece un poco extraño que el azar debe jugar un rol fundamental en un proceso de búsqueda dirigido? Examinaremos una parcial respuesta a la primera de las dos preguntas en un momento: la respuesta a la segunda pregunta fue bien reconocida por el matemático Hadamard (1949): Veremos un poco mas tarde que la posibilidad de atribuir descubrimientos por pura casualidad es ya excluida. Por el contrario, interviene el azar pero también un trabajo inconsciente, implicando lo último y no contradiciendo lo anterior.....Actualmente, es obvio que inventar o descubrir es en matemática o en cualquier parte falso, toma lugar la combinación de ideas. Hadamard sugiere que aún cuando descubrir no es un resultado- no puede ser un resultado- de puro casualidad, es casi naturalmente guiada para dirigir hallazgo casuales. Además, Hadamard, indica que una correcta interpretación para un evento fortuito en un mecanismo de descubrimiento mas en forma humana es causado por yuxtaposición de diferentes conceptos. Es interesante que los algoritmos genéticos adoptados por Hadamars mezclan dirección y evento fortuito en una manera que eficientemente construye nuevas soluciones desde la mejor solución parcial de pruebas previas. Para ver esto, considere una población de n series (quizá las cuatro series de la población para el problema de la caja negra) sobre alguna propiedad alfabética, codifique de esta manera para que cada idea completa desempeñe una tarea particular ( en este caso, cada serie es una idea completa switch-setting). Subseries dentro de cada serie (idea) contiene varios conceptos de que es importante o relevante para la tarea. Visto en esta forma, la población no contiene exactamente una muestra de n ideas; mas bien, contiene una multitud de conceptos y rankings de estos conceptos para desempeño de tareas. Algoritmo genéticos explota implacablemente esta riqueza de información para (1) reproducir alta calidad de conceptos de acuerdo a su rendimiento y (2) cruzar estos conceptos con muchos otros conceptos de alto rendimiento desde otras series. Así la acción de cruzamiento con reproducciones previas especula sobre nuevas ideas construidas desde el alto desempeño, construyendo bloques (conceptos) de pruebas pasadas. En transición, notamos que a pesar de la definición poco clara de un concepto, no tenemos limitado un concepto para combinaciones lineales simples de características simples o pares de características. Los biólogos tienen hace mucho tiempo reconocido que la evolución se debe a eficientes procesos de epistasis originado en la naturaleza. En una manera similar, el concepto de procesamiento de algoritmo genético se debe efectivamente a procesos de conceptos aún cuando dependen sobre sus características no lineales y formas complejas. Cambiando de conceptos para formar nuevas ideas es apelar intuitivamente, si pensamos en términos de procesos de innovación. ¿Qué es una idea innovadora? Como Hadamard sugiere, con mayor frecuencia es una yuxtaposición de cosas que tiene bien trabajadas en el pasado. En gran medida el mismo camino, reproducción y cruce, combinan para la búsqueda potencialmente nuevas ideas. Esta experiencia de énfasis y cruzamiento es análoga para la interacción humana, muchos de nosotros hemos observado a una exposición profesional o conferencia científica. En una conferencia por ejemplo, varios expertos de todo el mundo se juntan para discutir lo último en tecnología. Después de la sesión de lectura, todos los pares se juntan en un bar para intercambiar historias. Los expertos mas reconocidos del curso son los mas demandados e intercambian ideas, pensamientos y conceptos con sus colegas menos conocidos. Cuado termina la conferencia la gente retorna a sus laboratorios para probar todas las innovaciones recogidas. El proceso de reproducción y cruce en algoritmo genético es esta clase de cambio. Conceptos de alto desempeños son repetidamente probados y cambiados en la búsqueda mejor y mejor rendimiento. Si reproducir conforme a convenientes combinaciones con cruce brinda el algoritmo genético el aumento de su poder de procesamiento, ¿cuál es entonces el propósito de el operador de mutación? No sorprendentemente, hay mucha confusión acerca el papel de la mutación en genética (tanto artificial como natural). Quizá es el resultado de muchas películas detallando la explosión de berenjenas mutantes que consumen cantidades masas de gente de Tokio o Chicago, pero cualquiera sea la causa de la confusión, encontramos que la mutación juega un papel secundario en la operación de algoritmos genéticos. La mutación se necesitó porque aún cuando reproducción y cruce buscan y recombinan conceptos actuales, ocasionalmente pueden perder potencialmente algún material genético útil (unos o ceros en una localización particular). En sistemas genéticos artificiales, el operador de mutación protege contra tales pérdidas irrecuperables. En el algoritmo genético simple, mutación es la ocasional alteración aleatoria de el valor de la posición de una serie. En la codificación binaria del problema de la caja negra, este simplemente cambia un 1 por un 0 y viceversa. Por si mismo , mutación es un andar aleatorio a través del espacio de la serie. Cuando se usa reproducción y cruce con moderación, es una política segura contra pérdida prematura de importantes conceptos. Lo que el operador de mutación juega en el algoritmo genético simple es un papel secundario, simplemente notamos que la frecuencia de mutación para obtener buenos resultados en estudios de algoritmo genéticos empíricos es sobre el orden de una mutación por mil bits (posición) transferido. El índice de mutaciones es similarmente pequeño en poblaciones naturales. Concluimos que mutación es apropiadamente considerada como un mecanismo secundario de adaptación de algoritmo genético. Otros operadores genéticos y esquemas reproductivos han sido abstraído del estudio de ejemplos biológicos. Sin embargo, los tres examinados en esta sección, reproducción, cruce simple [simple crossover] y mutación, han probado ser computacionalmente simples y efectivos en atacar un número de importantes problemas de optimización. En la próxima sección realizaremos una simulación a mano de un algoritmo genético simple para mostrar el mecanismo y la potencia. ALGORITMO GENÉTICOS EN TRABAJO – UNA SIMULACIÓN A MANO (GENETIC ALGORITHMS AT WORK – A SIMULATION BY HAND) Aplicaremos nuestro simple algoritmo genético para un problema particular de optimización paso a paso. Considere el problema de maximizar la función f(x) = x2 , donde x varía entre 0 y 31, función mostrada en la figura 1.5. Para usar un algoritmo genético debemos primero codificar las variables determinadas por nuestro problema como una serie de longitud finita. Para este problema codificaremos la variable x simplemente como un entero positivo binario de longitud 5. Antes que procedamos con la simulación, repasemos brevemente la noción de un número entero binario. Tenemos poco problema en manejar números enteros en base 10. Por ejemplo, el número de 5 dígitos 53.095 puede ser pensado como: 5*104 + 3*103 + 0*102 + 9*101 + 5*100 = 53.095 En aritmética de base 2, esta claro que solo tenemos dos dígitos para trabajar, 0 y 1. Un ejemplo del número 10011 decodificado para un número de base 10 es: 1*24 + 0*23 + 0*22 + 1*21 + 1*20 = 19 Con cinco bits (dígitos binarios) podemos obtener números enteros positivos entre 0 (00000) y 31 (11111). Con una buena definición del objetivo de la función y la codificación, ahora simularemos una simple generación de algoritmo genético con reproducción, cruce [crossover] y mutación. Para comenzar, seleccionamos un población inicial al azar. Seleccionamos una población de tamaño 4 arrojando una moneda común y corriente 20 veces. Podemos saltar este paso usando la población inicial creada en esta forma anteriormente para el problema de permutación de la caja negra [the black box switching problem].Mirando a esta población, mostrada sobre el lado izquierdo de la tabla 1.2, observamos que el decodificado de los valores de x están presentados junto con los valores convenientes [fitness] de f(x) o función objetiva. Para asegurarse que conocemos el valor conveniente de la f(x) hacemos los cálculos desde la serie de representación, tomamos una mirada en la tercer serie de la población inicial, serie 01000. Decodificando esta serie como un número entero positivo binario, notamos que existe un único uno en la posición 23 = 8 . Por lo tanto para la serie 01000 obtenemos x = 8. Para calcular la función objetiva o conveniente simplemente elevamos al cuadrado el valor x y obtenemos el resultado del valor conveniente de f(x) = 64. Los otros valores de x y f(x) pueden ser obtenidos similarmente. Usted puede notar que los valores convenientes o de la función objetiva son los mismos que los valores de la caja negra (compare tabla 1.1 y 1.2). Esto no es coincidencia y el problema de optimización de la caja negra fue bien representado por la función particular f(x) y la codificación que estamos usando ahora. Naturalmente el algoritmo genético necesita no conocer nada de esto, es feliz optimizando algo arbitrariamente permutando funciones (o cualquier otra codificación finita y función para ese asunto) como alguna función polinómica por medio de código binario directo. Esta discusión simplemente refuerza una de las fortalezas del el algoritmo genético: explotando semejanza en codificaciones, el algoritmo genético puede negociar efectivamente con una amplia clase de funciones que pueden gran cantidad de otros procedimientos. Una generación de el algoritmo genético comienza con la reproducción. Seleccionamos el cruce combinado[mating pool] de la próxima generación haciendo girar la rueda de la ruleta (mostrado en figura 1.7) 4 veces. La simulación actual de este proceso usando el lanzado de moneda ha resultado en la serie 1 y 4 recibiendo una reproducción en el mating pool , serie 2 recibiendo dos reproducciones, y serie 3 no recibiendo reproducciones, como mostramos en el centro de la tabla 1.2. Comparando esto con el número esperado de reproducciones (n-pselect) hemos obtenido lo que debíamos esperar: conseguir la mejor reproducción otra vez , el promedio permanece parejo, y lo peor disminuye completamente. TABLA 1.2 UN ALGORITMO GENETICO A MANO Serie Población Valores de x f(x) Pselect Cuenta Cuenta Nro. Inicial enteros fi/Sumatoria f Esperada actual generada positivos x2 fi/f del giro de aleatoriamente la ruleta 1 0 1 1 0 1 13 169 0.14 0.58 1 2 1 1 0 0 0 24 576 0.49 1.97 2 3 0 1 0 0 0 8 64 0.06 0.22 0 4 1 0 0 1 1 19 361 0.31 1.23 1 Sum 1170 1 4 4 Prom 293 0.25 1 1 Max 576 0.49 1.97 2 TABLA 1.2 Mating Pool después de Cruce Crossover Site Reproducción (seleccionado (seleccionado Población Valor F(x) (Cruce de sitio mostrado) aleatoriamente) Aleatoriamente) Nueva X x2 0 1 1 0 1 2 4 0 1 1 0 0 12 144 1 1 0 0 0 1 4 1 1 0 0 1 25 625 1 1 0 0 0 4 2 1 1 0 1 1 27 429 1 0 0 1 1 3 2 1 0 0 0 0 16 256 Sum 1754 Prom 439 Max 729 NOTAS: 1) La población inicial cambia para 4 repeticiones en 5 lanzamiento de monedas donde cabeza = 1 y cola = 0. 2) La reproducción ejecutada en la primera parte acepta 8 simulaciones por selección de giro de la ruleta (tres arrojando moneda). 3) Cruce realizado a través de la decodificación binaria de lanzamiento de moneda (TT = 002 = 0 = cruce de sitio 1. HH = 112 = 3 = cruce de sitio 4). 4) Probabilidad de cruce asumida es la unidad p=1.0. 5) La probabilidad de mutación asumida es 0.001. p= 0.001. Mutación esperada = 5*4*0.001 = 0.02. No hay mutación esperada durante una generación simple. Ninguno simuló. Mediante una activa combinación de series para cruce, se observa por cruce, simples procedimientos de dos pasos: (1) series cruzadas aleatoriamente, usando el lanzado de moneda para arreglar en pares, combinaciones afortunadas, y (2) cruzar series combinadas [mated string couples cross over], usando el lanzado de moneda para seleccionar el cruzamiento de sitios. Refiriéndonos otra vez a la tabla 1.2. elegimos al azar los cruces seleccionados en la segunda serie en el mating pool para ser cruzados con la primera. Con el cruzamiento de los cuatro sitios, las dos series 01101 y 11000 se cruzan y producen dos nuevas series 01100 y 11001. Las dos series restantes en el mating pool son cruzada en 2 sitios, dando como resultado series que pueden ser chequeadas en tal tabla 1.2. El último operador, mutación, es ejecutado sobre una base bits por bits. Asumimos que la probabilidad de mutación en este test es 0.001. Mediante 20 posiciones de bits cedidos debemos aguardar 20*0.001 = 0.02 bits para experimentar mutación durante una determinada generación. La simulación de estos procesos indican que los bits no experimentan mutación para este valor de probabilidad. Como resultado, las posiciones de los bits no son cambiados desde 0 a 1 o viceversa durante esta generación. Subsiguiente a la reproducción, cruce y mutación, la nueva población es preparada para ser testeada. Para esto, decodificamos la nueva serie creada por el algoritmo genético simple y calculamos el valor conveniente de la función desde el valor x decodificado. El resultado de un generación única de la simulación es mostrado en la derecha de la tabla 1.2. Mientras traza conclusiones concretas de una única prueba de un proceso estocástico, en el mejor de los casos, un aventurado negocio, comenzaremos a ver como los algoritmos genéticos combinan la noción de alto rendimiento para lograr mejor desempeño. En la tabla, note como el rendimiento del maximal y el promedio es perfeccionado en la nueva población. El promedio conveniente de la población se ha perfeccionado de 292 a 439 en un generación. El máximo conveniente se ha incrementado de 576 a 729 durante el mismo período. Aunque procesos aleatorios ayudan a causar esta feliz circunstancia, comenzaremos a ver que esta mejora no es un evento fortuito. La mejor serie de la primera generación (11000) recibe dos reproducciones por su punto alto de rendimiento superior. Cuando combinamos esto al azar con la próxima serie mas alta (10011) y es cruzada con la localización 2 (otra vez al azar), uno de los resultado de la serie (11011) prueba ser una muy buena opción por cierto. Este evento es una excelente ilustración de las ideas y nociones analógicas desarrolladas en la sección previa. En este caso, la idea de un buen resultado es la combinación de dos ideas de superior calidad, particularmente la sub serie 11--- and ---11.Aunque el argumento es aún un tanto heurístico, comenzamos a ver como el algoritmo genético lleva a cabo una búsqueda robusta. En la próxima sección, ampliamos nuestro conocimiento de estos conceptos al analizar algoritmos genéticos en términos de esquema o plantillas [template] de similaridad. El punto de vista intuitivo desarrollado de este modo dista mucho de ser atractivo. Tenemos comparaciones de algoritmos genéticos con ciertos procesos de búsqueda humana llamados comúnmente innovadores o creativos. Además, la simulación manual de el algoritmo genético simple nos ha dado alguna confianza que efectivamente estamos en camino de algo interesante. Sin embargo, algo esta faltando. ¿Qué es procesado por el algoritmo genético y como sabemos si el procesamiento (cualquiera sea él) se dirigirá hacia lo óptimo o acercará al resultado óptimo en un problema particular?. Claramente como ingeniero científico y administrador de negocio necesitamos para entender, el que y el como del rendimiento del algoritmo genético. Para obtener este entendimiento, examinaremos los nuevos datos disponibles para cualquier procedimiento de búsqueda y descubrir lo que podemos buscar mas eficientemente si sacamos provecho de similaridades importantes en el código que usamos. Esto nos conduce a desarrollar la importante noción de plantilla [template] de similaridad [similarity template] o esquema. Esto a su vez nos dirige hacia la construcción de bloque de hipótesis. Grist for the search mill – important similarities Nosotros hemos ignorado por mucho tiempo una pregunta fundamental. Dentro de un proceso de búsqueda dado solamente datos payoff (valores de aptitud). ¿qué información esta contenida dentro de una población de cadenas y sus valores de la función objetivo para ayudar a una búsqueda dirigida para la mejora? . para preguntar está pregunta más claramente considere las cadenas y sus valores de aptitud originalmente dibujados en la tabla 1.1 la sección previa a la simulación (el problema de la caja negra) y recogido abajo por conveniencia:. String Fitness(aptitud) 01101 169 11000 576 01000 64 10011 361 ¿Qué información esta contenida en esta población para guiar una búsqueda dirigida para la mejora?.sobre esta face. No hay mucho más que cuatro ejemplos independientes de diferentes cadenas con sus valores fitness. Cuando nosotros miramos fijamente la página. Sin embargo realmente naturalmente nosotros empezamos un escaneo de arriba y abajo de las columanas de las cadenas. Y notamos ciertas similitudes entre las cadenas. Explorando estas similitudes en más profundidad. Notamos que ciertos patrones de cadenas parecen altamente asociados con un buen desempeño. Si nosotros miramos fijamente a las cadenas más largas y sus valores de aptitud, la mejor prueba es experimentar con estos asociaciones altas de aptitudes. Parece perfectamente razonable jugar mezclando y comparando con algunos de las subcadenas que estan altamente correlacionadas con un suceso pasado. Por ejemplo en la muestra de la población las cadenas empiezan con un 1 parece ser entre las mejores. Podría ser este un importante ingrediente dentro de esta función de optimización. Ciertamente con nuestra función (f(x)=x2 ) y nuestro codigo (el quinto bit entero sin signo) nosotros sabemos que esto es (¿Por qué esto es verdad). Pero ¿Qué estamos haciendo?. Realmente separamos dos cosas. Primero estamos buscando similitudes entre las cadenas de la población. Segundo estamos buscando las similitudes causales entre las cadenas de la población y aptitudes altas. Haciendo así admitimos una riqueza de nueva información para ayudar una búsqueda guiada. Para ver cuanto y precisamente que información admitimos, consideremos los conceptos importantes de un esquema (pluralidad, schemata) o plantillas de similitud. SIMILARITY TEMPLATES (SCHEMATA) En algún sentido nosotros no estamos interesados en las cadenas más largas como cadenas solitarias. Puesto que la importancia de similitudes entre cadenas propone favorablemente poder ayudar a una búsqueda guiada. Preguntamos como una cadena puede ser similar a su cadena compañero. Especificamente preguntamos, ¿De qué manera es una cadena representativa de otra clases de cadenas con similitudes en ciertas posiciones de las cadena?. El framework de schemadata provee las herramientas para responder estas preguntas. Un esquema (Holland, 1968,1975) es similar a una plantilla que descirbe subconjuntos de cadenas con similitudes en ciertas posiciones de la cadena. Para esta discusión permitanos una vez limitar sin perdida de la generalidad al alfabeto binario{0,1}. Para ser un esquema mucho más fácil agregamos un símbolo especial a este alfabeto; agregamos un * o no care simbolo. Con este alfabeto extendido podemos crear cadenas (schemata) sobre un alfabeto terneraio {0,1,*} y el significado del esquema esta claro si nosotros pensamos en el como un modelo de patron de emparejado de dispositivos: Un esquema empareja una cadena en particular si cada localización dentro del esquema un 1 empareja con un 1 en la cadena, un 0 empareja a un 0, un * empareja a cualquiera de los dos. Como un ejemplo, considere las cadenas y schemata de longitud 5. El schemata *0000 empareja dos cadenas {10000,00000}. Otro ejemplo, el esquema *111* describe un subconjunto con cuatro miembros {01110,01111,11110,11111}. Como último ejemplo el esquema 0*1** empareja cualquiera de las ocho cadenas de longitud 5 que empiezen con 0 y tengan un 1 en la tercera posición. Com usted puede ver, la idea de un esquema nos da una poderosa y compacta manera de hablar acerca de todos las similitudes bien difinidas entre cadenas de longitud finita sobre un alfabeto finito. Deberiamos enfatizar que * es solamente un meta símbolo (un símbolo acerca de otros símbolos); el nunca es procesado explicitamente por un algoritmo genetico. Es simplemente un dispositivo notacional que permite la discripción de todas las posibles similitudes entre las cadenas de una longitud particular y alfabetica. Contando el total de numeros posibles schemata en un ejercicio de ilustración. El ejemplo previo, con l =5, notamos que hay 3.3.3.3.3=35=243 diferentes plantillas similares porque cada una de las cinco posiciones puede ser 0,1 o*. En general, para la cardinalidad alfabetica (número de caracteres alfabeticos) k, hay (k+1)l schemata. A primera vista, parece que los schemata hacen la búsqueda más dificultosa. Para un alfabeto con k elementos hay solamente (¿solamente?) kl diferentes cadenas de longitud l. ¿Por qué considera que el schemata (k+1)l agranda el espacio de interes?.Poniendo de otra manera el ejemplo de longitud 5 ahora sólo tiene 25= 32 diferentes alternativas de cadenas. ¿Qué hace más dificil cunado se considera 35=243 schemata?. De hecho el razonamiento hecho en la sección previa hace las cosas más faciles. Usted recuerda de arriba y abajo la lista de las cuatro cadenas y los valores fitness, ¿intentando deducir que hacer luego?. Nosotros reconocimos que si consideramos las cadenas separadamente, entonces solamente teniamos cuatro piezas de información; sin embargo, cuando nosotros consideramos las cadenas, sus valores fitness y las similitudes entre las cadenas en la población. Admitimos una riqueza nueva de información para ayudar en una búsqueda directa. ¿cuánta información admitimos para considerar las imilitudes?. La respuesta a esta pregunta esta relacionado al número de unicos schemata contenidos en la población. Contar exactamente esta cantidad requiere conocimiento de las cadenas en una población en particular, primero contamos el número de schemata contenidos en una cadena individual y entonces conseguimos un límite superior superior en el número total de schemata en la población. Para ver esto considere una unica cadena de longitud 5: 11111, por ejemplo. Esta cadena es un miembro de 25 schemata porque es el valor real que puede asumir en cada posición o un no care símbolo. En general una cadena en particular contiene 2l y n.2l schemata. Como resultado, una población de tamaño n contiene algo entre 2l y n.2l schemata, dependiendo de la diversidad de la población. Este hecho verifica nuestra temprana intuición. El motivo original para considerar importante las similitudes fue conseguir más información para ayudar en una búsqueda guiada. Contando muestras de argumento que dan información acerca de la importancia de las similitudes como un premio, por cierto contenidas en cada tamaño de población moderadamente.examinaremos ahora los algoritmos geneticos explotando efectivamente esta información. En esta coyuntura, algunos procesos en paralelo parecen ser necesitados si estamos haciendo uso de toda esta información en una oportuna manera. Más significativamente, del 2l a n.2l schemata contenido en una población, ¿cuántos son procesados realmente de manera util para el algoritmo genetico?. Para obtener la respuesta a esta pregunta, consideremos los efectos de la reproducción, entrecruzamiento y mutación sobre el crecimiento o decrecimeinto de importancia en los schemata de una generación a otra generación. Los efectos de reproducción en un esquema particular es facíl determinarlo; subsecuentemente son más favorecidos las cadenas que tienen una probabilidad de selección por encima del promedio, damos un número creciente de ejemplos de las mejoras de los patrones de similitud (esto es bueno hacerlo, como se muestra en el siguiente capítulo); sin embargo la reproducción de una sólo ejemplo no da ningun nuevo punto en el espacio.¿qué sucede entonces a un schema particular cunado el entrecruzamiento es introducido?. El entrecruzamiento deja un esquema ileso si no corta el esquema, pero el puede romper un esquema. ¿cuándo lo hace?: por ejemplo, considere los dos schemata 1***0 y **11*. El primero probablemente será roto por el entrecruzamiento, considerando que el segundo es relativamente improbable que sea destruido. Como resultado, un schemata definido con longitud corta son exclusivamente para entrecruzamiento y es reproducido en una buena proporción probando operadores de reproducción. Mutación en general, las bajas proporciones no rompen un esquema particular muy frecuentemente y salimos con una conclusión sorprendente. Favorablemente, las cortas definiciones de longitud de los schemata (los llamaremos building blocks) y son propagados de generación a generación dando exponencialmente las mejores muestras crecientes en los mejores observados; todo esto entra en paralelo sin una especial bookkeeping o memoria especial en nuestra población de n cadenas. En el siguiente capítulo contaremos cuantos schemata se procesan utilmente en cada generación. Resulta que el número es algo como n3. esto compara favorablemente con el numero de evaluaciones de la función (n). Proque esta influencia del proceso es tan importante (y aparentemente unico en los algoritmos geneticos), les damos un nombre especial, implicit parallelism (paralelismo implicito). APRENDIENDO EL IDIOMA El poder detrás de las simples operaciones de nuestros GA (algoritmos genéticos) es al menos intuitivamente más clara si pensamos en componentes. Quedan algunas preguntas: ¿Cómo sabemos qué componentes nos llevan a una mejora? ¿Por qué es una óptima y cercana estrategia el brindar muestras que se incrementan exponencialmente hacia lo mejor? ¿Cómo podemos calcular el Nº de esquemas provechosamente procesados por el GA? Estas preguntas son respondidas totalmente en el próximo capítulo, pero primero necesitamos apropiarnos de la terminología usada por los investigadores que trabajan con GA. Como los GA están arraigados tanto en la genética natural como en la ciencia de computación , la terminología usada en la literatura de los GA es una mezcla no deseada de lo natural y lo artificial. Hasta ahora, nos focalizamos del lado artificial del linaje de los GA y hablamos sobre cadenas, alfabetos, posiciones en las cadenas, etc. Nosotros revisamos la correspondencia entre esos términos y sus contrapartidas naturales para conectarnos con la creciente literatura sobre GA y permitirnos ocasionales deslices de las expresiones naturales. Vulgarmente hablando, las cadenas de los sistemas genéticos artificiales son análogos a los cromosomas en los sistemas biológicos. En los sistemas naturales, uno o más cromosomas se combinan para formar la prescripción genética total [¿mapa genético?] para la construcción y operación de algún organismo. En los sistemas naturales el paquete genético total es llamado el “genotipo”. En los sistemas genéticos artificiales, el paquete total de cadenas es llamado estructura (en los primeros capítulos del libro la estructura consistirá en una simple cadena; así el texto se refiere a cadenas y estructuras en forma indistinta hasta que sea necesario diferenciarlas). En los sistemas naturales, el organismo formado por la interacción del paquete genético total con su entorno es llamado “fenotipo”. En los sistemas genéticos artificiales, las estructuras se decodifican para formar un particular conjunto de parámetros, una solución alternativa o un punto (en el espacio solución). El diseñador de un sistema genético artificial tiene una variedad de alternativas para codificar parámetros numéricos y no numéricos. Nosotros confrontaremos codificaciones y principios de codificación en capítulos posteriores; por ahora, nos remitimos a nuestra consideración de GA y terminología natural. En la terminología natural, decimos que los cromosomas están compuestos por “genes”, los cuales pueden tomar cierto número de valores llamados “alelos”. En la genética, la posición de un gen (su “locus”)[en castellano también se llama locus] se identifica en forma separada de su función genética. Así, podemos hablar de un gen particular, por ejemplo el gen del color de ojos de un animal. Su locus es la posición 10, y el valor de su alelo es: ojos azules. En la búsqueda genética artificial decimos que las cadenas están formadas por características o indicadores, los cuales toman diferentes valores. Las características pueden ser ubicadas en diferentes posiciones en la cadena. La correspondencia entre la terminología natural y artificial está resumida en la Tabla 1.3. TABLA 1.3 Comparación entre la terminología natural y la de GA NATURAL GA cromosoma cadena gen característica, caracter o indicador alelo valor de la característica locus posición en la cadena genotipo estructura fenotipo conjunto de parámetros, solución alternativa, una estructura decodificada epistasis no-linealidad Entonces, no hemos distinguido entre un gen (un caracter particular) y su locus ( su posición); la posición de un bit en una cadena ha determinado su significado (como se decodifica) uniformemente a través de toda la población y a través del tiempo. Por ejemplo la cadena binaria 10000 se decodifica como el entero sin signo 16 (en base 10) porque implícitamente el 1 está en el 16º lugar. No es necesario limitar las codificaciones así. Un capítulo posterior presenta estructuras más avanzadas para tratar locus y genes en forma separada. SUMARIO Este capítulo ha sentado la base para entender los GA, su mecánica y su poder. Nos dirigimos a estos métodos por nuestra búsqueda de robustez: los sistemas naturales son robustos – eficientes y eficaces – ya que se adaptan a una amplia variedad de entornos. Esperamos lograr un rendimiento similar por medio de la abstracción del algoritmo de selección natural. De hecho, los GA han demostrado su capacidad en un Nº de estudios analíticos y empíricos. El capítulo ha presentado la mecánica detallada de un simple GA de tres operadores. Los GA operan en poblaciones de cadenas, con las cadenas decodificadas para representar algún conjunto de parámetros destacados. Reproducción, entrecruzamiento y mutación son aplicados a sucesivas poblaciones de cadenas para crear nuevas poblaciones de cadenas. Esos operadores son simples en sí mismos, y no involucran nada más complejo que la generación de números aleatorios, la copia de cadenas, e intercambio parcial de cadenas; aun, a pesar de su simplicidad, la búsqueda del rendimiento es extremadamente variada e impresionante. Los GA realizan un intercambio innovador entre cadenas y así se conectan a nuestras ideas sobre el descubrimiento o la búsqueda humanos. La simulación de una generación del simple GA ha ayudado a ilustrar ambos detalles y el poder del método. Cuatro diferencias separan GA de otras técnicas convencionales de optimización: 1. Manipulación directa de una codificación. 2. Búsqueda a partir de una población, no de un simple punto. 3. Búsqueda a través de muestras, una búsqueda ciega. 4. Búsqueda usando operadores estocásticos, no reglas determinísticas. Los GA manipulan decisiones o controlan representaciones variables a nivel de cadenas para explotar similaridades a través de cadenas de alto rendimiento. Otros métodos usualmente tratan con funciones y controlan variables directamente. Como los GA operan a nivel de codificación, son difíciles de [fool even] cuando la función puede ser difícil para los esquemas tradicionales. Los GA trabajan a partir de una población; muchos otros métodos trabajan a partir de un simple punto. De esta forma, GA encuentran seguridad en los números. Manteniendo una población de puntos de muestra bien adaptados, la probabilidad de alcanzar un falso pico es reducida. GA logran la mayor parte de su desempeño ignorando información, excepto la concerniente al [payoff]. Otros métodos confían fuertemente en esa información, y en problemas donde la información necesaria no está disponible o es difícil de obtener, esas otras técnicas se quiebran. GA se mantienen generales, explotando información disponible en cualquier clase de problema. GA procesan similaridades en la codificación destacada, junto con un ranking de información de las estructuras, de acuerdo con su capacidad de supervivencia en el entorno actual. Explotando información ampliamente disponible, los GA pueden ser aplicados en virtualmente cualquier problema. Las reglas de transición de los GA son estocásticas; muchos otros métodos tienen reglas de transición determinísticas. Existe una diferencia, sin embargo, entre los operadores randomizados de los GA y otros métodos que son simples caminos aleatorios. Los GA usan elecciones aleatorias para guiar una búsqueda altamente explosiva [exploitative]. Esto puede parecer inusual, usar el azar para obtener resultados directos (los mejores puntos), pero la naturaleza está llena de precedentes. Hemos comenzado una valorización más rigurosa sobre el rendimiento de los GA a través del concepto de esquema o patrón de similaridad. Un esquema es una cadena sobre un alfabeto extendido {0,1,*} donde el 0 y el 1 mantienen su significado normal, y el * es un comodín [wild card] o un símbolo sin sentido. Esta notación simplifica el análisis del método de GA porque explícitamente reconoce todas las posibles similaridades en una población de cadenas. Hemos discutido como los componentes – pequeños, esquemas de gran desempeño – se combinan para formar cadenas con un desempeño esperado superior. Esto ocurre porque hay una óptima tasa de muestreo de los componentes, y éstos son recombinados mediante entrecruzamiento. La mutación tiene un pequeño efecto sobre esos componentes; como una política segura, ayuda a prevenir las pérdidas irrecuperables de material genético potencialmente importante. El simple GA estudiado en este capítulo tiene mucho que recomendar. En el próximo capítulo, analizaremos sus operaciones más cuidadosamente. Después de esto, implementaremos el simple GA en un corto programa de computadora y examinaremos algunas aplicaciones en problemas prácticos. Problemas 1.1. Considerar una caja negra conteniendo interruptores [switches] de ocho posiciones múltiples. El interruptor 1 y el 2 pueden setear (establecer) en cualquiera de las 16 posiciones. Los interruptores 3, 4, y 5 son cuatro las posiciones de swicheo, y los interruptores 6 a 8 sólo tienen dos posiciones. Calculé el número de configuraciones únicas posibles para este dispositivo de caja negra 1.2. Para el dispositivo de caja negra del problema 1.1, diseñe una codificación de cadena natural que use ocho posiciones, una posición para cada switch. Cuente el número de swich configurados representado por su código y cuente el número de esquemas o modelos similares en su codificación. 1.3. Para el dispositivo de caja negra del problema 1.1 diseñar un mínimo código binario para los ocho interruptores o switches y comparar el número de esquemas en esta codificación con el del problema 1.2. 1.4. Considerar una cadena binaria de longitud 11, y considerar un esquema, 1*********1. Bajo un cruce con la selección de un lugar con un cruce uniforme, calcule el límite inferior de la probabilidad de este esquema de cruce de supervivencia. Calcule la probabilidad de supervivencia bajo el misma suposición del esquema siguiente: ****10*****, 11*********, ***111*****, ****1*0****, **1***1**0*. 1.5. Si la distancia entre el alelo exterior de un esquema particular es llamado definiendo longitud (largo, extensión) δ, derivar una expresión aproximada para la probabilidad de supervivencia de un esquema particular de una longitud total l y definiendo longitud δ mediante la operación de simple cruce. 1.6. Seis cadenas tienen los siguientes valores de función de adaptabilidad (aptitud, habilidad, desenvoltura): 5, 15, 25, 50, 100. Mediante la selección del giro de una ruleta, calcular el número esperado de copias de cada cadena en el aparejamiento de igualdades si una constante de tamaño poblacional, n = 6, es mantenida. 1.7. En lugar de usar una la selección del giro de una ruleta durante la reproducción, suponga que nosotros definimos una copia de un contador para cada cadena, ncounti como el siguiente: ncounti = fi/f donde fi es la adaptabilidad de la iava cadena y f es la distribución de adaptabilidad de la población. La copia del contador es entonces usada para generar el número de miembros del aparejamiento de macheos dando la parte entera de ncounti copias del string iavo y una copia adicional con probabilidad igual a la parte fraccional de ncounti. Por ejemplo, con fi = 100 y f = 80, la cadena i necesitara recibir un ncounti de 1.25, y de esta forma necesitara recibir una copia con probabilidad 1.0 y otra copia con probabilidad 0.25. Usando el valor de la cadena de adaptabilidad en el problema 1.6, calcular el número esperado de copias para cada una de las seis cadenas. Calcular el número total de cadenas esperadas en el grupo de genes bajo esta forma de reproducción. 1.8. La forma de reproducción discutida en el problema 1.7 es algunas veces llamada reproducción con un número de control esperado. En una prueba corta, explicar (exponer), el motivo por el cual esto es así. ¿En que direcciones está el giro de la ruleta de selección y el número esperado similar de control? ¿En que direcciones diferentes están ellas? 1.9. Suponga que la probabilidad de una mutación en un simple bit de posición es 0.1. Calcular la probabilidad de una cadena de 10 bit sobreviviendo a mutaciones sin cambios. Calcular la probabilidad de una cadena de 20 bit sobreviviendo sin cambios. Recalcule la probabilidad de supervivencia para ambos cadenas de 10 y 20 bit cuando la probabilidad de mutación es de 0.01. 1.10. Considere la cadena y un esquema de longitud 11. Por ejemplo para el siguiente esquema, calcule la probabilidad de mutación sobrevivir si la probabilidad de mutación es 0.1 en una posición simple de bits: ***1**0****, 1*********0, ***111*****, *1000010*11. Recalcular la probabilidad de supervivencia para una probabilidad de mutación p = 0.01. Computadora asignadora: A. Una de las funciones primitivas requeridas al hacer el algoritmo genético sobre una computadora es la capacidad de generar números seudo-aleatorios. Los números son seudo-aleatorios porque como von Neumann una vez dijo “Cualquiera que considere los métodos aritméticos de producción aleatoria de dígitos esta, por supuesto, en un estado de pecado” Como parte de esta tarea (creación, confección, cometido trabajo, tarea, asignación), vamos en adelante, con algunos pecados más. Usar el generador de números aleatorios dado en el apéndice B, cree un programa donde usted genere 1000 números aleatorios entre 0 y 1. Mantener un registro de cuantos números son generados en cada uno de los cuatro cuartiles, 0 0.25, 0.25 – 0.5, 0.5 – 0.75, 0.75 – 1.0, y comparar el contador actual con el número esperado. ¿Está la diferencia dentro de un límite razonable? ¿Cómo puede usted cuantificar si la diferencia es razonable? B. Suponga usted que tiene 10 cadenas con las siguientes probabilidades de selección en la próxima generación: 0.1, 0.2, 0.05, 0.15, 0.0, 0.11, 0.07, 0.04, 0.00, 0.12, 0.16. Determinado eso estas son la única alternativa posible, calcule si las probabilidades son consistentes. Escriba un programa de computadora que simule la selección del giro de una ruleta para estas 10 cadenas. Girar la rueda 1000 veces y mantenga un registro del número de selecciones / elecciones, para cada cadena, comparando este número con el número esperado de selecciones. C. Escriba una función que genere un número entero seudo – aleatorio entre algún límite inferior especificado y algún límite superior especificado. Pruebe el programa para generar 1000 números entre 3 y 12. Mantenga un registro de la cantidad de cada número seleccionado y compare esta cifra con la cantidad esperada. D. Crear un procedimiento que reciba dos cadenas binarias y el valor del cruce de un lugar, ejecutar el cruce simple, y retornar dos cadenas descendientes. Probar el programa por el cruce con la siguientes cadenas de longitud 10: 1011101011, 0000110100. Intentando el cruce de los valores de sitio -3, 1, 6 y 20. E. Crear una función mutación que complemente un valor de bit particular con la probabilidad de mutación especificada pm = 0.001, 0.01, 0.1. Compare el número de mutaciones realizado con el número esperado. F. Usando el operador de cruce simple de asignación D, repetidamente aplicar el operador de cruce a las cadenas contenidas dentro de la siguiente población de tamaño n = 200 y l = 5: 100 copias de 11100 100 copias de 00011 Ejecutar cruzar (pc = 1.0) para 50 generaciones sin la sustitución, mediante la no selección. Compare la distribución inicial y final de las cadenas. También compare la cantidad esperada de cada cadena al haberse dado cuenta la cantidad en 50 generaciones. ALGORITMOS GENÉTICOS SEGUNDA PARTE: FUNDAMENTACIÓN MATEMÁTICA El amplio pasaje del capítulo 1 pinto una exacta, si un poco cruda, descripción de los algoritmos genéticos y su mecánica y poder. Quizá este pasaje trazo un interés a su propio sentimiento de descubrimiento humano y búsqueda. Esto de alguna manera es común sin embargo el procedimiento de aleatorizar puede conseguir algún tipo de variedad y don intuitivo de consulta humana, al parecer casi igualmente aceptable de verdad. De tal manera este procedimiento de descubrimiento debería reflejar el proceso natural que fabricada la especie contenida el procedimiento es una recursión del que Godel, Escher, o Bach (Hofstadter, 1979) puede cada uno gozar de orgullo. A pesar de su intuitivo interés, y pese a su simetría, es crucial que nosotros volvamos de esta imprecisa sensación y especulación, acerca de utilizar desapasionados algoritmos genéticos, y hecho matemático. Actualmente, nosotros tenemos ya el comienzo de una más rigurosa evaluación de algoritmos genéticos Gas. Hacia el final del último capítulo, el concepto fundamental de un esquema o modelo de similitud ya ha sido introducido. Cuantitativamente, nosotros encontramos que hay de hecho un largo número de similaridades por explorar en una población de cadenas. Intuitivamente, nosotros comprendemos como los algoritmos genéticos exploran en paralelo las muchas similaridades contenidas en una fase o pequeño, esquema de alta performance (rendimiento, prestación). En este capítulo, nosotros haremos estas observaciones más rigurosas por hacer la cosa severa. Primero, nosotros contamos el esquema representado dentro de una población de cadenas y considerar (tratar, tener presente, tener en cuenta) que aumenta de tamaño y que se deteriora durante cualquier generación dada. Para hacer esto, nosotros consideramos el efecto de reproducción, cruce, y mutación de un esquema particular. Este análisis lleva al teorema fundamental de los algoritmos genéticos el que cuantifica este crecimiento (aumento, expansión) y el radio de deterioro más precisamente; también puntos en formato matemático de este crecimiento. Esta conectado formalmente a un importante y clásico problema de decisión teórica, el problema armado con dos bandidos (y esta extensión, el k bandido armado). El parecido matemático entre la solución óptima (mínima pérdida) para el de dos armados y bandido k armado y la ecuación que describe el número de prueba dado sucesivo de generación de esquema en el simple algoritmo genético es notable. Contando el número de esquema que son últimamente procesados por el algoritmo genético revela tremenda influencia en la fase en proceso. Finalmente, nosotros consideramos una importante cuestión: ¿Cómo hacemos nosotros conociendo esa combinación de fase una ventaja de alta performance en problemas arbitrarios? La pregunta da comienzo a consideración nuestra de alguna relativamente nueva herramienta de análisis de algoritmos genéticos: transformar esquema y problema de engaño ínfimo. Cuando debe vivir y cuándo morir? El teorema fundamental la operación de los algoritmos genéticos es notablemente clara. después de todo, se inicializa con una población aleatoria de n strings, copia los strings con alguna parcialidad, cruza y parcialmente transfiere substrings, y muta el valor de un bit en forma ocasional para un mejoramiento. Sin embargo igualmente los algoritmos genéticos directamente manipula una población de strings en esta forma precisa, en el capitulo 1 iniciábamos el reconocimiento que esta procesando los strings es la verdadera del procesamiento implícito de algunos esquemas durante cada generación. Para analizar el progreso y el decaimiento de algunos de los esquemas contenidos en la población, nosotros necesitamos una notación simple y sumar rigor a la discusión. Consideraremos a la operación de reproducción, cruza y mutación en el esquema de datos contenidos en la población. Consideraremos strings, sin perdida de generalidad, para ser construido en el alfabeto binario. Es una notación conveniente, nos referimos a strings por la letra mayúscula y los caracteres individuales por la minúscula que estará con la posición del bit como subíndice. Por ejemplo, el string de 7 elementos A=0111000 puede ser representado simbólicamente de la siguiente manera: A=a1,a2,a3,a4,a5,a6,a7 Aquí cada uno de los valores de ai representa una característica simple o un indicador ( en concordancia con la naturaleza, llamamos gen ai), donde cada característica puede tomar los valores 0 o 1( llamaremos los valores de ai como aletas). En el st4ing 0111000 a1 es 0, a2 es 1, a3 es 1, etc. Esto es también posible si tenemos que los indicadores no estén en orden en el string A. El capitulo posterior explora el efecto de extender la representación para permitir rasgos para ser acomodados en una manera independiente para su función. Por ahora, asumimos que una función de rasgo puede ser determinada por su posición. Una búsqueda genética significativa requiere una población de strings, y consideraremos una población de strings individuales Ar j=1,2,.....,n, contenida en la población A(t) a veces (o generación) t cuando la letra en negrita es usada para denotar una población. Además de la notacion para describir poblaciones, strings, posiciones de bits y alelos, necesitaremos una notación conveniente para describir el esquema de datos contenidos individualmente en los strings y poblaciones. Nosotros consideraremos un esquema H tomado a partir de tres letras del alfabeto V+ = {0,1,*}. Como discusión en el capitulo anterior, el símbolo adicional asterisco, no importa o es tomado como comodín que puede tomar los valores 0 o 1 en una posición particular. Por ejemplo, consideremos el esquema de largo 7 H=*11*0**. Nótese que el string A=0111000 ponemos en tela de discusión so s un ejemplo del esquema H, porque los alelos ai corresponden a las pisicones del esquema b1 quedan fijos en las posiciones 2, 3 y 5. A partir de los resultados del siguiente capitulo, recordamos que allí hay___ esquemas de datos o similaridades definidas sobre un strings de binarios de largo l, en general, para alfabetos de cardinalidad k tendremos (k+1)^t esquemas de datos. Además, recordemos que en una población el string contiene n miembros con como máximo n-2^t esquemas de datos contenidos en la población porque cada string es en si mismo una representación de 2^t esquema de datos. No todos los esquemas de datos son creados igual. Algunos aún mas específicos que otros. Por ejemplo, el esquema 011*1** es una definición más cercana e importante que el esquema 0******. Además, un esquema definitivo abarca el total del largo del string y otros. Por ejemplo, el esquema 1****1* abarca una porción del string que tiene el esquema 1*1****. Para cuantificar estas ideas, introduciremos dos propiedades de esquemas: esquema ordenado y de largo definido. El orden de un esquema H, denotado por o(H), es solamente el numero de posiciones fijas presentes en la plantilla. En el ejemplo citado anteriormente, el orden del esquema 011*1** es 4, el orden de un esquema 1****** es 1. El largo definido por un esquema H, esta denotado por delta(H), es la distancia entre el primero y el ultimo string en una posición especifica. Por ejemplo en el esquema 011*1** el largo definido es 4 ya que el primer posición ocupada es la 1 y la ultima es la 5. En el otro ejemplo el lardo definido es 0. El esquema de datos y sus propiedades son interesantes para la discusión rigurosa y clasificar strings similares. Mas que eso, ellos proveen el método básico para analizar el efecto en la red de reproducción y operadores genéticos en bloques construidos que contienen la población. el efecto de la reproducción en el numero esperado de esquemas de datos en la población es fácil de determinar,, supongamos que un determinado tiempo t existen m ejemplos de un particular esquema H contenido con la población A(t) donde escribiremos m = m(H,t) ( esto es posible para diferentes cantidades de diferentes esque