Domingo Cortés

1. Resumen

En este documento persigue dos cosas. Por un lado se describe en que consiste el método de optimización por enjambre de partículas y por otro se presentan dos implementaciones del mismo con el objetivo de ilustrar como hacer programas que después sean fáciles de modificar y que otros puedan entender.

La primera implementación emplea una combinación de programación funcional e imperativa, mientras que la segunda implementación se hace en base a la programación orientada a objetos. Se hace énfasis en lo conveniente que es crear términos (o palabras o conceptos) antes de programar propiamente el método. Si estos términos son adecuados entonces el método será fácilmente expresable. Los aprendices de programación tratan de expresar un método directamente en el lenguaje (usando sólo asignaciones, ciclos y condicionales) resultando en programas difíciles de entender por otros y de modificar.

2. Introducción

Resolver un problema de optimización es encontrar el mínimo (o máximo) de una función. Por ejemplo, considere el problema de minimizar

\begin{equation} f(x,y)= x^{2} + y^{2}-x*y-3x+4y-5 \end{equation}

El problema consiste en encontrar valores \(x,y\) tal que la función tenga un mínimo valor.

Los problemas de optimización pueden ser sencillos o muy complejos, algunos incluso, no se pueden resolver de forma analítica. El hecho es que muchos problemas de ingeniería, se pueden poner como problemas de optimización. Es por ello que se sigue investigando en el área. En general, la función a minimizar se le conoce como función objetivo o función de costo. En algunos algoritmos de optimización computacionales, se le conoce como función de fitness.

3. Descripción del algoritmo Optimización por Enjambre de Partículas

El algoritmo de optimización por enjambre de partículas está inspirado en el comportamiento de grupo en los animales observado en enjambres, rebaños, parvadas, cardúmenes, manadas, etc. Vea por ejemplo Parvada de pájaros. Generalizando estos comportamientos de grupo, se habla de un enjambre de partículas. Así a este algoritmo se le conoce como Optimización por Enjambre de Partículas (Particle Swarm Optimization: PSO)

En la PSO se parte de generan de alguna manera un número de soluciones no óptimas. A cada una de estas soluciones se le considera como la posición de una partícula. Al conjunto de partículas se le considera un enjambre. La idea del PSO es mover el enjambre para que sus partículas se vayan aproximando a una solución óptima. Mover el enjambre significa mover cada una de las partículas. Así cada partícula debe cambiar buscando que cada vez esté más cerca de la solución óptima.

¿Qué significa mover una partícula? Recuerde que la posición de una partícula es una solución no óptima. Suponga que una solución (no óptima) de un problema está definida por un conjunto de parámetros, entonces la posición de una partícula está definida por un vector de parámetros. Mover una partícula es cambiar su posición, es decir, cambiar sus parámetros buscando que después del cambio la partícula esté más cerca de la solución óptima. Una idea simple es mover la partícula en la dirección del óptimo. Sin embargo, no se conoce el óptimo y por lo tanto tampoco en que dirección está.

Otra idea es mover una partícula en todas direcciones y encontrar aquella dirección en que la función de costo disminuya en mayor medida, ya que esa es la dirección del óptimo. Eso es lo que se llama el método de la fuerza bruta y no se usa porque generalmente requiere un costo computacional enorme aún en el caso de que cada solución sólo necesite unos pocos parámetros.

El PSO mueve cada partícula en la dirección que resulta de combinar tres direcciones:

La dirección inercial. Suponga que la partícula se ha movido antes, entonces se puede calcular un vector velocidad que es la diferencia entre la posición actual y la última. La dirección inercial es la dirección del vector velocidad.
La dirección cognitiva. Suponga qué se lleva el registro de la mejor posición que ha tenido la partícula. La resta de la mejor posición que ha ocupado la partícula y la posición actual es un vector que apunta hacia la mejor posición que ha ocupado la partícula. La dirección cognitiva es la dirección de este vector.
La dirección social. Suponga que se lleva un registro de la mejor posición que ha ocupado el enjambre. La resta entre la mejor posición que ha ocupado el enjambre y la posición actual de la partícula es un vector que apunta hacia la mejor posición del enjambre. La dirección social es la dirección de este vector.

