DEVELOPMENT AND INVESTIGATION OF THE EFFECTIVENESS OF THE PARTICLE SWARM OPTIMIZATION ALGORITHM

详细

This article deals with investigation of the effectiveness of the Particle Swarm Optimization (PSO) [1] algorithm for solving constrained and unconstrained one- and multi-criteria optimization problems. Besides the investigations were conducted both the standard and the binary PSO. Also parallelized modifications of these algorithms were developed for multi-processor operations and two real-world problems were solved.

全文:

PSO was originally developed for continuous valued spaces but many problems are, however, defined for discrete valued spaces where the domain of the variables is finite. Kennedy and Eberhart proposed a discrete binary version of PSO for binary problems [2]. They have adapted the PSO to search in binary spaces by applying a sigmoid transformation to the velocity component to squash the velocities into a range [0, 1] and force the component values of the positions of the particles to be 0’s or 1’s. The sigmoid expression is given by: s(v) = 1/(1 + exp(-v)). Two methods were used for solving constrained optimization problems [3]: the method of death penalties and the method of dynamic penalties. The method of death penalties is simple approach that just rejects infeasible solutions (solutions that doesn’t meet the constraints) from the population. In the method of dynamic penalties individuals are evaluated at the each iteration by using penalty function. To evaluate the performance of PSO with these penalty methods were used different test problems [4]. Most of them were with real variables and convex accessible regions. It is established that standard and binary serial PSO as with the method of death penalties so and with the method of dynamic penalties are effective for solving such constrained problems. Besides, using PSO with dynamic penalties helps to find local extremum of function for a smaller number of computations. Binary PSO requires little particles and a large number of generations. Then the algorithm was parallelized. PSO has parallelism as at the level of algorithm’s work organization (populations and their elements interact with each other, “exchange” information) so at the level of its computer realization. Investigation of effectiveness of the serial PSO for test constrained and unconstrained optimization problems showed that solving some of them required a large number of particles and/or generations and therefore a large number of computations. Besides, increasing of the dimension had also led to increasing of the spent resources. Consequently, the time, which is necessary for finding the best solution for the problem, increased too. Then parallelized PSO was used for these test problems. The given approach consists in the setting a number of particles. After that particles are dividing among the processors in a certain way. Thus populations generate on each processor and later calculations carry out for them. At each generation kernels exchange information. Namely, firstly at every step for every population we find best solutions. These best solutions are sent to the master processor and then they are compared between themselves. Thereby the best value of optimizable function is chosen for each generation, which is sent to every processor and maintained. These actions are repeated a specified number of times. So algorithm ends its work. Dependence of effectiveness of the algorithm from assignable computational resource was studied, that is dependence of effectiveness of the algorithm from the number of particles and the number of population’s generations. After that effectiveness of the algorithm was compared depending on amount of processors. This means that the obtained for every problem results were fixed but number of processors was changed. So it was found that effectiveness of the parallelized PSO coincides with effectiveness of the serial PSO. Besides, reliability of the algorithm is irrespective of the quantity of processors (kernels). And also serial PSO worked slower than parallelized PSO as with real particles so with binary particles. Also problems of multi-criterion optimization were considered. Theory of Pareto optimality was used for finding solutions for such problems, to wit PSO was used for approximate construction of Pareto set and Pareto front. Archive for storing non-dominated solutions was created. This archive was updated at the every iteration. While solving multi-criterion problems by using PSO cardinal problem is selection of global best position for particle. There are several ways to solve this problem, and one of them is с-algorithm. K-dimensional vector ст = (CTj,..., ct k ) is named с-parameter of i-th particle with coordinates xi and defined as follows: ст =ct( f { )) = {[ftf)-f2f))({f)-f2f))..)f)-f2(x)) . f2()+ f2 (f)+... + fK(f) Investigation of effectiveness of Particle Swarm Optimization algorithm was conducted by solving test constrained and unconstrained multi-criterion problems. The maximum number of particles, which could be stored in the archive of non-dominated solutions, was set up for algorithm’s work. Number of particles in the archive was different for all problems. For solving constrained optimization problems was used method of the dynamic penalties. When finding solutions for problems archive filled partially. Researches showed that increasing of number of criterions leads increasing of algorithms’ effectiveness. So, for example, archive of the non-dominated solutions was filled on the average on 20-30 % when constrained problems were solved by using standard PSO and also by using binary PSO. Advantage of the standard PSO was only in time that was spent for one program run. And again algorithms’ results didn’t differ significantly. Number of particles and generations was about the same as it was when unconstrained problems were solved. Solving one constrained problem, feature of which was that, there was no point from Pareto set in the feasible region, required notable increase in population size. And in the end points, that was obtained, were on the part of the boundary of feasible region, which was the closest to the Pareto set. Results that were obtained by using both standard and binary PSO were almost the same. After all the investigations conducted, two real-world problems were solved: problem of formation of optimal investment portfolio of the enterprise and problem of formation of optimal loan portfolio of the bank. Besides, first problem was solved as in one-criterion definition so in the multi-criterion definition.