Desarrollo nacional del algoritmo de enjambre de partículas

Introducción al algoritmo de enjambre de partículas (extraído de /newtech)

Los problemas de optimización se encuentran a menudo en el diseño industrial. En última instancia, muchos problemas se pueden atribuir a problemas de optimización. Para este tipo de problema de optimización, la gente ha propuesto muchos algoritmos de optimización, los más famosos son el método de escalada, el algoritmo genético, etc. Hay dos problemas principales en el problema de optimización: uno es encontrar el punto mínimo global y el otro es tener una alta velocidad de convergencia. El método Hill Climbing tiene una alta precisión, pero es fácil caer en mínimos locales. Los algoritmos genéticos son un tipo de algoritmos evolutivos que encuentran soluciones óptimas imitando los mecanismos genéticos y de selección de la naturaleza. Hay tres operadores básicos: selección, cruce y mutación. Sin embargo, la implementación de programación del algoritmo genético es más complicada. Primero, el problema debe codificarse. Después de encontrar la solución óptima, el problema debe decodificarse. Los otros tres operadores también tienen muchos parámetros, como la tasa de cruce y la tasa de mutación, y la selección de estos parámetros afecta seriamente la calidad de la solución, y la mayor parte de la selección actual de estos parámetros se basa en la experiencia. y el Dr. Kennedy propuso un nuevo algoritmo; el algoritmo de optimización de enjambre de partículas (PSO). Este algoritmo ha atraído la atención de la comunidad académica por sus ventajas de fácil implementación, alta precisión y rápida convergencia, y ha demostrado su superioridad en la resolución. problemas prácticos.

Optimización de enjambre de partículas: el algoritmo PSO es un nuevo algoritmo evolutivo (Evolu2tionary Algorithm - EA) desarrollado en los últimos años. El algoritmo PSO es un tipo de algoritmo evolutivo, similar al algoritmo genético. También parte de una solución aleatoria y encuentra la solución óptima mediante iteración. También evalúa la calidad de la solución mediante aptitud. Pero es más simple que las reglas del algoritmo genético. No tiene las operaciones de "Cruce" y "Mutación". Algoritmo genético. Funciona siguiendo el valor de búsqueda óptimo actual para encontrar el óptimo global.

Optimización de enjambre de partículas

1. ) es una tecnología de computación evolutiva ), inventada por el Dr. Eberhart y el Dr. Kennedy. Derivado del estudio del comportamiento de depredación de las aves

PSO es similar a un algoritmo genético y es una herramienta de optimización basada en iteración. El sistema se inicializa como un conjunto de soluciones aleatorias y se busca el valor óptimo mediante iteración. Pero no se utiliza ningún cruce ni mutación en los algoritmos genéticos. En cambio, las partículas buscan las partículas óptimas en el espacio de solución. Los pasos detallados se presentarán en capítulos posteriores.

En comparación con los algoritmos genéticos, la ventaja de PSO es que es simple y fácil de implementar y no requiere ajustar muchos parámetros.

Se ha utilizado ampliamente en optimización de funciones, entrenamiento de redes neuronales, control de sistemas difusos y otros campos de aplicación de algoritmos genéticos

2 Antecedentes: vida artificial

La "vida artificial" es para estudiar. Los sistemas artificiales con ciertas características básicas de la vida. La vida artificial incluye dos aspectos.

1. Estudiar cómo utilizar la tecnología informática para estudiar fenómenos biológicos.

2. problemas informáticos

Ahora nos centramos en la segunda parte. Ya existen muchas técnicas computacionales derivadas de fenómenos biológicos. Por ejemplo, las redes neuronales artificiales son modelos cerebrales simplificados que simulan el proceso de evolución genética. /p>

Ahora discutimos otro tipo de sistema biológico: el sistema social. Más precisamente, la interacción entre una comunidad compuesta de individuos simples y el medio ambiente y entre individuos. También se puede llamar "inteligencia de enjambre" (inteligencia de enjambre). Estos sistemas de simulación utilizan información local para producir comportamientos de enjambre impredecibles.