Si para la partícula \(i\) se define:

\(x_{i}(k)\) La posición actual de la partícula.
\(x_{i}(k-1)\) La posición previa de la partícula.
\(x_{ib}(k)\) La mejor posición de la partícula hasta el momento.
\(s_{b}(k)\) La mejor posición del enjambre hasta el momento.

entonces se puede calcular

La dirección inercial: \(x_{i}(k)-x_{i}(k-1)\)
La dirección cognitiva: \(x_{ib}(k)-x_{i}(k)\)
La dirección social: \(s_{b}(k)-x_{i}(k)\)

Si escalamos estas direcciones por constantes, haciendo un símil con la física podemos hablar de velocidades, así tenemos

La velocidad en la dirección inercial: \(v_{i_{inr}}(k)=w(x_{i}(k)-x_{i}(k-1))\)
La velocidad en la dirección cognitiva: \(v_{i_{cgn}}(k)=k_{cog}(x_{ib}(k)-x_{i}(k))\)
La velocidad en la dirección social: \(v_{i_{scl}}(k)=k_{scl}(s_{b}(k)-x_{i}(k))\)

donde \(w\), \(k_{cgn}\) y \(k_{scl}\) se conocen como constantes inercial, cognitiva y social respectivamente.

Se puede decir ahora que la partícula \(i\) se mueve a una velocidad

\begin{equation} \label{eq:vel} v_{i}(k)=v_{i_{inr}}(k) + v_{i_{inr}}(k) + v_{i_{inr}}(k) \end{equation}

Así la posición de la partícula \(i\) en el instante \(k+1\) está dado por \(x_{i}(k+1)=x_{i}(k)+v_{i}(k)\). Poniendo esta expresión sólo en términos de posiciones resulta

\begin{equation} x_{i}(k+1) = x_{i}(k) w \left( x_{i}(k)-x_{i}(k-1) \right) + k_{cgn} \left( x_{ib}(k)-x_{i}(k) \right) + k_{scl} \left( s_{b}(k)-x_{i}(k) \right) \end{equation}

Note que es conveniente expresar la siguiente posición en términos de posiciones anteriores (de la propia u otras partículas) ya que las posiciones son los parámetros de la soluciones (no óptimas) conocidas. Al mover una partícula estamos generando una nueva solución a partir de las soluciones conocidas.

Por alguna razón en la bibliografía en la expresión de la velocidad \ref{eq:vel} en lugar de \(v(k)\) se habla de \(v(k+1)\). Se considera aquí que no hay una justificación para ello.

En resumen la PSO podría describirse así (una mayor sangría significa subtarea). Dado un problema de optimización:

Crear el enjambre
- Crear cada partícula
Si no se cumpla la condición de paro
- Mover el enjambre
  - Mover cada partícula
- Repetir

4. Implementación

4.1. Ideas generales

La PSO es interesante porque es simple y a la vez útil. Implementar la PSO puede ser ilustrativo para aprender como programar. En esta sección se el desarrollo de un programa que implementa la PSO.

Siguiendo el enfoque usado en el libro "Structure and Interpretation of Computer Programs: SICP", de no buscar la traducción de la solución de un problema a un lenguaje de programación determinado, sino implementar en ese lenguaje las palabras (ideas, términos, conceptos) en las que la solución del problema se pueda expresar fácilmente. Es decir, no tratar de expresar la solución de un problema en un lenguaje de programación sino de crear un lenguaje para expresar la solución.

Por ello, para desarrollar el programa hay que pensar cuales son las palabras (ideas) principales del algoritmo. Podemos pensar en las siguientes:

Enjambre
Partícula
Problema de optimización
Mover enjambre
Mover partícula
Mejor posición de la partícula
Mejor posición del enjambre
Generar posiciones iniciales

Note que en la descripción del algoritmo se habló de un problema de optimización pero no se precisó cual es el problema. Esto es posible porque el algoritmo es bastante general. Para mantener esta generalidad en el programa es conveniente separar la implementación del algoritmo de un problema particular. Por ello de aquí en adelante nos referiremos al 'problema' como la parte del programa que cambiaría de un problema a otro.

