Hello everybody,
can anybody point me to a piece of literature that investigates how population size correlates to convergence in PSO algorithms. To what extent does an increase in the population size decrease the number of required iterations to find the optimum? Can the factors the convergence is influenced by be specified generally?
Thanks for any hints,
Juergen
A good rule of thumb is to set POP = 3x or 4x the problem dimensionality. Ofcourse this always depends on the nature of the problem, as expressed in the objective function. I.e. convergence is more problematic for obj. func. that use threshold operators (min, max, etc), since the search space has discontinuities (real encoding of parameters). Also the variations of PSO may have dissimilar performance for the same problem.
Try this paper, it is more focused on multi-swarm configuration, but it also describes the usual parameters for standard PSO.
http://uh-cu.academia.edu/AntonioBoluf%C3%A9/Papers/1313401/An_Analysis_of_Sub-swarms_in_Multi-swarm_Systems
It is problem dependent. Start with a relatively few particles and then increase the number. This will give yo an idea of the ideal number of particles.
I agree with Guillermo, it's highly problem dependent. It depends on the particular version of PSO used, the number of variables, and the complexity of the search space (see also Konstantinos' answer).
However, I would like to make a few points. First, convergence (i.e. loss of population diversity) shouldn't be confused with the optimisation result (i.e. the location of the optimum). Many PSO algorithms do not converge yet they are very effective at finding the global optimum. Second, unless you are trying to test the algorithm against a particular benchmark, it is more important to find the global optimum with certainty (at the cost of a few extra iterations) than to get quickly a (possibly sub-optimal) solution. In general, the computational cost of a few extra iterations on modern processors is very low. If you are working on a practical application, I would suggest to focus on the robustness (i.e. how reliably the algorithm finds a good/optimal solution) than the speed of the algorithm.
Marco is right, often is more important robustness in production systems. It is also possible to use parallel hardware to apply PSO, from a multi-core processor to a cluster or even a voluntary computing grid. I've been working on this subject. A GPU could be a good solution if your program takes too long in an ordinary computer. Anyway you have to do some trial and error to find the right number of particles.
I can suggest some papers regarding the initial population size:
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=5362795&contentType=Conference+Publications
http://www.sciencedirect.com/science/article/pii/S0020025512000266
http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5363936&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D5363936
I agree that the best thing to do is trial and error. The choice of population size depends on your specific application, meaning that same sizes might be inappropriate for different problems.
Is there a citation for a population size of 3x to 4x the dimensionality? The 2007 standard PSO paper recommends 40 without regard to dimensionality. For large scale problems (e.g. 1000 dimensions), this would get awkward, so I'd be curious to see any data that supports this suggestion for population size.
Thanks!
There should be no optimal population size for any population-based methods, especially for the methods with few tunning parameters, when apply to different problems.
If you have a method with 2 or 3 parameters (DE or PSO for example) and apply it to totally 2 or 3 different classes of testing problems, simple experiments will confirm this.
I strongly stress the important of knowing various classes of testing functions. We should know a test function which is easy for DE but quite hard for PSO and the other way around. For the popular testing functions, DE will perform better than PSO. But it is not difficult to get a function that is easy for PSO but difficult for DE.
The population size of a population-based method will have more effect if a function is quite easy and the operations contributing to its convergence matches the function's lanscape. For this case, a small population size will cause a premature convergence.
When we solve a difficult OP, converging to a real optimum point should be the first requirement. If we can obtain this, even with a couple million iterations (and not for too long), we should be happy with this. After that we might try to improve the performance.
Comparing the performances of different methods under small fixed number of iterations is not very useful. If the OP is quite difficult, none of them find good solutions. Take the Rosenbrock function as an example.
Actually, the is no clear answer to this question.. It is required to do testing of the algorithm by changing population size to select the best size for each problem.
Population size does affect the convergence rate but there is no general rule regarding this. It is a problem dependent phenomena and varies from problem to problem. So from my point of view you should test the variable population size for your problem and arrive at optimal population size.
https://www.researchgate.net/publication/296636431_Codes_in_MATLAB_for_Particle_Swarm_Optimization
Code Codes in MATLAB for Particle Swarm Optimization
https://www.researchgate.net/publication/297245624_Particle_Swarm_Optimization_Algorithm_and_its_Codes_in_MATLAB
Research Particle Swarm Optimization: Algorithm and its Codes in MATLAB
The number of iterations and swarm size should be selected based on optimal results that are convergence for certain problems.
The bigger the population, the better is the performance of the algorithm. However, the computational cost also increases.
Some times an sensitivity analysis of this parameter can calibrate the best trad off between accuracy and computational overload
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling