Actualmente estoy trabajando en un proyecto de algoritmo genético, así que lo registraré brevemente.
El algoritmo genético es un algoritmo que simula el mecanismo de evolución biológica en la naturaleza. En el proceso de optimización se retienen los útiles y se eliminan los inútiles. Incluye tres operadores genéticos básicos: selección, cruce y mutación. El efecto de las operaciones genéticas está estrechamente relacionado con la probabilidad de operación, el método de codificación, el tamaño de la población, la población inicial y la configuración de la función de aptitud de los tres operadores genéticos anteriores.
1. Inicialización de la población
tamaño de la población popsize, generalmente entre 20 y 100, si es demasiado pequeño, reducirá la diversidad de la población y conducirá a una madurez prematura; mayor, afectará la eficiencia operativa; el número de iteraciones es generalmente de 100 a 500; probabilidad de cruce: 0,4 a 0,99, demasiado pequeña destruirá el excelente patrón de probabilidad de mutación: 0,001 a 0,1, demasiado grande, la tendencia de búsqueda; ser aleatorio. La codificación incluye codificación de números reales y codificación binaria. Puede consultar varios problemas clásicos de algoritmos genéticos, TSP, problema de mochila y problema de programación de talleres.
2. Selección
El propósito es heredar directamente los individuos optimizados a la siguiente generación o generar nuevos individuos mediante emparejamiento y cruce y luego heredarlos a la siguiente generación. Utilice el método de la ruleta. Para obtener más información, consulte /u/1412321/blog/192454 Método de la ruleta. La probabilidad de selección de cada individuo es proporcional a su valor de aptitud. Cuanto mayor sea el valor de aptitud individual, mayor será la probabilidad de ser seleccionado, y viceversa. En problemas prácticos, el valor mínimo suele ser necesario como solución óptima. Existen varios métodos de conversión.
Para datos entre a y 0-1, puede usar 1: este valor, luego el valor mínimo. y el intercambio de valor máximo;
b. Encuentra el recíproco;
c. Encuentra el número opuesto
Los métodos anteriores pueden cambiar el valor máximo al mínimo; El valor mínimo se convierte en el valor máximo, lo que facilita el uso de la ruleta para seleccionar al individuo óptimo, que se determina de acuerdo con la situación real.
3. Cruce
El cruce es una operación que reemplaza y recombina parte de la estructura de dos individuos progenitores para generar un nuevo individuo. A través del cruce, la capacidad de búsqueda del algoritmo genético puede. mejorarse mucho. Dependiendo del método de codificación, se pueden utilizar los siguientes algoritmos:
a. Reorganización de valor real
Reorganización discreta, reorganización intermedia, reorganización lineal, reorganización lineal extendida
b. Cruce binario
Cruce de un solo punto, cruce multipunto, cruce uniforme, cruce aleatorio, cruce de agente reductor
4. Mutación
Básica Pasos: par Todos los individuos del grupo determinan si deben sufrir una mutación en función de la probabilidad de mutación preestablecida. Los bits de mutación de los individuos mutados se seleccionan aleatoriamente para la mutación. Según los diferentes métodos de representación de codificación, existen mutaciones de valor real y mutaciones binarias
Propósito de la mutación:
hacer que el algoritmo genético tenga capacidad de búsqueda aleatoria local. Cuando el algoritmo genético está cerca de la vecindad de solución óptima a través del operador de cruce, la capacidad de búsqueda local del operador de mutación se puede utilizar para acelerar la convergencia a la solución óptima. Obviamente, la probabilidad de mutación debería ser menor en este caso; de lo contrario, los componentes básicos cercanos a la solución óptima se destruirán debido a la mutación.
b.Hacer que el algoritmo genético mantenga la diversidad para evitar una convergencia prematura. En este momento, la probabilidad de convergencia debería tomar un valor mayor.
La probabilidad de mutación es generalmente de 0,001-0,1.
5. Condición de terminación
Cuando el fitness del individuo óptimo alcanza un umbral determinado, o el fitness del individuo óptimo y el fitness del grupo ya no aumentan, o el número de iteraciones El algoritmo finaliza cuando se alcanza el número preestablecido de generaciones. El álgebra predeterminada es generalmente 100-500.
6. Otros
Multivariable: conecta múltiples variables en secuencia
Multiobjetivo: un método es convertirlo en un solo objetivo, como ordenar por tamaño, según clasificación y selección, puede consultar /paulfeng20171114/article/details/82454310