¿Qué es un algoritmo genético?
Tarjeta de presentación de la Enciclopedia de Algoritmos Genéticos
El Algoritmo Genético es un modelo computacional que simula el proceso de evolución biológica de la selección natural y los mecanismos genéticos de la teoría de la evolución biológica de Darwin. El método de búsqueda de soluciones óptimas. En el proceso evolutivo fue propuesto por primera vez por el profesor J. Holland de la Universidad de Michigan en 1975, y publicó la influyente monografía "Adaptación en sistemas naturales y artificiales". Como sabemos, el nombre GA propuesto por el profesor. J. Holland suele ser un algoritmo genético simple (SGA).
El algoritmo genético es un tipo de método de búsqueda aleatoria evolucionado a partir de las leyes evolutivas del mundo biológico (supervivencia del más apto, mecanismo genético de supervivencia del más apto). Fue propuesto por primera vez por el profesor J. Holland en los Estados Unidos en 1975. Su característica principal es operar directamente en objetos estructurales sin las limitaciones de derivación y continuidad de funciones; tiene un paralelismo implícito inherente y mejores capacidades de optimización global; Método de optimización, puede obtener y guiar automáticamente el espacio de búsqueda optimizado y ajustar de forma adaptativa la dirección de búsqueda sin la necesidad de reglas definidas. Estas propiedades de los algoritmos genéticos se han utilizado ampliamente en campos como la optimización combinatoria, el aprendizaje automático, el procesamiento de señales, el control adaptativo y la vida artificial. Es una tecnología clave en la informática inteligente moderna. Para un problema de optimización de encontrar el valor máximo de una función (lo mismo ocurre con encontrar el valor mínimo de una función), generalmente se puede describir como el siguiente modelo de programación matemática: La fórmula del algoritmo genético es la variable de decisión y es la fórmula de la función objetivo. Las fórmulas 2-2 y 2-3 son restricciones, U es el espacio básico y R es un subconjunto de U. La solución X que satisface las restricciones se denomina solución factible y el conjunto R representa el conjunto de todas las soluciones que satisfacen las restricciones, lo que se denomina conjunto de soluciones factibles. El proceso de operación básico del algoritmo genético es el siguiente: a) Inicialización: establezca el contador de generación evolutiva t = 0, establezca la generación evolutiva máxima T y genere aleatoriamente M individuos como población inicial P (0). b) Evaluación individual: Calcular la aptitud de cada individuo del grupo P(t). c) Operación de selección: Aplicar el operador de selección al grupo. El propósito de la selección es heredar directamente individuos optimizados a la siguiente generación o generar nuevos individuos mediante cruce por pares y luego heredarlos a la siguiente generación. La operación de selección se basa en la evaluación de la aptitud de los individuos del grupo. d) Operación de cruce; aplicar el operador de cruce al grupo. El llamado cruce se refiere a la operación de reemplazar y reorganizar parte de la estructura de dos individuos progenitores para generar un nuevo individuo. El operador de cruce juega un papel central en el algoritmo genético. e) Operación de mutación: aplicar el operador de mutación a la población. Se trata de cambiar los valores genéticos en ciertos loci de cadenas individuales en la población. Después de que la población P (t) se somete a operaciones de selección, cruce y mutación, se obtiene la población P (t 1) de la próxima generación. f) Juicio de condición de terminación: Si tT, el individuo con la máxima aptitud obtenida durante el proceso de evolución se utilizará como salida de la solución óptima y se terminará el cálculo.
[Editar este párrafo] Definición de Algoritmo Genético
El algoritmo genético parte de una población que representa el conjunto de posibles soluciones potenciales al problema, y una población está compuesta por genes ( Gen) codificado por un cierto número de individuos. Cada individuo es en realidad un cromosoma (cromosoma) con entidades características. Como principal portador de material genético, los cromosomas son un conjunto de múltiples genes. Su expresión interna (es decir, el genotipo) es una determinada combinación de genes, que determina la expresión externa de la forma de un individuo. Por ejemplo, se controlan las características del cabello negro. por los cromosomas. Una característica está determinada por una determinada combinación de genes. Por lo tanto, el mapeo del fenotipo al genotipo, es decir, la codificación, debe realizarse desde el principio.
Dado que el trabajo de imitar la codificación genética es muy complicado, a menudo hacemos simplificaciones, como la codificación binaria. Después de generar la población de la primera generación, de acuerdo con los principios de supervivencia del más apto y supervivencia del más apto, la evolución generación tras generación produce mejores. y mejores soluciones aproximadas en una generación, los individuos se seleccionan en función de su idoneidad en el dominio del problema, y el cruce y la mutación se combinan con la ayuda de operadores genéticos de la genética natural para generar nuevos La población de conjuntos de soluciones. Este proceso hará que la población evolucione naturalmente y la población de la generación siguiente será más adaptable al medio ambiente que la generación anterior. El individuo óptimo de la población de la última generación se puede decodificar y utilizar como una solución óptima aproximada al problema.