Para separar el algoritmo del problema hay que precisar que partes del algoritmo dependen del problema. La PSO necesita del 'problema' dos cosas

La creación de partículas. Crear el enjambre significa crear partículas. Crear partículas es crear su posición inicial. La posición inicial de una partícula son los parámetros de una solución (no óptima) del problema. Es el 'problema' el que debe saber crear estas soluciones.
El fitness de una posición. El fitness es el valor de la función de costo que se desea minimizar (entre más pequeño mejor); note que el fitness es un número real positivo. Para mover una partícula se necesita saber la mejor posición de la partícula que ha tenido y la mejor posición que ha tenido el enjambre. Es decir se requiere saber si una posición es mejor que otra. Esta comparación se hace a través del fitness de cada posición, la que tenga menor fitness es mejor. El 'problema' debe saber como calcular el fitness asociado a una posición.

De las observaciones anteriores se puede expresar la PSO con las siguientes 'palabras'

Problema
Partícula
Enjambre
PSO

El 'Problema' debe poder crear posiciones no óptimas y calcular el fitnes de una posición.

Una partícula debe poder moverse. Para ello debe conocer además de su posición actual, su posición anterior y la mejor posición que ha ocupado hasta el momento. Note que la partícula debe saber que es una 'mejor posición'. Esto se hace mediante el fitness. El cálculo del fitness le corresponde al 'problema'. Para no calcular el fitness de una posición varias veces es conveniente que a cada posición se le asocie su fitness. En resumen la partícula debe almacenar:

La posición actual y su fitness
La posición previa y su fitness
La mejor posición hasta el momento y su fitness

Para moverse, la partícula debe conocer además la mejor posición del enjambre. Esa se la debe reportar el enjambre. En cada movimiento de la partícula se deben actualizar las tres posiciones y sus respectivos fitness. La partícula debe saber como crearse.

El enjambre contiene partículas y mantiene información de cual ha sido la mejor posición hasta el momento. El enjambre debe poder moverse. Note que mover el enjambre significa mover cada una de las partículas. En cada movimiento del enjambre debe actualizarse la mejor posición del enjambre. El enjambre debe saber como crearse.

La PSO debe crear un enjambre y moverlo hasta que una condición de paro se cumpla. Crear un enjambre significa crear varias partículas. Crear partículas significa crear soluciones no óptimas.

Es conveniente guardar las constantes necesarias de la PSO en un sólo lugar. Esta información consiste del número de partículas del enjambre, número máximo de generaciones (movimientos del enjambre), valor de la constantes de inercia, cognitiva y social.

A continuación se presentan dos implementaciones concretas de estas ideas usando sendos estilos de programación

4.2. Implementación usando un estilo de programación funcional-imperativa

La implementación presentada en esta sección está organizada usando funciones. Las funciones no cambian los objetos que reciben, en este sentido se habla de programación funcional. Sin embargo, al interior de cada función si es usa expresiones imperativas (asignación de variables) por lo que los objetos creados al interior de las funciones si podrían cambiar. La mayoría de los objetos en esta implementación están representados por tuplas para evitar que puedan ser cambiados por las funciones. Sólo las soluciones están representadas con "np.array()". Más adelante se explicará porque.

El usar constructores y selectores para cada tipo de dato aísla la representación del dato de su uso, haciendo que sea más fácil la modificación y/o extensión del programa (ver cap. 2 de SICP)

4.2.1. Los datos del método

Para encapsular la información del método en un solo lugar se representa con una tupla referida como 'spo_data'. Hay una función que imprime estos datos por si se requiere

# ==========   spo_data  ========== 
def make_spo_data(num_particles, max_generations, w, k_cgn, k_scl):
    return (num_particles, max_generations, w, k_cgn, k_scl)

def num_particles_spo_data(spo_data):
    return spo_data[0]

def max_generations_spo_data(spo_data):
    return spo_data[1]

def w_spo_data(spo_data):
    return spo_data[2]

def k_cgn_spo_data(spo_data):
    return spo_data[3]

def k_scl_spo_data(spo_data):
    return spo_data[4]

