Adecuación (fitness)
Medida de la bondad de una estructura considerada como solución a un problema. Cada individuo en un AG tiene asociado un valor de adecuación que indica la bondad de la solución que representa.
Alelo
Valor que puede tomar un gen, procedente de una posición de la estructura progenitora, que rige un carácter hereditario. Valor elemental de una de las posiciones de un individuo.
Algoritmo de búsqueda
Proceso para localizar una solución particular para un problema dado dentro de un conjunto de soluciones plausibles.
Algoritmo evolutivo
Algoritmo de búsqueda que mantiene una población de estructuras que evolucionan de acuerdo a reglas estocásticas como la selección natural (supervivencia de los más aptos), el emparejamiento (cruce) y la mutación.
Algoritmo genético (AG, GA)
Algoritmo evolutivo que mantiene una población de soluciones candidatas a una función objetivo dada. Está basado en los mecanismos de la Genética y en la selección natural de las especies y trabaja sobre cadenas de parámetros.
Cromosoma
Cada uno de los orgánulos celulares que contienen el material de la herencia biológica. Se considera una concatenación de genes. También conocido como estructura, cadena o individuo en un algoritmo evolutivo (caso haploide).
Cruce (crossover)
Operador estocástico genético que modifica la población de individuos mediante la producción de nuevos individuos resultantes de porciones elegidas de dos padres. Produce uno o más descendientes (típicamente dos) a partir de dos padres, previamente seleccionados por algún método. Formalmente produce un intercambio de información entre los hiperplanos presentes en el genotipo dando lugar a nuevos puntos de búsqueda en la población de forma acotada con o sin efectos sobre la diversidad presente (típicamente no afecta a la diversidad).
CX (cycle crossover)
Operador genético de cruce que construye dos descendientes de forma que, para cada uno, cada valor y su posición proviene de uno de sus progenitores. Respeta la posición absoluta de los elementos en las secuencias padre. Por ejemplo, de (1 2 3 4 5 6 7 8 9) y (4 1 2 8 7 6 9 3 5) produciría los descendientes (1 2 3 4 7 6 9 8 5) y (4 1 2 8 5 6 7 3 9).Deriva genética
Efecto de un AG por el que, aun cuando todas las estructuras de la población tienen el mismo valor de adecuación el algoritmo toma preferencia por una de ellas, a pesar de que no tiene elementos para definirse por una u otra estructura.
Descendiente
Individuo resultante de una operación genética aplicada a un conjunto de progenitores.
Diversidad
Variedad en el contenido de los individuos de una misma población genética. Tradicionalmente se mide como distancia de Hamming entre las estructuras de una población o como la frecuencia por cada locus de cada alelo posible. También puede medirse calculando la entropía media de la población.Elitismo
Variante de búsqueda evolutiva en la que un porcentaje de la población actual sobrevive de forma determinista al bucle reproductor.
Enumeración exhaustiva
Método de búsqueda que consiste en la evaluación de todos los puntos del dominio solución hasta encontrar un óptimo global. Se trata de un mecanismo reconocidamente seguro aunque de eficiencia muy baja en problemas reales.
Esquema evolutivo por generaciones
La población, llamada progenitora, se somete a tratamiento genético (selección, cruce, mutación, etc...) añadiendo los individuos así obtenidos a una población distinta, llamada descendiente: AE-(μ,λ). Una vez que se completa la población descendiente se sustituye la población progenitora por la población descendiente recién obtenida. El paso básico de avance de la evolución es la generación.
Evolución
Campo de la Biología que tiene por objeto el estudio de los cambios que han sufrido los seres vivos a lo largo del tiempo y que han dado lugar a su diversificación a partir de antepasados comunes.
Expresión (genotipo → fenotipo)
Proceso que gobierna la traslación del genotipo en fenotipo (decodificación binaria-a-decimal, por ejemplo).
Fenotipo
Aspecto observable que ha sido adquirido como consecuencia del genotipo que posee y de la acción del medio ambiente (función de adecuación).
Fitness
Adecuación.
Función objetivo
Función original que se pretende optimizar con un algoritmo genético.
Gen
Partícula elemental de un cromosoma, responsable de la transmisión hereditaria de un carácter. El conjunto de genes es el genotipo. En una técnica evolutiva representa uno de los parámetros del problema real que se desea resolver.
Generación
Paso evolutivo de toda una población en el que un conjunto de descendientes sustituye completamente a sus padres.
Genética
Parte de la Biología que se ocupa del estudio de la herencia biológica e intenta explicar los mecanismos y circunstancias que rigen la transmisión y variabilidad de caracteres de generación en generación.
Genotipo
Conjunto de caracteres o factores hereditarios (genes) que posee un individuo por haberlos recibido de sus progenitores (parámetros del problema codificados).Herencia
Proceso de transmisión de un conjunto de caracteres congénitos de los progenitores de una determinada especie a sus descendientes.
Herencia dominante
Tipo de herencia en la que, de los dos genes que rigen un mismo carácter, sólo uno de ellos, llamado dominante, se manifiesta en el fenotipo mientras que el otro, llamado recesivo, queda “oculto”.
Herencia intermedia
Tipo de herencia en la que los dos genes que rigen un mismo carácter tienen “fuerzas similares” para manifestarse en el fenotipo, por lo que el carácter que rigen se manifiesta como una mezcla de ambos.
HX (heuristic crossover)
Operador de cruce utilizado en algoritmos genéticos que se aplican a problemas que satisfacen unas determinadas restricciones. Admite muchas implementaciones y un número variable de estructuras origen. Altera algunas posiciones y calcula cómo dar la estructura hijo de forma heurística.
Individuo
Representación codificada de una solución a un problema dado. Típicamente es haploide aunque puede ser diploide o n-ploide en general. Igualmente es típico que sea una cadena de símbolos aunque pueden encontrarse otras estructuras como árboles sintácticos o mezclas de representaciones distintas en el mismo individuo.
Mutación
Cambio brusco y permanente de uno o de varios caracteres hereditarios. La mutación renueva el material genético existente en la población, generando fenotipos que quizá no hubieran aparecido de otro modo.
Mutación indiferente
Tipo de mutación que no repercute ni favorable ni desfavorablemente sobre el individuo.
Mutación progresiva
Tipo de mutación en la que el gen mutado resulta más favorable para el individuo que aquel del cual procede.
Mutación regresiva
Tipo de mutación en la que el gen mutado es desfavorable, es decir, provoca algún efecto negativo sobre el organismo.Operadores genéticos
Conjunto de operaciones a las que se ven sometidos los individuos que componen una población genética. Típicamente las más utilizados son selección, cruce, mutación y reemplazo. Todas ellas suelen incorporarse ordenadamente como parte del plan reproductor.
OX (order crossover)
Operador genético de cruce que genera dos descendientes eligiendo para cada uno de ellos un sub-recorrido de uno de los progenitores y preservando el orden relativo de los restantes valores presentes en el otro progenitor. Explota la propiedad de que el orden de los elementos (no su posición) es importante. Por ejemplo, a partir de (1 2 3 | 4 5 6 7 | 8 9 ) y (4 5 2 | 1 8 7 6 | 9 3) elegiría dos puntos de cruce (marcados con barras) y generaría los hijos (2 1 8 4 5 6 7 9 3) y (3 4 5 1 8 7 6 9 2).
Población
Conjunto de estructuras que representan soluciones subóptimas al problema que está intentando resolver con un algoritmo genético.
Progenitor
Individuo al que se la aplican uno o más operadores genéticos para obtener como resultado uno o más descendientes.
Punto de cruce
Valor entre 0 y L-1, siendo L el número de alelos del cromosoma. Delimita el fragmento de cadena que se va a intercambiar de cada padre.
Reemplazo de individuos
Técnica empleada para mantener constante el número de individuos que componen la población genética. Típicamente se usa el reemplazo del peor individuo (con el peor valor de adecuación asociada) o el reemplazo aleatorio.
Selección
Operador genético que guía la búsqueda hacia los lugares más prometedores del espacio de soluciones. Los individuos de más alto valor de adecuación deberían ser seleccionados frecuentemente para recombinarlos con el objeto de que sus descendientes hereden sus características. Sin embargo, una selección frecuente del mismo individuo puede provocar que toda la población esté salpicada con sus características, lo cual redunda en una pérdida de la diversidad. Por tanto, la clave del éxito para el operador de selección es permitir el equilibrio correcto entre la explotación y la exploración del espacio de soluciones. La selección se puede realizar de acuerdo a diferentes estrategias: el método de la ruleta (roulette wheel), el mecanismo ranking, selección aleatoria, mecanismos elitistas, etc... La selección puede usarse para elegir pareja antes de la recombinación o bien para elegir al individuo que va a ser reemplazado.
Selección elitista
Estrategia de selección que estipula que el individuo o estructura que ofrezca mejor rendimiento sobreviva de una generación a otra. Puede extenderse para hacer sobrevivir un porcentaje de individuos que pasarán a formar parte de la siguiente generación determinísticamente.
Selección natural
Teoría enunciada por Darwin como principal motor de la evolución. La selección natural es la consecuencia de la lucha por la vida y se supone que conduce a la supervivencia del más apto.
SPX (single point crossover)
Operador genético binario de único punto de cruce. Funciona seleccionando un punto aleatoriamente en las cadenas padres e intercambiando el contenido entre ellos para producir dos descendientes.
Steady-state
Esquema evolutivo por efectos inmediatos o de estado estacionario.UX (Uniform crossover)
Cruce uniforme. Para cada posición de la cadena descendiente, cada padre aporta con cierta probabilidad (dada por el usuario) cada uno de sus genes. En la mayoría de aplicaciones se utiliza 0.5 como probabilidad (no es la prob. de aplicación).