¿Puede el algoritmo de optimización del caos encontrar la solución óptima global?

Resumen: Combinando el método BFGS y el método de optimización del caos, se propone un método de optimización híbrido basado en variables de caos para resolver problemas de optimización no lineal con restricciones de límites variables. El algoritmo híbrido tiene en cuenta las ventajas de la fuerte capacidad de búsqueda global de la optimización del caos y la rápida velocidad de convergencia del método BFGS, y se ha convertido en un método eficaz para resolver la optimización global de problemas de optimización no convexos. Los ejemplos muestran que cuando el número de búsquedas caóticas alcanza un cierto número, el método de optimización híbrida puede garantizar que el algoritmo converja a la solución óptima global y la eficiencia computacional mejora enormemente en comparación con el método de optimización caótica.

Palabras clave: método híbrido; método BFGS; método de optimización del caos; óptimo global

1 Introducción

En ingeniería de sistemas, ingeniería de control, estadística, reacción En campos como Como optimización de problemas, muchos problemas no son convexos. Las técnicas de optimización ordinarias solo pueden encontrar soluciones óptimas locales, porque estos algoritmos deterministas siempre encuentran el punto extremo más cercano [1], y solo dando un buen punto inicial se puede obtener la solución óptima global requerida. Por esta razón, los métodos tradicionales de optimización numérica todavía se utilizan para encontrar soluciones globales en aplicaciones prácticas, pero este método tiene una baja probabilidad de encontrar una solución global y una baja confiabilidad. Establecer un algoritmo que encuentre una solución global con la mayor probabilidad posible sigue siendo una cuestión importante. En los últimos años, se han estudiado métodos de optimización global basados ​​​​en métodos de gradiente [2], y la aplicación de algoritmos genéticos y algoritmos de recocido simulados basados ​​​​en tecnología de búsqueda aleatoria en problemas de optimización global también ha recibido cada vez más atención [3-4]. Basado en la optimización del caos y el método BFGS, se propone un algoritmo híbrido para resolver el problema de optimización con límites restringidos simple (1).

El caos es un fenómeno común en los sistemas no lineales. El movimiento caótico es desordenado e irregular en el nivel macroscópico, con aleatoriedad inherente, no periodicidad e inestabilidad local. En el nivel microscópico, es un movimiento ordenado y regular, no completamente aleatorio, y tiene estructuras geométricas infinitamente anidadas y universales. leyes, no caos. Utilizando la aleatoriedad, la ergodicidad y la regularidad de las variables caóticas, se puede realizar una búsqueda de optimización [5]. Los métodos de optimización caótica pueden saltar fácilmente del óptimo local. Pero algunos estados tardan mucho en alcanzarse, y si el valor óptimo está en estos estados, el tiempo de cálculo debe ser muy largo [5]. Se puede decir que la optimización del caos tiene capacidades de búsqueda global, pero sus capacidades de búsqueda local son ligeramente insuficientes. En la literatura [5], se utiliza tecnología de portadora secundaria, y en la literatura [6], el espacio de búsqueda de variables de optimización se reduce gradualmente para compensar esta debilidad. Este artículo utiliza métodos de búsqueda de caos y BFGS para optimización y solución. Por un lado, la búsqueda caótica se utiliza para ayudar al método BFGS a saltar del óptimo local. Por otro lado, BFGS se utiliza para mejorar la velocidad de convergencia superlineal y las capacidades de búsqueda cerca de la solución, mejorando así la eficiencia de la búsqueda. óptimo.

2 Método de optimización híbrido Chaos-BFGS

2.1 Método BFGS

Como uno de los algoritmos más representativos para resolver problemas de optimización sin restricciones, el método cuasi-Newton es El método BFGS ha atraído mucha atención debido a su completa base teórica matemática, su convergencia superlineal cuando se utiliza búsqueda lineal no exacta y su eficacia en el manejo de problemas prácticos [7-9]. El método cuasi-Newton utiliza información derivada de segundo orden, pero no calcula directamente la matriz de Hesse de la función, sino que utiliza información de paso para construir una serie de matrices definidas positivas para aproximar la matriz de Hesse. Los pasos principales del uso del método BFGS para resolver el problema de optimización sin restricciones min() son los siguientes:

