[PYTHON] Try to solve the function minimization problem using particle swarm optimization

Particle swarm optimization

Particle Swarm Optimization (PSO) is a type of swarm intelligence and is used for combinatorial optimization problems as a solution search method. The search proceeds by repeating the update of two pieces of information, the velocity and position of the particle. The figure below is an image of particle swarm optimization. pso2.png

algorithm

The algorithm for particle swarm optimization is as follows. スクリーンショット 2019-11-25 15.33.15.png

Renewal formula

The velocity and position of the particles are updated by the following update formula. Simply put, velocity represents the direction in which the particle evolves, and position represents the parameters of the particle itself. スクリーンショット 2019-11-25 15.35.13.png

Experiment

Let's actually solve the optimization problem. This time

x^2 + y^2

Let's solve the minimization problem of. Therefore, (x, y) = (0,0) is the optimal solution. The code used is as follows.

# -*- coding: utf-8 -*-
import numpy as np
import random

#Evaluation function
def evaluate(particle):
    z = 0
    for i in range(len(particle)):
        z += particle[i] ** 2
    return z

#Position update
def update_position(particle, velocity):
    new_particle = particle + velocity
    return new_particle

#Speed update
def update_velocity(particle, velocity, pbest, gbest, w=0.5, max=0.15):
    new_velocity = np.array([0.0 for i in range(len(particle))])
    #new_velocity = [0.0 for i in range(len(particle))]
    r1 = random.uniform(0, max)
    r2 = random.uniform(0, max)
    for i in range(len(particle)):
        new_velocity[i] = (w * float(velocity[i]) + r1 * (float(pbest[i]) - float(particle[i])) + r2 * (float(gbest[0]) - float(particle[i])))

    return new_velocity

def main():
    N = 100 #Number of particles
    length = 2  #Number of dimensions
    para_max = 100  #Maximum value of parameter
    #Initialization of particle position
    ps = [[random.uniform(-para_max, para_max) for j in range(length)] for i in range(N)]
    vs = [[0.0 for j in range(length)] for i in range(N)]
    #Personal vest
    personal_best_position = ps
    #Personal best rating
    personal_best_scores = [evaluate(p) for p in ps]
    #Index of the particle with the lowest evaluation value
    best_particle = np.argmin(personal_best_scores)
    #Global best
    global_best_position = personal_best_position[best_particle]

    generation = 30 #Maximum number of generations
    #Loop for several generations
    for t in range(generation):
        file = open("data/pso/pso" + str(t+1) + ".txt", "w")
        #Particle number minute loop
        for n in range(N):
            #File writing
            file.write(str(ps[n][0]) + " " + str(ps[n][1]) + "\n")
            #Particle velocity update
            vs[n] = update_velocity(ps[n], vs[n], personal_best_position[n], global_best_position)
            #Update particle position
            ps[n] = update_position(ps[n], vs[n])

            #Calculate the evaluation value and find the personal best
            score = evaluate(ps[n])
            if score < personal_best_scores[n]:
                personal_best_scores[n] = score
                personal_best_position[n] = ps[n]
        #Update the global best
        best_particle = np.argmin(personal_best_scores)
        global_best_position = personal_best_position[best_particle]
        file.close()

    print(global_best_position)
    print(min(personal_best_scores))

if __name__ == '__main__':
    main()

Experimental result

The 1,10,20, and 30th generation individuals are color-coded and plotted in the figure. You can see that the particles converge to (0,0) as the generation progresses. PSO.png

Recommended Posts

Try to solve the function minimization problem using particle swarm optimization
Try to solve the Python class inheritance problem
Try function optimization using Hyperopt
Try to solve the internship assignment problem with Python
Try to solve the N Queens problem with SA of PyQUBO
Stack problem: Try to solve "20. Valid Parentheses"
How to solve the bin packing problem
Try to solve the traveling salesman problem with a genetic algorithm (Theory)
Find the minimum value of a function by particle swarm optimization (PSO)
Solve the knapsack problem using pyomo and glpk
Try to solve the man-machine chart with Python
Try to solve the traveling salesman problem with a genetic algorithm (execution result)
Try to solve the programming challenge book with python3
[Python] Try to read the cool answer to the FizzBuzz problem
Try to solve the problems / problems of "Matrix Programmer" (Chapter 1)
How to solve the recursive function that solved abc115-D
I tried to approximate the sin function using chainer
I tried to solve the problem with Python Vol.1
Try to solve Sudoku at explosive speed using numpy
Try to get the function list of Python> os package
I tried to simulate ad optimization using the bandit algorithm.
I tried to solve a combination optimization problem with Qiskit
Try to solve the problems / problems of "Matrix Programmer" (Chapter 0 Functions)
Solve the Japanese problem when using the CSV module in Python.
The problem becomes easier to solve depending on the formulation method
I tried to approximate the sin function using chainer (re-challenge)
Try function optimization with Optuna
Solve the Monty Hall problem
Try using the Twitter API
Try using the Twitter API
Particle swarm optimization (PSO) parameters
I tried to get the index of the list using the enumerate function
Try to edit a new image using the trained StyleGAN2 model
Try to operate the database using Python's ORM Peewee (August 2019 version)
I wanted to solve the ABC164 A ~ D problem with Python
I tried to solve the shift scheduling problem by various methods
Try to solve the shortest path with Python + NetworkX + social data
Solve multivariable optimization problems using sagemath
How to use the zip function
Try using pynag to configure Nagios
Precautions when using the urllib.parse.quote function
Try to get statistics using e-Stat
Try using the Python Cmd module
Cython to try in the shortest
The fastest way to try EfficientNet
The easiest way to try PyQtGraph
How to divide and process a data frame using the groupby function
The 16th offline real-time how to write reference problem to solve with Python
Try using the Python web framework Django (1)-From installation to server startup
Try to get the road surface condition using big data of road surface management
Try using n to downgrade the version of Node.js you have installed
The 19th offline real-time how to write reference problem to solve with Python
I tried to solve the E qualification problem collection [Chapter 1, 5th question]
I tried to solve the inverted pendulum problem (Cart Pole) by Q-learning.
Try to solve a set problem of high school math with Python