Idea principal:
El algoritmo genético es un algoritmo de búsqueda heurística basado en la población, donde mediante el uso repetido de operaciones genéticas, como mutación, selección, cruce, etc., se crean nuevas generaciones sucesivas de mejores poblaciones en la dirección de los objetivos de búsqueda mediante la adopción de principios darwinianos basados en la evolución natural. .
Algoritmo:
- ¿Cuáles son algunos algoritmos conocidos para encontrar una coincidencia perfecta en un gráfico bipartito?
- ¿Usar un tipo de inserción de 50 elementos tendrá el mismo tiempo de ejecución que usar un tipo de inserción de 10 elementos 5 veces?
- ¿Cuántas conjeturas necesitarías para determinar el número entre 1 y 100 en el peor de los casos usando una búsqueda lineal?
- ¿Cuáles son las características de un algoritmo codicioso?
- Hay dos imágenes ¿Hay algún algoritmo que pueda decirnos si una imagen se recorta de la otra?
- El algoritmo de búsqueda se realizará en algunos espacios de parámetros y buscará el rendimiento de los individuos dentro de la población. Tales individuos se llaman fenotipo.
- Los parámetros de tales fenotipos están representados por el genotipo para las operaciones genéticas apropiadas, que generalmente se representa por binario como cadenas de ceros y unos. Dichos componentes binarios de los genotipos se denominan genes. Dicha representación del gen como una cadena binaria se denomina genoma binario de tipo genoma y el algoritmo genético se etiqueta como algoritmo genético codificado en binario .
- Del mismo modo, las operaciones genéticas para la representación del valor real de un gen o tipo de genoma real también están disponibles, por lo tanto, también es posible el algoritmo genético codificado real . También es posible codificar con cualquier otro tipo de objeto si hay disponibles operaciones genéticas adecuadas para tales tipos de objeto.
- Por lo general, el algoritmo genético representa el genotipo en forma de matriz o lista de genes, lo que simplifica la operación de cruce. Otras representaciones también están disponibles como: programación genética para la representación de árbol; programación evolutiva para representaciones en forma de gráfico; programación de expresión génica para una mezcla de lista y árboles.
- Además de la representación de genotipo mencionada anteriormente de individuos en el dominio de búsqueda, también se requieren una o más funciones de aptitud para la implementación del algoritmo genético junto con algunas restricciones de igualdad o desigualdad. Cuando el número de funciones objetivo es más de uno, se denomina optimización de objetivos múltiples. La presencia de restricciones en la optimización se denomina optimización restringida.
- El algoritmo genético comienza con un conjunto de individuos creados al azar dentro del espacio de búsqueda y luego mejora a través de la aplicación repetitiva de operaciones genéticas para un mejor conjunto de individuos, donde dicho conjunto de individuos en cada iteración se llama generación . El número total de generación es uno de los parámetros libres que se utilizan para terminar el algoritmo.
- El tamaño de la población depende del tipo de problema y puede variar de unos pocos cientos a unos pocos miles, aunque el algoritmo microgenético puede funcionar con cuatro o cinco individuos en una población. El tamaño de la población también es uno de los parámetros libres importantes en el algoritmo genético.
- La operación genética comienza con el cálculo de la aptitud para cada individuo, que a veces es el costo de cálculo principal del algoritmo. Para la optimización de objetivos múltiples, se debe evaluar cada función objetivo para cada individuo para cada generación.
- Durante la generación sucesiva, algunos individuos de la generación principal se seleccionan para crear la próxima generación a través del operador de selección. Las personas más en forma tendrán más peso estocástico para contribuir a la próxima generación. Hay muchas variantes de operadores de selección en la literatura, como la selección proporcional de aptitud (selección de la ruleta), el muestreo estocástico universal , la selección de torneos , la selección de truncamiento , etc.
- En algún momento, los mejores individuos son empujados directamente a la próxima generación. Tal operación se llama elitismo o selección elitista. Tal probabilidad de elitismo es también uno de los parámetros libres en el algoritmo genético.
- Después de la selección, se lleva a dos o más padres a transmitir rasgos de información genética y, por lo tanto, producen uno o más individuos de la próxima generación, que es similar al cruce biológico del cromosoma. El uso repetido de dicha operación cruzada se utiliza para llenar la población de la próxima generación. Dependiendo de la estructura de datos utilizada para almacenar el fenotipo individual, muchas técnicas de cruce están disponibles en la literatura como: cruce de un punto, cruce de dos puntos, corte y empalme, cruce uniforme, cruce medio uniforme, cruce de varios padres, etc.
- Finalmente, para crear diversidad genética en la próxima generación, se usa la mutación como operador genético; Esto altera uno o más componentes de la representación genotípica de individuos estocásticamente, lo cual es similar a la mutación biológica. Están disponibles diferentes tipos de mutación dependiendo del tipo de genoma como: mutación de cadena de bits, bit flip, límite, uniforme, no uniforme, gaussiano, etc.
- La probabilidad de mutación también es un parámetro libre en el algoritmo genético. La baja probabilidad de mutación puede conducir a una deriva genética, lo que reduce la variación genética y la convergencia prematura del algoritmo. De manera similar, una probabilidad de mutación muy alta puede perder buenas soluciones a menos que la selección elitista se aplique conjuntamente.
- Además de la inspección manual, para terminar dicho algoritmo iterativo, algunos criterios de terminación también se consideran como: uno o más individuos dentro de la población final han alcanzado los criterios, la mejora o el progreso óptimos predeterminados; número preestablecido de generación, tiempo, almacenamiento o cálculo; La generación sucesiva ha alcanzado la meseta de las funciones objetivas, etc.
La principal ventaja del algoritmo genético o la familia completa de algoritmos de algoritmos evolutivos es que, idealmente, no hacen suposiciones sobre los problemas subyacentes, por lo tanto, son adecuados para cualquier problema tan diverso como ingeniería, arte, biología, economía, marketing, genética, investigación de operaciones, robótica , ciencias sociales, física, política, química, etc.
La principal desventaja de dicha familia de algoritmos es la gran cantidad de evaluaciones para las costosas funciones físicas. Se puede utilizar alguna forma de aproximación de la condición física como polinomios, regresión, modelo sustituto, etc. para reducir el costo de la función de condición física real que se debe evaluar para cada individuo de cada generación.
Algoritmo genético pertenece al campo de
- Inteligencia artificial
- -> Computación suave
- -> Computación Evolutiva
- -> Algoritmo evolutivo y otros algoritmos similares son
- estrategias de evolución,
- programación evolutiva,
- recocido simulado,
- Adaptación gaussiana,
- Montañismo,
- inteligencia de enjambre
- optimización de colonias de hormigas,
- optimización de Enjambre de partículas,
- Partículas autopropulsadas
- Evolución diferencial
- programación lineal entera
- etc.
