Notas sobre el algoritmo de optimización (26) Algoritmo de búsqueda de armonía
(Las siguientes descripciones no son términos académicos, son solo para el placer de leer de todos)
El algoritmo de búsqueda de armonía está inspirado en la armonía en la música. Se propuso la fórmula del algoritmo (. publicado) en 2001, que se considera un algoritmo relativamente antiguo. Hoy en día, el rendimiento del algoritmo de búsqueda de armonía es muy mediocre, pero se propone un método de implementación específico para la búsqueda de dominio, que se puede integrar con diferentes algoritmos para mejorar el rendimiento de otros algoritmos.
No tiene mucho sentido observar una armonía sola. Una dimensión de una armonía determinará su alcance de campo en función de todos los valores de esa dimensión en el grupo y luego realizará un campo. buscar.
El algoritmo original está inspirado en la música, por lo que el problema objetivo que resuelve también es un problema discreto.
Un individuo en el algoritmo de búsqueda de armonía se llama Memoria de armonía (HM). El número de memorias de armonía en el grupo es N, y el número de notas (dimensión) en cada memoria de armonía es D. El rango de valores de cada dimensión es .
El rango de valores L de cada dimensión en el algoritmo original es un conjunto de valores discretos ordenados, es decir, uno de los valores variables especificados se selecciona como valor de memoria de armonía.
Cada memoria de armonía sólo puede cambiar el valor de su campo en cada iteración.
Hay dos operaciones en el algoritmo de armonía: 1. Mover al campo, 2. Mutación al campo
Las probabilidades son la tasa de consideración de la memoria de armonía (HMCR) y la tasa de ajuste del tono. (PAR).
Entre ellos, el valor de HMCR es de aproximadamente 0,95 y el valor de PAR es de aproximadamente 0,10.
Se puede observar que los pasos y valores de este algoritmo se refieren al algoritmo genético, y ambos están diseñados para abordar problemas discretos.
El ejemplo es el siguiente:
El número de memorias de armonía es 3 y la dimensión es 2. El rango de valores de la primera dimensión es {A, B, C, D, E, F, G}, el valor de la segunda dimensión es {3, 4, 5, 6}.
En la primera generación, los valores de los tres individuos son los siguientes
Al calcular la segunda generación, cada dimensión de cada individuo solo puede ir al valor de la vecindad de esa dimensión.
El valor que puede obtener el individuo 1_2 es (A, 3) (A, 4) (B, 3) (B, 4)
El valor que puede obtener el individuo 2_2 es (F , 4) (F, 5) (F, 6) (G, 4) (G, 5) (G, 6)
El valor que puede obtener el individuo 3_2 es (C, 3) (C, 4)(C,5)(D,3)(D,4)(D,5)(E,3)(E,4)(E,5),
Esto es marcados en la figura Barrios accesibles para tres personas.
La operación de mutación a vecindad también es muy simple. Esta operación es el punto de referencia de la operación de mutación en el algoritmo genético.
Al mutar a la operación de vecindad, la dimensión no mutará al valor existente actual.
Por ejemplo, si el individuo 1_1 muta la primera dimensión, dado que el valor de la primera dimensión en la población es {A,D,G}, esta dimensión solo puede tomar {B,C,E,F }.
En la figura siguiente, los bloques de colores están fuera de posiciones que no se pueden alcanzar mediante operaciones de mutación, y las posiciones en blanco son posiciones que se pueden alcanzar mediante operaciones de mutación. (¿Qué pasa si no hay una posición en blanco? La probabilidad es muy pequeña. Después de todo, la posición individual es mucho menor que la posición del espacio de solución. Si ocurre, no importará si no está mutada o es una posición aleatoria)
Después de la iteración, si la nueva posición es mejor, la memoria de armonía se conserva y se elimina la peor memoria de armonía.
Finalmente, el artículo proporciona una función de juicio para juzgar si la solución encontrada es la solución óptima.
Donde Hr=HMCR, Hi aumentará con el número de iteraciones cuando tenga un mejor valor. se encuentra cada vez más en esta dimensión. La función de esta fórmula es principalmente determinar cuándo finalizar el programa del algoritmo. Sin embargo, antes de que usáramos el número máximo de iteraciones para finalizar el programa del algoritmo, parece ser de poca utilidad.
El proceso del algoritmo también es bastante simple:
El algoritmo original de búsqueda de armonía se basa en el concepto de armonía en la música. Las notas son discretas y todos los algoritmos también son discretos. Los algoritmos genéticos se utilizan para abordar problemas de espacios de solución discretos, entonces, ¿cómo modificar el algoritmo de búsqueda de armonía para que pueda abordar problemas numéricos continuos?
El punto más crítico es cómo lidiar con la "vecindad". En el espacio de solución continua, es difícil definir el dominio de un punto y el número de valores en cada dimensión es. también infinito.
Hay varias ideas para definir vecindades para el algoritmo de búsqueda de armonía:
1. Definir todos los individuos como la vecindad del individuo, es decir, seleccionar aleatoriamente uno del grupo cada vez. Individual, esta dimensión se traslada al individuo seleccionado.
Entre ellos, D, E y F son los puntos medios de AB, AC y BC respectivamente. Las vecindades de las tres memorias armónicas de A, B y C estarán determinadas por los tres puntos de. DEF y el límite del espacio de solución. Esta vecindad es más pequeña que la de la idea 2 y no habrá superposición.
Cuando los dos valores de dominio en una determinada dimensión son iguales, la vecindad (superficie) anterior (bidimensional) degenerará en una vecindad (línea), lo que puede hacer que la dimensión converja rápidamente a este valor, por lo que en este momento es necesario ignorar los valores duplicados y volver a expandir la vecindad (convertirse en una superficie).
En el algoritmo continuo, cuando se cumple la condición HCMR, el algoritmo seleccionará aleatoriamente un valor en la vecindad según el bloque de color anterior cuando se cumpla la condición PAR, ya que el valor especificado no se puede eliminar; Para simplificar, muévase directamente a esa dimensión de memoria armónica aleatoria.
Dado que los experimentos posteriores son para resolver el valor máximo de la función continua, elegiremos las tres ideas en el algoritmo continuo mencionado anteriormente.
Función fitness.
Experimento 1: Idea 1
Como se puede ver en la imagen, la estrategia de la Idea 1 es muy similar al algoritmo genético. La ruta en movimiento es similar a una cruz, y. eventualmente converge hacia la vecindad de la solución correcta. La búsqueda inicial se basa principalmente en el movimiento vecinal, mientras que el movimiento posterior se basa en la mutación.
También se puede ver en los resultados que no hay mucha diferencia con el algoritmo genético. El algoritmo no es muy estable. Su estrategia es volar a la memoria de armonía adyacente, por lo que el lapso es relativamente grande. , y la precisión depende completamente de la mutación.
Experimento 2: Idea 2
Se puede ver en la imagen que la ruta de búsqueda de la población no es una ruta cruzada recta como en el Experimento 1, y la velocidad de convergencia también es mucho más lento, pero aún puede converger cerca de la solución correcta.
Se puede ver en los resultados que los resultados de la segunda idea son mucho mejores y más estables (mal, buena suerte, se produjeron malos resultados en experimentos anteriores y no se pudieron reproducir).
El área de búsqueda de vecindarios de esta idea será mayor y habrá superposición en los vecindarios entre individuos, por lo que puede converger en una mala ubicación, pero la probabilidad también es pequeña.
Experimento 3: Idea 3
¡La imagen poco a poco se convierte en una serpiente! Las primeras imágenes son similares a la primera idea, y las imágenes posteriores son un poco similares al algoritmo genético. Puede ser que el área del vecindario se reduzca gradualmente hasta convertirse en una franja larga, pero al final la "serpiente codiciosa". todavía come la comida.
Se puede ver en los resultados que la estabilidad de la idea tres no es muy buena cuando todos los individuos convergen en un punto, sin embargo, comenzará la operación de reemplazo de la idea uno, sin importar cuál sea el reemplazo. , el valor será el mismo y es difícil encontrar una posición mejor, se producirá un mal resultado. Aquí también puede aumentar el rango de aleatoriedad para saltar del óptimo local.
El algoritmo de búsqueda de armonía es un algoritmo propuesto en base al conocimiento de la teoría musical de la armonía. Dado que las notas musicales son valores discretos, el algoritmo también compara el algoritmo genético, por lo que el algoritmo original también se propone para problemas discretos. Al resolver problemas de continuidad, es necesario ampliar y modificar su concepto de vecindad, y el efecto final no es muy diferente del algoritmo genético.
Desde el punto de vista actual, el efecto del algoritmo de búsqueda de armonía es realmente promedio y no hay mucha investigación específica al respecto. Este algoritmo propone principalmente una forma de atravesar el espacio de solución que es diferente de. El algoritmo genético. Por lo tanto, en muchos artículos se pueden ver ejemplos de mejoras utilizando el algoritmo de búsqueda de armonía y otros algoritmos.
En comparación con el algoritmo genético, el concepto de vecindad del algoritmo de búsqueda de armonía extiende los genes del algoritmo genético desde líneas hasta superficies. Esto es algo similar a la relación entre SVM y redes neuronales convolucionales. Sin embargo, la diferencia entre los algoritmos genéticos y los algoritmos de búsqueda de armonía no es tan grande, solo los métodos de búsqueda son diferentes.
Referencias
Geem Z W, Kim J H, Loganathan G V. Un nuevo algoritmo de optimización heurística: Harmony Search[J], 2001, 2(2): 60-68. Código de extracción: 4udl
Omran M, Mahdavi M. Búsqueda de la mejor armonía global [J]. Matemáticas aplicadas y computación, 2008, 198(2): 643-656.
Los siguientes indicadores son puramente personales y solo como referencia
Tabla de contenido
Notas del algoritmo de optimización anterior (veinticinco) Algoritmo de polilla a llama
Artículo siguiente Notas sobre el algoritmo de optimización (veintisiete) Algoritmo Mayfly