Find the minimum value of a function by particle swarm optimization (PSO)

Overview

Particle swarm optimization (PSO) is a type of swarm intelligence inspired by the behavior of swarms of animals. In this article, I will introduce a simple example of particle swarm optimization.

Parabolic formula

The paraboloidal equation is given in the following form.

\begin{aligned}
z = x^2+y^2
\end{aligned}

Obviously, the minimum value is $ z = 0 $ when $ (x, y) = (0, 0) $. This is calculated using the particle swarm optimization method.

Explanation of particle swarm optimization method

See the article below. (Is the subscript in §2 partly wrong?) Particle Swarm Optimization and Nonlinear System

Let's implement §2 of this article.

Source code

main.py


# -*- coding: utf-8 -*-

import numpy as np
import random

#Evaluation function: z = x^2 + y^2
def criterion(x, y):
    z = x * x + y * y
    return z

#Function to update the position of particles
def update_position(x, y, vx, vy):
    new_x = x + vx
    new_y = y + vy
    return new_x, new_y

#A function that updates the velocity of particles
def update_velocity(x, y, vx, vy, p, g, w=0.5, ro_max=0.14):
    #Parameter ro is given randomly
    ro1 = random.uniform(0, ro_max)
    ro2 = random.uniform(0, ro_max)
    #Update the particle velocity
    new_vx = w * vx + ro1 * (p["x"] - x) + ro2 * (g["x"] - x)
    new_vy = w * vy + ro1 * (p["y"] - y) + ro2 * (g["y"] - y)
    return new_vx, new_vy


def main():
    N = 100  #Number of particles
    x_min, x_max = -5, 5
    y_min, y_max = -5, 5
    #Particle position,speed,Personal vest,Initialize the global best
    ps = [{"x": random.uniform(x_min, x_max), 
        "y": random.uniform(y_min, y_max)} for i in range(N)]
    vs = [{"x": 0.0, "y": 0.0} for i in range(N)]
    personal_best_positions = list(ps)
    personal_best_scores = [criterion(p["x"], p["y"]) for p in ps]
    best_particle = np.argmin(personal_best_scores)
    global_best_position = personal_best_positions[best_particle]
    
    T = 30  #Time limit(Number of loops)
    for t in range(T):
        for n in range(N):
            x, y = ps[n]["x"], ps[n]["y"]
            vx, vy = vs[n]["x"], vs[n]["y"]
            p = personal_best_positions[n]
            #Update the position of the particles
            new_x, new_y = update_position(x, y, vx, vy)
            ps[n] = {"x": new_x, "y": new_y}
            #Update the velocity of particles
            new_vx, new_vy = update_velocity(
                new_x, new_y, vx, vy, p, global_best_position)
            vs[n] = {"x": new_vx, "y": new_vy}
            #Find the evaluation value,Update your personal vest
            score = criterion(new_x, new_y)
            if score < personal_best_scores[n]:
                personal_best_scores[n] = score
                personal_best_positions[n] = {"x": new_x, "y": new_y}
        #Update the global best
        best_particle = np.argmin(personal_best_scores)
        global_best_position = personal_best_positions[best_particle]
    #Optimal solution
    print(global_best_position)
    print(min(personal_best_scores))

if __name__ == '__main__':
    main()

result

result


{'y': 0.00390598718159734, 'x': -0.0018420875049243782}
1.86500222386e-05

Visualization

It looks like $ N (= 100) $ particles are concentrated on $ (x, y) = (0, 0) $. B2psHNqCMAAIXcf.png

Other

How do you determine some parameters such as the number of particles? (Trial and Error?)


The order of position update, speed update, personal best, global best is out of order depending on the literature ... In this article, we will update the position ⇒ update the speed ⇒ update the personal best ⇒ update the global best.

Edit history

Recommended Posts

Find the minimum value of a function by particle swarm optimization (PSO)
Find the index of the maximum value (minimum value) of a multidimensional array
Find the optimal value of a function with a genetic algorithm (Part 2)
Particle swarm optimization (PSO) parameters
I also learned + init, class, which tried to find the minimum value of a quadratic function by making an optimization method (SGD, momentum, AdaGrad) in deep learning by myself.
Find the definition of the value of errno
How to find the memory address of a Pandas dataframe value
Finding the optimum value of a function using a genetic algorithm (Part 1)
[Python] A simple function to find the center coordinates of a circle
Try to solve the function minimization problem using particle swarm optimization
Combinatorial optimization to find the hand of "Millijan"
[Circuit x Python] How to find the transfer function of a circuit using Lcapy
Get the caller of a function in Python
[Scientific / technical calculation by Python] Numerical calculation to find the value of derivative (differential)
Find the number of days in a month
Find the divisor of the value entered in python
Minimize the number of polishings by combinatorial optimization
Judging the finish of mahjong by combinatorial optimization
Search by the value of the instance in the list
Return value of quit ()-Is there anything returned by the "function that ends everything"?
Notification of weather forecast (rain, etc.) by DM as a part of the function of bot
Add a function to tell the weather of today to slack bot (made by python)
Find the cumulative distribution function by sorting (Python version)
○○ Solving problems in the Department of Mathematics by optimization
# Function that returns the character code of a string
[Linux] [C / C ++] How to get the return address value of a function and the function name of the caller
Get the output value of the command (as received by xargs)
Let's decide the lecture of PyCon JP 2016 by combinatorial optimization
Find out the apparent width of a string in python
Reuse the behavior of the @property method by using a descriptor [16/100]
Inherit the standard library to find the average value of Queue
I made a function to check the model of DCGAN
[Python3] Call by dynamically specifying the keyword argument of the function
How to find the scaling factor of a biorthogonal wavelet
Find the diameter of the graph by breadth-first search (Python memory)
I tried to fight the Local Minimum of Goldstein-Price Function
Extract the value of dict or list as a string
Find the eigenvalues of a real symmetric matrix in Python
Let's prove the addition theorem of trigonometric functions by replacing the function with a function in SymPy (≠ substitution)
Find the white Christmas rate by prefecture with Python and map it to a map of Japan
[python] Value of function object (?)
When incrementing the value of a key that does not exist
Find the transfer function of one degree of freedom system with PythonControl.
Visualize by adding "a bite" to the "boxplot" (boxen / swarm / violin)
Find out the mystery change of Pokédex description by Levenshtein distance
If you give a list with the default argument of the function ...
Read the standard output of a subprocess line by line in Python
A function that measures the processing time of a method in python
[Python3] Define a decorator to measure the execution time of a function
Find the rank of a matrix in the XOR world (rank of a matrix on F2)
Create a function to get the contents of the database in Go
A class that freely changes the PLC value by socket communication
Find the ratio of the area of Lake Biwa by the Monte Carlo method
Find the intersection of a circle and a straight line (sympy matrix)