Por ejemplo, los flotadores y boids, que se utilizan para simular los patrones de movimiento de bandadas de peces y aves, se utilizan principalmente en visión por computadora y asistida por computadora. diseño

En el campo de la inteligencia computacional, existen dos algoritmos basados ​​​​en la optimización de colonias de hormigas y la optimización de enjambres de partículas. utilizado con éxito en muchos problemas de optimización discretos.

El algoritmo de optimización de enjambre de partículas (PSO) también se originó a partir de la simulación de sistemas sociales simples. La idea original era simular el proceso de búsqueda de alimento de una bandada de pájaros. Más tarde se descubrió que PSO es una buena herramienta de optimización.

3. Introducción al algoritmo

Como se mencionó anteriormente, PSO simula el comportamiento depredador de una bandada de pájaros. Considere este escenario: una bandada de pájaros busca comida al azar. En esta zona sólo hay un trozo de comida. Ninguno de los pájaros sabe que la comida está allí. Pero saben a qué distancia está la comida de su ubicación actual. Entonces, ¿cuál es la estrategia óptima para encontrar comida? Lo más sencillo y eficaz es buscar en la zona alrededor del ave más cercana al alimento.

PSO se inspira en este modelo y se utiliza para resolver problemas de optimización. En PSO, la solución a cada problema de optimización es un pájaro en el espacio de búsqueda. Las llamamos "partículas". Todos los ejemplos tienen un valor de aptitud determinado por la función que se optimiza, y cada partícula también tiene una velocidad que determina la dirección y la distancia que vuelan. Luego, las partículas siguen la partícula óptima actual y buscan en el espacio de solución.

PSO se inicializa como un grupo de partículas aleatorias (solución aleatoria). Luego encuentre la solución óptima mediante iteración. En cada iteración, la partícula se actualiza siguiendo dos "valores extremos". La primera es la solución óptima encontrada por la propia partícula. Esta solución se llama valor extremo individual pBest. El otro valor extremo es la solución óptima encontrada actualmente por toda la población. Este valor extremo es el valor extremo global gBest. Además, no se puede utilizar toda la población sino solo una parte de ella como vecina de las partículas, entonces el valor extremo entre todos los vecinos es el valor extremo local.

Cuando se encuentran estos dos valores óptimos, la partícula actualiza su velocidad y nueva posición según la siguiente fórmula

v[] = v[] + c1 * rand() * (pbest[] - presente[]) + c2 * rand() * (gbest[] - presente[]) (a)

presente[] = presente[] + v[] (b )

v[] es la velocidad de la partícula, persistente[] es la posición actual de la partícula. pbest[] y gbest[] son ​​como se definió anteriormente rand () es un valor aleatorio entre (0). , 1) Número c1, c2 son factores de aprendizaje. Generalmente c1 = c2 = 2.

El pseudocódigo del programa es el siguiente

Para cada partícula

____Inicializar partícula

END

Hacer

____Para cada partícula

________Calcular valor de aptitud

________Si la aptitud El valor es mejor que el mejor valor de aptitud (pBest) de la historia

____________establece el valor actual como el nuevo pBest

____End

____Elige la partícula con el mejor valor de aptitud de todas las partículas como gBest

____Para cada partícula

________Calcular la velocidad de las partículas según la ecuación (a)

_______Actualizar la posición de las partículas según la ecuación (b)

____End

____End

____ p>

Mientras no se alcance el criterio de iteraciones máximas o error mínimo

La velocidad de las partículas en cada dimensión se limitará a una velocidad máxima Vmax. Si la velocidad actualizada de una determinada dimensión excede la configuración del usuario Vmax, entonces la velocidad de esta dimensión se limita a Vmax

4.