def print_spo_data(spo_data):
    print("Número de partículas: ", num_particles_spo_data(spo_data))
    print("Número de máximo de generaciones: ", max_generations_spo_data(spo_data))
    print("Constante inercial: ", w_spo_data(spo_data))
    print("Constante cognitiva: ", k_cgn_spo_data(spo_data))
    print("Constante social: ", k_scl_spo_data(spo_data))
    print("\n")

4.2.2. El 'problema'

Para evaluar el método se usará la función \(f(x,y)=x^{2}+y^{2}\) como función a minimizar (función de fitness). Se sabe que esta función tiene un mínimo global en \((0,0)\). La posición de la partícula son simplemente las coordenadas \((x,y)\) de un punto.

El 'problema' está definido por dos funciones 'problem_make_sol()' que genera una posición (solución no óptima) y 'problem_cal_fitness()' que recibe una posición (solución) y devuelve un fitness. Un problema está especificado por estas dos funciones. Así que para otro problema sólo habría que modificar estas funciones. Note que una posición está representada por un arreglo.

# ==========   Problem  ========== 
def problem_make_sol():   
    a,b = [-10, 10]
    x =  uniform(a, b)
    y =  uniform(a, b)
    return np.array( [x, y] )
    
def problem_calc_fitness(pos):
    x,y=pos
    fit = x*x + y*y
    return fit

4.2.3. La partícula

Una partícula se representa con una tupla de 6 elementos referida como 'particle':

Posición actual
Fitness de la posición actual
Posición previa
Fitness de la posición previa
Mejor posición hasta el momento
Fitness de la mejor posición hasta el momento.

Tres funciones organizan a la partícula:

init_particle() que crea una partícula llamando a las funciones que definen el 'problema'. Al principio la posición de la partícula, la posición previa y la mejor posición son la misma. Esto quiere decir que al inicio la velocidad inercial y la cognitiva de la partícula son cero. La única velocidad distinta de cero es la velocidad social. Como consecuencia, al inicio todas las partículas se mueven en la dirección de la mejor partícula. Note que en el caso de la mejor partícula del enjambre la velocidad social también es cero, por lo que no se mueve.
mov_particle() que mueve a la partícula. En esta función está el núcleo del método. Note que casi todos los datos necesarios para mover la partícula están contenidos en la propia partícula. Del exterior sólo necesita la mejor posición del enjambre y las constantes inercial, cognitiva y social.
print_particle que muestra todos los datos de una partícula

Note que cuando se mueve una partícula no se modifica la anterior sino que se crea una nueva a partir de la anterior.

# ==========   particle  ========== 
def make_particle(pos,fit,prev_pos,prev_fit,best_pos,best_fit):
    return (pos,fit, prev_pos,prev_fit, best_pos,best_fit)

def pos_particle(particle):
    return particle[0]

def fit_particle(particle):
    return particle[1]

def prev_pos_particle(particle):
    return particle[2]

def prev_fit_particle(particle):
    return particle[3]

def best_pos_particle(particle):
    return particle[4]

def best_fit_particle(particle):
    return particle[5]

def init_particle():
    pos = problem_make_sol()
    fit = problem_calc_fitness(pos)
    prev_pos = pos
    prev_fit = fit
    best_pos = pos
    best_fit = fit
    return make_particle(pos,fit,prev_pos,prev_fit,best_pos,best_fit)

def move_particle(particle,swarm_best_pos,spo_data):
    # extract necesary constants
    w = w_spo_data(spo_data) 
    k_cgn = k_cgn_spo_data(spo_data)
    k_scl = k_scl_spo_data(spo_data)
    # extract particle data
    pos      = pos_particle(particle)
    fit      = fit_particle(particle)
    prev_pos = prev_pos_particle(particle)
    best_pos = best_pos_particle(particle)
    best_fit = best_fit_particle(particle)
    # calc partial and total velocities
    vel_inercial = w * (pos - prev_pos)
    vel_cognitiva = k_cgn * (best_pos - pos)
    vel_social = k_scl * (swarm_best_pos - pos)
    vel = vel_inercial + vel_cognitiva + vel_social
    # save the current position as the prev position
    prev_pos = pos
    prev_fit = fit
    # changes the current position and fitness
    pos = pos + vel
    fit = problem_calc_fitness(pos)
    # update best_pos and best_fit if necessary
    if fit < best_fit:
        best_pos = pos
        best_fit = fit
    # make a particle with the new particle data
    return make_particle(pos,fit,prev_pos,prev_fit,best_pos,best_fit)
    
