Los objetos del algoritmo genético determinan qué individuos deberían vivir, cuáles deberían reproducirse y cuáles deberían morir. También registra estadísticas y decide cuánto tiempo debe durar la evolución. En general, los algoritmos genéticos no tienen criterios obvios para detener el ping. Tienes que decirle al algoritmo cuándo detenerse. Normalmente, el número de generaciones se utiliza como medida de parada, pero si lo prefiere, puede utilizar la bondad de la mejor solución, la convergencia de la población o cualquier criterio específico del problema.
Esta biblioteca contiene cuatro tipos de algoritmos genéticos. El primero es el algoritmo genético simple estándar, descrito por Goldberg en su libro. El algoritmo utiliza poblaciones que no se superponen y una estrategia elitista opcional. Cada generación del algoritmo produce una población de individuos completamente nueva. El segundo es un algoritmo genético de estado estacionario que utiliza poblaciones superpuestas. En esta variante se puede especificar qué parte de la población debe ser reemplazada en cada generación. Una tercera variación es el algoritmo genético incremental, en el que cada generación consta de sólo uno o dos hijos. Los algoritmos genéticos incrementales permiten métodos de reemplazo personalizados para definir cómo se deben integrar las nuevas generaciones en la población. Así, por ejemplo, una descendencia recién generada puede reemplazar a su progenitor, reemplazar a un individuo aleatorio en la población o reemplazar al individuo al que es más similar. El cuarto es el algoritmo genético "alemán-estadounidense". Este algoritmo utiliza un algoritmo de estado estacionario para hacer evolucionar múltiples poblaciones en paralelo. Cada algoritmo de generación mueve algunos individuos de cada población a otra población.
Además de los tipos integrados básicos, GA lib también define los componentes necesarios para derivar sus propias clases de algoritmo genético. Estos ejemplos incluyen varios de estos derivados, incluido (654^38 0) un algoritmo genético que utiliza múltiples poblaciones y "migración" entre poblaciones en múltiples CPU, y (2) un algoritmo genético que realiza un "apiñamiento determinista". Algoritmos genéticos para preservar diferentes especies durante la evolución.
La clase de algoritmo genético básico contiene operadores y datos comunes a la mayoría de los algoritmos genéticos. Cuando deriva su propio algoritmo genético, puede utilizar estos datos y funciones de miembros para realizar un seguimiento de las estadísticas y monitorear el rendimiento.
Un algoritmo genético contiene estadísticas, estrategias de reemplazo y parámetros para ejecutar el algoritmo. El objeto de población es un contenedor para el genoma y también contiene algunas estadísticas, así como operadores de selección y escalado. Un algoritmo genético típico funcionará para siempre. La biblioteca tiene funciones integradas para especificar cuándo termina el algoritmo. Estos incluyen la terminación en generación (en cuyo caso puede especificar un número específico de generaciones que debe ejecutar el algoritmo) y la terminación en convergencia (en cuyo caso puede especificar el valor al que debe converger la mejor puntuación generacional). Puede personalizar la función de terminación para utilizar sus propios criterios de detención.
El número de veces que se evalúa una función es una buena manera de comparar diferentes algoritmos genéticos con otros métodos de búsqueda. El algoritmo genético GA lib rastrea el número de evaluaciones del genoma y de la población.
Defina representación
Utilice una estructura de datos adecuada a su problema. Si está optimizando una función numérica, utilice números reales en su genoma. Si la solución a su problema puede representarse mediante algunos números imaginarios y algunos valores enteros, defina un genoma con estas características.
Definir una representación apropiada es parte del arte de utilizar algoritmos genéticos (a estas alturas, sigue siendo un arte, no una ciencia). Utilice una de las expresiones más simples pero completamente expresivas. Su representación debe poder representar cualquier solución a su problema, pero si es posible, debe diseñarla de manera que no represente una solución inviable a su problema. Recuerde, si el genoma puede representar soluciones inviables, entonces la función objetivo debe diseñarse para dar crédito a las partes inviables.
La representación no debe contener información distinta a la requerida para representar la solución del problema. Aunque puede haber ventajas al utilizar una representación que contenga material genético "extra", a menos que se implemente apropiadamente (consistente con la función objetivo y con plena consideración del tipo y las características del espacio de búsqueda), esto tiende a aumentar el tamaño de la búsqueda. espacio, lo que dificulta el uso de algoritmos genéticos.
Existen innumerables expresiones posibles. Puedes elegir una representación puramente numérica, como una matriz de números reales.
Estos se pueden implementar como números reales o como una cadena de bits estilo Goldberg asignada a números reales (tenga en cuenta que para la mayoría de los problemas, usar números reales directamente es muy superior a las representaciones de binario a decimal, especialmente si usa un operador de intersección razonable). ). Su problema puede depender del orden de los elementos, en cuyo caso una representación basada en orden (lista o matriz) puede ser más apropiada. En muchos casos, debe elegir operadores que preserven la integridad de la secuencia; el cruce debe producir una lista reordenada sin copiar ningún elemento de la lista. Otros problemas son adecuados para estructuras de árboles. Aquí es posible que desee representar la solución explícitamente como un árbol y realizar operaciones genéticas directamente en el árbol. Alternativamente, muchas personas codifican el árbol en una matriz o cadena analizable y luego operan sobre la cadena. Algunos problemas incluyen una combinación de elementos continuos y discretos, en cuyo caso es posible que necesite crear una nueva estructura para contener la información mixta. En estos casos, se deben definir operadores genéticos que se ajusten a la estructura de la solución. Por ejemplo, una solución que tiene una parte entera y una parte de punto flotante podría usar un cruce que cruce la parte entera con la parte entera y la parte de punto flotante con la parte de punto flotante, pero nunca mezcle la parte de punto flotante. parte con la parte entera.
No importa qué representación elija, asegúrese de elegir un operador apropiado para su representación.
Operadores genómicos
Cada genoma tiene tres operadores principales: inicialización, mutación y cruce. Con estos operadores, puede sesgar una población inicial, definir una mutación o cruce específico para la representación de su problema o evolucionar partes del algoritmo genético a medida que evoluciona su población. La biblioteca GA viene con estos operadores predefinidos para cada tipo de genoma, pero puede personalizar cualquiera de ellos.
El operador de inicialización determina cómo inicializar el genoma. Se llama cuando inicializas una población o un algoritmo genético. En realidad, este operador no crea un nuevo genoma, sino que "puebla" el genoma con el material genético original a partir del cual evolucionarán todas las soluciones. Los objetos de población tienen sus propios operadores de inicialización. De forma predeterminada, esto simplemente llama al operador de inicialización de los genomas de la población, pero puedes personalizarlo para que haga lo que quieras.
El operador de mutación define el proceso de mutación de cada genoma. La mutación significa cosas diferentes para diferentes tipos de datos. Por ejemplo, una variante de un genoma de cadena binaria típico invierte bits en la cadena con una probabilidad determinada. Por otro lado, el variograma típico de árboles intercambia subárboles con una probabilidad determinada. En general, se debe definir una mutación que realice tanto exploración como explotación; las mutaciones deberían poder introducir nuevo material genético y cambiar el material existente. Es posible que desee definir más de un tipo de variación para un problema.
El operador de cruce define el proceso de producir descendencia a partir de dos genomas parentales. Al igual que el operador de mutación, el cruce es específico del tipo de datos. Sin embargo, a diferencia de las mutaciones, los cruces involucran múltiples genomas. En GA lib, cada genoma "conoce" su método de apareamiento preferido (el método de hibridación predeterminado), pero no puede realizar la hibridación por sí solo. Cada algoritmo genético "sabe" cómo obtener el método de cruce predeterminado de su genoma y luego utilizar ese método para el apareamiento. Con este modelo, es posible derivar nuevas clases de algoritmos genéticos que utilizan métodos de apareamiento diferentes al predeterminado definido para el genoma.
Cada uno de estos métodos se puede personalizar para que sea específico no solo del tipo de datos sino también del tipo de problema. Esta es una forma de poner "inteligencia" específica de un problema en un algoritmo genético (no entraré en si esto es algo bueno...)
Además de los tres operadores principales, cada uno El genoma también debe contener una función objetivo y posiblemente un comparador. La función objetivo se utiliza para evaluar el genoma. Los comparadores (a menudo llamados "funciones de distancia") se utilizan para determinar en qué se diferencia un genoma de otro. Todo algoritmo genético requiere la definición de una función objetivo; así es como un algoritmo genético determina qué individuos son mejores que otros. Algunos algoritmos genéticos requieren un comparador.
La biblioteca tiene algunos tipos de datos básicos integrados, pero si ya tiene una matriz o un objeto de lista, puede construir rápidamente un genoma heredando multiplicadamente su objeto y el objeto del genoma. Luego puede usar este nuevo objeto directamente en el objeto del algoritmo genético GA lib.
En términos generales, un algoritmo genético no necesita conocer el contenido de la estructura de datos sobre la que opera. Las bibliotecas reflejan esta universalidad. Puede mezclar y combinar tipos de genomas utilizando algoritmos genéticos. Los algoritmos genéticos saben cómo clonar genomas para crear una población, inicializar genomas para que comiencen a funcionar, cruzar genomas para producir descendencia y mutar genomas. Todas estas operaciones se realizan a través de funciones de miembros del genoma.
Objetos de población
Los objetos de población son contenedores de genomas. Cada objeto de población tiene su propio inicializador (que de forma predeterminada solo se llama para cada individuo de la población) y evaluador (que de forma predeterminada solo se llama para cada individuo de la población). También registra los mejores valores de la población, medias, desviaciones, etc. También se puede registrar la diversidad, pero dado que los cálculos de diversidad a menudo requieren cálculos adicionales significativos, la diversidad no se registra de forma predeterminada.
El método de selección también se define en el objeto de población. Los algoritmos genéticos utilizan este método para seleccionar qué individuos deben aparearse.
Cada objeto de relleno tiene un objeto de esquema de escala asociado. El objeto del esquema de escala convierte la puntuación objetiva para cada genoma en una puntuación SS adecuada para la selección mediante el algoritmo genético. También almacena en caché información de aptitud para su uso posterior por parte de alternativas.
Funciones objetivas y escalas de aptitud
Los algoritmos genéticos son generalmente más atractivos que los métodos de búsqueda de gradiente porque no requieren ecuaciones diferenciales complejas ni espacios de búsqueda suaves. Los algoritmos genéticos solo requieren una única métrica para medir qué tan bien se compara un individuo con otros individuos. La función objetivo proporciona esta medida; dada una única solución a un problema, ¿qué tan buena es?
Es importante tener en cuenta la diferencia entre puntuaciones de salud y objetivas. La puntuación objetiva es el valor devuelto por su función objetivo; esta es una evaluación cruda del desempeño de un genoma. La puntuación de aptitud, por otro lado, es la clasificación de posibles transformaciones utilizadas por el algoritmo genético para determinar la aptitud de un individuo para aparearse. La puntuación de aptitud generalmente se obtiene mediante una escala lineal de la puntuación del objetivo original (pero puede definir cualquier mapeo que desee o ninguna transformación). Por ejemplo, si utiliza la escala lineal de Arthur, la puntuación de aptitud se deriva de la puntuación objetiva utilizando la técnica de escala proporcional de aptitud descrita en el libro de Goldberg. Los algoritmos genéticos utilizan puntuaciones de aptitud en lugar de puntuaciones objetivas para realizar selecciones.
Puedes evaluar individuos en una población usando una función de evaluación individual (definida por ti) o un evaluador grupal (también definido por ti). Si utiliza la orientación individual, las funciones se asignan a cada genoma. Una función objetivo basada en la población puede utilizar una función objetivo individual o puede establecer las puntuaciones individuales por sí misma.