La mayoría de las técnicas de computación evolutiva utilizan el mismo proceso

1. Inicialización aleatoria de la población

2 Calcule el valor de aptitud (valor de aptitud) para cada individuo en. la población. El valor de aptitud está directamente relacionado con la distancia desde la solución óptima

3. La población se replica según el valor de aptitud

4 Si se cumple la condición de terminación, deténgase. De lo contrario, vaya al paso 2.

De los pasos anteriores, podemos ver que hay muchos PSO y GA *** Lo mismo. Ambos inicializan aleatoriamente la población, ambos utilizan valores de aptitud para evaluar el sistema y ambos realizan ciertas búsquedas aleatorias basadas en los valores de aptitud. Ninguno de los sistemas garantiza que se encontrará la solución óptima.

Sin embargo, PSO no tiene operaciones genéticas como cruce y mutación, sino que determina la búsqueda en función de su propia velocidad. Otra característica importante de las partículas es que tienen memoria.

En comparación con los algoritmos genéticos, el mecanismo de intercambio de información de PSO es muy diferente. En los algoritmos genéticos, los cromosomas comparten información entre sí, por lo que el movimiento de toda la población es relativamente uniforme. En PSO, solo gBest (o lBest) proporciona información a otras partículas, que es un flujo de información unidireccional. En la mayoría de los casos, todo el proceso de búsqueda y actualización es un proceso que sigue la solución óptima actual. , todas las partículas pueden converger a la solución óptima más rápido

5 Red neuronal artificial y PSO

La red neuronal artificial (ANN) es una simulación de análisis cerebral. Un modelo matemático simple del proceso. El algoritmo Backcast es el algoritmo de entrenamiento de redes neuronales más popular. Recientemente, muchos estudios han comenzado a utilizar tecnología de computación evolutiva para estudiar varios aspectos de las redes neuronales artificiales.

La computación evolutiva se puede utilizar para estudiar tres aspectos de las redes neuronales: pesos de conexión de red, estructura de red (topología de red, función de transferencia) y algoritmos de aprendizaje de red.

Sin embargo, la mayor parte del trabajo en esta área se centra en los pesos de las conexiones de red y la topología de la red. En GA, los pesos y/o la topología de la red generalmente se codifican como cromosomas, y la selección de la función de aptitud generalmente se determina en función del propósito de la investigación. Por ejemplo, en problemas de clasificación, la tasa de clasificación errónea se puede utilizar como valor de aptitud.

La ventaja de la computación evolutiva es que puede manejar algunos ejemplos que los métodos tradicionales no pueden manejar, como funciones de transferencia de nodos indiferenciables o la ausencia de información de gradiente. Pero la desventaja es que el rendimiento no es especialmente bueno en algunas cuestiones. 2. La codificación de los pesos de la red y la selección de operadores genéticos son a veces problemáticas.

Recientemente, se han publicado algunos artículos que utilizan PSO para reemplazar el algoritmo de retropropagación para entrenar redes neuronales. Las investigaciones muestran que PSO es un algoritmo de red neuronal prometedor. PSO es más rápido y puede obtener mejores resultados. Y los algoritmos genéticos no encuentran problemas.

Aquí hay un ejemplo simple para ilustrar el proceso de entrenamiento de la red neuronal PSO. Este ejemplo utiliza el conjunto de datos IRIS, una función de referencia para problemas de clasificación. (Iris es una planta de iris) En el registro de datos, cada conjunto de datos contiene cuatro atributos de las flores de Iris: longitud del sépalo, ancho del sépalo, longitud del pétalo y ancho del pétalo. De esta manera, cada una de las tres flores diferentes tiene 50 conjuntos de datos. Hay un total de 150 conjuntos de datos o patrones.