def print_particle(particle):
    # print current, previous and best position and its associated fitness
    print(pos_particle(particle), fit_particle(particle))
    print(prev_pos_particle(particle), prev_fit_particle(particle))
    print(best_pos_particle(particle), best_fit_particle(particle))
    print()

4.2.4. El enjambre

El enjambre está representado por una tupla de dos elementos:

El conjunto de partículas que a la vez es una tupla de partículas
La mejor partícula hasta el momento.

El enjambre está organizado por 4 funciones:

init_swarm que crea el enjambre construyendo el número especificado de partículas y llamando a update_best_particle para calcular cual es la partícula con mejor posición.
move_swarm que mueve el enjambre moviendo cada una de las partículas y llamando a update_best_particle para actualizar la partícula con mejor posición.
update_best_particle que calcula cual es la partícula del enjambre con la mejor posición.
print_swarm que muestra los datos del enjambre, pidiendo a cada una de las partículas que se imprima y después mostrando la mejor partícula del enjambre.

Note que cuando se mueve del enjambre no se modifica el anterior sino que se crea uno nuevo a partir del anterior.

# ==========   swarm  ========== 
def make_swarm(particles,best_particle):
    return (particles,best_particle)

def particles_swarm(swarm):
    return swarm[0]

def best_particle_swarm(swarm):
    return swarm[1]

def best_pos_swarm(swarm):
    return best_pos_particle(best_particle_swarm(swarm))

def best_fit_swarm(swarm):
    return best_fit_particle(best_particle_swarm(swarm))

def init_swarm(spo_data):
    #extract necessary constants
    num_particles = num_particles_spo_data(spo_data)
    #create particles 
    particles = tuple([init_particle() for i in range(num_particles)])
    # create a temporary swarm with particles and the first_particle
    tmp_swarm = make_swarm(particles,particles[0])
    # return a swarm with particles and best particle
    return update_best_particle(tmp_swarm)

def move_swarm(swarm,spo_data):
    # estract particles, best_particle and swarm best position
    particles = particles_swarm(swarm)
    best_particle = best_particle_swarm(swarm)
    sbp = best_pos_swarm(swarm)
    # produce new particles
    particles = tuple([move_particle(particle,sbp,spo_data) for particle in particles])
    # create a temporary swarm with new particles but old best_particle
    tmp_swarm = make_swarm(particles,best_particle)
    # update the best particle and return a new swarm
    return update_best_particle(tmp_swarm)

def update_best_particle(swarm):
    particles = particles_swarm(swarm)
    best_particle_found = particles[0]
    for particle in particles:
        if best_fit_particle(particle) < best_fit_particle(best_particle_found):
            best_particle_found = particle
    return make_swarm(particles,best_particle_found)

def print_swarm(swarm):
    particles = particles_swarm(swarm)
    print("\n")
    print("printing swarm")
    print("particles:")
    for particle in particles:
        print_particle(particle)
    print("swarm best postion and fitness:")
    print(best_pos_swarm(swarm),best_fit_swarm(swarm))

4.2.5. El método PSO

Teniendo las ideas de problema, partícula y enjambre, el método se puede expresar de manera sencilla en una sola función que crea un enjambre, que a su vez crea a la partículas. Después mueve al enjambre hasta que una condición de paro se cumple. El código puede ser:

def spo(spo_data):
    swarm = init_swarm(spo_data)
    print_swarm(swarm)
    gen_num = 0
    while(not stop_condition(swarm, gen_num, spo_data)):
        swarm = move_swarm(swarm,spo_data)
        gen_num += 1
    print_swarm(swarm)
    return best_particle_swarm(swarm)

Note que las dos llamadas a print_swarm() no son necesarias en el código, están ahí sólo para conocer como es la primera generación y la última. La función va contando el número de generaciones y para cuando la condición de paro es verdadera. Se devuelve la mejor partícula de la última generación del enjambre.

En la función anterior se usa una función que determina si una condición de paro se cumplió. Note que como no se sabe cual es el mínimo que se está buscando, no se puede saber si ya se llegó al mínimo. Así esta condición de paro no puede examinar directamente si ya es está en un mínimo o no. Algo que se podría hacer es saber si en las últimas n generaciones el mejor fitness ha cambiado significativamente. Para ello habría que llevar un registro de los últimos mejores fitness (y sus partículas). Por el momento se presenta una condición de paro que sólo examina si ya se llegó al número máximo de generaciones.

def stop_condition(swarm, generation_num, spo_data):
    max_generations = max_generations_spo_data(spo_data)
    return (generation_num >= max_generations)

Esta función stop_condition() no necesita los datos del enjambre, pero se incluyen porque en una implementación más elaborada sí se necesitarían.

El código para evaluar la implementación también es sencillo

  data = make_spo_data(5, 25, 1, 0.3, 0.3)
  print("Datos empleados:")
  print_spo_data(data)

  posible_minimo = spo(data)

  print("Resultados:")
  print(posible_minimo)

4.3. Implementación con programación orientada a objetos.

La programación orientada a objetos (OOP) disminuye el problema del estado (variables que son cambiadas por más de una función) en los programas. En este tipo de programación los datos son encapsulados junto con las funciones que los pueden modificar. Así el estado, es guardado dentro de los objetos y solo pueden ser cambiados por medio de 'mensajes' que se envían al objeto. Los mensajes no son más que funciones que sólo actúan sobre los datos del objeto. A estas funciones se les conoce comúnmente como métodos. Las ideas principales de este tipo de programación se describen en el capítulo 3 de SICP.

Al margen de las particularidades de la OOP, el principio de acercar el lenguaje a la solución se mantiene. Para desarrollar la PSO en OOP se usarán las mismas ideas que en la sección anterior: problema, partícula, enjambre. Además de encapsular también los datos que es necesario especificar para el método.

4.3.1. Los datos del método.

Los datos del método se encapsulan en la clase Spo_data() note que la clase no tienen métodos, es solo para almacenar datos de forma encapsulada

class Spo_data():
    def __init__(self,num_particles, max_generations, w, k_cgn, k_scl):
        self.num_particles = num_particles
        self.max_generations = max_generations
        self.w = w
        self.k_cgn = k_cgn
        self.k_scl = k_scl

4.3.2. El 'problema'

Las dos funciones que el 'problema' debe proveer ahora están encapsuladas por medio de la clase Optimization_problem(). Un objeto de esta clase no almacena datos, sólo consistiría en dos funciones.

class Optimization_problem_a():
    def __init__(self):
        pass
    
    def make_sol(self):
        a,b = [-10, 10]
        x =  uniform(a, b)
        y =  uniform(a, b)
        return np.array( [x, y] )
    
    def calc_fitness(self,pos):
        x,y=pos
        fit = x*x + y*y
        return fit

4.3.3. La partícula

Un objeto de la clase Partícula mantiene los mismos datos y tiene las mismas funciones que en la versión funcional. Como el objeto encapsula los datos aquí no es necesario ponerlos en una tupla. Por lo mismo, cuando una partícula 'se mueve' no se crea una nueva partícula sino que se cambian los datos de la propia partícula y esto se hace envíandole el mensaje 'move()' a la partícula. Gracias a la OOP se puede especificar el método __ini_₍₎ que se ejecuta de manera automática cuando se crea el objeto. Este método manda el mensaje al 'problema' de que le de una solución y calcule su fittness. De la misma manera que en la versión funcional, al inicio, la posición actual, la previa y la mejor de cada partícula son iguales. Por lo tanto la velocidad inercial y cognitiva son cero. Eso hace que en un inicio todas las partículas se muevan hacia la mejor

