Implementación del algoritmo PSO original

[pic 1]

UNIVERSIDAD DE GUANAJUATO

Tópico Selecto en Inteligencia Artificial

Inteligencia de Enjambres

Dr. Carlos Hugo García Capulín

Tarea 02:

Implementación del algoritmo PSO original

Guillermo Ramírez Carpio

14/09/21

Introducción

El algoritmo de Optimización por Enjambres de Partículas (PSO) es uno de los algoritmos más conocidos en los métodos de Inteligencia de Enjambre. Como varios métodos, el algoritmo PSO no es perfecto y lleva varios inconvenientes que hacen que termine en fenómeno conocido como explosión de partículas.

El truncamiento de velocidad o Velocity Clamping es una alternativa para lidiar con uno de los grandes inconvenientes del PSO, la aceleración de la partícula. Esta versión del PSO es utilizada para que la velocidad de la partícula sea alterada o penalizada en caso de que su posición se encuentre cerca de los límites de nuestro espacio de búsqueda.

Esta práctica implementa la versión del algoritmo PSO Standard utilizando el lenguaje de programación C.

Desarrollo

Como sabemos del algoritmo original PSO se busca un valor optimo a través de una función fitness mediante el movimiento de un conjunto N de partículas dentro de un espacio definido por el espacio dimensional.

Dentro del programa, las partículas están constituidas por:

• Un vector posición de N posiciones.
• Un vector velocidad de N posiciones.
• Un vector que almacena la mejor posición histórica del particular en base a su evaluación en la función fitness.

Para la actualización de la velocidad de la partícula, y por ende su posición, se utilizó un proceso iterativo definido por:

[pic 2]

Donde

•  y  son constantes con valores predefinidos en base a programas de pruebas o benchmarks.[pic 3][pic 4]
•  y  son factores aleatorios comprendidos entre 0 y 1 para brindar variabilidad.[pic 5][pic 6]
•  vector d dimensional de la velocidad actual de la i-ésima partícula.[pic 7]
•  vector d dimensional de la mejor posición histórica de la i-ésima partícula.[pic 8]
• vector d dimensional de la posición actual de la i-ésima partícula.[pic 9]
•  número de iteraciones.[pic 10]
•  representa la tendencia de un individuo a seguir explorando la misma dirección.[pic 11]

• [pic 12] representa la tendencia a permanecer próximo a posiciones que dieron un buen resultado pasado.
• [pic 13]representa la influencia que ejercen el resto de los individuos o la imitación del mejor individuo conocido.

Después la nueva posición se obtiene:

[pic 14]

Para llevar a cabo el truncamiento de velocidad, y evitar o postergar la explosión de enjambre se especifica un límite de velocidad definido para el enjambre expresado por:

[pic 15]

[pic 16]

Donde:

•  y  son los límites del espacio de búsqueda.[pic 17][pic 18]

• K es un factor de velocidad entre 0.1 y 1.0 predefinido en base a programas de pruebas o benchmarks.

Donde se establece el truncamiento como:

[pic 19]

Acotando todas aquellas velocidades que salgan del límite establecidos.

Dentro del cambio de velocidad, el factor K intercede directamente en el algoritmo ayudando a aproximarse a un valor de convergencia o llegar a una explosión de enjambre. Al utilizar valores pequeños las partículas se desplazan lentamente por lo cual la convergencia puede llevar muchas iteraciones, mientras que con valores grandes se hace complicado la precisión en los resultados.

Código del programa implementado

Las variables lower, higher son los límites de nuestro espacio dimensional, en este caso para 2 dimensiones. La constante PARTICLES define el número de partículas en nuestro enjambre. PARAMETER es dado en base a las dimensiones de nuestro programa, en este cado 2.

Las variables low_v y high_v son los límites de las velocidades para el truncamiento

#define PARTICLES 10

#define PARAMETERS 2

const unsigned int MAX_I_NUM = 300;

const float lower = -10;

const float higher = 10;

const float low_v = -1.0;

const float high_v = 1.0;

Estructura PARTICLE que contiene los arreglos que almacenan la velocidad Vi y la posición Xi actual de la partícula, la posición Pi que representa la mejor posición en base al valor de la función de activación, el valor actual en base a la función a la posición al evaluado por la función fitness, y Pfit que representa la mejor posición cuyo valor es más aproximado a la función de convergencia.

typedef struct PARTICLE {

    float Xi[PARTICLES];//vector -> position

    float Vi[PARTICLES];//vector -> velocity

    float Pi[PARTICLES];// vector -> best historical position     

    float Xfit; //Fitness value for the random generate position Xi    

    float Pfit; //Fitness value for the random generate position Pi    

} PARTICLE;

Estructura SWARM que contiene el conjunto de partículas utilizadas, además de diversos parámetros y variables de acceso público para utilizar dentro del programa. Incluyendo las velocidad máxima y mínima para realizar el truncamiento.

...