Utilizamos una red neuronal de 3 capas para la clasificación. Ahora hay cuatro entradas y tres salidas. Entonces, la capa de entrada de la red neuronal tiene 4 nodos y la capa de salida tiene 3 nodos. También podemos ajustar dinámicamente el número de nodos de la capa oculta, pero aquí asumimos que la capa oculta tiene 6 nodos. También podemos entrenar otros parámetros en la red neuronal. Pero aquí sólo estamos determinando el peso de la red. Las partículas representan un conjunto de pesos de la red neuronal, que deben tener 4*6+6*3=42 parámetros. El rango de pesos se establece en [-100, 100] (esto es solo un ejemplo, es posible que se requieran ajustes experimentales en situaciones reales. Después de completar la codificación, debemos determinar la función de adaptación). Para problemas de clasificación, enviamos todos los datos a la red neuronal y los pesos de la red están determinados por los parámetros de las partículas. Luego registre el número de todas las clasificaciones erróneas como el valor de aptitud de esa partícula. Ahora usamos PSO para entrenar la red neuronal para obtener el menor número posible de clasificaciones erróneas. La propia PSO no tiene muchos parámetros que ajustar. Por lo tanto, en el experimento, solo es necesario ajustar el número de nodos y el rango de pesos en la capa oculta para lograr mejores resultados de clasificación.

6. Configuración de parámetros de PSO

Del ejemplo anterior podemos ver que hay dos pasos importantes en el proceso de aplicación de PSO para resolver problemas de optimización: codificación y adecuación de las soluciones de problemas.

Una ventaja de PSO es que utiliza codificación de números reales y no necesita codificación binaria como los algoritmos genéticos (ni utilizar operaciones genéticas en números reales. Por ejemplo, para el problema f(x) = x1^2 + x2^2 Para resolver +x3^2, las partículas se pueden codificar directamente como (x1, x2, x3) y la función de aptitud es f (x). Luego podemos usar el proceso anterior para optimizar esto. El proceso de optimización es un proceso iterativo, la condición de aborto generalmente se establece para alcanzar el número máximo de ciclos o el error mínimo.

No hay muchos parámetros que deban ajustarse en PSO. Estos parámetros y configuraciones empíricas son. se enumeran a continuación

Número de partículas: generalmente, es de 20 a 40. De hecho, para la mayoría de los problemas, 10 partículas son suficientes para lograr buenos resultados, pero para problemas más difíciles o tipos de problemas específicos, el número de partículas puede ser 100 o 200

La longitud de la partícula: Esto está determinado por el problema de optimización, que es la longitud de la solución del problema

El rango de la partícula: está determinada por el problema de optimización y se puede establecer un rango diferente para cada dimensión.

Vmax: la velocidad máxima determina la distancia máxima de movimiento de las partículas en un ciclo. Generalmente se establece en el ancho del rango. Por ejemplo, en el ejemplo anterior, la partícula (x1, x2, x3) x1 pertenece a [-10, 10], entonces el tamaño de Vmax es 20

Factores de aprendizaje: c1 y c2 son. suele ser igual a 2. Sin embargo, existen otros valores en la literatura, pero generalmente c1 es igual a c2 y el rango está entre 0 y 4.

Condiciones de parada: número máximo de ciclos y requisitos mínimos de error. Por ejemplo, en el ejemplo de entrenamiento de red neuronal anterior, el error mínimo se puede establecer en 1 clasificación de error y el ciclo máximo en 2000. Esta condición de terminación está determinada por el problema específico

Global. PSO y PSO local: presentamos dos versiones del algoritmo de optimización del enjambre de partículas: la versión global y la versión local. La primera es rápida pero a veces cae en el óptimo local. La segunda converge más lentamente pero es difícil alcanzar el óptimo local. En aplicaciones prácticas, primero puede usar el PSO global para encontrar el resultado aproximado y luego usar el PSO local para buscar.

Otro parámetro es el peso de inercia, propuesto por Shi y Eberhart, si está interesado. consulte su artículo de 1998 (título: Un optimizador de enjambre de partículas modificado)