class Particle():
    def __init__(self,problem): 
        self.pos = problem.make_sol()
        self.fit = problem.calc_fitness(self.pos)
        self.prev_pos = self.pos
        self.prev_fit = self.fit
        self.best_pos = self.pos
        self.best_fit = self.fit

    def move(self,spo_data,problem,swarm_best_pos):
        # estract constants
        w = spo_data.w
        k_cgn = spo_data.k_cgn
        k_scl = spo_data.k_scl
        # calc partial and total velocities
        vel_inercial =  w*( self.pos - self.prev_pos )
        vel_cognitiva = k_cgn*( self.best_pos - self.pos )
        vel_social =    k_scl*( swarm_best_pos - self.pos )
        vel = vel_inercial + vel_cognitiva + vel_social
        # save the current position as the prev position
        self.prev_pos = self.pos
        self.prev_fit = self.fit
        # changes the current position and fitness
        self.pos = self.pos + vel
        self.fit = problem.calc_fitness(self.pos)
        # update best_pos and best_fit if necessary
        if self.fit < self.best_fit:
            self.best_pos = self.pos
            self.best_fit = self.fit

    def printp(self):
        print(self.pos,self.fit)
        print(self.prev_pos,self.prev_fit)
        print(self.best_pos,self.best_fit)
        print()

4.3.4. El enjambre

Al igual que la partícula un swarm tiene los mismos datos y las mismas funciones que en su versión anterior, sólo que ahora estos datos y funciones están encapsulados. Al igual que antes un swarm mantiene un conjunto de partículas y la mejor partícula. El conjunto de partículas es una lista de partículas. El método __init_₍₎, que se corre automáticamente cuando se crea un swarm, crea una lista de un número especificado de partículas. El método 'move()' mueve el enjambre llamando al método particle.move de cada partícula y actualizando la mejor partícula. Los métodos __find_best_particle() y __update_best_particle() sólo son necesarios para actualizar la mejor partícula y no deben ser accesibles desde el exterior. En Python la forma de lograr esto es iniciando el nombre de los métodos con doble guión.

class Swarm():
    def __init__(self,spo_data,problem):
        self.particles = [Particle(problem) for i in range(spo_data.num_particles)]
        self.__update_best_particle()

    def __update_best_particle(self):
        self.best_particle = self.__find_best_particle()
        self.best_pos = self.best_particle.best_pos
        self.best_fit = self.best_particle.best_fit

    def __find_best_particle(self):
        # set the bes particle to the first particle
        best_particle_found = self.particles[0]
        #update best particle  if necessary
        for particle in self.particles:
            if particle.best_fit < best_particle_found.best_fit:
                best_particle_found = particle
        # return best particle
        return best_particle_found
        
    def move(self,spo_data, problem):
        for particle in self.particles:
            particle.move(spo_data, problem, self.best_pos)
        self.__update_best_particle() 

    def prints(self):
        print("printing swarm")
        print("particles:")
        for particle in self.particles:
            particle.printp()
            print()
        print("swarm best position and fitness")
        print(self.best_pos,self.best_fit)
        print()

4.3.5. El método spo

Como en la versión funcional, una vez implementado el 'problema', la partícula y el enjambre, es sencillo expresar el método. Este consiste en crear un enjambre y moverlo hasta que se cumpla la condición de paro. Al crear un enjambre se crean sus partículas y se encuentra la mejor partícula. Mover un enjambre significa mover las partículas.

def spo(data, problem):
    swarm = Swarm(data, problem)
    swarm.prints()   # print the initial swarm
    generation_num = 0
    while(not stop_condition(swarm, data, generation_num)):
        swarm.move(data, problem)
        generation_num += 1
    swarm.prints()   # print the final swarm
    return swarm.best_particle

Note que el método se ha expresado como una función y no como un objeto. Se podría haber creado como un objeto, pero no se ganaría mucho.

La condición de paro es casi la misma que antes.

def stop_condition(swarm, data, generation_num):
    return (generation_num >= data.max_generations)

Se puede evaluar la implementación con las siguientes instrucciones

problem = Optimization_problem_a()
data = Spo_data(10, 250, 0.7, 0.3, 0.3)

problem_c = Optimization_problem_a()
best_particle_a = spo(data,problem_a)

5. Extensiones del método y la implementación

5.1. Modificaciones del método

