CN115222006A - Numerical function optimization method based on improved particle swarm optimization algorithm - Google Patents

Abstract

The invention relates to the field of intelligent calculation, in particular to a numerical function optimization algorithm based on an improved particle swarm optimization algorithm. The main technical characteristics are as follows: the particle swarm optimization algorithm is improved, the diversity of the swarm is enhanced, and the optimization range of the particles is expanded. According to the optimization mode of the particle swarm optimization algorithm, the initial search space loses guiding significance for the whole algorithm after a few iterations, and the problems that the algorithm is easy to converge to a local minimum value, the diversity is reduced too fast, the parameters are sensitive and the like are easily caused. The algorithm is considered from the aspects of expanding the optimizing range and enhancing the diversity of the particle swarm, and a space search strategy combining local search and global search is added, namely, the initialization stage, the speed and the position iterative formula of the particle swarm algorithm are modified by using Bernstein particles and a reverse learning strategy.

Description

A Numerical Function Optimization Method Based on Improved Particle Swarm Optimization Algorithm

technical field

The invention belongs to the field of intelligent computing, in particular to a numerical function optimization algorithm based on an improved particle swarm optimization algorithm.

Background technique

In recent years, an emerging evolutionary computing technology called swarm intelligence has become the focus of more and more researchers. It has a very special relationship with artificial life, especially evolutionary strategies and genetic algorithms. Swarm intelligence takes advantage of swarms and provides new ideas for finding solutions to complex problems without centralized control and without a global model. At present, swarm intelligence algorithms have been applied to practical scenarios. And a large number of literatures have shown that the research on algorithm optimization using the spatial parallel search method combined with the spatial local search strategy and the spatial global search strategy is not common in swarm intelligence. It is not difficult to find that for the genetic algorithm, the initial search space loses its guiding significance to the entire algorithm after a few iterations. The reason is that due to the hybridization within the population, the individuals are limited to those limited by the known individuals in the population. evolution in space. It is also for this reason that the optimization of the algorithm by the combination of the spatial local search strategy and the global search strategy will be reflected in the swarm intelligence optimization algorithm.

The invention is based on the representative swarm intelligence algorithm-particle swarm optimization algorithm, improves its existing shortcomings, considers the expansion of the optimization range and the enhancement of population diversity, and adds a space combining local search and global search. Search strategy, an improved particle swarm optimization algorithm is proposed for numerical function optimization, and the feasibility and effectiveness of the improved particle swarm optimization algorithm are verified by standard test functions.

SUMMARY OF THE INVENTION

The purpose of the present invention is to solve the problem that in the process of numerical function optimization, the convergence speed is too slow, the convergence accuracy is not high, it is easy to converge to a local minimum value, the diversity declines too fast, and the parameter sensitivity, etc. In the existing particle swarm optimization algorithm, the space parallel search method combining the spatial local search strategy and the spatial global search strategy is added to modify the update formula of particles, which alleviates the easy trapping in the process of numerical function optimization to a certain extent. The problem of local optima. The convergence of the algorithm is better than that of the traditional particle swarm optimization algorithm. Under a certain task scale, the cost and time required to complete the numerical function optimization are lower.

Particle Swarm Optimization (PSO) is a global stochastic optimization algorithm based on swarm intelligence, which was proposed by Dr. Eberhart and Dr. Kennedy in 1995. It imitates the foraging behavior of birds, compares the search space of the problem to the flight space of birds, and abstracts each bird into a particle to represent a candidate solution to the problem, and the optimal solution to be found is equivalent to for the food to be found. The algorithm gives each particle an initial position and velocity, and each particle updates its own position by updating the velocity. Through iterative search, the population can continuously find better particle positions, thereby obtaining a better solution to the optimization problem. In the particle swarm optimization algorithm, particles have two properties: speed and position, speed represents the speed of movement, and position represents the direction of movement. Each particle searches for the optimal solution independently in the search space, and records it as the current individual extremum, and shares the individual extremum with other particles in the entire particle swarm, and finds the optimal individual extremum as the entire particle The current global optimal solution of the swarm, all particles in the particle swarm adjust their speed and position according to the current individual extremum found by themselves and the current global optimal solution shared by the entire particle swarm. The formula of particle swarm optimization algorithm is as follows:

和

为粒子i在第t次迭代时的速度和历史最优位置；

是第t次迭代时整个种群的最优位置。Among them: ω is the inertia weight; r ₁ and r ₂ are random numbers uniformly distributed between (0, 1); c ₁ and c ₂ are learning factors.