(1) Asigne el valor inicial x0 a la variable, la dimensión de la variable n y la precisión de convergencia ε de el método BFGS, de modo que B0=I (matriz de identidad), k=0, calcule el gradiente g0 en el punto x0.

(2) Tome sk=-Bk-1gk, realice una búsqueda unidimensional a lo largo de sk, determine la longitud óptima del paso αk, obtenga el nuevo punto xk 1=xk αksk y calcule el gradiente gk 1 de xk 1.

(3) Si ||gk 1||≤ε, finalice la búsqueda BFGS y vaya al paso 3; de lo contrario, ejecute (4).

(4) Calcular Bk 1:

(2)

(3)

(5) k=k 1, transferir (2).

2.2 Método de optimización del caos

Cuando utilizamos la búsqueda caótica para resolver el problema (1), primero establecemos una correspondencia uno a uno entre las variables a resolver y las variables caóticas. Luego se genera una variable caótica () con diferentes trayectorias a través de la fórmula de mapeo logístico (4), y se realiza la búsqueda óptima, donde = 4. Se ha demostrado que =4 es un caos "monolítico", que pasa por [0, 1].

(4)

(1) Dado el número máximo de movimientos variables caóticos m; asigne un valor inicial y calcule la suma;

(2).

(3).

(4) Si k

Si, haga,;

Si, y permanezca sin cambios;

Entonces sea k=k 1 Vaya a (2).

Si k gt entonces la búsqueda caótica ha terminado.

2.3 Método de optimización híbrida

El método del caos y el método BFGS se combinan para resolver el problema de optimización mínima global (1) de objetos continuos. Los pasos son los siguientes:

Paso 1 Establecer el caos máximo. El número de búsquedas es m, el número de pasos de iteración es iter = 0 y a la variable se le asigna un valor inicial x0.

El paso 2 busca el punto de partida BFGS y obtiene la solución óptima del método BFGS actual y =.

Paso 3 Si, toma =; si, toma; Si, toma, es un número menor que.

Paso 4: Realice una búsqueda caótica m veces en el punto de partida. Después de la búsqueda caótica, se obtiene la solución óptima y =.

Si

Paso 6: cambie la trayectoria de búsqueda caótica, realice la búsqueda caótica nuevamente, es decir, agregue una ligera perturbación, realice el paso 4 y obtenga la suma de los resultados de la búsqueda. Si

Para el problema máximo global, max se puede transformar para resolver el problema mínimo global min.

La función de la búsqueda caótica en los algoritmos híbridos es la búsqueda macro a gran escala, que permite que el algoritmo tenga un rendimiento de optimización global. La función de la búsqueda BFGS es optimizar la búsqueda local y meticulosamente, y abordar los problemas de la búsqueda a pequeña escala y la aceleración de la búsqueda.

3 ejemplos

Figura 1 Diagrama esquemático de características funcionales Figura 2 Diagrama esquemático de características funcionales

Las siguientes dos funciones muy complejas que se usan comúnmente para probar el Se utiliza el rendimiento de los algoritmos genéticos. Para probar el algoritmo de este artículo:

Esta función se llama función camello y tiene seis mínimos locales (1.607105, 0.5651), (-1.605438 005, -0.5681), (65438 ). 0.796084), (-0.0898, 0.7126) y (0.0898, -0.7126), entre los cuales (-0.0898, 0.7126) y (0.0898, -0. Esta función se llama función de Schaffer, la cual tiene innumerables valores máximos, de los cuales solo (0 , 0) es el valor máximo global y el valor máximo es 1. Hay un círculo de crestas alrededor del valor máximo máximo de esta función, y sus valores son todos 0,990283, por lo que es fácil permanecer en este máximo local valor.La literatura [10] utilizó esta función para examinar el método propuesto en este artículo. El rendimiento del algoritmo genético mejorado basado en movimiento y selección artificial (GAMAS) después de 50 ejecuciones, el óptimo global único de la función se puede encontrar en. En 40 casos, mientras se utiliza el algoritmo híbrido de este artículo, se obtienen 100 puntos iniciales diferentes. La función aleatoria dentro de la computadora se genera automática y aleatoriamente a partir de estos puntos iniciales, y el algoritmo híbrido general puede converger después de 2 a 4 iteraciones. m toma valores diferentes, los resultados del cálculo de la función se muestran en la Tabla 1 y la Tabla 2 respectivamente. El tiempo de cálculo en la tabla se refiere al tiempo de cálculo en una microcomputadora Pentium 133.

Como se puede ver. De la Tabla 2, cuando M = 1500, la probabilidad de encontrar la solución óptima mediante este método es 40. La cantidad de cálculo es menor que la de la Referencia [10]. De manera similar, a partir de 100 puntos de partida del algoritmo híbrido, el algoritmo en. La referencia [5] se utiliza para calcular la optimización de la función 100 veces.

Como criterio de convergencia, la búsqueda del caos se realizó 50.000 veces y el resultado del cálculo fue que se encontró la solución óptima 67 veces, con una probabilidad de 67 y un tiempo de cálculo promedio de 1,2369 s. Incluso si se garantiza que el algoritmo híbrido. convergen a la solución óptima 100 veces, el tiempo de cálculo promedio es de solo 0.2142s (Tabla 1), se puede ver que el algoritmo híbrido es mejor que el método en la literatura [5].

Tabla 1 Resultados del cálculo de M funciones de valores diferentes

______________________________________________________________

m El número de veces para buscar el punto óptimo global y el tiempo promedio de cálculo para buscar la probabilidad óptima.

(-0.0898, 0.7126) (0.0898, -0.7126)

_______________________________________________________________________________________________

1000 44 39 83

3000 53 45 98 0.1955 s

5000 53 47 100

______________________________________________________________________________

Tabla 2 Resultados de cálculo de diferentes funciones de valor m

_______________________________________________________________

mEl número de veces para buscar el punto óptimo global y el tiempo de cálculo promedio para buscar la probabilidad óptima.

__________________________________________________________________________

1500 40 0.1406s

5000 73 73 0.2505 segundos

10000 88 88

50000 100 100 1.6856s

____________________________________________________________________________

4 Análisis de los resultados del cálculo

Se puede ver en las Tablas 1 y 2 que la capacidad de optimización global del algoritmo híbrido aumenta con m Cuando m alcanza un valor μ suficientemente grande, la probabilidad de encontrar el óptimo global puede llegar a 100.

Teóricamente, cuando Mu tiende al infinito, las variables del caos pueden atravesar todos los estados y realmente buscar el punto óptimo con una probabilidad de 1. La función del movimiento caótico M en este artículo es ayudar al método BFGS a saltar del óptimo local y alcanzar otro punto cerca del óptimo local que sea más pequeño que el valor de la función óptima local actual. Las variables del caos no tienen que atravesar todos los estados. Según la ergodicidad del movimiento caótico, se puede ver que para un problema específico, cuando μ alcanza un valor finito específico, la ergodicidad de las variables caóticas se puede simular bien, lo cual también se ha obtenido en la práctica. ejemplos.

Debido al comportamiento y la complejidad de diferentes funciones, el valor Mu es diferente para diferentes funciones, como la función de prueba aquí. Para la misma función, el intervalo de búsqueda aumenta. Con el mismo número de movimientos caóticos, incluso si el punto de partida es el mismo, la probabilidad general de buscar el óptimo global disminuirá. Para garantizar que el algoritmo aún converja al óptimo global con una probabilidad de 1, inevitablemente conducirá a un aumento en Mu. Los resultados intermedios del cálculo de seguimiento muestran que cuando m es lo suficientemente grande, el algoritmo híbrido tiene la capacidad de saltar del óptimo local y continuar buscando el óptimo global.

Además, el tiempo de cálculo del algoritmo híbrido se dedica principalmente a búsquedas caóticas, lo que le otorga al algoritmo híbrido capacidades de búsqueda global.

5 Conclusión

El uso de las características de movimiento de variables caóticas para la optimización tiene una gran capacidad para saltar fuera de la solución óptima local. Este método, combinado con el método BFGS, puede calcular la solución óptima al problema con una cantidad de cálculo aceptable. De hecho, la optimización del caos se puede combinar con algoritmos de descenso generales y no se limita al método BFGS utilizado en este artículo. El mapeo logístico es uno de los métodos efectivos para generar variables caóticas.

El movimiento caótico es diferente del movimiento aleatorio. El caos es un movimiento complejo y aparentemente aleatorio en un sistema determinista debido a la aleatoriedad inherente. El caos no es desorden y desorden, sino más bien un orden sin ciclos. A diferencia del movimiento aleatorio, el movimiento caótico se puede describir mediante características numéricas estadísticas bajo el supuesto de que se experimentan todos los estados. Además, el movimiento caótico no pasa por el mismo estado repetidamente, por lo que la optimización con variables caóticas es mejor que la optimización con variables aleatorias.

La combinación de optimización del caos y método de descenso es un método de optimización global potencial y un método confiable para resolver problemas de optimización de restricciones de límites variables. Cómo mejorar aún más la eficiencia de la búsqueda y cómo aplicar eficazmente la optimización del caos a problemas complejos de optimización restringida son temas que merecen más investigación.

Se está realizando una prueba matemática estricta de la convergencia global del algoritmo.

Referencia

Hu, Chen Bingzhen, He Xiaorong, Shen. Método de recocido simulado para la optimización global de problemas de programación no lineal [J] Journal of Tsinghua University, 37(6), 1997, 5-9.

[2]C A Floudas, A Aggarwal, A R Ciric. Búsqueda óptima global de problemas de PNL y MINLP no convexos [J]. 1989, 13(10), 1117~1132.

Kang Lishan, Xie Yun, You Yayong, et al. Algoritmos paralelos no numéricos (Volumen 1) - Algoritmo de recocido simulado [M Beijing: Science]. Prensa, 1998.

, Kang Lishan, Chen. Algoritmos paralelos no numéricos (Volumen 2) - Algoritmo genético [M Beijing: Science Press, 1998].

, Jiang,. Método de optimización del caos y su aplicación [J]. Teoría y aplicación del control, 14 (4), 1997, 613-615.

Zhang Tong, Wang Hongwei, Wang Zicai. Método de optimización del caos a escala variable y su aplicación [J]. Control y toma de decisiones, 14(3), 1999, 285-287.

Xi Shaolín. Método de optimización no lineal [M]. Beijing: Higher Education Press, 1992.

Shaolin, Zhao. Método de cálculo de optimización [M]. Shanghai: Prensa de Ciencia y Tecnología de Shanghai, 1983.

[9] Peng Wenhui, Tenkolsky, Wetterling, Flannery. Métodos de cálculo numérico en lenguaje C, el arte de la computación científica [M] Segunda edición, Cambridge University Press Society, 1992.

[10]Puerto J C. Desarrollo y evaluación de algoritmos genéticos mejorados basados ​​en migración y selección artificial [J]. IEEE Trans. sistema. Man and Network..1994, 24(1), 73-85.

Método híbrido de optimización no lineal

Resumen: Combinando el método BFGS y el método de optimización del caos, se crea un método. propuso métodos híbridos para resolver problemas de optimización no lineal con restricciones de límites en variables. El método híbrido es un método eficaz para resolver problemas de optimización no convexos. Tiene en cuenta las ventajas inherentes del método de optimización caótica para localizar el óptimo global y la rápida velocidad de convergencia del método BFGS. Los ejemplos numéricos muestran que este método no solo tiene buenas capacidades de búsqueda global, sino que también tiene una velocidad de convergencia mucho más rápida que el método de optimización caótica.