Hay varias modificaciones que se pueden hacer al método. Por ejemplo, hacer que el movimiento de una partícula dependa de las que están 'mas cerca' que ella. Por la manera que están programadas las dos versiones que se presentan aquí, no es difícil implementar nuevas ideas. Se debe cuidad siempre de programar ideas que permitan expresar al método en lugar de traducir directamente el método al lenguaje de programación tal cual.

5.2. Creación de partículas con velocidad inercial y cognitiva distintas de cero

Note que en las dos implementaciones del método presentadas, cuando se crea una partícula las velocidades inercial y cognitiva son cero. Esto es porque la posición previa y la mejor son iguales a la posición actual de la partícula. Si que quisiera cambiar esta situación solo habría que cambiar la forma en que se crea la partícula. Por ejemplo, la partícula podría 'pedir' al 'problema' en lugar de una, dos soluciones no óptimas (posiciones). Una de esas soluciones sería asignada a la actual y otra a la posición previa. La mejor posición se calcularía de ambas posiciones. De esta manera la velocidad inercial no sería cero y en ocasiones la velocidad cognitiva tampoco.

La solución descrita antes es sólo una posibilidad. Hay otras, por ejemplo, que el 'problema' genere al azar la velocidad inercial y/o la velocidad cognitiva y a partir de estas velocidades calcular la posición previa y la mejor posición con que inicia la partícula. Cualquiera que sea el caso, se debe hacer notar que sólo sería necesario cambiar la inicialización de la partícula y/o el 'problema'. El resto del programa quedaría igual. Esto es posible por la forma en que está programado el método.

5.3. Aplicación a otro tipo de problemas

Si la solución de un problema puede especificarse como un vector de parámetros, sólo es necesario programar la función que genera una solución no óptima y la que calcula el fitnes. Por ejemplo, suponga que se quiere encontrar el mejor controlador PID para un sistema. Cada controlador se puede especificar como una tripleta \((k_{p},k_{i},k_{d})\). Por lo tanto, la función que genera una solución no óptima solo debe generar una tripleta. Si se conoce en que rango es conveniente que que están las constantes del controlador, esto puede reducir el espacio de búsqueda.

Para programar la función que calcule el fitness de cada solución es necesario precisar que se quiere decir por 'mejor' controlador. En este caso 'mejor' en este caso puede ser un objetivo (o la combinación de varios) de diseño del controlador. Por ejemplo, el tiempo de establecimiento, o el máximo sobre impulso, o el valor cuadrático medio del error, etc. Para calcular cualquiera de estos índices es necesario realizar una simulación del sistema con el controlador en cuestión. Note que esto es necesario para cada solución. Al final la función que calcula el fitness arrojará un número. Así, aunque el cálculo del fitness pueda ser complejo, no se necesita cambiar el resto del programa.

5.4. Cuando una solución no se pueda especificar como un vector de parámetros

Aunque la solución no sea las coordenadas de un punto en el espacio \(R^{n}\), si se puede especificarse como un vector de parámetros entonces sólo hay que cambiar la parte del 'problema'. La razón de esto es que cada solución es un arreglo (np.array) por lo que automáticamente las soluciones se pueden sumar y multiplicarse por un escalar como cualquier espacio vectorial. Esto ya lo sabe hacer la biblioteca 'numpy'.

Sin embargo, pudiera ocurrir que las soluciones a un problema puedan no especificarse como un vector de parámetros. Se nos ocurre por ejemplo el caso de un controlador difuso, donde hay que especificar cosas, como tipo de conjuntos difusos involucrados en el controlador; expresiones para esos conjuntos, etc. En este caso la partícula debe saber moverse, pero para moverse deberá deberá preguntar al problema como 'sumar' las posiciones (soluciones del problema) y como 'multiplicarlas por un escalar'. Así estás operaciones entre las posiciones ('suma' de soluciones y 'multiplicación por un escalar') deberán ser programadas en el problema. En los casos que hemos abordado no ha sido necesario porque 'numpy' sabe como hacerlo para arreglos.

Date: Agosto de 2023

Author: Domingo Cortés

Email: domingo.cortes@gmail.com

Validate

Optimización por Enjambre de Partículas Usando Python