Overview and Implementation of Particle Swarm Optimization

The PSO algorithm proceeds in the following steps

1. Initialize the population: randomly determine the initial position and initial velocity. Each individual is placed at a random position in the search space and has a random velocity.
2. Compute the evaluation function for each individual: Using the position of each individual, compute the value of the evaluation function.
3. Update each individual’s “best solution he/she has found so far”: Each individual remembers the best solution he/she has found so far. This is called the personal best.
4. Update the “best overall solution” of the population: The best solution of the entire population is called the Global Best. The global best is updated if the solution is better than the personal best.
5. Update the velocity of each individual: Each individual calculates a new velocity using its current velocity and acceleration. The acceleration is calculated by the following equation. [a_i = c_1 times rand() times (p_{best_i} – x_i) + c_2 times rand() times (g_{best} – x_i)] where ai is the acceleration, c1 and c2 are random coefficients, pbesti is the personal best that individual i has, xi is the current position, and gbest is the overall global best.
6. Update the position of each individual: Each individual calculates a new position using its current position and new velocity.
7. Check for termination conditions: If the termination conditions are met, the search is terminated. r. If not, return to step 2. Otherwise, return to step 2.

The PSO searches for the optimal solution by repeating the above steps. As the position and velocity of the population in the search space change, the search proceeds closer to the optimal solution.

PSO can be applied to a wide variety of problems. Some specific applications are discussed below.

• Pattern Recognition: PSO may be used to optimize the weights of a neural network. For example, PSO has been reported to be highly accurate in pattern recognition problems such as face recognition and speech recognition.
• Robot Control: PSO is also applied to robot control problems. For example, PSO has been reported to provide high control accuracy in inverse kinematics and trajectory generation problems.
• Combinatorial optimization problems: Combinatorial optimization problems involve finding the optimal solution under certain constraints. PSO has also been applied to these problems to obtain high solution quality.
• Parameter Optimization: PSO is also used to optimize the parameters of a function. For example, PSO may be used to optimize parameters in simulation and optimal control problems.
• Neural Network Training: PSO is also used to train neural networks. For example, PSO may be used to optimize the weights and biases of a multilayer perceptron.

In addition to these examples, PSO has been applied to a variety of other problems.

Some actual implementations using PSO include.

Implementation in Python

See “Python and Machine Learning” for more information on building a python environment.

• Particle swarm optimization (PSO) with constraint support

PSO implementation using pyswarm, a python PSO library

pip install pyswarms
# Import modules
import numpy as np

# Import PySwarms
import pyswarms as ps
from pyswarms.utils.functions import single_obj as fx

# Some more magic so that the notebook will reload external python modules;
# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython
%load_ext autoreload
%autoreload 2

• We’ll implement the optimization algorithm (particle swarm optimization) (external link)

Original implementation. Code is available on github.

PSO implementation in R

See “R Language and Machine Learning” for information on building an R environment.

• Introduction to Particle Swarm Optimization(External link)

A page on PSO implementation using R with carefully described theory and tutorial. It is not a simple hello world, but has sample codes for various practical examples.

Example 1: Engineering: Optimizing Spring Weight

This problem is a replication of the problem in Hu et al. (2003) 3. which is to minimize the weight of a tension-compression spring subject to minimum deflection, shear stress, surge frequency, outer diameter limits, and design variable constraints. The design variables are average coil diameter D, wire diameter d, and effective number of coils N:

Example 2: Finance: Portofolio Optimization

This problem is replicated from Zhu et al. (2011)5 , where the PSO algorithm is employed for portfolio selection and optimization in investment management.

The portfolio optimization problem involves managing a portfolio of assets that minimizes a risk target under constraints to guarantee a given level of return. One of the basic principles of financial investment is diversification, where the investor diversifies his investments across different types of assets. Portfolio diversification minimizes the investor’s exposure to risk and maximizes portfolio returns.

The fitness function is the adjusted Sharpe ratio of the restricted portfolio. It combines information from the mean and variance of the assets and serves as a risk-adjusted measure of average return and is often used to evaluate portfolio performance.

The Sharpe ratio helps explain whether a portfolio’s excess returns are the result of smart investment decisions or too much risk. A given portfolio or fund may enjoy higher returns than its peers, but it is a good investment only if those higher returns are not accompanied by excessive additional risk.

The higher the Sharpe ratio of a portfolio, the better its risk-adjusted performance. A negative Sharpe ratio as a result of the analysis means that the risk-free rate exceeds the portfolio’s return or that the portfolio’s return is expected to be negative.

• Introduction page of “pso”, a PSO package in R (external link)

Implementation in Clojure

See “Setting up a Clojure development environment with SublimeText4, VS code and LightTable” for more information on setting up a Clojure environment.

• CAPSOS (Cellular Automata, Particle Swarm Optimization, Synth)(External link)

github page of CAPSOS (Cellular Automata, Particle Swarm Optimization, Synth).

(ns capsos.pso-test
  (:use midje.sweet
        capsos.pso))


;; (defn update-particle-xy
;;   [gbest p]
;;   (let [pbest (:pbest p)
;;         nvelx (+ (* 2 (rand) (- (first pbest) (:x p)))
;;                  (* 2 (rand) (- (first gbest) (:x p))))
;;         nvely (+ (* 2 (rand) (- (second pbest) (:y p)))
;;                  (* 2 (rand) (- (second gbest) (:y p))))]
;;     (assoc p :x (+ nvelx (:x p)) :y (+ nvely (:y p)) :vel [nvelx nvely])))


(def ^:dynamic ^java.util.Random *rnd* (java.util.Random. 42)) 
;;(.nextDouble *rnd*)


(make-particle 1000 1000)
;; => {:x 740, :y 815, :pbest [740 815]}

(last (take 90000 (iterate (partial update-particle-xy [50 50]) {:x 740, :y 815, :pbest [740 815]})))

(update-particle-xy [50 50] {:x 740, :y 815, :pbest [740 815]})
{:norm-vel [-0.36547344376116647 -0.930821766991594], :vel [-473.25580940929353 -1205.3319229434064], :y 814.0691782330084, :x 739.6345265562388, :pbest [740 815]}


{:norm-vel [-0.4051418860917991 -0.9142538225974118], :vel [-633.3074826612985 -1429.138301368925], :y 649.0857461774026, :x 637.5948581139082, :pbest [1 1]}

;; (facts "Particle XY updating"
;;        (update-particle-xy [0 0] {:pbest [0 0] :x 1 y 1})
;;        => 
    
;;        )