and

is the velocity and historical optimal position of particle i at the t-th iteration;

is the optimal position of the entire population at the t-th iteration.

In the optimization mode of particle swarm optimization, _vi represents the speed, which can have a certain influence on the direction and position of the current position randomly, so that the algorithm can search in a given area. If the evolutionary iteration of the algorithm is understood as an adaptive process, the particle position x _i is not replaced by new particles, but adaptively changes according to the velocity vector v _i . Its uniqueness is that each iteration algorithm Each particle of s only flies in the direction that the swarm experience thinks is good, which means that the basic particle swarm algorithm performs a kind of "conscious" evolution.

In the standard particle swarm optimization algorithm, the movement direction of the particle is mainly determined by the historical optimal position and the global optimal position of the particle. In order to increase the diversity of the population, the proposed algorithm expands the scope of optimization, and introduces a combination of spatial local search strategy and spatial global search strategy, that is, the idea of reverse learning is added in the initialization stage, and the t-th In the next iteration, the Bernstein particle of the optimal particle of the population and the reverse particle of any particle in the population are randomly selected as the guiding particle, which increases the diversity of the population, expands the optimization range, and helps the algorithm to quickly find the global optimal position. .

The proposed algorithm is adjusted based on the optimization mode of the particle swarm optimization algorithm, and the velocity iteration formula, that is, the position iteration formula, is modified as follows:

The improved particle swarm optimization algorithm increases the diversity of the population in the initialization stage and improves the convergence speed of the population; in the evolution stage, the speed and position iteration formula can ensure that the particles follow the optimization mode of the algorithm, and the position is adjusted according to the speed. The range of optimization, the convergence speed is improved.

In the experiment, in order to verify whether the improvement is effective, two types of Benchmark international standard functions, unimodal and multimodal, are selected for testing to verify the optimization effect of the improved algorithm. The invention helps the algorithm to escape from the local optimum position by increasing the diversity of the population and improving the probability of finding an optimum. Experiments show that the present invention has faster convergence speed and higher precision than other algorithms.

Description of drawings

Fig. 1 is the flow chart of the particle swarm algorithm of the present invention

Fig. 2 is the result comparison diagram of the present invention and the original algorithm on the single peak test function

Fig. 3 is the result comparison diagram of the present invention and the original algorithm on the multi-peak test function

Detailed ways

The present invention is a numerical function optimization method based on an improved particle swarm optimization algorithm, and the method comprises the following steps:

Step 1: Generate the initial population. The quality of the initial population is related to the speed of the search. A good initial population is helpful for the algorithm to quickly find the optimal solution. Usually when we solve the problem of x, the initial value of x is a guess that we have accumulated through experience or simply random. On this basis, we can use the opposite value of x to try to get a better solution at the same time, so that the next generation of x can approach the optimal solution faster. The idea of space global search strategy, namely reverse learning, is adopted, that is, in the process of population evolution, each particle generates a corresponding reverse position every time it finds a current optimal position. If the fitness value of the reverse position is better, Then select particles with better fitness to form the initial population. Assuming the position of the i-th particle in the population at the t-th iteration, the position of the corresponding reverse particle can be defined as:

Where x _ij ∈[a _j , b _j ], k, k ₁ and k ₂ belong to random numbers between (0, 1), [a _j , b _j ] is the interval of the jth dimension of x _ij , specifically expressed as: a _j (t)=min(x _ij (t), b _j (t)-min(x _ij (t))

Step 2: Inertial weights and learning factors can control the performance of particles in the optimization process. The existence of weights can effectively control the convergence speed of particle swarms, and the existence of learning factors makes full use of the “genetic knowledge” of the entire population and individuals, and effectively guides the direction of particle movement through social activities between particles. The proposed algorithm changes the fixed learning factor to a semi-fixed learning factor, in which the learning factor c ₃ is controlled by the Bernstein polynomial generation, so that c ₁ and c ₂ ensure the independence of the particles, while reducing the second learning factor to reduce Possibility of particle aggregation. Bernstein polynomials are expressed as:

where β～U(0,1), k ₁ ～U(0,1), k∈U{1:3},

Step 3: In the standard particle swarm optimization algorithm, the movement direction of the particle is mainly determined by the historical optimal position and the global optimal position of the particle. In order to increase the diversity of the population, the proposed algorithm introduces a spatial local search strategy, that is, adding the Bernstein particle of the optimal particle of the population at the t-th iteration and the reverse particle of any particle in the population randomly selected as the guiding particle to expand It can help the algorithm to quickly find the global optimal position. The proposed optimization mode based on the particle swarm algorithm is adjusted, so in the improvement of the PSO algorithm, the velocity iteration formula and the position iteration formula are modified as follows:

和

为粒子i在第t次迭代时的速度和历史最优位置；

是第t次迭代时整个种群的最优位置；

表示第t次迭代时种群最优粒子的伯恩斯坦粒子。Among them: c ₁ , c ₂ and c ₃ are learning factors; ω is the inertia weight; r ₁ , r ₂ and r ₃ are all between (0, 1);

and

is the velocity and historical optimal position of particle i at the t-th iteration;

is the optimal position of the entire population at the t-th iteration;

The Bernstein particle representing the optimal particle of the population at iteration t.

Step 4: In the experiment, in order to verify whether the improvement is effective, two types of Benchmark international standard functions, unimodal and multimodal, are selected for testing to verify the optimization effect of the improved algorithm.

Claims (4)

1. A numerical function optimization method based on an improved particle swarm optimization algorithm is characterized by comprising the following steps:

step 1: the quality of the initial population is related to the speed of the search speed, and the good initial population is beneficial to an algorithm to quickly find an optimal solution. In general, when we solve the problem x, the initial value x is a guess that we accumulated through experience or is purely random. On this basis, we can simultaneously use the opposite value of x to try to get a better solution, by doing so making the next generation x approach the optimal solution faster. And (3) adopting a space global search strategy, namely the idea of reverse learning, namely, in the population evolution process, each particle generates a corresponding reverse position every time when finding a current optimal position, and if the adaptive value of the reverse position is better, selecting the particles with better fitness to form an initial population.

Step 2: the inertial weight and the learning factor can control the performance of the particles in the optimizing process. The weight can effectively control the convergence speed of the particle swarm; and the presence of a learning factorThe 'genetic knowledge' of the whole population and individuals is fully utilized, and the learning factors are used for effectively guiding the movement direction of the particles through social activities among the particles. The proposed algorithm changes the constant learning factor to a semi-constant learning factor, wherein the learning factor c ₃ Control is generated by Bernstein polynomials such that c ₁ 、c ₂ The independence of the particles is ensured, and the possibility of particle aggregation is reduced by reducing the second learning factor.

And step 3: in the standard particle swarm optimization algorithm, the movement direction of the particles is mainly determined by the historical optimal position and the global optimal position of the particles. In order to increase the diversity of the population, the proposed algorithm introduces a space local search strategy, namely adding Bernstein particles of population optimal particles in the t-th iteration and randomly selecting reverse particles of any particles in the population as guide particles, so that the optimization range is expanded, and the algorithm is helped to quickly find the global optimal position.

And 4, step 4: in the experiment, in order to verify whether the improvement is effective, unimodal and multimodal two types of Benchmark international standard functions are selected for testing, and the optimization effect of the improved algorithm is verified.

2. The numerical function optimization algorithm based on the improved particle swarm optimization algorithm according to claim 1, further comprising generating an initial population using a reverse learning strategy in step 1. Let X _i (t)＝(x _i1 ，x _i2 ，...，x _iD ) The position of the ith particle in the population at the time of the t iteration is the position of the corresponding reverse particle

The above can be defined as:

wherein x _ij ∈[a _j ，b _j ]，k、k ₁ And k ₂ Belongs to random number between (0,1) [ a ] _j ，b _j ]Is x _ij The j-th dimension is specifically represented as follows:

a _j (t)＝min(x _ij (t)，b _j (t)-min(x _ij (t)) (2)。

3. the numerical function optimization algorithm based on the improved particle swarm optimization algorithm according to claim 1, further comprising learning factor c in step 2 ₃ Generated by a bernstein polynomial expressed as:

wherein beta-U (0,1), k ₁ ～U(0，1)，k∈U{1∶3}，

4. The improved particle swarm optimization algorithm-based numerical function optimization algorithm according to claim 1, further comprising that, in the step 3, the proposed particle swarm optimization-based optimization mode is adjusted, so that in the improvement of the PSO algorithm, the velocity iteration formula and the position iteration formula are modified to the following formulas:

wherein, c ₁ 、c ₂ And c ₃ Is a learning factor; omega is the inertial weight; r is ₁ 、r ₂ And r ₃ Are all between (0,1);

and

and particle i at the t-th iterationThe speed of the time and the historical optimal position,

is the optimal position of the whole population during the t iteration;

bernstein particles representing the best population of particles at the t-th iteration.

Images